skip to main content
10.5555/1402298.1402307acmconferencesArticle/Chapter ViewAbstractPublication PagesaamasConference Proceedingsconference-collections
research-article

BnB-ADOPT: an asynchronous branch-and-bound DCOP algorithm

Published: 12 May 2008 Publication History

Abstract

Distributed constraint optimization (DCOP) problems are a popular way of formulating and solving agent-coordination problems. It is often desirable to solve DCOP problems optimally with memory-bounded and asynchronous algorithms. We introduce Branch-and-Bound ADOPT (BnB-ADOPT), a memory-bounded asynchronous DCOP algorithm that uses the message passing and communication framework of ADOPT, a well known memory-bounded asynchronous DCOP algorithm, but changes the search strategy of ADOPT from best-first search to depth-first branch-and-bound search. Our experimental results show that BnB-ADOPT is up to one order of magnitude faster than ADOPT on a variety of large DCOP problems and faster than NCBB, a memory-bounded synchronous DCOP algorithm, on most of these DCOP problems.

References

[1]
S. Ali, S. Koenig, and M. Tambe. Preprocessing techniques for accelerating the DCOP algorithm ADOPT. In Proceedings of AAMAS, pages 1041--1048, 2005.
[2]
C. Bessiere, A. Maestre, and P. Messeguer. Distributed dynamic backtracking. In Proceedings of the Distributed Constraint Reasoning Workshop, pages 9--16, 2001.
[3]
A. Chechetka and K. Sycara. No-commitment branch and bound search for distributed constraint optimization. In Proceedings of AAMAS, pages 1427--1429, 2006.
[4]
A. Gershman, A. Meisels, and R. Zivan. Asynchronous forward-bounding for distributed constraints optimization. In Proceedings of ECAI, pages 103--107, 2006.
[5]
P. Hart, N. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, SSC4(2):100--107, 1968.
[6]
K. Hirayama and M. Yokoo. Distributed partial constraint satisfaction problem. In Principles and Practice of Constraint Programming, pages 222--236, 1997.
[7]
R. Korf. Linear-space best-first search. Artificial Intelligence, 62(1):41--78, 1993.
[8]
R. Maheswaran, M. Tambe, E. Bowring, J. Pearce, and P. Varakantham. Taking DCOP to the real world: Efficient complete solutions for distributed event scheduling. In Proceedings of AAMAS, pages 310--317, 2004.
[9]
R. Mailler and V. Lesser. Solving distributed constraint optimization problems using cooperative mediation. In Proceedings of AAMAS, pages 438--445, 2004.
[10]
R. Marinescu and R. Dechter. AND/OR branch-and-bound for graphical models. In Proceedings of IJCAI, pages 224--229, 2005.
[11]
A. Meisels, E. Kaplansky, I. Razgon, and R. Zivan. Comparing performance of distributed constraints processing algorithms. In Proceedings of the Distributed Constraint Reasoning Workshop, pages 86--93, 2002.
[12]
P. Modi, W. Shen, M. Tambe, and M. Yokoo. ADOPT: Asynchronous distributed constraint optimization with quality guarantees. Artificial Intelligence, 161(1--2):149--180, 2005.
[13]
A. Petcu and B. Faltings. A scalable method for multiagent constraint optimization. In Proceedings of IJCAI, pages 1413--1420, 2005.
[14]
N. Schurr, S. Okamoto, R. Maheswaran, P. Scerri, and M. Tambe. Evolution of a teamwork model. In R. Sun, editor, Cognition and Multi-Agent Interaction: From Cognitive Modeling to Social Simulation, pages 307--327. Cambridge University Press, 2005.
[15]
W. Yeoh, A. Felner, and S. Koenig. BnB-ADOPT: An asynchronous branch-and-bound DCOP algorithm. In Proceedings of the Distributed Constraint Reasoning Workshop, 2007.
[16]
W. Zhang and R. Korf. Performance of linear-space search algorithms. Artificial Intelligence, 79(2):241--292, 1995.

Cited By

View all
  • (2020)Collaborative optimization networksProceedings of the 5th International Conference on Sustainable Information Engineering and Technology10.1145/3427423.3427468(1-4)Online publication date: 16-Nov-2020
  • (2018)Decentralized Collective Learning for Self-managed Sharing EconomiesACM Transactions on Autonomous and Adaptive Systems10.1145/327766813:2(1-33)Online publication date: 26-Nov-2018
  • (2017)Self-adaptive learning in decentralized combinatorial optimizationProceedings of the 12th International Symposium on Software Engineering for Adaptive and Self-Managing Systems10.1109/SEAMS.2017.8(54-64)Online publication date: 20-May-2017
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
AAMAS '08: Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems - Volume 2
May 2008
673 pages
ISBN:9780981738116

Sponsors

In-Cooperation

Publisher

International Foundation for Autonomous Agents and Multiagent Systems

Richland, SC

Publication History

Published: 12 May 2008

Check for updates

Author Tags

  1. agent cooperation
  2. distributed problem solving

Qualifiers

  • Research-article

Conference

AAMAS08
Sponsor:

Acceptance Rates

Overall Acceptance Rate 1,155 of 5,036 submissions, 23%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 14 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2020)Collaborative optimization networksProceedings of the 5th International Conference on Sustainable Information Engineering and Technology10.1145/3427423.3427468(1-4)Online publication date: 16-Nov-2020
  • (2018)Decentralized Collective Learning for Self-managed Sharing EconomiesACM Transactions on Autonomous and Adaptive Systems10.1145/327766813:2(1-33)Online publication date: 26-Nov-2018
  • (2017)Self-adaptive learning in decentralized combinatorial optimizationProceedings of the 12th International Symposium on Software Engineering for Adaptive and Self-Managing Systems10.1109/SEAMS.2017.8(54-64)Online publication date: 20-May-2017
  • (2013)Stratified tree searchProceedings of the 2013 international conference on Autonomous agents and multi-agent systems10.5555/2484920.2485009(555-562)Online publication date: 6-May-2013
  • (2011)A study for representations of distributed cooperative search algorithms based on pseudo-treesProceedings of the 10th WSEAS international conference on Software engineering, parallel and distributed systems10.5555/1959791.1959818(172-179)Online publication date: 20-Feb-2011
  • (2010)BnB-ADOPT+ with Several Soft Arc Consistency LevelsProceedings of the 2010 conference on ECAI 2010: 19th European Conference on Artificial Intelligence10.5555/1860967.1860982(67-72)Online publication date: 4-Aug-2010
  • (2010)A quantified distributed constraint optimization problemProceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: volume 1 - Volume 110.5555/1838206.1838344(1023-1030)Online publication date: 10-May-2010
  • (2010)Improving DPOP with function filteringProceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: volume 1 - Volume 110.5555/1838206.1838226(141-148)Online publication date: 10-May-2010
  • (2009)Connecting BnB-ADOPT with soft arc consistencyProceedings of the 14th Annual ERCIM international conference on Constraint solving and constraint logic programming10.5555/1987019.1987021(19-37)Online publication date: 15-Jun-2009
  • (2009)Trading off solution quality for faster computation in DCOP search algorithmsProceedings of the 21st International Joint Conference on Artificial Intelligence10.5555/1661445.1661502(354-360)Online publication date: 11-Jul-2009
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media