High-dimensional stochastic optimal control using continuous tensor decompositions
Motion planning and control problems are embedded and essential in almost all robotics applications. These problems are often formulated as stochastic optimal control problems and solved using dynamic programming algorithms. Unfortunately, most existing algorithms that guarantee convergence to optim...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Published: |
SAGE Publications
2019
|
| Online Access: | http://hdl.handle.net/1721.1/120322 https://orcid.org/0000-0003-3152-8206 https://orcid.org/0000-0002-2225-7275 https://orcid.org/0000-0001-8242-3290 |
| _version_ | 1811091109093310464 |
|---|---|
| author | Gorodetsky, Alex Arkady Karaman, Sertac Marzouk, Youssef M |
| author2 | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics |
| author_facet | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Gorodetsky, Alex Arkady Karaman, Sertac Marzouk, Youssef M |
| author_sort | Gorodetsky, Alex Arkady |
| collection | MIT |
| description | Motion planning and control problems are embedded and essential in almost all robotics applications. These problems are often formulated as stochastic optimal control problems and solved using dynamic programming algorithms. Unfortunately, most existing algorithms that guarantee convergence to optimal solutions suffer from the curse of dimensionality: the run time of the algorithm grows exponentially with the dimension of the state space of the system. We propose novel dynamic programming algorithms that alleviate the curse of dimensionality in problems that exhibit certain low-rank structure. The proposed algorithms are based on continuous tensor decompositions recently developed by the authors. Essentially, the algorithms represent high-dimensional functions (e.g. the value function) in a compressed format, and directly perform dynamic programming computations (e.g. value iteration, policy iteration) in this format. Under certain technical assumptions, the new algorithms guarantee convergence towards optimal solutions with arbitrary precision. Furthermore, the run times of the new algorithms scale polynomially with the state dimension and polynomially with the ranks of the value function. This approach realizes substantial computational savings in “compressible” problem instances, where value functions admit low-rank approximations. We demonstrate the new algorithms in a wide range of problems, including a simulated six-dimensional agile quadcopter maneuvering example and a seven-dimensional aircraft perching example. In some of these examples, we estimate computational savings of up to 10 orders of magnitude over standard value iteration algorithms. We further demonstrate the algorithms running in real time on board a quadcopter during a flight experiment under motion capture. Keywords: Stochastic optimal control; motion planning; dynamic programming; tensor decompositions |
| first_indexed | 2024-09-23T14:57:10Z |
| format | Article |
| id | mit-1721.1/120322 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T14:57:10Z |
| publishDate | 2019 |
| publisher | SAGE Publications |
| record_format | dspace |
| spelling | mit-1721.1/1203222022-10-01T23:33:14Z High-dimensional stochastic optimal control using continuous tensor decompositions Gorodetsky, Alex Arkady Karaman, Sertac Marzouk, Youssef M Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Massachusetts Institute of Technology. Department of Mechanical Engineering Gorodetsky, Alex Arkady Karaman, Sertac Marzouk, Youssef M Motion planning and control problems are embedded and essential in almost all robotics applications. These problems are often formulated as stochastic optimal control problems and solved using dynamic programming algorithms. Unfortunately, most existing algorithms that guarantee convergence to optimal solutions suffer from the curse of dimensionality: the run time of the algorithm grows exponentially with the dimension of the state space of the system. We propose novel dynamic programming algorithms that alleviate the curse of dimensionality in problems that exhibit certain low-rank structure. The proposed algorithms are based on continuous tensor decompositions recently developed by the authors. Essentially, the algorithms represent high-dimensional functions (e.g. the value function) in a compressed format, and directly perform dynamic programming computations (e.g. value iteration, policy iteration) in this format. Under certain technical assumptions, the new algorithms guarantee convergence towards optimal solutions with arbitrary precision. Furthermore, the run times of the new algorithms scale polynomially with the state dimension and polynomially with the ranks of the value function. This approach realizes substantial computational savings in “compressible” problem instances, where value functions admit low-rank approximations. We demonstrate the new algorithms in a wide range of problems, including a simulated six-dimensional agile quadcopter maneuvering example and a seven-dimensional aircraft perching example. In some of these examples, we estimate computational savings of up to 10 orders of magnitude over standard value iteration algorithms. We further demonstrate the algorithms running in real time on board a quadcopter during a flight experiment under motion capture. Keywords: Stochastic optimal control; motion planning; dynamic programming; tensor decompositions National Science Foundation (U.S.) (Grant IIS-1452019) United States. Department of Energy (Award DE-SC0007099) 2019-02-11T16:39:16Z 2019-02-11T16:39:16Z 2018-02 2018-03 2019-02-01T14:28:32Z Article http://purl.org/eprint/type/JournalArticle 0278-3649 1741-3176 http://hdl.handle.net/1721.1/120322 Gorodetsky, Alex et al. “High-Dimensional Stochastic Optimal Control Using Continuous Tensor Decompositions.” The International Journal of Robotics Research 37, 2–3 (February 2018): 340–377 © 2018 The Author(s) https://orcid.org/0000-0003-3152-8206 https://orcid.org/0000-0002-2225-7275 https://orcid.org/0000-0001-8242-3290 http://dx.doi.org/10.1177/0278364917753994 International Journal of Robotics Research Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf SAGE Publications arXiv |
| spellingShingle | Gorodetsky, Alex Arkady Karaman, Sertac Marzouk, Youssef M High-dimensional stochastic optimal control using continuous tensor decompositions |
| title | High-dimensional stochastic optimal control using continuous tensor decompositions |
| title_full | High-dimensional stochastic optimal control using continuous tensor decompositions |
| title_fullStr | High-dimensional stochastic optimal control using continuous tensor decompositions |
| title_full_unstemmed | High-dimensional stochastic optimal control using continuous tensor decompositions |
| title_short | High-dimensional stochastic optimal control using continuous tensor decompositions |
| title_sort | high dimensional stochastic optimal control using continuous tensor decompositions |
| url | http://hdl.handle.net/1721.1/120322 https://orcid.org/0000-0003-3152-8206 https://orcid.org/0000-0002-2225-7275 https://orcid.org/0000-0001-8242-3290 |
| work_keys_str_mv | AT gorodetskyalexarkady highdimensionalstochasticoptimalcontrolusingcontinuoustensordecompositions AT karamansertac highdimensionalstochasticoptimalcontrolusingcontinuoustensordecompositions AT marzoukyoussefm highdimensionalstochasticoptimalcontrolusingcontinuoustensordecompositions |