An Any-space Algorithm for Distributed Constraint Optimization

Anton Chechetka and Katia Sycara
Proceedings of AAAI Spring Symposium on Distributed Plan and Schedule Management, March, 2006.


Download
  • Adobe portable document format (pdf) (144KB)
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
The Distributed Constraint Optimization Problem (DCOP) is a powerful formalism for multiagent coordination problems, including planning and scheduling. This paper presents modifications to a polynomial-space branch-and-bound based algorithm, called NCBB, for solving DCOP, that make the algorithm any-space. This enables a continuous tradeoff between O(bp) space, O(bpH+1) time complexity and O(pw + bp) space and O(bHpw+1) time, where p is variables domain size, H is Depth-First Search (DFS) traversal depth of constraint graph, b is the branching factor of DFS tree, and w is the context width of the tree. This flexibility allows one to apply NCBB to areas, where the limited amount of available memory prevents one from using more efficient exponential space algorithms. Sensor networks is an example of such domain. We demonstrate both theoretically and empirically that caching does not lead to an increase in complexity even under assumption that all cache lookups fail. We also show experimentally that the use of caching leads to significant speedups of problem solving.

Notes
Sponsor: DARPA
Associated Center(s) / Consortia: Center for Integrated Manfacturing Decision Systems
Associated Lab(s) / Group(s): Advanced Agent - Robotics Technology Lab

Text Reference
Anton Chechetka and Katia Sycara, "An Any-space Algorithm for Distributed Constraint Optimization," Proceedings of AAAI Spring Symposium on Distributed Plan and Schedule Management, March, 2006.

BibTeX Reference
@inproceedings{Chechetka_2006_5311,
   author = "Anton Chechetka and Katia Sycara",
   title = "An Any-space Algorithm for Distributed Constraint Optimization",
   booktitle = "Proceedings of AAAI Spring Symposium on Distributed Plan and Schedule Management",
   month = "March",
   year = "2006",
}