Seminar by Dr. Robert Holte, U of A: Bidirectional Search that is Guaranteed to Meet in the Middle

Mon., May. 9, 2016 2:00 p.m.

Location: ED 193

Dr. Robert Holte, a collaborator of Dr. Sandra Zilles, will be visiting from the University of Alberta to give a special seminar presentation. He will be talking about his work (with co-authors Ariel Felner, Guni Sharon, and Nathan R. Sturtevant) that won the 2016 Outstanding Paper Award at a major conference.

Dr. Holte is a highly renowned researcher in Artificial Intelligence (AI) and an excellent speaker, who will give a keynote address at another major AI conference later this year.

The presentation will be aimed at a general Computer Science audience. No topic-specific background knowledge will be expected.

Abstract: In this talk I will 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. I also present a novel framework for comparing MM, A*, and brute-force search, and identify conditions favouring each algorithm. Our analysis reveals several fundamental differences between unidirectional search and bidirectional search. Finally, I present experimental results that support the conjectures arising from our analysis.