We use the theory of motion-planning gadgets (and closely-related motion-planning gizmos) to study the complexity of various motion-planning problems, including block-pushing and block-pulling games, and asynchronous cellular automata.

A motion-planning gadget is an object with a set of ports, a set of internal states, and a transition table. The agent (‘player’) can enter a gadget through one port, change the internal state of the gadget, and exit through a different port, according to the transition table. Multiple gadgets can be combined by connecting some of their ports. The gadgets are often embedded in the plane, and the connections between gadgets must respect planarity. The typical decision problem is reachability: given a network of gadgets, determine whether it’s possible to move from one location to another. This problem is in PSPACE and for many classes of gadgets it is PSPACE-complete.

One of the simplest gadgets is the door gadget, which has 3 pairs of ports and 2 states (‘open’ and ‘closed’). Moving between the first pair of ports switches the state to ‘open’, moving between the second pair switches the state to ‘closed’, and moving between the third pair of ports doesn’t change the state, but is only allowed in the ‘open’ state. Viglietta showed in 2012 that motion planning with door gadgets is PSPACE-hard, if you ignore planarity. We show that any planar embedding of the door gadget is universal, i.e. can simulate an arbitrary gadget (and therefore PSPACE-hard, by simulating your favorite PSPACE-hard gadget). We also show analogous results for several other types of gadgets, namely self-closing doors and symmetric self-closing doors.

Sokoban is a classic video game in which the player has to push boxes in a warehouse, and the goal is to push all boxes to target storage locations. Culberson showed in 1997 that this game is PSPACE-complete. A closely related game is Push-1F, where the goal is simply to reach the end of the level, rather than push the boxes to target locations. This game was first posed by O’Rourke in 1999 and has stubbornly remained open for over two decades. We develop a theory of checkable gizmos, and use it to show that Push-1F and several other related block-pushing games are all PSPACE-complete, resolving this long-standing open problem.

In addition to block-pushing games, we consider several block-pulling games. We show that many of them are also PSPACE-complete.

Both block-pushing and block-pulling games can be naturally modeled as asynchronous cellular automata, with transition rules such as (agent, block, empty) -> (empty, agent, block). We consider a larger class of asynchronous cellular automata which includes both pushing and pulling blocks, and for each automaton in this class determine its computational complexity (in P, NP-complete, or PSPACE-complete).

We also study the computational complexity of another class of asynchronous cellular automata, known as surface Chemical Reaction Networks (sCRNs). In an sCRN, every transition rule (‘reaction’) involves only a pair of adjacent cells (‘molecules’). We use the gadget framework to show that sCRNs can be NP-hard with just 3 types of molecules and 1 reaction, and PSPACE-complete with just 4 types of molecules and 3 reactions.