ADOPT: Asynchronous Distributed Constraint Optimization with Quality Guarantees

P. J. Modi, Wei-Min Shen, M. Tambe, and M. Yokoo. ADOPT: Asynchronous Distributed Constraint Optimization with Quality Guarantees. Artificial Intelligence Journal, 161(1-2):149–180, January 2005.

Download

[516.1kB pdf] 

Abstract

The Distributed Constraint Optimization Problem (DCOP) is a promising approach for modeling distributed reasoning tasks that arise in multiagent systems. Unfortunately, existing 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 approach 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.

BibTeX Entry

@Article{	  modi2005adopt:-asynchronous-distributed-constraint,
  abstract	= {The Distributed Constraint Optimization Problem (DCOP) is
		  a promising approach for modeling distributed reasoning
		  tasks that arise in multiagent systems. Unfortunately,
		  existing 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 approach 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.},
  author	= {P. J. Modi and Wei-Min Shen and M. Tambe and M. Yokoo},
  journal	= {Artificial Intelligence Journal},
  keywords	= { multiagent systems; constraints; distributed
		  optimization},
  month		= jan,
  number	= {1-2},
  pages		= {149--180},
  title		= {{ADOPT}: Asynchronous Distributed Constraint Optimization
		  with Quality Guarantees},
  volume	= {161},
  year		= {2005}
}