BnB-ADOPT

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

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

Full text

Pdf (453 KB)

Source

International Conference on Autonomous Agents archive
Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems - Volume 2 table of contents

Estoril, Portugal

SESSION: Agent cooperation table of contents

Pages 591-598

Year of Publication: 2008

ISBN:978-0-9817381-1-6

Authors

William Yeoh	University of Southern California, Los Angeles, CA
Ariel Felner	Ben-Gurion University, Beer-Sheva, Israel
Sven Koenig	University of Southern California, Los Angeles, CA

Sponsors

AAAI : Association for the Advancement of Artifical Intelligence
ACM: Association for Computing Machinery

Publisher

International Foundation for Autonomous Agents and Multiagent Systems Richland, SC

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 55, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

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

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Syed Ali , Sven Koenig , Milind Tambe, Preprocessing techniques for accelerating the DCOP algorithm ADOPT, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands [doi>10.1145/1082473.1082631]
	2	C. Bessiere, A. Maestre, and P. Messeguer. Distributed dynamic backtracking. In Proceedings of the Distributed Constraint Reasoning Workshop, pages 9--16, 2001.
	3	Anton Chechetka , Katia Sycara, No-commitment branch and bound search for distributed constraint optimization, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160900]
	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	Richard E. Korf, Linear-space best-first search, Artificial Intelligence, v.62 n.1, p.41-78, July 1993 [doi>10.1016/0004-3702(93)90045-D]
	8	Rajiv T. Maheswaran , Milind Tambe , Emma Bowring , Jonathan P. Pearce , Pradeep Varakantham, Taking DCOP to the Real World: Efficient Complete Solutions for Distributed Multi-Event Scheduling, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.310-317, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.257]
	9	Roger Mailler , Victor Lesser, Solving Distributed Constraint Optimization Problems Using Cooperative Mediation, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.438-445, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.249]
	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	Pragnesh Jay Modi , Wei-Min Shen , Milind Tambe , Makoto Yokoo, Adopt: asynchronous distributed constraint optimization with quality guarantees, Artificial Intelligence, v.161 n.1-2, p.149-180, January 2005 [doi>10.1016/j.artint.2004.09.003]
	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	Weixiong Zhang , Richard E. Korf, Performance of linear-space search algorithms, Artificial Intelligence, v.79 n.2, p.241-292, Dec. 1995 [doi>10.1016/0004-3702(94)00047-6]