Title: | Distributed Breakout Algorithm for Solving Distributed Constraint Satisfaction Problems |

Author: | Makoto Yokoo and Katsutoshi Hirayama |

Book Tittle: | Proceedings of the Second International Conference on Multiagent Systems |

Pages: | 401--408 |

Year: | 1996 |

Abstract: | This paper presents a new algorithm for solving dis- tributed 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 di cult problem instances of distributed graph-coloring problems. |

Cited by 62

@InProceedings{yokoo96a, author = {Makoto Yokoo and Katsutoshi Hirayama}, title = {Distributed Breakout Algorithm for Solving Distributed Constraint Satisfaction Problems}, booktitle = {Proceedings of the Second International Conference on Multiagent Systems}, pages = {401--408}, year = 1996, abstract = {This paper presents a new algorithm for solving dis- tributed 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 di cult problem instances of distributed graph-coloring problems.}, keywords = {multiagent dcsp}, googleid = {_EnMORkzsesJ:scholar.google.com/}, url = {http://jmvidal.cse.sc.edu/library/yokoo96a.pdf}, cluster = {16983411853227739644} }Last modified: Wed Mar 9 10:14:05 EST 2011