Abstract:

ADOPT and BnB-ADOPT are two optimal DCOP search algorithms that are similar except for their search strategies: the former uses best-first search and the latter uses depth-first branch-and-bound search. In this paper, we present a new algorithm, called ADOPT($k$), that generalizes them. Its behavior depends on the $k$ parameter. It behaves like ADOPT when $k=1$, like BnB-ADOPT when $k=\infty$ and like a hybrid of ADOPT and BnB-ADOPT when $1 < k < \infty$. We prove that ADOPT($k$) is a correct and complete algorithm and experimentally show that ADOPT($k$) outperforms ADOPT and BnB-ADOPT on several benchmarks across several metrics.

• Tagged
• XML
• BibTex