A tensor-train-decomposition-based algorithm for high-dimensional pursuit-evasion games
Thesis: S.M., Massachusetts Institute of Technology, Department of Aeronautics and Astronautics, 2016.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2016
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/105615 |
| _version_ | 1826199300887019520 |
|---|---|
| author | Grimm, Christopher Lee, Jr |
| author2 | Sertac Karaman. |
| author_facet | Sertac Karaman. Grimm, Christopher Lee, Jr |
| author_sort | Grimm, Christopher Lee, Jr |
| collection | MIT |
| description | Thesis: S.M., Massachusetts Institute of Technology, Department of Aeronautics and Astronautics, 2016. |
| first_indexed | 2024-09-23T11:18:00Z |
| format | Thesis |
| id | mit-1721.1/105615 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T11:18:00Z |
| publishDate | 2016 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1056152019-04-12T17:45:01Z A tensor-train-decomposition-based algorithm for high-dimensional pursuit-evasion games Grimm, Christopher Lee, Jr Sertac Karaman. Massachusetts Institute of Technology. Department of Aeronautics and Astronautics. Massachusetts Institute of Technology. Department of Aeronautics and Astronautics. Aeronautics and Astronautics. Thesis: S.M., Massachusetts Institute of Technology, Department of Aeronautics and Astronautics, 2016. Cataloged from PDF version of thesis. Includes bibliographical references (pages 99-100). The research presented in this thesis was inspired by an interest in determining feedback strategies for high-dimensional pursuit-evasion games. When a problem is high-dimensional or involves a state space that is defined by several variables, various methods used to solve pursuit-evasion games often require unrealistic computation time. This problem, called the curse of dimensionality, can be mitigated under certain circumstances by utilizing tensor-train (TT) decomposition. By using this intuition, a new algorithm for solving high dimensional pursuit-evasion problems called Best-Response Tensor-Train-decomposition-based Value Iteration (BR-TT-VI) was developed. BR-TT-VI builds on concepts from game theory, dynamic programming (DP), and tensor-train decomposition. By using TT decomposition, BR-TT-VI greatly reduces the effects of the curse of dimensionality. This work culminates in the application of BR-TT-VI to two different pursuit-evasion problems. First, a four-dimensional problem capable of being solved by traditional value iteration(VI) is tackled by the BR-TT-VI algorithm. This problem allows a direct comparison between VI and BR-TT-VI to demonstrate the reduced computational time of the new algorithm. Finally, BR-TT-VI is used to solve a six-dimensional problem involving two Dubins vehicles that is impractical to solve with VI. by Christopher Lee Grimm Jr. S.M. 2016-12-05T19:55:03Z 2016-12-05T19:55:03Z 2016 2016 Thesis http://hdl.handle.net/1721.1/105615 962488585 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 100 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Aeronautics and Astronautics. Grimm, Christopher Lee, Jr A tensor-train-decomposition-based algorithm for high-dimensional pursuit-evasion games |
| title | A tensor-train-decomposition-based algorithm for high-dimensional pursuit-evasion games |
| title_full | A tensor-train-decomposition-based algorithm for high-dimensional pursuit-evasion games |
| title_fullStr | A tensor-train-decomposition-based algorithm for high-dimensional pursuit-evasion games |
| title_full_unstemmed | A tensor-train-decomposition-based algorithm for high-dimensional pursuit-evasion games |
| title_short | A tensor-train-decomposition-based algorithm for high-dimensional pursuit-evasion games |
| title_sort | tensor train decomposition based algorithm for high dimensional pursuit evasion games |
| topic | Aeronautics and Astronautics. |
| url | http://hdl.handle.net/1721.1/105615 |
| work_keys_str_mv | AT grimmchristopherleejr atensortraindecompositionbasedalgorithmforhighdimensionalpursuitevasiongames AT grimmchristopherleejr tensortraindecompositionbasedalgorithmforhighdimensionalpursuitevasiongames |