Generalizing ADOPT and BnB-ADOPT

Gutierrez, Patricia; Meseguer, Pedro; Yeoh, William

doi:10.5591/978-1-57735-516-8/IJCAI11-100

Generalizing ADOPT and BnB-ADOPT

Patricia Gutierrez, Pedro Meseguer, William Yeoh

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 554-558.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-100

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 = ∞ 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.

Patricia Gutierrez, Pedro Meseguer, and William Yeoh. 2011. Generalizing ADOPT and BnB-ADOPT. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 554–558. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-100

@inproceedings{ijcai2011p100,
  title     = {Generalizing ADOPT and BnB-ADOPT},
  author    = {Gutierrez, Patricia and Meseguer, Pedro and Yeoh, William},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {554--558},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-100},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-100},
}

TY  - CPAPER
TI  - Generalizing ADOPT and BnB-ADOPT
AU  - Gutierrez, Patricia
AU  - Meseguer, Pedro
AU  - Yeoh, William
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 554
EP  - 558
DO  - 10.5591/978-1-57735-516-8/IJCAI11-100
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-100
ER  -