Improving Bidirectional Heuristic Search by Bounds Propagation


  • Shahaf Shperberg Ben-Gurion University of the Negev
  • Ariel Felner Ben-Gurion University of the Negev
  • Solomon Shimony Ben-Gurion University of the Negev
  • Nathan Sturtevant University of Alberta
  • Avi Hayoun Ben-Gurion University of the Negev



Recent work in bidirectional heuristic search characterize pairs of nodes from which at least one node must be expanded in order to ensure optimality of solutions. We use these findings to propose a method for improving existing heuristics by propagating lower bounds between the forward and backward frontiers. We then define a number of desirable properties for bidirectional heuristic search algorithms, and show that applying the bound propagations adds these properties to many existing algorithms (e.g. to the MM family of algorithms). Finally, experimental results show that applying these propagations significantly reduce the running time of various algorithms.