posted on 1991-01-01, 00:00authored byKatia 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.