Computer Science Speaking Skills Talk - CANCELLED

— 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.

Add event to Google
Add event to iCal