It is well-known that any admissible unidirectional heuristic search algorithm must expand all states whose @math -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 algorithms, and often outperforms A* as well.
Bidirectional search has a long history, beginning with bidirectional brute force search @cite_1 , and proceeding to heuristic search algorithms such as BHPA @cite_8 . Other notable algorithms include BS* @cite_7 , which avoids re-expanding states in both directions, and MM @cite_0 , which ensures that the search frontiers meet in the middle. Along with these algorithms there have been explanations for the poor performance of bidirectional heuristic search, including that the frontiers miss @cite_10 or that the frontiers meet early, and a long time is spent proving the optimal solution @cite_4 . Recent work has refined this, showing that with strong heuristics the frontiers meet later @cite_6 .
@cite_4 @cite_7 @cite_8 @cite_1 @cite_6 @cite_0 @cite_10
1539048696 1971267722 1965469937 1881819129 2566652907
The assessment of bidirectional heuristic search has been incorrect since it was first published more than a quarter of a century ago. For quite a long time, this search strategy did not achieve the expected results, and there was a major misunderstanding about the reasons behind it. Although there is still wide-spread belief that bidirectional heuristic search is afflicted by the problem of search frontiers passing each other, we demonstrate that this conjecture is wrong. Based on this finding, we present both a new generic approach to bidirectional heuristic search and a new approach to dynamically improving heuristic values that is feasible in bidirectional search only. These approaches are put into perspective with both the traditional and more recently proposed approaches in order to facilitate a better overall understanding. Empirical results of experiments with our new approaches show that bidirectional heuristic search can be performed very efficiently and also with limited memory. These results suggest that bidirectional heuristic search appears to be better for solving certain difficult problems than corresponding unidirectional search. This provides some evidence for the usefulness of a search strategy that was long neglected. In summary, we show that bidirectional heuristic search is viable and consequently propose that it be reconsidered. Abstract In order to reap the potential advantage of less extensive searching which bidirectional heuristic search algorithms offer, strategies are needed to influence the two search wavefronts to meet such that early termination will occur. The principled search control strategy aims to achieve this without trading running time, but can be found wanting still. An improved algorithm BS∗ is described which expands significantly less nodes on average than any other algorithm in the same class of non-wave-shaping admissible bidirectional algorithms. When pitted against BHPA, the only other heuristically guided member in this class, BS∗'s average search efficiency in time and space is about 30 better. BS∗'s superior performance stems from the use of all opportunities to achieve early termination and the elimination of unfruitful avenues by search reduction operations: nipping, pruning, trimming and screening. Such operations exploit information gathered during search and have several spin-offs: more accurate guidance of search control, early exposure of nonpromising nodes and reduced bookkeeping overheads, all of which further enhance BS∗'s performance. A further noteworthy feature of BS∗ is that it is the first staged search algorithm which preserves admissibility. A new method is proposed for finding the shortest route between two points in an interconnected network. The shortest route is found by investigating a selection of routes from both the starting point and the terminal point. The selection of routes is decided dynamically by extending one by one the routes which have currently covered the least distance. Once a complete through route has been found, it has to be made certain that it is the minimum. The new method appears to be more efficient than alternative approaches to the problem through linear or dynamic programming. Some applications of the technique to scheduling and other problems are briefly described. We present an intuitive explanation for the limited effectiveness of front-to-end bidirectional heuristic search, supported with extensive evidence from many commonly-studied domains. While previous work has proved the limitations of specific algorithms, we show that any front-to-end bidirectional heuristic search algorithm will likely be dominated by unidirectional heuristic search or bidirectional brute-force search. We also demonstrate a pathological case where bidirectional heuristic search is the dominant algorithm, so a stronger claim cannot be made. Finally, we show that on the four-peg Towers Of Hanoi with arbitrary start and goal states, bidirectional brute-force search outperforms unidirectional heuristic search using pattern-database heuristics. We present MM, the first bidirectional heuristic search algorithm whose forward and backward searches are guaranteed to "meet in the middle", i.e. never expand a node beyond the solution midpoint. We also present a novel framework for comparing MM, A*, and brute-force search, and identify conditions favoring each algorithm. Finally, we present experimental results that support our theoretical analysis.