We prove PSPACE-completeness of the well-studied pushing-block puzzle Push-1F, a
theoretical abstraction of many video games (introduced in 1999). The proof also extends to …

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 …

Consider an agent traversing a graph of “gadgets”, where each gadget has local state that
changes with each traversal by the agent according to specified rules. Prior work has …

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 …

State-of-the-art motion planners cannot scale to a large number of systems. Motion planning
for multiple agents is an NP (non-deterministic polynomial-time) hard problem, so the …

The popularity of molecular computation has given rise to several models of abstraction, one
of the more recent ones being Chemical Reaction Networks (CRNs). These are equivalent …

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 prove PSPACE-completeness of several reversible, fully deterministic systems. At the
core, we develop a framework for such proofs (building on a result of Tsukiji and Hagiwara …

Recent work has developed a theory of motion-planning gadgets, which are a useful tool for
proving hardness for a variety of problems that can be thought of in terms of an agent …

We prove PSPACE-completeness of all but one problem in a large space of pulling-block
problems where the goal is for the agent to reach a target destination. The problems are …