D-Node Retargeting in Bidirectional Heuristic Search

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 4

Automated Reasoning

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.