TOYOTA AI SEMINAR SERIES
        Department of Electrical Engineering and Computer Science
                 Stained-Glass Conference Room (3725 CSE)
                  4:00 - 5:30 PM Tuesday, October 23, 2007


  Real-Time Path Planning for Autonomous Driving in Unknown Environments

                                   by

                              Dmitri Dolgov

                        Senior Research Scientist
                         Toyota Technical Center


Abstract:

I will describe a real-time path-planning algorithm that generates
smooth paths for robotic cars in unknown environments (when no map is
available a priori, and the obstacles are incrementally detected by 
on-board sensors). This work is motivated, in part, by the upcoming
DARPA Urban Challenge (November 3, 2007), where autonomous vehicles
will be required---among other tasks---to navigate parking lots with
other cars present. 

The main challenges of path planning for autonomous cars are: i) the
design of a good cost function that trades off path length and
clearance to nearby obstacles; ii) the continuous and multi-modal
nature of the search space of possible paths; and iii) computational 
challenges associated with achieving real-time performance.

Our solution to the above challenges utilizes several techniques, the
main contributions of which are: i) a novel type of a potential field
that takes the geometry of the workspace into account to effectively 
repel the robot from obstacles without blocking off narrow passages,
ii) an extensions of A* search applied to the 3D kinematic state of
the vehicle that addresses the problem of continuous states and the
non-holonomic nature of the robot, and iii) a formulation and solution 
to a non-linear optimization problem for path smoothing.

I will present results obtained in experiments on a real robotic car,
Junior, which will compete for the Stanford Racing Team in the DARPA
Urban Challenge in November. 

Bio:
Dmitri Dolgov is a Senior Research Scientist at the AI & Robotics
group at the Toyota Technical Center in Ann Arbor and a Visiting
Researcher at the Stanford University. His current main research focus 
is on real-time decision making and prediction for robotic systems in
real-life environments. Dmitri got his PhD from the University of
Michigan AI lab in 2006 for his work on decision making under resource
constraints in stochastic multiagent systems.