Erik D. Demaine

MIT Hardness Group, Josh Brunner, Lily Chung et al. · mit

We prove that Hamiltonicity in maximum-degree-3 grid graphs (directed or undirected) is ASP-complete, i.e., it has a parsimonious reduction from every NP search problem (including a polynomial-time bijection between solutions). As a consequence, given k Hamiltonian cycles, it is NP-complete to find another; and counting Hamiltonian cycles is #P-complete. If we require the grid graph's vertices to form a full $m \times n$ rectangle, then we show that Hamiltonicity remains ASP-complete if the edges are directed or if we allow removing some edges (whereas including all undirected edges is known to be easy). These results enable us to develop a stronger "T-metacell" framework for proving ASP-completeness of rectangular puzzles, which requires building just a single gadget representing a degree-3 grid-graph vertex. We apply this general theory to prove ASP-completeness of 38 pencil-and-paper puzzles where the goal is to draw a loop subject to given constraints: Slalom, Onsen-meguri, Mejilink, Detour, Tapa-Like Loop, Kouchoku, Icelom; Masyu, Yajilin, Nagareru, Castle Wall, Moon or Sun, Country Road, Geradeweg, Maxi Loop, Mid-loop, Balance Loop, Simple Loop, Haisu, Reflect Link, Linesweeper; Vertex/Touch Slitherlink, Dotchi-Loop, Ovotovata, Building Walk, Rail Pool, Disorderly Loop, Ant Mill, Koburin, Mukkonn Enn, Rassi Silai, (Crossing) Ichimaga, Tapa, Canal View, Aqre, and Paintarea. The last 14 of these puzzles were not even known to be NP-hard. Along the way, we prove ASP-completeness of some simple forms of Tree-Residue Vertex-Breaking (TRVB), including planar multigraphs with degree-6 breakable vertices, or with degree-4 breakable and degree-1 unbreakable vertices.

MIT Hardness Group, Josh Brunner, Lily Chung et al. · mit

We prove PSPACE-completeness of Push-1: given a rectangular grid of 1 x 1 cells, each possibly occupied by a movable block, can a robot move from one specified location to another, given the ability to push up to one block at a time? In particular, we remove the need for fixed (immovable) walls from a 2022 result. This fundamental model of block pushing, introduced in 1999, abstracts the mechanics of many video games. It was shown NP-hard in 2000, but its final complexity remained open for 25 years. Our result uses a new framework for checkable gadgets/gizmos, extending a prior framework for checkable gadgets to handle reconfiguration problems, at the cost of requiring a stronger auxiliary gadget. We also introduce a new connection between the motion-planning-through-gadgets framework (with an agent) and the Graph Orientation Reconfiguration Problem (with no agent), including Nondeterministic Constraint Logic.

MIT Hardness Group, Josh Brunner, Erik D. Demaine et al. · mit

We analyze the computational complexity of Tetris clearing (determining whether the player can clear an initial board using a given sequence of pieces) and survival (determining whether the player can avoid losing before placing all the given pieces in an initial board) when restricted to a single polyomino piece type. We prove, for any tetromino piece type $P$ except for O, the NP-hardness of Tetris clearing and survival under the standard Super Rotation System (SRS), even when the input sequence consists of only a specified number of $P$ pieces. These surprising results disprove a 23-year-old conjecture on the computational complexity of Tetris with only I pieces (although our result is only for a specific rotation system). As a corollary, we prove the NP-hardness of Tetris clearing when the sequence of pieces has to be able to be generated from a $7k$-bag randomizer for any positive integer $k\geq 1$. On the positive side, we give polynomial-time algorithms for Tetris clearing and survival when the input sequence consists of only dominoes, assuming a particular rotation model, solving a version of a 9-year-old open problem. Along the way, we give polynomial-time algorithms for Tetris clearing and survival with $1\times k$ pieces (for any fixed $k$), provided the top $k-1$ rows are initially empty, showing that our I NP-hardness result needs to have filled cells in the top three rows.

Hugo A. Akitaya, Erik D. Demaine, Matias Korman et al.

A well-established theoretical model for modular robots in two dimensions are edge-connected configurations of square modules, which can reconfigure through so-called sliding moves. Dumitrescu and Pach [Graphs and Combinatorics, 2006] proved that it is always possible to reconfigure one edge-connected configuration of $n$ squares into any other using at most $O(n^2)$ sliding moves, while keeping the configuration connected at all times. For certain pairs of configurations, reconfiguration may require $Ω(n^2)$ sliding moves. However, significantly fewer moves may be sufficient. We prove that it is NP-hard to minimize the number of sliding moves for a given pair of edge-connected configurations. On the positive side we present Gather&Compact, an input-sensitive in-place algorithm that requires only $O(\bar{P} n)$ sliding moves to transform one configuration into the other, where $\bar{P}$ is the maximum perimeter of the two bounding boxes. The squares move within the bounding boxes only, with the exception of at most one square at a time which may move through the positions adjacent to the bounding boxes. The $O(\bar{P} n)$ bound never exceeds $O(n^2)$, and is optimal (up to constant factors) among all bounds parameterized by just $n$ and $\bar{P}$. Our algorithm is built on the basic principle that well-connected components of modular robots can be transformed efficiently. Hence we iteratively increase the connectivity within a configuration, to finally arrive at a single solid $xy$-monotone component. We implemented Gather&Compact and compared it experimentally to the in-place modification by Moreno and Sacristán [EuroCG 2020] of the Dumitrescu and Pach algorithm (MSDP). Our experiments show that Gather&Compact consistently outperforms MSDP by a significant margin, on all types of square configurations.

Hugo A. Akitaya, Erik D. Demaine, Andrei Gonczi et al.

We give both efficient algorithms and hardness results for reconfiguring between two connected configurations of modules in the hexagonal grid. The reconfiguration moves that we consider are "pivots", where a hexagonal module rotates around a vertex shared with another module. Following prior work on modular robots, we define two natural sets of hexagon pivoting moves of increasing power: restricted and monkey moves. When we allow both moves, we present the first universal reconfiguration algorithm, which transforms between any two connected configurations using $O(n^3)$ monkey moves. This result strongly contrasts the analogous problem for squares, where there are rigid examples that do not have a single pivoting move preserving connectivity. On the other hand, if we only allow restricted moves, we prove that the reconfiguration problem becomes PSPACE-complete. Moreover, we show that, in contrast to hexagons, the reconfiguration problem for pivoting squares is PSPACE-complete regardless of the set of pivoting moves allowed. In the process, we strengthen the reduction framework of Demaine et al. [FUN'18] that we consider of independent interest.

Hayashi Ani, Jeffrey Bosboom, Erik D. Demaine et al.

A door gadget has two states and three tunnels that can be traversed by an agent (player, robot, etc.): the "open" and "close" tunnel sets the gadget's state to open and closed, respectively, while the "traverse" tunnel can be traversed if and only if the door is in the open state. We prove that it is PSPACE-complete to decide whether an agent can move from one location to another through a planar assembly of such door gadgets, removing the traditional need for crossover gadgets and thereby simplifying past PSPACE-hardness proofs of Lemmings and Nintendo games Super Mario Bros., Legend of Zelda, and Donkey Kong Country. Our result holds in all but one of the possible local planar embedding of the open, close, and traverse tunnels within a door gadget; in the one remaining case, we prove NP-hardness. We also introduce and analyze a simpler type of door gadget, called the self-closing door. This gadget has two states and only two tunnels, similar to the "open" and "traverse" tunnels of doors, except that traversing the traverse tunnel also closes the door. In a variant called the symmetric self-closing door, the "open" tunnel can be traversed if and only if the door is closed. We prove that it is PSPACE-complete to decide whether an agent can move from one location to another through a planar assembly of either type of self-closing door. Then we apply this framework to prove new PSPACE-hardness results for eight different 3D Mario games and Sokobond.

Hugo A. Akitaya, Esther M. Arkin, Mirela Damian et al.

We present the first universal reconfiguration algorithm for transforming a modular robot between any two facet-connected square-grid configurations using pivot moves. More precisely, we show that five extra "helper" modules ("musketeers") suffice to reconfigure the remaining $n$ modules between any two given configurations. Our algorithm uses $O(n^2)$ pivot moves, which is worst-case optimal. Previous reconfiguration algorithms either require less restrictive "sliding" moves, do not preserve facet-connectivity, or for the setting we consider, could only handle a small subset of configurations defined by a local forbidden pattern. Configurations with the forbidden pattern do have disconnected reconfiguration graphs (discrete configuration spaces), and indeed we show that they can have an exponential number of connected components. But forbidding the local pattern throughout the configuration is far from necessary, as we show that just a constant number of added modules (placed to be freely reconfigurable) suffice for universal reconfigurability. We also classify three different models of natural pivot moves that preserve facet-connectivity, and show separations between these models.

John Calvin Alumbaugh, Joshua J. Daymude, Erik D. Demaine et al.

Self-assembly refers to the process by which small, simple components mix and combine to form complex structures using only local interactions. Designed as a hybrid between tile assembly models and cellular automata, the Tile Automata (TA) model was recently introduced as a platform to help study connections between various models of self-assembly. However, in this paper we present a result in which we use TA to simulate arbitrary systems within the amoebot model, a theoretical model of programmable matter in which the individual components are relatively simple state machines that are able to sense the states of their neighbors and to move via series of expansions and contractions. We show that for every amoebot system, there is a TA system capable of simulating the local information transmission built into amoebot particles, and that the TA "macrotiles" used to simulate its particles are capable of simulating movement (via attachment and detachment operations) while maintaining the necessary properties of amoebot particle systems. The TA systems are able to utilize only the local interactions of state changes and binding and unbinding along tile edges, but are able to fully simulate the dynamics of these programmable matter systems.

Erik D. Demaine, Isaac Grosof, Jayson Lynch et al.

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.

Erik D. Demaine, Sándor P. Fekete, Phillip Keldenich et al.

We present a number of breakthroughs for coordinated motion planning, in which the objective is to reconfigure a swarm of labeled convex objects by a combination of parallel, continuous, collision-free translations into a given target arrangement. Problems of this type can be traced back to the classic work of Schwartz and Sharir (1983), who gave a method for deciding the existence of a coordinated motion for a set of disks between obstacles; their approach is polynomial in the complexity of the obstacles, but exponential in the number of disks. Other previous work has largely focused on {\em sequential} schedules, in which one robot moves at a time. We provide constant-factor approximation algorithms for minimizing the execution time of a coordinated, {\em parallel} motion plan for a swarm of robots in the absence of obstacles, provided some amount of separability. Our algorithm achieves {\em constant stretch factor}: If all robots are at most $d$ units from their respective starting positions, the total duration of the overall schedule is $O(d)$. Extensions include unlabeled robots and different classes of robots. We also prove that finding a plan with minimal execution time is NP-hard, even for a grid arrangement without any stationary obstacles. On the other hand, we show that for densely packed disks that cannot be well separated, a stretch factor $Ω(N^{1/4})$ may be required. On the positive side, we establish a stretch factor of $O(N^{1/2})$ even in this case.

Aaron T. Becker, Erik D. Demaine, Sándor P. Fekete et al.

We investigate algorithmic control of a large swarm of mobile particles (such as robots, sensors, or building material) that move in a 2D workspace using a global input signal (such as gravity or a magnetic field). We show that a maze of obstacles to the environment can be used to create complex systems. We provide a wide range of results for a wide range of questions. These can be subdivided into external algorithmic problems, in which particle configurations serve as input for computations that are performed elsewhere, and internal logic problems, in which the particle configurations themselves are used for carrying out computations. For external algorithms, we give both negative and positive results. If we are given a set of stationary obstacles, we prove that it is NP-hard to decide whether a given initial configuration of unit-sized particles can be transformed into a desired target configuration. Moreover, we show that finding a control sequence of minimum length is PSPACE-complete. We also work on the inverse problem, providing constructive algorithms to design workspaces that efficiently implement arbitrary permutations between different configurations. For internal logic, we investigate how arbitrary computations can be implemented. We demonstrate how to encode dual-rail logic to build a universal logic gate that concurrently evaluates and, nand, nor, and or operations. Using many of these gates and appropriate interconnects, we can evaluate any logical expression. However, we establish that simulating the full range of complex interactions present in arbitrary digital circuits encounters a fundamental difficulty: a fan-out gate cannot be generated. We resolve this missing component with the help of 2x1 particles, which can create fan-out gates that produce multiple copies of the inputs. Using these gates we provide rules for replicating arbitrary digital circuits.

Nadia M. Benbernou, Erik D. Demaine, Martin L. Demaine et al.

We present two universal hinge patterns that enable a strip of material to fold into any connected surface made up of unit squares on the 3D cube grid--for example, the surface of any polycube. The folding is efficient: for target surfaces topologically equivalent to a sphere, the strip needs to have only twice the target surface area, and the folding stacks at most two layers of material anywhere. These geometric results offer a new way to build programmable matter that is substantially more efficient than what is possible with a square $N \times N$ sheet of material, which can fold into all polycubes only of surface area $O(N)$ and may stack $Θ(N^2)$ layers at one point. We also show how our strip foldings can be executed by a rigid motion without collisions (albeit assuming zero thickness), which is not possible in general with 2D sheet folding. To achieve these results, we develop new approximation algorithms for milling the surface of a grid polyhedron, which simultaneously give a 2-approximation in tour length and an 8/3-approximation in the number of turns. Both length and turns consume area when folding a strip, so we build on past approximation algorithms for these two objectives from 2D milling.

Aaron Becker, Erik D. Demaine, Sándor P. Fekete et al.

Micro- and nanorobots are often controlled by global input signals, such as an electromagnetic or gravitational field. These fields move each robot maximally until it hits a stationary obstacle or another stationary robot. This paper investigates 2D motion-planning complexity for large swarms of simple mobile robots (such as bacteria, sensors, or smart building material). In previous work we proved it is NP-hard to decide whether a given initial configuration can be transformed into a desired target configuration; in this paper we prove a stronger result: the problem of finding an optimal control sequence is PSPACE-complete. On the positive side, we show we can build useful systems by designing obstacles. We present a reconfigurable hardware platform and demonstrate how to form arbitrary permutations and build a compact absolute encoder. We then take the same platform and use dual-rail logic to build a universal logic gate that concurrently evaluates AND, NAND, NOR and OR operations. Using many of these gates and appropriate interconnects we can evaluate any logical expression.