Paper by Erik D. Demaine

Reference:

MIT Hardness Group, Hayashi Ani, Josh Brunner, Erik D. Demaine, Jenny Diomidova, Timothy Gomez, Della Hendrickson, Yael Kirkpatrick, Jeffery Li, Jayson Lynch, Ritam Nag, and Frederick Stock, “Agent Motion Planning as Block Asynchronous Cellular Automata: Pushing, Pulling, Suplexing, and More”, in Proceedings of the 21st International Conference on Unconventional Computation and Natural Computation (UCNC 2024), Lecture Notes in Computer Science, volume 14776, Pohang, Korea, June 17–21, 2024, pages 219–236.

Abstract:

In this paper, we explore how agent reachability problems from motion planning, games, and puzzles can be generalized and analyzed from the perspective of block asynchronous cellular automata, inspired by asynchronous cellular automata, surface chemical reaction networks, and similar rewriting dynamical systems. Specifically, we analyze square grids with three or four cell types (states) that model motion planning with blocks: an agent which occurs uniquely, empty space, blocks, and (optionally) fixed walls. The agent can freely exchange with (walk through) empty space, and can interact with blocks according to a single local asynchronous 3-cell replacement rule; the goal is for the agent to reach a specified destination (reachability). This setting generalizes well-studied motion-planning problems such as Push-1F and Pull-1F, which are known to be PSPACE-complete. We analyze all 40 possible 3-cell replacement rules (22 that conserve blocks so are naturally in PSPACE, and 18 that create or destroy blocks so are naturally in NP), and except for a few open problems, characterize their complexity — ranging from L to NL to as hard as Planar Monotone Circuit Value Problem to P-complete to NP-complete to PSPACE-complete.

Comments:

This paper is also available from SpringerLink.

Availability:

The paper is available in PDF (415k).

See information on file formats.

[Google Scholar search]