No-Commitment Branch and Bound Search for Distributed Constraint Optimization

Anton Chechetka and Katia Sycara
Proceedings of Fifth International Joint Conference on Autonomous Agents and Multi-Agent Systems, May, 2006, pp. 1427 - 1429.


Download
  • Adobe portable document format (pdf) (141KB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract
We present a new polynomial-space algorithm for solving Distributed Constraint Optimization problems (DCOP). The algorithm, called NCBB, is branch and bound search with modifications for efficiency in a multiagent setting. Two main features of the algorithm are: (a) using different agents to search non-intersecting parts of a search space concurrently, and (b) communicating lower bounds on solution cost every time there is a possibility the bounds might change due to changed variable assignments. The first leads to a better utilization of computational resources of multiple participating agents, while the second provides for more efficient pruning of search space.

Experimental results show that NCBB has significantly better performance than another polynomial-space algorithm, ADOPT, on random graph coloring problems. Under assumptions of cheap communication it also has compara ble performance with DPOP despite using only polynomial memory as opposed to exponential memory for DPOP.


Keywords
Cooperative distributed problem solving in agent systems

Notes
Associated Center(s) / Consortia: Center for Integrated Manfacturing Decision Systems
Associated Lab(s) / Group(s): Advanced Agent - Robotics Technology Lab
Number of pages: 3

Text Reference
Anton Chechetka and Katia Sycara, "No-Commitment Branch and Bound Search for Distributed Constraint Optimization," Proceedings of Fifth International Joint Conference on Autonomous Agents and Multi-Agent Systems, May, 2006, pp. 1427 - 1429.

BibTeX Reference
@inproceedings{Chechetka_2006_5481,
   author = "Anton Chechetka and Katia Sycara",
   title = "No-Commitment Branch and Bound Search for Distributed Constraint Optimization",
   booktitle = "Proceedings of Fifth International Joint Conference on Autonomous Agents and Multi-Agent Systems",
   pages = "1427 - 1429",
   month = "May",
   year = "2006",
}