### 複雑な局所問題に対応する分散制約充足アルゴリズム

横尾 真, 平山 勝敏，
人工知能学会誌, Vol.15, No.2, pp.348--354,
2000.

A distributed constraint satisfaction problem
can formalize various application problems in Multi-agent systems, 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
algorithm.
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.