Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings         Authors   Author's Info   Article details         Search    
Mini-Bucket Heuristics for Improved Search
Kalev Kask, Rina Dechter
Abstract:
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.
Keywords: Bayesian Networks, Heuristic Search
Pages: 314-323
PS Link:
PDF Link: /papers/99/p314-kask.pdf
BibTex:
@INPROCEEDINGS{Kask99,
AUTHOR = "Kalev Kask and Rina Dechter",
TITLE = "Mini-Bucket Heuristics for Improved Search",
BOOKTITLE = "Proceedings of the Fifteenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-99)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "1999",
PAGES = "314--323"
}


hosted by DSL   •   site info   •   help