AAAI Publications, Twenty-Seventh International Conference on Automated Planning and Scheduling

Font Size: 
Sufficient Conditions for Node Expansion in Bidirectional Heuristic Search
Juergen Eckerle, Jingwei Chen, Nathan R. Sturtevant, Sandra Zilles, Robert C. Holte

Last modified: 2017-06-05


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.

Full Text: PDF