Using Lookaheads with Optimal Best-First Search
Abstract
We present an algorithm that exploits the complimentary benefits of best-first search (BFS) and depth-first search (DFS) by performing limited DFS lookaheads from the frontier of BFS. We show that this continuum requires significantly less memory than BFS. In addition, a time speedup is also achieved when choosing the lookahead depth correctly. We demonstrate this idea for breadth-first search and for A*. Additionally, we show that when using inconsistent heuristics, Bidirectional Pathmax (BPMX), can be implemented very easily on top of the lookahead phase. Experimental results on several domains demonstrate the benefits of all our ideas.
Cite
Text
Stern et al. "Using Lookaheads with Optimal Best-First Search." AAAI Conference on Artificial Intelligence, 2010. doi:10.1609/AAAI.V24I1.7559Markdown
[Stern et al. "Using Lookaheads with Optimal Best-First Search." AAAI Conference on Artificial Intelligence, 2010.](https://mlanthology.org/aaai/2010/stern2010aaai-using/) doi:10.1609/AAAI.V24I1.7559BibTeX
@inproceedings{stern2010aaai-using,
title = {{Using Lookaheads with Optimal Best-First Search}},
author = {Stern, Roni and Kulberis, Tamar and Felner, Ariel and Holte, Robert},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2010},
pages = {185-190},
doi = {10.1609/AAAI.V24I1.7559},
url = {https://mlanthology.org/aaai/2010/stern2010aaai-using/}
}