Anytime computation of time-optimal off-road vehicle maneuvers using the RRT*
Open Access
- 1 December 2011
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 8 (01912216), 3276-3282
- https://doi.org/10.1109/cdc.2011.6161521
Abstract
Incremental sampling-based motion planning algorithms such as the Rapidly-exploring Random Trees (RRTs) have been successful in efficiently solving computationally challenging motion planning problems involving complex dynamical systems. A recently proposed algorithm, called the RRT*, also provides asymptotic optimality guarantees, i.e., almost-sure convergence to optimal trajectories (which the RRT algorithm lacked) while maintaining the computational efficiency of the RRT algorithm. In this paper, time-optimal maneuvers for a high-speed off-road vehicle taking tight turns on a loose surface are studied using the RRT* algorithm. Our simulation results show that the aggressive skidding maneuver, usually called the trail-braking maneuver, naturally emerges from the RRT* algorithm as the minimum-time trajectory. Along the way, we extend the RRT* algorithm to handle complex dynamical systems, such as those that are described by nonlinear differential equations and involve high-dimensional state spaces, which may be of independent interest. We also exploit the RRT* as an anytime computation framework for nonlinear optimization problems.Keywords
This publication has 27 references indexed in Scilit:
- Sampling-based algorithms for optimal motion planningThe International Journal of Robotics Research, 2011
- Optimal kinodynamic motion planning using incremental sampling-based methodsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2010
- Path planning in 1000+ dimensions using a task-space Voronoi biasPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2009
- Incremental Search Methods for Reachability Analysis of Continuous and Hybrid SystemsLecture Notes in Computer Science, 2004
- Medical robotics in computer-integrated surgeryIEEE Transactions on Robotics and Automation, 2003
- Assembly maintainability study with motion planningPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Randomized Kinodynamic PlanningThe International Journal of Robotics Research, 2001
- Probabilistic roadmaps for path planning in high-dimensional configuration spacesIEEE Transactions on Robotics and Automation, 1996
- Complexity of the mover's problem and generalizationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- On Curves of Minimal Length with a Constraint on Average Curvature, and with Prescribed Initial and Terminal Positions and TangentsAmerican Journal of Mathematics, 1957