Constraint Satisfaction for Formalizing Distributed Problem Solving
Makoto Yokoo, Edmund H. Durfee, Toru Ishida, Kazuhiro Kuwabara
12th International Conference on Distributed Computing Systems
(ICDCS-92), pp. 614-621, 1992.
Viewing cooperative distributed problem solving (CDPS) as
distributed constraint satisfaction provides a useful formalism
for characterizing CDPS techniques. In this paper, we
describe this formalism and compare algorithms for solving
distributed constraint satisfaction problems (DCSPs). In
particular, we present our newly developed technique called
asynchronous backtracking that allows agents to act
asynchronously and concurrently, in contrast to the traditional
sequential backtracking techniques employed in constraint
satisfaction problems. Our experimental results show that solving
DCSPs in a distributed fashion is worthwhile when the problems
solved by individual agents are loosely-coupled.