Paper by Erik D. Demaine
- Erik D. Demaine, Dylan Hendrickson, and Jayson Lynch, “Toward a General Theory of Motion Planning Complexity: Characterizing Which Gadgets Make Games Hard”, in Proceedings of the 11th Conference on Innovations in Theoretical Computer Science (ITCS 2020), Seattle, Washington, January 12–14, 2020, 62:1–62:42.
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.
- The full version of this paper is available as arXiv:1812.03592 and from LIPIcs.
- The paper is available in PDF (1451k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- Toggles_FUN2018 (Computational Complexity of Motion Planning of a Robot through Simple Gadgets)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated September 18, 2020 by