Distributed Constraint Satisfaction Algorithm for Complex Local Problems
Makoto Yokoo, Katsutoshi Hirayama
Conference on Multiagent Systems (ICMAS-98),
A distributed constraint satisfaction problem
can formalize various application problems in MAS, and several
algorithms for solving this problem have been developed.
One limitation of these algorithms is
that they assume each agent has only one local variable.
Although simple modifications enable these algorithms to handle
multiple local variables,
obtained algorithms are neither efficient nor scalable to larger problems.
We develop a new algorithm that can handle multiple local variables
efficiently, which is based on the asynchronous weak-commitment search
In this algorithm, a bad local solution can be modified without
forcing other agents to exhaustively search local problems.
Also, the number of interactions among agents can be decreased since
agents communicate only when they find local solutions that satisfy
all of the local constraints.
Experimental evaluations show that this algorithm is far more
efficient than an algorithm that uses the prioritization among agents.