Graphics enhanced version of this site

An Any-space Algorithm for Distributed Constraint Optimization
A. Chechetka and K. Sycara
Proceedings of AAAI Spring Symposium on Distributed Plan and Schedule Management, March, 2006.

Jump to: Download | Abstract | Notes | Text Reference | BibTeX Reference

Adobe portable document format (pdf) [143 KB]
Compressed postscript (ps.gz) [116 KB]

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.

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.

Sponsor: DARPA
Grant ID: HR0011-05-1-0020

Associated center: CIMDS
Associated lab/group: Intelligent Software Agents

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

@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"
}