TY - GEN
T1 - Generalizing ADOPT and BnB-ADOPT
AU - Gutierrez, Patricia
AU - Meseguer, Pedro
AU - Yeoh, William
PY - 2011
Y1 - 2011
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/84877995139
U2 - 10.5591/978-1-57735-516-8/IJCAI11-100
DO - 10.5591/978-1-57735-516-8/IJCAI11-100
M3 - Conference contribution
AN - SCOPUS:84877995139
SN - 9781577355120
T3 - IJCAI International Joint Conference on Artificial Intelligence
SP - 554
EP - 559
BT - IJCAI 2011 - 22nd International Joint Conference on Artificial Intelligence
T2 - 22nd International Joint Conference on Artificial Intelligence, IJCAI 2011
Y2 - 16 July 2011 through 22 July 2011
ER -