Algorithms for Solving Distributed Constraint Satisfaction Problems (DCSPs).
Gadi Solotorevsky, Ehud Gudes · 1996
This paper investigates Constraint Satisfaction Prob-lems (CSPs) that axe distributed by nature, i.e., there is a division of the CSP into sub components (agents) that axe connected via constraints, where each sub-component includes several of the CSP variables with the constraints between them. We call such a problem a Distributed CSP (DCSP). In this paper we give a for-mal definition of DCSPs and present four algorithms for solving them. Two of the algorithms are based on the difference between the difficulty of solving the internal constraints in the CSP components (we call them the peripheral components) of the DCSP and the difficulty of solving the constraints between the differ-ent CSPs (the central component). The two other algorithms use local and global views of the DCSP respectively. All the algorithms permit the use of dif-ferent techniques (CSP, knowledge based, and opera-tion research algorithms) in solving each of the prob-lem components. We probe that as long as all the selected techniques axe sound and complete, our algo-rithms are sound and complete. The algorithms were tested in a real distributed environment; the results show that when there is a difference between the dif-ficulty of solving the peripheral components and the central one, taking advazltage of it may reduce sig-nificantly the amount of work (constraint checks and message passing) needed for solving the DCSP. Introduction. Constraint satisfaction problems (CSP) appear many domains, e.g., image processing and resource allocation problems (Solotorevsky G., Gudes E.,