AAAI

Association for the Advancement of Artificial Intelligence

Home > Proceedings / Proceedings of the International Symposium on Combinatorial Search, 10

The Minimal Set of States that Must Be Expanded in a Front-to-End Bidirectional Search

Authors

Eshed Shaham,Ariel Felner,Jingwei Chen,Nathan Sturtevant

Hebrew University of Jerusalem,Ben-Gurion University of the Negev,University of Denver,University of Denver


Proceedings:

Proceedings of the International Symposium on Combinatorial Search, 10

Volume

Issue:

Vol. 10 No. 1 (2017): Tenth Annual Symposium on Combinatorial Search

Track:

Long Papers

Downloads:

Download PDF

Abstract:

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.

DOI:

10.1609/socs.v8i1.18426


SOCS

Vol. 10 No. 1 (2017): Tenth Annual Symposium on Combinatorial Search