Paper by Erik D. Demaine
- Joshua Ani, Erik D. Demaine, Dylan Hendrickson, and Jayson Lynch, “Trains, Games, and Complexity: 0/1/2-Player Motion Planning through Input/Output Gadgets”, in Proceedings of the 16th International Conference and Workshops on Algorithms and Computation (WALCOM 2022), edited by Petra Mutzel, Md. Saidur Rahman, and Slamin, Lecture Notes in Computer Science, volume 13174, Jember, Indonesia, March 24–26, 2022, pages 187–198.
We analyze the computational complexity of motion planning through local
“input/output” gadgets with separate entrances and exits, and a
subset of allowed traversals from entrances to exits, each of which changes
the state of the gadget and thereby the allowed traversals. We study such
gadgets in the zero-, one-, and two-player settings, in particular extending
past motion-planning-through-gadgets work [3, 4] to zero-player games for the
first time, by considering “branchless” connections between
gadgets that route every gadget's exit to a unique gadget's entrance. Our
complexity results include containment in L, NL, P, NP, and PSPACE; as well as
hardness for NL, P, NP, and PSPACE. We apply these results to show
PSPACE-completeness for certain mechanics in Factorio, [the Sequence], and a
restricted version of Trainyard, improving the result of . This work
strengthens prior results on switching graphs, ARRIVAL , and
reachability switching games .
- This paper is also available as arXiv:2005.03192 and from SpringerLink.
- The paper is available in PDF (338k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated November 6, 2023 by