Optimal kinodynamic motion planning using incremental sampling-based methods
Top Cited Papers
- 1 December 2010
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 01912216,p. 7681-7687
- https://doi.org/10.1109/cdc.2010.5717430
Abstract
Sampling-based algorithms such as the Rapidly-exploring Random Tree (RRT) have been recently proposed as an effective approach to computationally hard motion planning problem. However, while the RRT algorithm is known to be able to find a feasible solution quickly, there are no guarantees on the quality of such solution, e.g., with respect to a given cost functional. To address this limitation, the authors recently proposed a new algorithm, called RRT*, which ensures asymptotic optimality, i.e., almost sure convergence of the solution returned by the algorithm to an optimal solution, while maintaining the same properties of the standard RRT algorithm, both in terms of computation of feasible solutions, and of computational complexity. In this paper, the RRT* algorithm is extended to deal with differential constraints. A sufficient condition for asymptotic optimality is provided. It is shown that the RRT* algorithm equipped with any local steering procedure that satisfies this condition converges to an optimal solution almost surely. In particular, simple local steering procedures are provided for a Dubins' vehicle as well as a double integrator. Simulation examples are also provided for these systems comparing the RRT and the RRT* algorithms.Keywords
This publication has 17 references indexed in Scilit:
- Planning Long Dynamically Feasible Maneuvers for Autonomous VehiclesThe International Journal of Robotics Research, 2009
- Motion Planning Under Uncertainty for Image-guided Medical Needle SteeringThe International Journal of Robotics Research, 2008
- Real-Time Randomized Path Planning for Robot NavigationLecture Notes in Computer Science, 2003
- Real-Time Motion Planning for Agile Autonomous VehiclesJournal of Guidance, Control, and Dynamics, 2002
- Randomized Kinodynamic PlanningThe International Journal of Robotics Research, 2001
- Motion Planning: A Journey of Robots, Molecules, Digital Actors, and Other ArtifactsThe International Journal of Robotics Research, 1999
- Probabilistic roadmaps for path planning in high-dimensional configuration spacesIEEE Transactions on Robotics and Automation, 1996
- Real-Time Obstacle Avoidance for Manipulators and Mobile RobotsThe International Journal of Robotics Research, 1986
- Nonlinear controllability and observabilityIEEE Transactions on Automatic Control, 1977
- On Curves of Minimal Length with a Constraint on Average Curvature, and with Prescribed Initial and Terminal Positions and TangentsAmerican Journal of Mathematics, 1957