Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
Recursive Best-First AND/OR Search for Optimization in Graphical Models
Akihiro Kishomoto, Radu Marinescu
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.
Keywords:
Pages: 400-409
PS Link:
PDF Link: /papers/14/p400-kishomoto.pdf
BibTex:
@INPROCEEDINGS{Kishomoto14,
AUTHOR = "Akihiro Kishomoto and Radu Marinescu",
TITLE = "Recursive Best-First AND/OR Search for Optimization in Graphical Models",
BOOKTITLE = "Proceedings of the Thirtieth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-14)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2014",
PAGES = "400--409"
}


hosted by DSL   •   site info   •   help