RI Homepage Carnegie Mellon Homepage RI Homepage

The Robotics Institute

Carnegie Mellon Robotics Institute

Distributed Constrained Heuristic Search

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


Download
  • Adobe portable document format (pdf) (2MB)
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.

Abstract
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.

Notes
Associated Center(s) / Consortia: Center for Integrated Manfacturing Decision Systems

Text Reference
Katia Sycara, Steven F. Roth, Norman Sadeh-Koniecpol, and Mark S. Fox, "Distributed Constrained Heuristic Search," IEEE Transactions on Systems, Man, and Cybernetics, Vol. 21, No. 6, December, 1991, pp. 1446-1461.

BibTeX Reference
@article{Sycara_1991_2091,
   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",
   pages = "1446-1461",
   month = "December",
   year = "1991",
   volume = "21",
   number = "6",
}

The Robotics Institute is part of the School of Computer Science, Carnegie Mellon University.
Contact Us | Update Instructions