BnB-ADOPT: An asynchronous branch-and-bound DCOP algorithm Conference Paper uri icon

abstract

  • 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, & 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 …

publication date

  • May 23, 2010