D-Node Retargeting in Bidirectional Heuristic Search

George Politowski, Ira Pohl

AIthough 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 starches 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.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.