Limitations of Front-to-End Bidirectional Heuristic Search
Abstract
We present an intuitive explanation for the limited effectiveness of front-to-end bidirectional heuristic search, supported with extensive evidence from many commonly-studied domains. While previous work has proved the limitations of specific algorithms, we show that any front-to-end bidirectional heuristic search algorithm will likely be dominated by unidirectional heuristic search or bidirectional brute-force search. We also demonstrate a pathological case where bidirectional heuristic search is the dominant algorithm, so a stronger claim cannot be made. Finally, we show that on the four-peg Towers Of Hanoi with arbitrary start and goal states, bidirectional brute-force search outperforms unidirectional heuristic search using pattern-database heuristics.
Cite
Text
Barker and Korf. "Limitations of Front-to-End Bidirectional Heuristic Search." AAAI Conference on Artificial Intelligence, 2015. doi:10.1609/AAAI.V29I1.9374Markdown
[Barker and Korf. "Limitations of Front-to-End Bidirectional Heuristic Search." AAAI Conference on Artificial Intelligence, 2015.](https://mlanthology.org/aaai/2015/barker2015aaai-limitations/) doi:10.1609/AAAI.V29I1.9374BibTeX
@inproceedings{barker2015aaai-limitations,
title = {{Limitations of Front-to-End Bidirectional Heuristic Search}},
author = {Barker, Joseph Kelly and Korf, Richard E.},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2015},
pages = {1086-1092},
doi = {10.1609/AAAI.V29I1.9374},
url = {https://mlanthology.org/aaai/2015/barker2015aaai-limitations/}
}