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.