Single-Frontier Bidirectional Search

Authors

  • Carsten Moldenhauer Universitat zu Berlin
  • Ariel Felner Ben-Gurion University
  • Nathan Sturtevant University of Alberta
  • Jonathan Schaeffer University of Alberta

DOI:

https://doi.org/10.1609/socs.v1i1.18153

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.

Downloads

Published

2010-08-25

Issue

Section

Abstracts from Other Conference Papers