Bidirectional Search That Is Guaranteed to Meet in the Middle

We present MM, the first bidirectional heuristic search algorithm whose forward and backward searches are guaranteed to ''meet in the middle'', i.e. never expand a node beyond the solution midpoint. We also present a novel framework for comparing MM, A*, and brute-force search, and identify conditions favoring each algorithm. Finally, we present experimental results that support our theoretical analysis.

Acknowledgements

Thanks to Joseph Barker for answering questions and providing extra data related to (Barker and Korf 2015) and to Sandra Zilles and Andre Grahl Pereira for suggesting im- ´ provements in the theoretical analysis of MM. Financial support for this research was in part provided by Canada’s Natural Science and Engineering Research Council (NSERC) and by Israel Science Foundation (ISF) grant #417/13. Computational facilities for some of our experiments were provided by Compute Canada. This material is based upon work supported by the National Science Foundation under Grant No. 1551406.