Distributed constrained heuristic search
- 1 January 1991
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Systems, Man, and Cybernetics
- Vol. 21 (6) , 1446-1461
- https://doi.org/10.1109/21.135688
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.<>Keywords
This publication has 7 references indexed in Scilit:
- Enhancement schemes for constraint processing: Backjumping, learning, and cutset decompositionArtificial Intelligence, 1990
- Multistage Negotiation in Distributed PlanningPublished by Elsevier ,1988
- The complexity of some polynomial network consistency algorithms for constraint satisfaction problemsArtificial Intelligence, 1985
- A Review of Production SchedulingOperations Research, 1981
- An Organizational View of Distributed SystemsIEEE Transactions on Systems, Man, and Cybernetics, 1981
- Backtrack programming techniquesCommunications of the ACM, 1975
- Backtrack ProgrammingJournal of the ACM, 1965