Distributed Breakout Algorithm for Solving Distributed Constraint Satisfaction Problems

Makoto Yokoo, NTT, and Katsutoshi Hirayama, Kobe University of Mercantile Marine, Japan

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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.