Improving Bidirectional Heuristic Search by Bounds Propagation

Proceedings of the International Symposium on Combinatorial Search, 12

Volume

Vol. 12 No. 1 (2019): Twelfth Annual Symposium on Combinatorial Search

Long Papers

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.

10.1609/socs.v10i1.18508