ADOPT-ing: Unifying asynchronous distributed optimization with asynchronous backtracking

Marius C. Silaghi, Makoto Yokoo

研究成果: ジャーナルへの寄稿学術誌査読

17 被引用数 (Scopus)


This article presents an asynchronous algorithm for solving distributed constraint optimization problems (DCOPs). The proposed technique unifies asynchronous backtracking (ABT) and asynchronous distributed optimization (ADOPT) where valued nogoods enable more flexible reasoning and more opportunities for communication, leading to an important speed-up. While feedback can be sent in ADOPT by COST messages only to one predefined predecessor, our extension allows for sending such information to any relevant agent. The concept of valued nogood is an extension by Dago and Verfaille of the concept of classic nogood that associates the list of conflicting assignments with a cost 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). ADOPT has the property of maintaining the initial distribution of the problem. To be efficient, ADOPT needs a preprocessing step consisting of computing a Depth-First Search (DFS) tree on the constraint graph. Valued nogoods allow for automatically detecting and exploiting the best DFS tree compatible with the current ordering. To exploit such DFS trees it is now sufficient to ensure that they exist. Also, the inference rules available for valued nogoods help to exploit schemes of communication where more feedback is sent to higher priority agents. Together they result in an order of magnitude improvement.

ジャーナルAutonomous Agents and Multi-Agent Systems
出版ステータス出版済み - 10月 2009

!!!All Science Journal Classification (ASJC) codes

  • 人工知能


「ADOPT-ing: Unifying asynchronous distributed optimization with asynchronous backtracking」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。