D-Node Retargeting in Bidirectional Heuristic Search

Abstract

Although it is generally agreed that bidirectional heuristic search is potentially more efficient than unidirectional heuristic search, so far there have been no algorithms which realize this potential. The basic difficulty is that the two search trees (one rooted at the start, the other at the goal) do not meet in the middle. This results in essentially two unidirectional searches and poorer performance. In this paper we present an efficient algorithm for bidirectional heuristic search which overcomes this difficulty. We also compare this algorithm with de Champeaux's BHFFA [2,3] on the basis of search efficiency, solution quality, and computational cost.