File(s) stored somewhere else
Please note: Linked content is NOT stored on Carnegie Mellon University and we can't guarantee its availability, quality, security or accept any liability.
Distributed Constrained Heuristic Search
journal contributionposted on 1991-01-01, 00:00 authored by Katia SycaraKatia Sycara, Stephen Roth, Norman Sadeh, Mark S. Fox
In this paper we present a model of decentralized problem solving, called Distributed Constrained Heuristic Search (DCHS) that provides both structure and focus in individual agent search spaces so as to optimize decisions in the global space. The model achieves this by integrating decentralized constraint satisfaction and heuristic search. It is a formalism suitable for describing a large set of DAI problems. We introduce the notion of textures that allow agents to operate in an asynchronous concurrent manner. The employment of textures coupled with distributed asynchronous backjumping (DAB), a type of distributed dependency-directed backtracking that we have developed, enables agents to instantiate variables in such a way as to substantially reduce backtracking. We have experimentally tested our approach in the domain of decentralized job-shop scheduling. A formulation of distributed job-shop scheduling as a DCHS is presented as well as experimental results.