Bidirectional Heuristic Search: Expanding Nodes by a Lower Bound
Abstract
Recent work on bidirectional search defined a lower bound on costs of paths between pairs of nodes, and introduced a new algorithm, NBS, which is based on this bound. Building on these results, we introduce DVCBS, a new algorithm that aims to to further reduce the number of expansions. Generalizing beyond specific algorithms, we then propose a method for enhancing heuristics by propagating such lower bounds (lb-propagation) between frontiers. This lb-propagation can be used in existing algorithms, often improving their performance, as well as making them "well behaved".
Cite
Text
Shperberg et al. "Bidirectional Heuristic Search: Expanding Nodes by a Lower Bound." International Joint Conference on Artificial Intelligence, 2020. doi:10.24963/IJCAI.2020/664Markdown
[Shperberg et al. "Bidirectional Heuristic Search: Expanding Nodes by a Lower Bound." International Joint Conference on Artificial Intelligence, 2020.](https://mlanthology.org/ijcai/2020/shperberg2020ijcai-bidirectional/) doi:10.24963/IJCAI.2020/664BibTeX
@inproceedings{shperberg2020ijcai-bidirectional,
title = {{Bidirectional Heuristic Search: Expanding Nodes by a Lower Bound}},
author = {Shperberg, Shahaf S. and Felner, Ariel and Sturtevant, Nathan R. and Shimony, Solomon Eyal and Hayoun, Avi},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2020},
pages = {4775-4779},
doi = {10.24963/IJCAI.2020/664},
url = {https://mlanthology.org/ijcai/2020/shperberg2020ijcai-bidirectional/}
}