2 citations · 4 across the 7 of their papers we have counts for
7 papers
Pushing Blocks via Checkable Gadgets: PSPACE-completeness of Push-1F and Block/Box Dude
Hayashi Ani, Lily Chung, Erik D. Demaine +3
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 Push-$k…
Complexity of Motion Planning of Arbitrarily Many Robots: Gadgets, Petri Nets, and Counter Machines
Hayashi Ani, Michael Coulombe, Erik D. Demaine +4
We extend the motion-planning-through-gadgets framework to several new scenarios involving various numbers of robots/agents, and analyze the complexity of the resulting motion-plan…
This Game Is Not Going To Analyze Itself
Aviv Adler, Hayashi Ani, Lily Chung +5
We analyze the puzzle video game This Game Is Not Going To Load Itself, where the player routes data packets of three different colors from given sources to given sinks of the corr…
Traversability, Reconfiguration, and Reachability in the Gadget Framework
Hayashi Ani, Erik Demaine, Jenny Diomidova +2
Consider an agent traversing a graph of "gadgets", each with local state that changes with each traversal by the agent. We characterize the complexity of universal traversal, where…
Orthogonal Fold & Cut
Hayashi Ani, Josh Brunner, Erik D. Demaine +4
We characterize the cut patterns that can be produced by "orthogonal fold & cut": folding an axis-aligned rectangular sheet of paper along horizontal and vertical creases, and then…
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…
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…