Alice: Path Planning
| 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
Reading
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.
Realtime Path Planning Via Nonlinear Optimization Methods, Dmitriy Kogan. MS Thesis, 2005. This thesis describes most of the internals of the path planning algorithm. It was written before some of the final tuning was performed on Alice (during summer of 2005).
