AAAI Publications, Thirtieth AAAI Conference on Artificial Intelligence

Font Size: 
Bidirectional Search That Is Guaranteed to Meet in the Middle
Robert C. Holte, Ariel Felner, Guni Sharon, Nathan R. Sturtevant

Last modified: 2016-03-05

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.

Keywords


Artificial Intelligence; Heuristic Search

Full Text: PDF