|
iDEA: Drexel E-repository and Archives >
Drexel Academic Community >
College of Engineering >
Department of Computer Science >
Faculty Research and Publications (Comp Sci) >
ADOPT: asynchronous distributed constraint optimization with quality guarantees
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1860/816
|
| Title: | ADOPT: asynchronous distributed constraint optimization with quality guarantees |
| Authors: | Modi, Pragnesh Jay
Shen, Wei-Shen
Tambe, Milind
Yokoo, Makoto |
| Issue Date: | 2006 |
| Publisher: | Elsevier |
| Citation: | Artificial Intelligence (http://www.elsevier.com/locate/artint) Volume 161, Issues 1-2, Pages 149-180. Retrieved 3/16/2006 from http://www.cs.drexel.edu/~pmodi/papers/modi-aij03.pdf. |
| Abstract: | The Distributed Constraint Optimization Problem (DCOP) is able to model a wide
variety of distributed reasoning tasks that arise in multiagent systems. Unfortunately, ex-
isting methods for DCOP are not able to provide theoretical guarantees on global solution
quality while allowing agents to operate asynchronously. We show how this failure can be
remedied by allowing agents to make local decisions based on conservative cost estimates
rather than relying on global certainty as previous approaches have done. This novel ap-
proach results in a polynomial-space algorithm for DCOP named Adopt that is guaranteed
to find the globally optimal solution while allowing agents to execute asynchronously and
in parallel. Detailed experimental results show that on benchmark problems Adopt obtains
speedups of several orders of magnitude over other approaches. Adopt can also perform
bounded-error approximation – it has the ability to quickly find approximate solutions and,
unlike heuristic search methods, still maintain a theoretical guarantee on solution quality. |
| URI: | http://hdl.handle.net/1860/816 |
| Appears in Collections: | Faculty Research and Publications (Comp Sci)
|
Items in iDEA are protected by copyright, with all rights reserved, unless otherwise indicated.
|
www.drexel.edu
