Paper by Erik D. Demaine
- Erik D. Demaine, Isaac Grosof, Jayson Lynch, and Mikhail Rudoy, “Computational Complexity of Motion Planning of a Robot through Simple Gadgets”, in Proceedings of the 9th International Conference on Fun with Algorithms (FUN 2018), La Maddalena, Italy, June 13–15, 2018, 18:1–18:21.
We initiate a general theory for analyzing the complexity of motion planning
of a single robot through a graph of “gadgets”, each with their
own state, set of locations, and allowed traversals between locations that can
depend on and change the state. This type of setup is common to many robot
motion planning hardness proofs. We characterize the complexity for a natural
simple case: each gadget connects up to four locations in a perfect matching
(but each direction can be traversable or not in the current state), has one
or two states, every gadget traversal is immediately undoable, and that gadget
locations are connected by an always-traversable forest, possibly restricted
to avoid crossings in the plane. Specifically, we show that any single
nontrivial four-location two-state gadget type is enough for motion planning
to become PSPACE-complete, while any set of simpler gadgets (effectively
two-location or one-state) has a polynomial-time motion planning algorithm.
As a sample application, our results show that motion planning games with
“spinners” are PSPACE-complete, establishing a new hard aspect of
Zelda: Oracle of Seasons.
- The full version of this paper is available as arXiv:1806.03539.
- The paper is available in PDF (542k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- Gadgets_ITCS2020 (Toward a General Theory of Motion Planning Complexity: Characterizing Which Gadgets Make Games Hard)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated September 2, 2021 by