Bidirectional Best-First Search with Bounded Error: Summary of Results

Abstract

For more than two decades there has been consensus that bidirectional heuristic search is afflicted by the problem of search wavefronts missing each other. However, our results indicate that a different problem appears to be of primary importance. The fronts typically meet rather early even without using wave-shaping techniques. Especially when aiming for optimal solutions, however, much effort has to be spent for subsequently improving the solution quality, and finally for proving that there is indeed no better solution possible. Therefore, only slightly relaxing the requirements on the solution quality already leads to strong improvements in efficiency. We describe several new €-admissible bidirectional search algorithms which do not use wave-shaping techniques. The most efficient of these use a novel termination criterion designed to address the suspected primary problem of bidirectional heuristic search. We prove €-admissibility and a dominance result based on this termination criterion. In summary, we show that and how bidirectional best-first search can be more efficient than the corresponding unidirectional counterpart without using computationally very demanding waveshaping techniques.