BnB-ADOPT: An Asynchronous Branch-and-Bound DCOP Algorithm
This work addresses the need for faster and more intuitive bounded-error solutions in agent-coordination problems, though it is incremental as it builds on existing ADOPT and NCBB methods.
The paper tackles the problem of solving distributed constraint optimization (DCOP) problems more efficiently by introducing BnB-ADOPT, an asynchronous algorithm that uses depth-first branch-and-bound search, resulting in finding cost-minimal solutions up to one order of magnitude faster than ADOPT for large problems and matching the speed of NCBB in most cases.
Distributed constraint optimization (DCOP) problems are a popular way of formulating and solving agent-coordination problems. A DCOP problem is a problem where several agents coordinate their values such that the sum of the resulting constraint costs is minimal. It is often desirable to solve DCOP problems with memory-bounded and asynchronous algorithms. We introduce Branch-and-Bound ADOPT (BnB-ADOPT), a memory-bounded asynchronous DCOP search algorithm that uses the message-passing and communication framework of ADOPT (Modi, Shen, Tambe, and Yokoo, 2005), a well known memory-bounded asynchronous DCOP search algorithm, but changes the search strategy of ADOPT from best-first search to depth-first branch-and-bound search. Our experimental results show that BnB-ADOPT finds cost-minimal solutions up to one order of magnitude faster than ADOPT for a variety of large DCOP problems and is as fast as NCBB, a memory-bounded synchronous DCOP search algorithm, for most of these DCOP problems. Additionally, it is often desirable to find bounded-error solutions for DCOP problems within a reasonable amount of time since finding cost-minimal solutions is NP-hard. The existing bounded-error approximation mechanism allows users only to specify an absolute error bound on the solution cost but a relative error bound is often more intuitive. Thus, we present two new bounded-error approximation mechanisms that allow for relative error bounds and implement them on top of BnB-ADOPT.