Anytime Motion Planning using the RRT*
Top Cited Papers
Open Access
- 1 May 2011
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10504729,p. 1478-1483
- https://doi.org/10.1109/icra.2011.5980479
Abstract
The Rapidly-exploring Random Tree (RRT) algorithm, based on incremental sampling, efficiently computes motion plans. Although the RRT algorithm quickly produces candidate feasible solutions, it tends to converge to a solution that is far from optimal. Practical applications favor "anytime" algorithms that quickly identify an initial feasible plan, then, given more computation time available during plan execution, improve the plan toward an optimal solution. This paper describes an anytime algorithm based on the RRT* which (like the RRT) finds an initial feasible solution quickly, but (unlike the RRT) almost surely converges to an optimal solution. We present two key extensions to the RRT% committed trajectories and branch-and-bound tree adaptation, that together enable the algorithm to make more efficient use of computation time online, resulting in an anytime algorithm for real-time implementation. We evaluate the method using a series of Monte Carlo runs in a high-fidelity simulation environment, and compare the operation of the RRT and RRT* methods. We also demonstrate experimental results for an outdoor wheeled robotic vehicle.Keywords
This publication has 12 references indexed in Scilit:
- Optimal kinodynamic motion planning using incremental sampling-based methodsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2010
- A voice-commandable robotic forklift working alongside humans in minimally-prepared outdoor environmentsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2010
- Multimodal interaction with an autonomous forkliftPublished by Association for Computing Machinery (ACM) ,2010
- Anytime search in dynamic graphsArtificial Intelligence, 2008
- Stanley: The robot that won the DARPA Grand ChallengeJournal of Field Robotics, 2006
- Sampling-based planning, control and verification of hybrid systemsIEE Proceedings - Control Theory and Applications, 2006
- 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
- On Curves of Minimal Length with a Constraint on Average Curvature, and with Prescribed Initial and Terminal Positions and TangentsAmerican Journal of Mathematics, 1957