Bidirectional Search That Is Guaranteed to Meet in the Middle
- Robert Holte, Department of Computing Science, University of Alberta
- Ariel Felner, Information Systems Engineering, Ben-Gurion University, Israel
- Guni Sharon
- Nathan R. Sturtevant
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.
Citation
R. Holte, A. Felner, G. Sharon, N. Sturtevant. "Bidirectional Search That Is Guaranteed to Meet in the Middle". National Conference on Artificial Intelligence (AAAI), (ed: Dale Schuurmans, Michael P. Wellman), pp 3411-3417, February 2016.| Keywords: | |
| Category: | In Conference |
| Web Links: | AAAI |
BibTeX
@incollection{Holte+al:AAAI16,
author = {Robert Holte and Ariel Felner and Guni Sharon and Nathan R.
Sturtevant},
title = {Bidirectional Search That Is Guaranteed to Meet in the Middle},
Editor = {Dale Schuurmans, Michael P. Wellman},
Pages = {3411-3417},
booktitle = {National Conference on Artificial Intelligence (AAAI)},
year = 2016,
}Last Updated: July 05, 2020Submitted by Sabina P
