Bidirectional Heuristic Search: Expanding Nodes by a Lower Bound

Shahaf Shperberg; Ariel Felner; Nathan Sturtevant; Eyal Shimony; Avi Hayoun

IJCAI 2020poster0 citations

Bidirectional Heuristic Search: Expanding Nodes by a Lower Bound

Shahaf Shperberg, Ariel Felner, Nathan Sturtevant, 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".

Heuristic Search and Game Playing: Heuristic Search

BibTeX

@inproceedings{ijcai2020p664,
  title     = {Bidirectional Heuristic Search: Expanding Nodes by a Lower Bound},
  author    = {Shperberg, Shahaf and Felner, Ariel and Sturtevant, Nathan and Shimony, Eyal and Hayoun, Avi},
  booktitle = {Proceedings of the Twenty-Ninth International Joint Conference on
               Artificial Intelligence, {IJCAI-20}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Christian Bessiere},
  pages     = {4775--4779},
  year      = {2020},
  month     = {7},
  note      = {Sister Conferences Best Papers},
  doi       = {10.24963/ijcai.2020/664},
  url       = {https://doi.org/10.24963/ijcai.2020/664},
}