LQR-RRT*: Optimal sampling-based motion planning with automatically derived extension heuristics
The RRT* algorithm has recently been proposed as an optimal extension to the standard RRT algorithm [1]. However, like RRT, RRT* is difficult to apply in problems with complicated or underactuated dynamics because it requires the design of a two domain-specific extension heuristics: a distance metri...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2014
|
| Online Access: | http://hdl.handle.net/1721.1/87036 https://orcid.org/0000-0001-6365-6937 https://orcid.org/0000-0002-8657-2450 https://orcid.org/0000-0001-6054-7145 |
| _version_ | 1826207801460916224 |
|---|---|
| author | Perez, Alejandro Platt, Robert Konidaris, George Lozano-Perez, Tomas Kaelbling, Leslie P. |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Perez, Alejandro Platt, Robert Konidaris, George Lozano-Perez, Tomas Kaelbling, Leslie P. |
| author_sort | Perez, Alejandro |
| collection | MIT |
| description | The RRT* algorithm has recently been proposed as an optimal extension to the standard RRT algorithm [1]. However, like RRT, RRT* is difficult to apply in problems with complicated or underactuated dynamics because it requires the design of a two domain-specific extension heuristics: a distance metric and node extension method. We propose automatically deriving these two heuristics for RRT* by locally linearizing the domain dynamics and applying linear quadratic regulation (LQR). The resulting algorithm, LQR-RRT*, finds optimal plans in domains with complex or underactuated dynamics without requiring domain-specific design choices. We demonstrate its application in domains that are successively torque-limited, underactuated, and in belief space. |
| first_indexed | 2024-09-23T13:55:10Z |
| format | Article |
| id | mit-1721.1/87036 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:55:10Z |
| publishDate | 2014 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/870362022-10-01T17:58:32Z LQR-RRT*: Optimal sampling-based motion planning with automatically derived extension heuristics Perez, Alejandro Platt, Robert Konidaris, George Lozano-Perez, Tomas Kaelbling, Leslie P. Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Perez, Alejandro Platt, Robert Konidaris, George Kaelbling, Leslie P. Lozano-Perez, Tomas The RRT* algorithm has recently been proposed as an optimal extension to the standard RRT algorithm [1]. However, like RRT, RRT* is difficult to apply in problems with complicated or underactuated dynamics because it requires the design of a two domain-specific extension heuristics: a distance metric and node extension method. We propose automatically deriving these two heuristics for RRT* by locally linearizing the domain dynamics and applying linear quadratic regulation (LQR). The resulting algorithm, LQR-RRT*, finds optimal plans in domains with complex or underactuated dynamics without requiring domain-specific design choices. We demonstrate its application in domains that are successively torque-limited, underactuated, and in belief space. National Science Foundation (U.S.) (Grant 019868) United States. Office of Naval Research. Multidisciplinary University Research Initiative (Grant N00014-09-1-1051) United States. Air Force Office of Scientific Research (Grant AOARD-104135) 2014-05-16T17:38:25Z 2014-05-16T17:38:25Z 2012-05 Article http://purl.org/eprint/type/ConferencePaper 978-1-4673-1405-3 978-1-4673-1403-9 978-1-4673-1578-4 978-1-4673-1404-6 http://hdl.handle.net/1721.1/87036 Perez, Alejandro, Robert Platt, George Konidaris, Leslie Kaelbling, and Tomas Lozano-Perez. “LQR-RRT*: Optimal Sampling-Based Motion Planning with Automatically Derived Extension Heuristics.” 2012 IEEE International Conference on Robotics and Automation (n.d.). https://orcid.org/0000-0001-6365-6937 https://orcid.org/0000-0002-8657-2450 https://orcid.org/0000-0001-6054-7145 en_US http://dx.doi.org/10.1109/ICRA.2012.6225177 Proceedings of the 2012 IEEE International Conference on Robotics and Automation Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) MIT web domain |
| spellingShingle | Perez, Alejandro Platt, Robert Konidaris, George Lozano-Perez, Tomas Kaelbling, Leslie P. LQR-RRT*: Optimal sampling-based motion planning with automatically derived extension heuristics |
| title | LQR-RRT*: Optimal sampling-based motion planning with automatically derived extension heuristics |
| title_full | LQR-RRT*: Optimal sampling-based motion planning with automatically derived extension heuristics |
| title_fullStr | LQR-RRT*: Optimal sampling-based motion planning with automatically derived extension heuristics |
| title_full_unstemmed | LQR-RRT*: Optimal sampling-based motion planning with automatically derived extension heuristics |
| title_short | LQR-RRT*: Optimal sampling-based motion planning with automatically derived extension heuristics |
| title_sort | lqr rrt optimal sampling based motion planning with automatically derived extension heuristics |
| url | http://hdl.handle.net/1721.1/87036 https://orcid.org/0000-0001-6365-6937 https://orcid.org/0000-0002-8657-2450 https://orcid.org/0000-0001-6054-7145 |
| work_keys_str_mv | AT perezalejandro lqrrrtoptimalsamplingbasedmotionplanningwithautomaticallyderivedextensionheuristics AT plattrobert lqrrrtoptimalsamplingbasedmotionplanningwithautomaticallyderivedextensionheuristics AT konidarisgeorge lqrrrtoptimalsamplingbasedmotionplanningwithautomaticallyderivedextensionheuristics AT lozanopereztomas lqrrrtoptimalsamplingbasedmotionplanningwithautomaticallyderivedextensionheuristics AT kaelblinglesliep lqrrrtoptimalsamplingbasedmotionplanningwithautomaticallyderivedextensionheuristics |