A framework for proving the computational intractability of motion planning problems
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, September, 2020
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2021
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/1721.1/129205 |
| _version_ | 1811093000133017600 |
|---|---|
| author | Lynch, Jayson(Jayson R.) |
| author2 | Erik D. Demaine. |
| author_facet | Erik D. Demaine. Lynch, Jayson(Jayson R.) |
| author_sort | Lynch, Jayson(Jayson R.) |
| collection | MIT |
| description | Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, September, 2020 |
| first_indexed | 2024-09-23T15:37:58Z |
| format | Thesis |
| id | mit-1721.1/129205 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T15:37:58Z |
| publishDate | 2021 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1292052022-10-04T05:33:58Z A framework for proving the computational intractability of motion planning problems Lynch, Jayson(Jayson R.) Erik D. Demaine. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Electrical Engineering and Computer Science. Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, September, 2020 Cataloged from student-submitted PDF of thesis. Includes bibliographical references (pages 235-240). This thesis develops a framework for proving computational complexity results about motion planning problems. The model captures reactive environments with local interaction. We introduce a motion planning problem involving one or more agents that move around a connection graph and through "gadgets" which are stateful parts of the environment whose state and traversability can change only in response to traversals of the agent within the gadget. The model includes variants for 0-player, 1-player, 2-player, and team imperfect information games. This thesis considers various classes of gadgets and give both algorithms and hardness results ranging from NL-completeness to Undecidability. Full dichotomies are obtained for some classes including the natural class of gadgets which can be traversed a bounded number of times. For 1-player this gives a separation between containment in NL versus NP-completeness, for 2-player a separation between containment in P and PSPACE-completeness, and for team imperfect information games a separation between containment in P and NEXPTIME-completeness. Our model builds on and generalizes several other proof techniques for motion planning problems and games. This thesis also provides examples of how this new framework can simplify many of those old results, as well as applying to many new hardness results for video games and variants of block pushing puzzles. New hardness results include PSPACE-hardness for Trainyard, Sokobond, The Legend of Zelda: Breath of the Wild, The Legend of Zelda: The Minish Cap, The Legend of Zelda: Oracle of Seasons, Captain Toad: Treasure Tracker, Super Mario Oddsey, Super Mario Galaxy 1 and 2, Super Mario Sunshine, and Super Mario 64. by Jayson Lynch. Ph. D. Ph.D. Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science 2021-01-06T19:32:27Z 2021-01-06T19:32:27Z 2020 2020 Thesis https://hdl.handle.net/1721.1/129205 1227521093 eng MIT theses may be protected by copyright. Please reuse MIT thesis content according to the MIT Libraries Permissions Policy, which is available through the URL provided. http://dspace.mit.edu/handle/1721.1/7582 240 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Lynch, Jayson(Jayson R.) A framework for proving the computational intractability of motion planning problems |
| title | A framework for proving the computational intractability of motion planning problems |
| title_full | A framework for proving the computational intractability of motion planning problems |
| title_fullStr | A framework for proving the computational intractability of motion planning problems |
| title_full_unstemmed | A framework for proving the computational intractability of motion planning problems |
| title_short | A framework for proving the computational intractability of motion planning problems |
| title_sort | framework for proving the computational intractability of motion planning problems |
| topic | Electrical Engineering and Computer Science. |
| url | https://hdl.handle.net/1721.1/129205 |
| work_keys_str_mv | AT lynchjaysonjaysonr aframeworkforprovingthecomputationalintractabilityofmotionplanningproblems AT lynchjaysonjaysonr frameworkforprovingthecomputationalintractabilityofmotionplanningproblems |