Not Logged In

MM: A Bidirectional Search That Is Guaranteed to Meet in the Middle

Full Text: holte2017mm.pdf PDF

Bidirectional search algorithms interleave two separate searches, a normal search forward from the start state, and a search backward from the goal. It is well known that adding a heuristic to unidirectional search dramatically reduces the search effort. By contrast, despite decades of research, bidirectional heuristic search has not yet had a major impact. Additionally, no comprehensive theory was ever devised to understand the nature of bidirectional heuristic search. In this paper we aim to close this gap. We first present MM, a novel bidirectional heuristic search algorithm. Unlike previous bidirectional heuristic search algorithms, MM's forward and backward searches are guaranteed to "meet in the middle", i.e. never expand a node beyond the solution midpoint. Based on this unique attribute we present a novel framework for comparing MM, A*, and their brute-force variants. We do this by dividing the entire state-space into disjoint regions based on their distance from the start and goal. This allows us to perform a comparison of these algorithms on a per region basis 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, J. Chen. "MM: A Bidirectional Search That Is Guaranteed to Meet in the Middle". Artificial Intelligence (AIJ), 252, pp 232-266, August 2017.

Keywords: Heuristic search, Bidirectional search
Category: In Journal
Web Links: doi
  Elsevier

BibTeX

@article{Holte+al:AIJ17,
  author = {Robert Holte and Ariel Felner and Guni Sharon and Nathan R.
    Sturtevant and Jingwei Chen},
  title = {MM: A Bidirectional Search That Is Guaranteed to Meet in the Middle},
  Volume = "252",
  Pages = {232-266},
  journal = {Artificial Intelligence (AIJ)},
  year = 2017,
}

Last Updated: July 05, 2020
Submitted by Sabina P

University of Alberta Logo AICML Logo