The Minimal Set of States that Must Be Expanded in a Front-to-End Bidirectional Search
- Eshed Shaham
- Ariel Felner, Information Systems Engineering, Ben-Gurion University, Israel
- Jingwei Chen
- Nathan R. Sturtevant
A* is optimal among admissible unidirectional algorithms when searching with a consistent heuristic. Recently, similar optimality bounds have been established for bidirectional search but, no practical algorithm is guaranteed to always achieve this bound. In this paper we study the nature of the number of nodes that must be expanded in any front-to-end bidirectional search. We present an efficient algorithm for computing that number and show that a theoretical parameterized generalization of MM, with the correct parameter, is the optimal front-to-end bidirectional search. We then experimentally compare various algorithms and show how far they are from optimal.
Citation
E. Shaham, A. Felner, J. Chen, N. Sturtevant. "The Minimal Set of States that Must Be Expanded in a Front-to-End Bidirectional Search". Symposium on Combinatorial Search, (ed: Alex Fukunaga, Akihiro Kishimoto), pp 82-90, June 2017.| Keywords: | |
| Category: | In Conference |
| Web Links: | AAAI |
BibTeX
@incollection{Shaham+al:SoCS17,
author = {Eshed Shaham and Ariel Felner and Jingwei Chen and Nathan R.
Sturtevant},
title = {The Minimal Set of States that Must Be Expanded in a Front-to-End
Bidirectional Search},
Editor = {Alex Fukunaga, Akihiro Kishimoto},
Pages = {82-90},
booktitle = {Symposium on Combinatorial Search},
year = 2017,
}Last Updated: July 05, 2020Submitted by Sabina P
