The Robotics Institute

Carnegie Mellon Robotics Institute

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(bp^H+1) time complexity and O(p^w + bp) space and O(bHp^w+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",
}

The Robotics Institute

Menu