Anytime Motion Planning using the RRT*
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” algo...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers
2011
|
| Online Access: | http://hdl.handle.net/1721.1/63170 https://orcid.org/0000-0002-0505-1400 https://orcid.org/0000-0002-2225-7275 |
| _version_ | 1811076813220216832 |
|---|---|
| author | Karaman, Sertac Walter, Matthew R. Perez, Alejandro Frazzoli, Emilio Teller, Seth |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Karaman, Sertac Walter, Matthew R. Perez, Alejandro Frazzoli, Emilio Teller, Seth |
| author_sort | Karaman, Sertac |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T10:27:59Z |
| format | Article |
| id | mit-1721.1/63170 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:27:59Z |
| publishDate | 2011 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | mit-1721.1/631702022-09-27T09:38:39Z Anytime Motion Planning using the RRT* Karaman, Sertac Walter, Matthew R. Perez, Alejandro Frazzoli, Emilio Teller, Seth Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Teller, Seth Karaman, Sertac Walter, Matthew R. Frazzoli, Emilio Teller, Seth 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. United States. Army. Logistics Innovation Agency United States. Army Combined Arms Support Command United States. Dept. of the Air Force (Air Force Contract FA8721-05-C-0002) 2011-06-02T17:41:24Z 2011-06-02T17:41:24Z 2011-05 Article http://purl.org/eprint/type/ConferencePaper 2152-4092 http://hdl.handle.net/1721.1/63170 Karaman, Sertac et al. "Anytime Motion Planning using the RRT*." 2011 IEEE International Conference on Robotics and Automation (ICRA) May 9-13, 2011, Shanghai International Conference Center, Shanghai, China. https://orcid.org/0000-0002-0505-1400 https://orcid.org/0000-0002-2225-7275 en_US https://ras.papercept.net/conferences/scripts/abstract.pl?ConfID=34&Number=1887 IEEE International Conference on Robotics and Automation. ICRA 2011 Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Institute of Electrical and Electronics Engineers MIT web domain |
| spellingShingle | Karaman, Sertac Walter, Matthew R. Perez, Alejandro Frazzoli, Emilio Teller, Seth Anytime Motion Planning using the RRT* |
| title | Anytime Motion Planning using the RRT* |
| title_full | Anytime Motion Planning using the RRT* |
| title_fullStr | Anytime Motion Planning using the RRT* |
| title_full_unstemmed | Anytime Motion Planning using the RRT* |
| title_short | Anytime Motion Planning using the RRT* |
| title_sort | anytime motion planning using the rrt |
| url | http://hdl.handle.net/1721.1/63170 https://orcid.org/0000-0002-0505-1400 https://orcid.org/0000-0002-2225-7275 |
| work_keys_str_mv | AT karamansertac anytimemotionplanningusingtherrt AT waltermatthewr anytimemotionplanningusingtherrt AT perezalejandro anytimemotionplanningusingtherrt AT frazzoliemilio anytimemotionplanningusingtherrt AT tellerseth anytimemotionplanningusingtherrt |