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

摘要: It is well-known that any admissible unidirectional heuristic search algorithm must expand all states whose $f$-value smaller than the optimal solution cost when using a consistent heuristic. Such are called "surely expanded" (s.e.). A recent study characterized s.e. pairs of for bidirectional with heuristics: if pair then at least one two be expanded. This paper derives lower bound, VC, on minimum number expansions required to cover pairs, and present new front-to-end algorithm, Near-Optimal Bidirectional Search (NBS), guaranteed do no more 2VC expansions. We further prove has worst case better 2VC. Experimental results show NBS competes or outperforms existing algorithms, often A* as well.