Optimally Efficient Bidirectional Search
Abstract
A* is optimally efficient with regard to node expansions among unidirectional admissible algorithms — those that only assume that the heuristic used is admissible. This paper studies algorithms that are optimally efficient for bidirectional search algorithms. We present the Fractional MM algorithm and its sibling, the MT algorithm, which is simpler to analyze. We then develop variants of these algorithms that are optimally efficient, each under different assumptions on the information available to the algorithm.
Cite
Text
Shaham et al. "Optimally Efficient Bidirectional Search." International Joint Conference on Artificial Intelligence, 2019. doi:10.24963/IJCAI.2019/867Markdown
[Shaham et al. "Optimally Efficient Bidirectional Search." International Joint Conference on Artificial Intelligence, 2019.](https://mlanthology.org/ijcai/2019/shaham2019ijcai-optimally/) doi:10.24963/IJCAI.2019/867BibTeX
@inproceedings{shaham2019ijcai-optimally,
title = {{Optimally Efficient Bidirectional Search}},
author = {Shaham, Eshed and Felner, Ariel and Sturtevant, Nathan R. and Rosenschein, Jeffrey S.},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2019},
pages = {6221-6225},
doi = {10.24963/IJCAI.2019/867},
url = {https://mlanthology.org/ijcai/2019/shaham2019ijcai-optimally/}
}