A Quadratic Regulator-Based Heuristic for Rapidly Exploring State Space
Kinodynamic planning algorithms like Rapidly-Exploring Randomized Trees (RRTs) hold the promise of finding feasible trajectories for rich dynamical systems with complex, nonconvex constraints. In practice, these algorithms perform very well on configuration space planning, but struggle to grow effic...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2012
|
| Online Access: | http://hdl.handle.net/1721.1/73534 https://orcid.org/0000-0001-5178-3496 https://orcid.org/0000-0002-8712-7092 |
| _version_ | 1826217760083935232 |
|---|---|
| author | Glassman, Elena L. Tedrake, Russell Louis |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Glassman, Elena L. Tedrake, Russell Louis |
| author_sort | Glassman, Elena L. |
| collection | MIT |
| description | Kinodynamic planning algorithms like Rapidly-Exploring Randomized Trees (RRTs) hold the promise of finding feasible trajectories for rich dynamical systems with complex, nonconvex constraints. In practice, these algorithms perform very well on configuration space planning, but struggle to grow efficiently in systems with dynamics or differential constraints. This is due in part to the fact that the conventional distance metric, Euclidean distance, does not take into account system dynamics and constraints when identifying which node in the existing tree is capable of producing children closest to a given point in state space. We show that an affine quadratic regulator (AQR) design can be used to approximate the exact minimum-time distance pseudometric at a reasonable computational cost. We demonstrate improved exploration of the state spaces of the double integrator and simple pendulum when using this pseudometric within the RRT framework, but this improvement drops off as systems' nonlinearity and complexity increase. Future work includes exploring methods for approximating the exact minimum-time distance pseudometric that can reason about dynamics with higher-order terms. |
| first_indexed | 2024-09-23T17:08:42Z |
| format | Article |
| id | mit-1721.1/73534 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T17:08:42Z |
| publishDate | 2012 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/735342022-09-29T23:57:50Z A Quadratic Regulator-Based Heuristic for Rapidly Exploring State Space Glassman, Elena L. Tedrake, Russell Louis Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Glassman, Elena L. Tedrake, Russell Louis Kinodynamic planning algorithms like Rapidly-Exploring Randomized Trees (RRTs) hold the promise of finding feasible trajectories for rich dynamical systems with complex, nonconvex constraints. In practice, these algorithms perform very well on configuration space planning, but struggle to grow efficiently in systems with dynamics or differential constraints. This is due in part to the fact that the conventional distance metric, Euclidean distance, does not take into account system dynamics and constraints when identifying which node in the existing tree is capable of producing children closest to a given point in state space. We show that an affine quadratic regulator (AQR) design can be used to approximate the exact minimum-time distance pseudometric at a reasonable computational cost. We demonstrate improved exploration of the state spaces of the double integrator and simple pendulum when using this pseudometric within the RRT framework, but this improvement drops off as systems' nonlinearity and complexity increase. Future work includes exploring methods for approximating the exact minimum-time distance pseudometric that can reason about dynamics with higher-order terms. 2012-10-02T13:06:04Z 2012-10-02T13:06:04Z 2010-07 2010-05 Article http://purl.org/eprint/type/ConferencePaper 978-1-4244-5040-4 978-1-4244-5038-1 1050-4729 http://hdl.handle.net/1721.1/73534 Glassman, Elena, and Russ Tedrake. “A Quadratic Regulator-based Heuristic for Rapidly Exploring State Space.” IEEE International Conference on Robotics and Automation (ICRA), 2010. 5021–5028. © Copyright 2010 IEEE https://orcid.org/0000-0001-5178-3496 https://orcid.org/0000-0002-8712-7092 en_US http://dx.doi.org/10.1109/ROBOT.2010.5509718 Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), 2010 Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Institute of Electrical and Electronics Engineers (IEEE) IEEE |
| spellingShingle | Glassman, Elena L. Tedrake, Russell Louis A Quadratic Regulator-Based Heuristic for Rapidly Exploring State Space |
| title | A Quadratic Regulator-Based Heuristic for Rapidly Exploring State Space |
| title_full | A Quadratic Regulator-Based Heuristic for Rapidly Exploring State Space |
| title_fullStr | A Quadratic Regulator-Based Heuristic for Rapidly Exploring State Space |
| title_full_unstemmed | A Quadratic Regulator-Based Heuristic for Rapidly Exploring State Space |
| title_short | A Quadratic Regulator-Based Heuristic for Rapidly Exploring State Space |
| title_sort | quadratic regulator based heuristic for rapidly exploring state space |
| url | http://hdl.handle.net/1721.1/73534 https://orcid.org/0000-0001-5178-3496 https://orcid.org/0000-0002-8712-7092 |
| work_keys_str_mv | AT glassmanelenal aquadraticregulatorbasedheuristicforrapidlyexploringstatespace AT tedrakerusselllouis aquadraticregulatorbasedheuristicforrapidlyexploringstatespace AT glassmanelenal quadraticregulatorbasedheuristicforrapidlyexploringstatespace AT tedrakerusselllouis quadraticregulatorbasedheuristicforrapidlyexploringstatespace |