AAAI

Association for the Advancement of Artificial Intelligence

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

Single-Frontier Bidirectional Search

Authors

Carsten Moldenhauer,Ariel Felner,Nathan Sturtevant,Jonathan Schaeffer

Universitat zu Berlin,Ben-Gurion University,University of Alberta,University of Alberta


Proceedings:

Proceedings of the International Symposium on Combinatorial Search, 3

Volume

Issue:

Vol. 3 No. 1 (2010): Third Annual Symposium on Combinatorial Search

Track:

Abstracts from Other Conference Papers

Downloads:

Download PDF

Abstract:

We introduce a new bidirectional search algorithm, Single-Frontier Bidirectional Search (SFBDS). Unlike traditional BDS which keeps two frontiers, SFBDS uses a single frontier. At a particular node we can decide to search from start to goal or from goal to start, choosing the direction with the highest potential for minimizing the total work done. We provide theoretical analysis that explains when SFBDS will work validated by experimental results.

DOI:

10.1609/socs.v1i1.18153


SOCS

Vol. 3 No. 1 (2010): Third Annual Symposium on Combinatorial Search