Sufficient Conditions for Node Expansion in Bidirectional Heuristic Search
- Jürgen Eckerle
- Jingwei Chen
- Nathan R. Sturtevant
- Sandra Zilles
- Robert Holte, Department of Computing Science, University of Alberta
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.
Citation
J. Eckerle, J. Chen, N. Sturtevant, S. Zilles, R. Holte. "Sufficient Conditions for Node Expansion in Bidirectional Heuristic Search". ICAPS, (ed: Laura Barbulescu, Jeremy Frank, Mausam, Stephen F. Smith), pp 79-87, June 2017.| Keywords: | |
| Category: | In Conference |
| Web Links: | AAAI |
BibTeX
@incollection{Eckerle+al:ICAPS17,
author = {Jürgen Eckerle and Jingwei Chen and Nathan R. Sturtevant and
Sandra Zilles and Robert Holte},
title = {Sufficient Conditions for Node Expansion in Bidirectional Heuristic
Search},
Editor = {Laura Barbulescu, Jeremy Frank, Mausam, Stephen F. Smith},
Pages = {79-87},
booktitle = {},
year = 2017,
}Last Updated: July 05, 2020Submitted by Sabina P
