An Any-space Algorithm for Distributed Constraint Optimization

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

View Publication

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(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.

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},
year = {2006},
month = {March},
} 2017-09-13T10:42:54-04:00