4 citations · 10 across the 13 of their papers we have counts for
7 papers · 1 filter
Characterizing Universal Reconfigurability of Modular Pivoting Robots
Hugo A. Akitaya, Erik D. Demaine, Andrei Gonczi +7
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 co…
Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess is Hard
Josh Brunner, Erik D. Demaine, Dylan Hendrickson +1
We prove PSPACE-completeness of two classic types of Chess problems when generalized to n-by-n boards. A "retrograde" problem asks whether it is possible for a position to be reach…
PSPACE-completeness of Pulling Blocks to Reach a Goal
Hayashi Ani, Sualeh Asif, Erik D. Demaine +5
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 param…
Walking through Doors is Hard, even without Staircases: Universality and PSPACE-hardness of Planar Door Gadgets
MIT Gadgets Group, Jeffrey Bosboom, Erik D. Demaine +4
An open-close door gadget has two states and three tunnels that can be traversed by an agent (player, robot, etc.): the "opening" and "closing" tunnels set the gadget's state to op…
Trains, Games, and Complexity: 0/1/2-Player Motion Planning through Input/Output Gadgets
Hayashi Ani, Erik D. Demaine, Dylan H. Hendrickson +1
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 entrances…
1 x 1 Rush Hour with Fixed Blocks is PSPACE-complete
Josh Brunner, Lily Chung, Erik D. Demaine +4
Consider unit-square blocks in an square board, where each block is labeled as movable horizontally (only), movable vertically (only), or immovable -- a variat…