An Any-space Algorithm for Distributed Constraint Optimization

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.