/Distributed Constrained Heuristic Search

Distributed Constrained Heuristic Search

Katia Sycara, Steven F. Roth, Norman Sadeh-Koniecpol and Mark S. Fox
Journal Article, IEEE Transactions on Systems, Man, and Cybernetics, Vol. 21, No. 6, pp. 1446-1461, December, 1991

Download Publication (PDF)

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. These works may not be reposted without the explicit permission of the copyright holder.


A model of decentralized problem solving, called distributed constrained heuristic search (DCHS), that provides both structure and focus in individual agent search spaces to optimize decisions in the global space, is presented. The model achieves this by integrating decentralized constraint satisfaction and heuristic search. It is a formalism suitable for describing a large set of distributed artificial intelligence problems. The notion of textures that allow agents to operate in an asynchronous concurrent manner is introduced. The use of textures coupled with distributed asynchronous backjumping, a type of distributed dependency-directed backtracking that the authors have developed, enables agents to instantiate variables in such a way as to substantially reduce backtracking. The approach has been tested experimentally in the domain of decentralized job-shop scheduling. A formulation of distributed job-shop scheduling as a DCHS and experimental results are presented.

BibTeX Reference
author = {Katia Sycara and Steven F. Roth and Norman Sadeh-Koniecpol and Mark S. Fox},
title = {Distributed Constrained Heuristic Search},
journal = {IEEE Transactions on Systems, Man, and Cybernetics},
year = {1991},
month = {December},
volume = {21},
number = {6},
pages = {1446-1461},