Generalizing ADOPT and BnB-ADOPT
Patricia Gutierrez, Pedro Meseguer and William Yeoh
ADOPT and BnB-ADOPT are two optimal DCOP search algorithms that are related. They use the same kind of messages, but they use different search strategies: the former uses best-first search while the latter uses depth-first branch-and-bound search. In this paper, we present a new algorithm, ADOPT($k$), that generalizes them. ADOPT($k$) depends on the $k$ parameter: when $k=1$, it behaves like ADOPT, and when $k=\infty$, it behaves like BnB-ADOPT. For intermediate values, $1 < k < \infty$, it behaves like a hybrid of ADOPT and BnB-ADOPT. We show that ADOPT($k$) is an optimal algorithm. Lastly, ADOPT($k$) exhibits a better performance than ADOPT and BnB-ADOPT on different benchmarks.