AAAI Publications, Twelfth Annual Symposium on Combinatorial Search

Font Size: 
A Theoretical Comparison of the Bounds of MM, NBS, and GBFHS
Vidal Alcazar, Mike Barley, Pat Riddle

Last modified: 2019-06-24


Recent work in bidirectional front-to-end heuristic search has led to the development of novel algorithms that have advanced the state of the art after many years without major developments. In particular, three different algorithms with very different behavior have been proposed: MM, NBS and GBFHS. In this paper we perform a theoretical comparison of these algorithms, defining lower and upper bounds for each of them and analyzing why a given algorithm displays beneficial characteristics that the others lack. With this information, we propose a simple and intuitive near-optimal algorithm to be used as a baseline for comparison in bidirectional front-to-end heuristic search.

Full Text: PDF