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

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.

authors

• Sharon, Guni

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

publisher

• Association for the Advancement of Artificial Intelligence (AAAI)  Publisher

published in

• Proceedings of the ... AAAI Conference on Artificial Intelligence. AAAI Conference on Artificial Intelligence  Journal

keywords

• 46 Information And Computing Sciences
• 4605 Data Management And Data Science

Digital Object Identifier (DOI)

• 10.1609/aaai.v30i1.10436

International Standard Book Number (ISBN) 13

• 9781577357605

start page

• 3411

end page

• 3417

volume

• 30

issue

• 1

URL

• http://dx.doi.org/10.1609/aaai.v30i1.10436