Front-to-End Bidirectional Heuristic Search with Near-Optimal Node Expansions
- Jingwei Chen
- Robert Holte, Department of Computing Science, University of Alberta
- Sandra Zilles
- Nathan R. Sturtevant
It is well-known that any admissible unidirectional heuristic search algorithm must expand all states whose f-value is smaller than the optimal solution cost when using a consistent heuristic. Such states are called “surely expanded†(s.e.). A recent study characterized s.e. pairs of states for bidirectional search with consistent heuristics: if a pair of states is s.e. then at least one of the two states must be expanded. This paper derives a lower bound, VC, on the minimum number of expansions required to cover all s.e. pairs, and present a new admissible front-to-end bidirectional heuristic search algorithm, Near-Optimal Bidirectional Search (NBS), that is guaranteed to do no more than 2VC expansions. We further prove that no admissible front-to-end algorithm has a worst case better than 2VC. Experimental results show that NBS competes with or outperforms existing bidirectional search algo-rithms, and often outperforms A* as well.
Citation
J. Chen, R. Holte, S. Zilles, N. Sturtevant. "Front-to-End Bidirectional Heuristic Search with Near-Optimal Node Expansions". International Joint Conference on Artificial Intelligence (IJCAI), (ed: Carles Sierra), pp 489-495, August 2017.Keywords: | Combinatorial search/optimisation, Heuristic Search |
Category: | In Conference |
Web Links: | doi |
IJCAI |
BibTeX
@incollection{Chen+al:IJCAI17, author = {Jingwei Chen and Robert Holte and Sandra Zilles and Nathan R. Sturtevant}, title = {Front-to-End Bidirectional Heuristic Search with Near-Optimal Node Expansions}, Editor = {Carles Sierra}, Pages = {489-495}, booktitle = {International Joint Conference on Artificial Intelligence (IJCAI)}, year = 2017, }Last Updated: July 05, 2020
Submitted by Sabina P