Enriching Non-Parametric Bidirectional Search Algorithms
Abstract
NBS is a non-parametric bidirectional search algorithm proven to expand at most twice the number of node expansions required to verify the optimality of a solution. We introduce new variants of NBS that are aimed at finding all optimal solutions. We then introduce an algorithmic framework that includes NBS as a special case. Finally, we introduce DVCBS, a new algorithm in this framework that aims to further reduce the number of expansions. Unlike NBS, DVCBS does not have any worst-case bound guarantees, but in practice it outperforms NBS in verifying the optimality of solutions.
Cite
Text
Shperberg et al. "Enriching Non-Parametric Bidirectional Search Algorithms." AAAI Conference on Artificial Intelligence, 2019. doi:10.1609/AAAI.V33I01.33012379Markdown
[Shperberg et al. "Enriching Non-Parametric Bidirectional Search Algorithms." AAAI Conference on Artificial Intelligence, 2019.](https://mlanthology.org/aaai/2019/shperberg2019aaai-enriching/) doi:10.1609/AAAI.V33I01.33012379BibTeX
@inproceedings{shperberg2019aaai-enriching,
title = {{Enriching Non-Parametric Bidirectional Search Algorithms}},
author = {Shperberg, Shahaf S. and Felner, Ariel and Sturtevant, Nathan R. and Shimony, Solomon Eyal and Hayoun, Avi},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2019},
pages = {2379-2386},
doi = {10.1609/AAAI.V33I01.33012379},
url = {https://mlanthology.org/aaai/2019/shperberg2019aaai-enriching/}
}