Bidirectional Heuristic Search Reconsidered

TLDR

Bidirectional heuristic search has been incorrectly assessed for over a quarter of a century, with persistent misunderstandings about its performance and a widespread belief that frontiers passing each other impede progress. The study introduces a new generic bidirectional heuristic search method and a dynamic heuristic improvement technique that is feasible only in bidirectional search. The authors develop a generic bidirectional search framework and a dynamic heuristic refinement strategy that operates exclusively within bidirectional search. Experimental results demonstrate that bidirectional heuristic search can be performed efficiently with limited memory, outperforms unidirectional search on challenging problems, and confirms its viability, prompting a reconsideration of the strategy.

Abstract

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.