BIDA^*: an improved perimeter search algorithm

In this paper we present a new bidirectional heuristic search algorithm. Our algorithm can be viewed as a perimeter search algorithm, and it uses a new technique for reducing the number of heuristic evaluations. We also prove some general results on the behavior of iterative deepening perimeter search algorithms, and we discuss some new 'lazy evaluation' techniques for improving their performance. The theoretical and experimental results show that perimeter search algorithms outperform the other bidirectional algorithms, and we believe it is worthwhile to give them a deep look in subsequent research.