BnB-ADOPT: An Asynchronous Branch-and-Bound DCOP Algorithm

Distributed constraint optimization (DCOP) problems are a popular way of formulating and solving agent-coordination problems. It is often desirable to solve DCOP problems optimally with memory-bounded and asynchronous algorithms. We introduce Branch-and-Bound ADOPT (BnB- ADOPT), a memory-bounded asynchronous DCOP algorithm that uses the message passing and communication framework of ADOPT, a well known memory-bounded asynchronous DCOP algorithm, but changes the search strategy of ADOPT from best-first search to depth-first branch-andbound search. Our experimental results show that BnB- ADOPT is up to one order of magnitude faster than ADOPT on a variety of large DCOP problems and faster than NCBB, a memory-bounded synchronous DCOP algorithm, on most of these DCOP problems.

Authors

• William Yeoh Washington University in St. Louis
• Ariel Felner Computer and Information Sciences, Ben-Gurion University of the Negev
• Sven Koenig University of California & Örebro University

Keywords

• Agent cooperation::distributed problem solving