Recursive Best-First AND/OR Search for Graphical Models

Akihiro Kishimoto, Radu Marinescu
Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, PMLR R12:421-430, 2014.

Abstract

The paper presents and evaluates the power of limited memory best-first search over AND/OR spaces for optimization tasks in graphical mod- els. We propose Recursive Best-First AND/OR Search with Overestimation (RBFAOO), a new algorithm that explores the search space in a best-first manner while operating with restricted memory. We enhance RBFAOO with a simple overestimation technique aimed at minimizing the overhead associated with re-expanding inter- nal nodes and prove correctness and complete- ness of RBFAOO. Our experiments show that RBFAOO is often superior to the current state- of-the-art approaches based on AND/OR search, especially on very hard problem instances.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR12-kishimoto14a, title = {Recursive Best-First {AND}/{OR} Search for Graphical Models}, author = {Kishimoto, Akihiro and Marinescu, Radu}, booktitle = {Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence}, pages = {421--430}, year = {2014}, editor = {Zhang, Nevin L. and Tian, Jin}, volume = {R12}, series = {Proceedings of Machine Learning Research}, month = {23--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r12/main/assets/kishimoto14a/kishimoto14a.pdf}, url = {https://proceedings.mlr.press/r12/kishimoto14a.html}, abstract = {The paper presents and evaluates the power of limited memory best-first search over AND/OR spaces for optimization tasks in graphical mod- els. We propose Recursive Best-First AND/OR Search with Overestimation (RBFAOO), a new algorithm that explores the search space in a best-first manner while operating with restricted memory. We enhance RBFAOO with a simple overestimation technique aimed at minimizing the overhead associated with re-expanding inter- nal nodes and prove correctness and complete- ness of RBFAOO. Our experiments show that RBFAOO is often superior to the current state- of-the-art approaches based on AND/OR search, especially on very hard problem instances.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Recursive Best-First AND/OR Search for Graphical Models %A Akihiro Kishimoto %A Radu Marinescu %B Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2014 %E Nevin L. Zhang %E Jin Tian %F pmlr-vR12-kishimoto14a %I PMLR %P 421--430 %U https://proceedings.mlr.press/r12/kishimoto14a.html %V R12 %X The paper presents and evaluates the power of limited memory best-first search over AND/OR spaces for optimization tasks in graphical mod- els. We propose Recursive Best-First AND/OR Search with Overestimation (RBFAOO), a new algorithm that explores the search space in a best-first manner while operating with restricted memory. We enhance RBFAOO with a simple overestimation technique aimed at minimizing the overhead associated with re-expanding inter- nal nodes and prove correctness and complete- ness of RBFAOO. Our experiments show that RBFAOO is often superior to the current state- of-the-art approaches based on AND/OR search, especially on very hard problem instances. %Z Reissued by PMLR on 04 October 2026.
APA
Kishimoto, A. & Marinescu, R.. (2014). Recursive Best-First AND/OR Search for Graphical Models. Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R12:421-430 Available from https://proceedings.mlr.press/r12/kishimoto14a.html. Reissued by PMLR on 04 October 2026.

Related Material