License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2020.62
URN: urn:nbn:de:0030-drops-117478
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11747/
Demaine, Erik D. ;
Hendrickson, Dylan H. ;
Lynch, Jayson
Toward a General Complexity Theory of Motion Planning: Characterizing Which Gadgets Make Games Hard
Abstract
We begin a general theory for characterizing the computational complexity of motion planning of robot(s) through a graph of "gadgets", where each gadget has its own state defining a set of allowed traversals which in turn modify the gadget’s state. We study two general families of such gadgets within this theory, one which naturally leads to motion planning problems with polynomially bounded solutions, and another which leads to polynomially unbounded (potentially exponential) solutions. We also study a range of competitive game-theoretic scenarios, from one player controlling one robot to teams of players each controlling their own robot and racing to achieve their team’s goal. Under certain restrictions on these gadgets, we fully characterize the complexity of bounded 1-player motion planning (NL vs. NP-complete), unbounded 1-player motion planning (NL vs. PSPACE-complete), and bounded 2-player motion planning (P vs. PSPACE-complete), and we partially characterize the complexity of unbounded 2-player motion planning (P vs. EXPTIME-complete), bounded 2-team motion planning (P vs. NEXPTIME-complete), and unbounded 2-team motion planning (P vs. undecidable). These results can be seen as an alternative to Constraint Logic (which has already proved useful as a basis for hardness reductions), providing a wide variety of agent-based gadgets, any one of which suffices to prove a problem hard.
BibTeX - Entry
@InProceedings{demaine_et_al:LIPIcs:2020:11747,
author = {Erik D. Demaine and Dylan H. Hendrickson and Jayson Lynch},
title = {{Toward a General Complexity Theory of Motion Planning: Characterizing Which Gadgets Make Games Hard}},
booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
pages = {62:1--62:42},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-134-4},
ISSN = {1868-8969},
year = {2020},
volume = {151},
editor = {Thomas Vidick},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11747},
URN = {urn:nbn:de:0030-drops-117478},
doi = {10.4230/LIPIcs.ITCS.2020.62},
annote = {Keywords: motion planning, computational complexity, NP, PSPACE, EXP, NEXP, undecidability, games}
}
|
Keywords: |
|
motion planning, computational complexity, NP, PSPACE, EXP, NEXP, undecidability, games |
|
Collection: |
|
11th Innovations in Theoretical Computer Science Conference (ITCS 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
06.01.2020 |
