Monday, May 2, 2016 - 12:00pm to 1:00pm
Location:2109 Gates & Hillman Centers
Speaker:ARAM EBTEKAR, Ph.D. Student http://www.cs.cmu.edu/~aebtekar/
The A* algorithm aims to balance depth-first (greedy) and breadth-first (Dijkstra) search to quickly find an approximate shortest path in a graph. While its runtime will depend on choosing a good heuristic suitable to the domain's structure, we can under mild conditions guarantee that each state is expanded at most once, and that a solution will be found to within a configurable optimality factor. In this talk, we explore these conditions in great generality, leading to a framework that encapsulates a family of known search algorithms. Some of these algorithms provide additional benefits, such as anytime solution bound improvement, dynamic path repair, multi-core processing, and the use of multiple inadmissible heuristics. Using this framework, we can better understand existing algorithms, mix and match their features in a modular fashion, and design new variants with the same theoretical guarantees. In particular, we present ePA*SE, an efficient parallel version of A*.
Presented in Partial Fulfillment of the CSD Speaking Skills Requirement.