Algorithms for Distributed Constraint Satisfaction: A Review
Makoto Yokoo, Katsutoshi Hirayama
Autonomous Agents and Multi-Agent Systems}, Vol.3, No.2,
pp.189--212,
2000.
When multiple agents are in a shared environment, there
usually exist constraints among the possible actions of these agents.
A distributed constraint satisfaction problem (distributed CSP) is a
problem to find a consistent combination of actions that satisfies
these inter-agent constraints.
Various application problems in multi-agent systems can be formalized
as distributed CSPs.
This paper gives an overview of the existing research on distributed
CSPs.
First, we briefly describe the problem formalization and algorithms
of normal, centralized CSPs.
Then, we show the problem formalization and several MAS application
problems of distributed CSPs.
Furthermore, we describe a series of algorithms for solving distributed
CSPs, i.e., the asynchronous backtracking, the asynchronous
weak-commitment search, the distributed breakout,
and distributed consistency algorithms.
Finally, we show two extensions of the basic problem formalization of
distributed CSPs, i.e., handling multiple local variables, and dealing
with over-constrained problems.