### Distributed Breakout Algorithm for Solving Distributed
Constraint Satisfaction Problems

Makoto Yokoo, Katsutoshi Hirayama

Second International
Conference on Multiagent Systems (ICMAS-96),
1996.

This paper presents a new algorithm for solving distributed constraint satisfaction
problems (distributed CSPs) called the distributed breakout
algorithm, which is inspired by the breakout algorithm for solving
centralized CSPs.
In this algorithm, each agent tries to optimize its evaluation value
(the number of constraint violations) by exchanging its current value and
the possible amount of its improvement among neighboring
agents.
Instead of detecting the fact that agents as a whole are trapped
in a local-minimum, each agent detects whether it is in a
quasi-local-minimum, which is a weaker condition than a
local-minimum, and changes the weights of constraint violations to
escape from the quasi-local-minimum.
Experimental evaluations show this algorithm to be much more efficient
than existing algorithms for critically difficult problem instances of
distributed graph-coloring problems.