Not Logged In

Front-to-End Bidirectional Heuristic Search with Near-Optimal Node Expansions

Full Text: 0069.pdf PDF

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

University of Alberta Logo AICML Logo