Not Logged In

Enriching Non-Parametric Bidirectional Search Algorithms

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.

Citation

S. Shperberg, A. Felner, N. Sturtevant, S. Shimony, A. Hayoun. "Enriching Non-Parametric Bidirectional Search Algorithms". National Conference on Artificial Intelligence (AAAI), pp 2379-2386, January 2019.

Keywords:  
Category: In Conference
Web Links: AAAI
  doi

BibTeX

@incollection{Shperberg+al:AAAI19,
  author = {Shahaf S. Shperberg and Ariel Felner and Nathan R. Sturtevant and
    Solomon Eyal Shimony and Avi Hayoun},
  title = {Enriching Non-Parametric Bidirectional Search Algorithms},
  Pages = {2379-2386},
  booktitle = {National Conference on Artificial Intelligence (AAAI)},
  year = 2019,
}

Last Updated: July 03, 2020
Submitted by Sabina P

University of Alberta Logo AICML Logo