research
∙
06/01/2023
Complexity of Motion Planning of Arbitrarily Many Robots: Gadgets, Petri Nets, and Counter Machines
We extend the motion-planning-through-gadgets framework to several new s...
share
research
∙
02/02/2023
This Game Is Not Going To Analyze Itself
We analyze the puzzle video game This Game Is Not Going To Load Itself, ...
research
∙
04/01/2022
Traversability, Reconfiguration, and Reachability in the Gadget Framework
Consider an agent traversing a graph of "gadgets", each with local state...
research
∙
02/02/2022
Orthogonal Fold Cut
We characterize the shapes that can be produced by "orthogonal fold ...
research
∙
06/08/2020
PSPACE-completeness of Pulling Blocks to Reach a Goal
We prove PSPACE-completeness of all but one problem in a large space of ...
research
∙
06/01/2020
Walking through Doors is Hard, even without Staircases: Proving PSPACE-hardness via Planar Assemblies of Door Gadgets
A door gadget has two states and three tunnels that can be traversed by ...
research
∙
05/07/2020