TitleGeneralizing ADOPT and BnB-ADOPT
Publication TypeConference Paper
Year of Publication2011
AuthorsGutierrez P, Meseguer P, Yeoh W
Conference Name22nd International Joint Conference on Artificial Intelligence (IJCAI 2011)
Conference LocationBarcelona, Spain
Date Published16/07/2011

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=∞$ and like a hybrid of ADOPT and BnB-ADOPT when $1 < k < ∞$. 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.