Bidirectional Search That Is Guaranteed to Meet in the Middle Conference Paper uri icon

abstract

  • 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.

published proceedings

  • Proceedings of the AAAI Conference on Artificial Intelligence

author list (cited authors)

  • Holte, R., Felner, A., Sharon, G., & Sturtevant, N.

citation count

  • 8

complete list of authors

  • Holte, Robert||Felner, Ariel||Sharon, Guni||Sturtevant, Nathan

publication date

  • January 2016