Multiply-constrained distributed constraint optimization

E. Bowring, M. Tambe, M. Yokoo

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

26 Citations (Scopus)


Distributed constraint optimization (DCOP) has emerged as a useful technique for multiagent coordination. While previous DCOP work focuses on optimizing a single team objective, in many domains, agents must satisfy additional constraints on resources consumed locally (due to interactions within their local neighborhoods). Such resource constraints may be required to be private or shared for efficiency's sake. This paper provides a novel multiply-constrained DCOP algorithm for addressing these domains which is based on mutually-intervening search, i.e. using local resource constraints to intervene in the search for the optimal solution and vice versa. It is realized through three key ideas: (i) transforming n-ary constraints to maintain privacy; (ii) dynamically setting upper bounds on joint resource consumption with neighbors; and (iii) identifying if the local DCOP graph structure allows agents to compute exact resource bounds for additional efficiency. These ideas are implemented by modifying Adopt, one of the most efficient DCOP algorithms. Both detailed experimental results as well as proofs of correctness are presented.

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

  • General Engineering


Dive into the research topics of 'Multiply-constrained distributed constraint optimization'. Together they form a unique fingerprint.

Cite this