"Anytime Motion Planning Using the RRT*"
Matthew WalterResearch Scientist
Computer Science and Artificial Intelligence Laboratory
Massachusetts Institute of Technology
The following documents the presentation of our work in optimal motion planning at the 2011 ICRA Conference in Shanghai, China. We describe an algorithm based upon the RRT* that exhibits the desired anytime properties: It quickly finds an initial feasible solution and exploits the time available while the vehicle executes the trajectory to improve the solution towards one that is optimal.
Karaman, S., Walter, M.R., Perez, A., Frazzoli, E., and Teller, S.,
Anytime Motion Planning Using the RRT*. Proceedings
of the IEEE International Conference on Robotics and Automation
(ICRA), Shanghai, China, May 2011.
[bibtex] [pdf]
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.
Slides
Media
(2009_02_agile_rrt.mp4)
[mp4 (h264, 12MB)]
This video demonstrates the use of a closed-loop RRT to plan collision free trajectories for a robotic forklift. The planner is closed-loop in that it searches over inputs to a stabilizing controller rather than the configuration space of the robot.
(2007_11_duc_25_mph)
[mp4 (h264, 21MB)]
This video demonstrates the use of a closed-loop RRT to plan collision free trajectories for MIT's DARPA Urban Challenge vehicle as it drives at speeds upwards of 40 kph. The planner is closed-loop in that it searches over inputs to a stabilizing controller rather than the configuration space of the robot.
(2011_05_10_icra_rrt)
[mp4 (h264, 2MB)]
A simulation of an RRT planning an obstacle-free trajectory for a single integrator in two dimensions.
(2011_05_10_icra_rrtstar)
[mp4 (h264, 4MB)]
A simulation of the RRT* algorithm planning an obstacle-free trajectory for a single integrator in two dimensions.
(2011_02_pr2_12dof_rrt)
[mp4 (h264, 6MB)]
A typical solution identified by the RRT tasked with finding path for the two arms of the PR2 (12DOF) from an initial pose underneath the table to a pre-grasp pose above the table. Note that no smoothing was employed. Due to the slow execution (not planning) time, the video is sped up by a factor of 2.
(2011_02_pr2_12dof_rrbtstar)
[mp4 (h264, 5MB)]
Our recent work extends our anytime algorithm to motion planning in higher dimensions. This video demonstrates the application to pre-grasp manipulation planning for the PR2. The algorithm quickly finds an initial solution that is more efficient than that of the RRT and exploits remaining time to improve the trajectories. A discussion of this work is currently under review for the 2011 IROS conference. Due to the slow execution (not planning) time, the video is sped up by a factor of 2.
(2010_06_agile_rrt)
[mp4 (h264, 12MB)]
A visualization of our robotic forklift attempting to plan a feasible trajectory online. Due to errors in the sensor pose calibration, the perception algorithm frequently hallucinates obstacles that lie along the current committed trajectory. This planner responds by choosing a different trajectory from the RRT tree or, when necessary, destroying ("trashing") the tree and planning anew. A more effective approach would be to reason over obstacle likelihoods (e.g., via an obstacle grid) and to identify trajectories for which the likelihood of collision is below a predefined threshold.
(2011_04_constraint_optimization)
[mp4 (h264, 6MB)]
Our current work focuses on solving for optimal trajectories within uncertain environments. In particular, we pose the problem as a multi-objective optimization in which the goal is to identify the lowest-cost trajectory that satisfies constraints on collision likelihood. This work is in joint collaboration with Adam Bry and Nick Roy and builds upon their Rapidly-exploring Random Belief Tree (pdf) work. This video demonstrates the result of employing our algorithm in a simulated environment in which the obstacle likelihoods change over time. Darker shades denote higher likelihoods. By searching over the space of trajectories, the algorithm identifies the current best solution that satisfies the chance constraints.
Last Modified: February 21, 2013
