Extended Abstract: An Improved Priority Function for Bidirectional Heuristic Search Conference Paper uri icon

abstract

  • 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 MMs priority function and is expected to expand fewer nodes than MM under most circumstances. We sketch a proof of MMes 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.

published proceedings

  • Proceedings of the International Symposium on Combinatorial Search

author list (cited authors)

  • Sharon, G., Holte, R., Felner, A., & Sturtevant, N.

citation count

  • 0

complete list of authors

  • Sharon, Guni||Holte, Robert||Felner, Ariel||Sturtevant, Nathan

publication date

  • January 2016