Improving Bidirectional Heuristic Search by Bounds Propagation
- Shahaf S. Shperberg
- Ariel Felner, Information Systems Engineering, Ben-Gurion University, Israel
- Solomon Eyal Shimony
- Nathan R. Sturtevant
- Avi Hayoun
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.
Citation
S. Shperberg, A. Felner, S. Shimony, N. Sturtevant, A. Hayoun. "Improving Bidirectional Heuristic Search by Bounds Propagation". Symposium on Combinatorial Search, (ed: Pavel Surynek, William Yeoh), pp 106-114, July 2019.| Keywords: | |
| Category: | In Conference |
| Web Links: | AAAI |
BibTeX
@incollection{Shperberg+al:SoCS19,
author = {Shahaf S. Shperberg and Ariel Felner and Solomon Eyal Shimony and
Nathan R. Sturtevant and Avi Hayoun},
title = {Improving Bidirectional Heuristic Search by Bounds Propagation},
Editor = {Pavel Surynek, William Yeoh},
Pages = {106-114},
booktitle = {Symposium on Combinatorial Search},
year = 2019,
}Last Updated: July 03, 2020Submitted by Sabina P
