AAAI

Association for the Advancement of Artificial Intelligence

Home > Proceedings / Proceedings of the International Symposium on Combinatorial Search, 12

Enriching Non-Parametric Bidirectional Search Algorithms — Extended Abstract

Authors

Shahaf Shperberg,Ariel Felner,Nathan Sturtevant,Solomon Shimony,Avi Hayoun

Ben-Gurion University of the Negev,Ben-Gurion University of the Negev,University of Alberta,Ben-Gurion University of the Negev,Ben-Gurion University of the Negev


Proceedings:

Proceedings of the International Symposium on Combinatorial Search, 12

Volume

Issue:

Vol. 12 No. 1 (2019): Twelfth Annual Symposium on Combinatorial Search

Track:

Extended Abstracts

Downloads:

Download PDF

Abstract:

NBS is a non-parametric bidirectional search algorithm, proved 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.

DOI:

10.1609/socs.v10i1.18488


SOCS

Vol. 12 No. 1 (2019): Twelfth Annual Symposium on Combinatorial Search