Enriching Non-Parametric Bidirectional Search Algorithms

Authors

  • Shahaf S. Shperberg Ben-Gurion University
  • Ariel Felner Ben-Gurion University
  • Nathan R. Sturtevant University of Alberta
  • Solomon E. Shimony Ben-Gurion University
  • Avi Hayoun Ben-Gurion University

DOI:

https://doi.org/10.1609/aaai.v33i01.33012379

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.

Downloads

Published

2019-07-17

How to Cite

Shperberg, S. S., Felner, A., Sturtevant, N. R., Shimony, S. E., & Hayoun, A. (2019). Enriching Non-Parametric Bidirectional Search Algorithms. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 2379-2386. https://doi.org/10.1609/aaai.v33i01.33012379

Issue

Section

AAAI Technical Track: Heuristic Search and Optimization