Nogood based asynchronous distributed optimization (ADOPT ng)

Marius C. Silaghi, Makoto Yokoo

Research output: Chapter in Book/Report/Conference proceedingConference contribution

31 Citations (Scopus)


This work proposes an asynchronous algorithm for solving Distributed Constraint Optimization problems (DCOPs) using a new kind of nogoods, namely valued nogoods. The proposed technique is an extension of the asynchronous distributed optimization (ADOPT) where valued nogoods enable more flexible reasoning, leading to important speed-up. Valued nogoods are an extension of classic nogoods that associates each nogood with a threshold and optionally with a set of references to culprit constraints. DCOPs have been shown to have very elegant distributed solutions, such as ADOPT, distributed asynchronous overlay (DisAO), or DPOP. These algorithms are typically tuned to minimize the longest causal chain of messages, as a measure of how the algorithms will scale for systems with remote agents (with large latency in communication). Among the mentioned techniques, DPOP performs very well for the chosen metric (requiring a number of such sequential messages linear in the number of agents), but in general has exponential space requirements. DisAO and ADOPT have the advantage of needing only polynomial space. ADOPT has the property of maintaining the initial distribution of the problem. ADOPT needs a preprocessing step consisting of computing a depth first search (DFS) tree on the agent graph. We show that valued nogoods reduce the practical importance/need of this preprocessing since independent subproblems are now dynamically detected and exploited.

Original languageEnglish
Title of host publicationProceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems
Number of pages8
Publication statusPublished - 2006
EventFifth International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS - Hakodate, Japan
Duration: May 8 2006May 12 2006

Publication series

NameProceedings of the International Conference on Autonomous Agents


OtherFifth International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS

All Science Journal Classification (ASJC) codes

  • Engineering(all)


Dive into the research topics of 'Nogood based asynchronous distributed optimization (ADOPT ng)'. Together they form a unique fingerprint.

Cite this