Continuous Tensor Train-Based Dynamic Programming for High-Dimensional Zero-Sum Differential Games
© 2018 AACC. Zero-sum differential games constitute a prominent research topic in several fields ranging from economics to motion planning. Unfortunately, analytical techniques for differential games can address only simple, illustrative problem instances, and most existing computational methods suf...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137851 |
| _version_ | 1826212089549553664 |
|---|---|
| author | Tal, Ezra Gorodetsky, Alex Karaman, Sertac |
| author2 | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics |
| author_facet | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Tal, Ezra Gorodetsky, Alex Karaman, Sertac |
| author_sort | Tal, Ezra |
| collection | MIT |
| description | © 2018 AACC. Zero-sum differential games constitute a prominent research topic in several fields ranging from economics to motion planning. Unfortunately, analytical techniques for differential games can address only simple, illustrative problem instances, and most existing computational methods suffer from the curse of dimensionality, i.e., the computational requirements grow exponentially with the dimensionality of the state space. In order to alleviate the curse of dimensionality for a certain class of two-player pursuit-evasion games, we propose a novel dynamic-programming-based algorithm that uses a continuous tensor-train approximation to represent the value function. In this way, the algorithm can represent high-dimensional tensors using computational resources that grow only polynomially with dimensionality of the state space and with the rank of the value function. The proposed algorithm is shown to converge to optimal solutions. It is demonstrated in several problem instances; in case of a seven-dimensional game, the value function representation was obtained with seven orders of magnitude savings in computational and memory cost, when compared to standard value iteration. |
| first_indexed | 2024-09-23T15:16:13Z |
| format | Article |
| id | mit-1721.1/137851 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T15:16:13Z |
| publishDate | 2021 |
| publisher | IEEE |
| record_format | dspace |
| spelling | mit-1721.1/1378512023-02-09T21:38:29Z Continuous Tensor Train-Based Dynamic Programming for High-Dimensional Zero-Sum Differential Games Tal, Ezra Gorodetsky, Alex Karaman, Sertac Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Massachusetts Institute of Technology. Laboratory for Information and Decision Systems © 2018 AACC. Zero-sum differential games constitute a prominent research topic in several fields ranging from economics to motion planning. Unfortunately, analytical techniques for differential games can address only simple, illustrative problem instances, and most existing computational methods suffer from the curse of dimensionality, i.e., the computational requirements grow exponentially with the dimensionality of the state space. In order to alleviate the curse of dimensionality for a certain class of two-player pursuit-evasion games, we propose a novel dynamic-programming-based algorithm that uses a continuous tensor-train approximation to represent the value function. In this way, the algorithm can represent high-dimensional tensors using computational resources that grow only polynomially with dimensionality of the state space and with the rank of the value function. The proposed algorithm is shown to converge to optimal solutions. It is demonstrated in several problem instances; in case of a seven-dimensional game, the value function representation was obtained with seven orders of magnitude savings in computational and memory cost, when compared to standard value iteration. 2021-11-09T13:15:12Z 2021-11-09T13:15:12Z 2018-06 2019-10-28T18:31:10Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/137851 Tal, Ezra, Gorodetsky, Alex and Karaman, Sertac. 2018. "Continuous Tensor Train-Based Dynamic Programming for High-Dimensional Zero-Sum Differential Games." en 10.23919/acc.2018.8431472 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf IEEE website |
| spellingShingle | Tal, Ezra Gorodetsky, Alex Karaman, Sertac Continuous Tensor Train-Based Dynamic Programming for High-Dimensional Zero-Sum Differential Games |
| title | Continuous Tensor Train-Based Dynamic Programming for High-Dimensional Zero-Sum Differential Games |
| title_full | Continuous Tensor Train-Based Dynamic Programming for High-Dimensional Zero-Sum Differential Games |
| title_fullStr | Continuous Tensor Train-Based Dynamic Programming for High-Dimensional Zero-Sum Differential Games |
| title_full_unstemmed | Continuous Tensor Train-Based Dynamic Programming for High-Dimensional Zero-Sum Differential Games |
| title_short | Continuous Tensor Train-Based Dynamic Programming for High-Dimensional Zero-Sum Differential Games |
| title_sort | continuous tensor train based dynamic programming for high dimensional zero sum differential games |
| url | https://hdl.handle.net/1721.1/137851 |
| work_keys_str_mv | AT talezra continuoustensortrainbaseddynamicprogrammingforhighdimensionalzerosumdifferentialgames AT gorodetskyalex continuoustensortrainbaseddynamicprogrammingforhighdimensionalzerosumdifferentialgames AT karamansertac continuoustensortrainbaseddynamicprogrammingforhighdimensionalzerosumdifferentialgames |