            |
GRASP Seminar Series: Fall 2008
September 12th, 11:00 a.m., Wu and Chen Auditorium, Levine Hall (3330 Walnut Street)
Maxim Likhachev
University of Pennsylvania
"Solving Hard Planning Problems in Robotics with Simple Graph Searches "
Abstract: Graph-based searches, such as A* search, are highly popular means of planning due to their generality, solid theoretical ground and simplicity in the implementation. The type of planning problems they can usually solve in real-time, however, is limited to low-dimensional problems and problems that do not involve any uncertainty. Planning problems in robotics, on the other hand, frequently involve high-dimensional spaces, need to consider uncertainty and are nearly always done under time constraints. In this talk, I will present a series of algorithms we have recently developed that extend the applicability of graph-based searches to meet these requirements while maintaining the generality, theoretical ground and simplicity in the implementation.
In particular, in the first part of the talk, I will describe several novel versions of A* search we have developed suitable for higher-dimensional planning under time constraints and planning in dynamic and partially-known environments. These algorithms were used to solve a range of planning problems including motion planning for several kinds of articulated robots and planning dynamically constrained trajectories for various outdoor vehicles including a full-size SUV that has won DARPA Urban Challenge in 2007. In the second part of the talk, I will describe how graph-based searches can also be used to solve several kinds of planning under uncertainty problems. I will show how these seemingly very difficult non-deterministic planning problems can sometimes be solved by running a series of simple and fast deterministic A*-like searches. The resulting algorithms were used to solve large-scale POMDPs with hundreds of billions of states.
Biography: Maxim Likhachev is a research faculty at the Computer and Information Science department of University of Pennsylvania. His research interests are primarily in planning for deterministic and probabilistic domains with application to robotics. He develops planning methods that can be used in real-time, can be analyzed theoretically and are easy to use. Maxim has obtained Ph.D. in Computer Science from Carnegie Mellon University in 2005. He then had a 2-year Postdoctoral appointment at the Robotics Institute in Carnegie Mellon University. Maxim has numerous publications in AI and Robotics journals and major conferences and has applied his algorithms to such problems as high-speed robot navigation in unknown and adversarial environments, the DARPA Urban Challenge project, coordination of multi-agent systems and motion planning of high-degree of freedom articulated robots.
GRASP
Laboratory
Site maintained by graspadm@grasp.cis.upenn.edu
Last update:9 September, 2008