Alice: Path Planning

From Murray Wiki
Jump to navigationJump to search
Prev: RHC Course Home Next: Kalman Filtering

Vehicle navigation through unstructured and previously unknown terrain is a challenging problem in autonomous robotics. This lecture describes the vehicle navigation algorithm used for Alice, Caltech's entry in the 2005 DARPA Grand Challenge. An optimization problem is continually solved to find a time-optimal, dynamically feasible trajectory from the vehicle’s position to some receding horizon ahead (20m-70m forward). The optimization is performed in two stages, one seeding the other. First, a rough, globally optimal spatial path is found by evaluating sets of piecewise linear curves through the map. Then the locally optimal nonlinear optimizer is run, optimizing both the spatial and temporal components of the trajectory simultaneously.

Lecture Materials


  • Realtime Path Planning Via Nonlinear Optimization Methods, Dmitriy Kogan and Richard Murray. To be submitted, IEEE T. Robotics, 2006. This paper describes Alice's path planner in a fair bit of detail, including the latest results of the optimizations that were performed and data taken from the grand challenge events.

Additional Resources