2013/01/23 by Kalev Kask, Kask, Kalev, Rina Dechter +1
Computer Science · #AI-based Problem Solving and Planning #Artificial Intelligence (cs.AI) #Bayesian Modeling and Causal Inference #FOS: Computer and information sciences #Machine Learning and Algorithms #cs.AI
paper · pdf · doi:10.48550/arxiv.1301.6708
Appears in Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence (UAI1999)
arxiv created 2013/01/23 · openalex publication_date 2013/01/23 · arxiv updated 2013/01/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The paper is a second in a series of two papers evaluating the power of a new scheme that generates search heuristics mechanically. The heuristics are extracted from an approximation scheme called mini-bucket elimination that was recently introduced. The first paper introduced the idea and evaluated it within Branch-and-Bound search. In the current paper the idea is further extended and evaluated within Best-First search. The resulting algorithms are compared on coding and medical diagnosis problems, using varying strength of the mini-bucket heuristics. Our results demonstrate an effective search scheme that permits controlled tradeoff between preprocessing (for heuristic generation) and search. Best-first search is shown to outperform Branch-and-Bound, when supplied with good heuristics, and sufficient memory space.