Distributed Constraint Satisfaction Problems-a model and application Academic Article uri icon

abstract

  • A canonical model for distributed constraint satisfaction problems (DCSP) is presented and algorithms for processing constraints on a DCSP are described. The central idea behind a constraint network that is given as a DCSP is the existence of large di erences between the cost of message passing among di erent components of a DCSP and the cost of local consistency checks within each component. Therefore, algorithms which operate in a multi- agent environment to solve these problems are required to take into consideration these di erences. Four basic algorithms for solving DCSPs that are sound and complete are proposed. Two of these algorithms are sequential and two algorithms operate in parallel and are inherently distributed. The behavior of the proposed algorithms was tested by generating and solving a set of random DCSPs (for a variety of parameters of density and …

publication date

  • October 1, 1997