A framework for proving the computational intractability of motion planning problems

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.

Name thesis:degree_name

Doctoral

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2020

Author dc:creator

• Lynch, Jayson(Jayson R.)

Advisor dc:contributor.advisor

• Erik D. Demaine.

• Electrical Engineering and Computer Science.

Statement dc:rights

• 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.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/129205

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/129205