Bidirectional Heuristic Search: Expanding Nodes by a Lower Bound

Shahaf S. Shperberg, Ariel Felner, Nathan R. Sturtevant, Solomon Eyal Shimony, Avi Hayoun

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".
BibTeX
@inproceedings{shperberg2020bidirectional,
  author = {Shahaf S. Shperberg and Ariel Felner and Nathan R. Sturtevant and Solomon Eyal Shimony and Avi Hayoun},
  title = {{Bidirectional Heuristic Search: Expanding Nodes by a Lower Bound}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/664},
}

Loading related content...

Figure