Improving Bidirectional Heuristic Search by Bounds Propagation
Shperberg, Shahaf S. (Ben-Gurion University of the Negev) | Felner, Ariel (Ben-Gurion University of the Negev) | Shimony, Solomon Eyal (Ben-Gurion University of the Negev) | Sturtevant, Nathan R. (University of Alberta) | Hayoun, Avi (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.
