Drexel University Home Pagewww.drexel.edu DREXEL UNIVERSITY LIBRARIES HOMEPAGE >>

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)

Files in This Item:

File Description SizeFormat
2006042087.pdf330.04 kBAdobe PDFView/Open
View Statistics

Items in iDEA are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0! iDEA Software Copyright © 2002-2010  Duraspace - Feedback