Extended Abstract: An Improved Priority Function for Bidirectional Heuristic Search

Proceedings of the International Symposium on Combinatorial Search, 9

Volume

Vol. 9 No. 1 (2016): Ninth Annual Symposium on Combinatorial Search

Short Papers

Bidirectional search algorithms interleave a search forward from the start state (start ) and a search backward (i.e. using reverse operators) from the goal state (goal). We say that the two searches “meet in the middle” if neither search expands a node whose g-value (in the given direction) exceeds C*/2 , where C* is the cost of an optimal solution. The only bidirectional heuristic search algorithm that is guaranteed to meet in the middle under all circumstances is the recently introduced MM algorithm (Holte et al. 2016). The feature of MM that provides this guarantee is its unique priority functions for nodes on its open lists. In this short note we present MMe, which enhances MM’s priority function and is expected to expand fewer nodes than MM under most circumstances. We sketch a proof of MMe’s correctness, describe conditions under which MMe will expand fewer nodes than MM and vice versa, and experimentally compare MMe and MM on the 10-Pancake problem.

10.1609/socs.v7i1.18399