Sufficient Conditions for Node Expansion in Bidirectional Heuristic Search

Authors

  • Juergen Eckerle Berner Fachhochschule
  • Jingwei Chen University of Denver
  • Nathan Sturtevant University of Denver
  • Sandra Zilles University of Regina
  • Robert Holte University of Alberta

DOI:

https://doi.org/10.1609/icaps.v27i1.13825

Abstract

In this paper we study bidirectional state space search with consistent heuristics, with a focus on obtaining sufficient conditions for node expansion, that is, conditions characterizing nodes that must be expanded by any admissible bidirectional search algorithm. We provide such conditions for front-to-front and front-to-end bidirectional search. The sufficient conditions are used to prove that the front-to-front bidirectional search algorithm BDS1 is optimally efficient, in terms of node expansion, among a broad class of bidirectional search algorithms, for a specific class of problem instances. Dechter and Pearl's well-known result on sufficient conditions for node expansion by unidirectional algorithms such as A* is shown to be a special case of our results.

Downloads

Published

2017-06-05

How to Cite

Eckerle, J., Chen, J., Sturtevant, N., Zilles, S., & Holte, R. (2017). Sufficient Conditions for Node Expansion in Bidirectional Heuristic Search. Proceedings of the International Conference on Automated Planning and Scheduling, 27(1), 79-87. https://doi.org/10.1609/icaps.v27i1.13825

Issue

Vol. 27 (2017): Twenty-Seventh International Conference on Automated Planning and Scheduling

Section

Main Track