Title: | An Asynchronous Complete Method for General Distributed Constraint Optimization |

Author: | Pragnesh Jay Modi, Wei-Min Shen, Milind Tambe, and Makoto Yokoo |

Book Tittle: | Proceedings of Autonomous Agents and Multi-Agent Systems Workshop on Distributed Constraint Reasoning |

Pages: | 104--118 |

Year: | 2002 |

Abstract: | Distributed constraint optimization requires the optimization of a global objective function that is distributed as a set of valued constraints among a set of autonomous, communicating agents. To date, there does not exist an asynchronous, complete algorithm for general distributed constraint optimization problems. This paper presents Adopt, the first such algorithm that is asynchronous, operates on a general representation, uses linear space and is guaranteed to find optimal solutions. The main idea behind Adopt is a new distributed search strategy that is similar to iterative deepening search and that allows concurrent execution by a set of distributed agents. We show that Adopt outperforms Synchronous Branch and Bound, the only existing optimal algorithm for distributed constraint optimization. Furthermore, in order to isolate whether the speed-ups are due to Adopt s new search strategy or its exploitation of asynchrony, we compare to a synchronous version of iterative deepening, which simulates the centralized iterative deepening search strategy in a distributed environment. We show that the cause of speed-up is partly due to Adopt s new search strategy and partly due to its asynchrony. |

Cited by 8

@InProceedings{modi02a, author = {Pragnesh Jay Modi and Wei-Min Shen and Milind Tambe and Makoto Yokoo}, title = {An Asynchronous Complete Method for General Distributed Constraint Optimization}, booktitle = {Proceedings of Autonomous Agents and Multi-Agent Systems Workshop on Distributed Constraint Reasoning}, year = 2002, comment = {The Adopt algorithm.}, pages = {104--118}, abstract = {Distributed constraint optimization requires the optimization of a global objective function that is distributed as a set of valued constraints among a set of autonomous, communicating agents. To date, there does not exist an asynchronous, complete algorithm for general distributed constraint optimization problems. This paper presents Adopt, the first such algorithm that is asynchronous, operates on a general representation, uses linear space and is guaranteed to find optimal solutions. The main idea behind Adopt is a new distributed search strategy that is similar to iterative deepening search and that allows concurrent execution by a set of distributed agents. We show that Adopt outperforms Synchronous Branch and Bound, the only existing optimal algorithm for distributed constraint optimization. Furthermore, in order to isolate whether the speed-ups are due to Adopt s new search strategy or its exploitation of asynchrony, we compare to a synchronous version of iterative deepening, which simulates the centralized iterative deepening search strategy in a distributed environment. We show that the cause of speed-up is partly due to Adopt s new search strategy and partly due to its asynchrony.}, keywords = {multiagent dcop}, url = {http://jmvidal.cse.sc.edu/library/modi02a.pdf}, googleid = {D62NcyY7DP0J:scholar.google.com/}, cluster = {18234014027649756431} }Last modified: Wed Mar 9 10:15:30 EST 2011