Comparing Front-to-Front and Front-to-End Heuristics in Bidirectional Search


  • Lior Siag Ben-Gurion University of the Negev
  • Shahaf Shperberg Ben-Gurion University of the Negev
  • Ariel Felner Ben-Gurion University of the Negev
  • Nathan R. Sturtevant University of Alberta Alberta Machine Intelligence Institute (Amii)



Analysis Of Search Algorithms, Time, Memory, And Solution Quality Trade-offs


Most recent theoretical and algorithmic work in bidirectional heuristic search (BiHS) used front-to-end (F2E) heuristics that estimate the distance to the start and goal states. In this paper, we start exploring front-to-front (F2F) heuristics, which estimate the distance between any pair of states. Devising efficient algorithms that use F2F heuristics is a challenging task. Thus, it is important to first understand the benefits of using F2F heuristics compared to F2E heuristics. To this end, we theoretically and experimentally demonstrate that there is a great potential in using F2F heuristics implying that F2F BiHS is a promising area of future research.