ML Anthology

Generalizing ADOPT and BnB-ADOPT

Patricia Gutierrez, Pedro Meseguer, William Yeoh
IJCAI 2011 pp. 554-559
doi:10.5591/978-1-57735-516-8/IJCAI11-100 /ijcai/2011/gutierrez2011ijcai-generalizing/

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.

PDF IJCAI Semantic Scholar

Cite

Text

Gutierrez et al. "Generalizing ADOPT and BnB-ADOPT." International Joint Conference on Artificial Intelligence, 2011. doi:10.5591/978-1-57735-516-8/IJCAI11-100

Markdown

[Gutierrez et al. "Generalizing ADOPT and BnB-ADOPT." International Joint Conference on Artificial Intelligence, 2011.](https://mlanthology.org/ijcai/2011/gutierrez2011ijcai-generalizing/) doi:10.5591/978-1-57735-516-8/IJCAI11-100

BibTeX

@inproceedings{gutierrez2011ijcai-generalizing,
  title     = {{Generalizing ADOPT and BnB-ADOPT}},
  author    = {Gutierrez, Patricia and Meseguer, Pedro and Yeoh, William},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2011},
  pages     = {554-559},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-100},
  url       = {https://mlanthology.org/ijcai/2011/gutierrez2011ijcai-generalizing/}
}