Pushing Blocks without Fixed Blocks via Checkable Gizmos: Push-1 is PSPACE-Complete

内容摘要

We prove PSPACE-completeness of Push-1: given a rectangular grid of 1 x 1 cells, each possibly occupied by a movable block, can a robot move from a specified location to another, given the ability to push up to one block at a time? In particular, we remove the need for fixed (unmovable) blocks in a previous result (FUN 2022), which seems to require a completely different reduction. This fundamental model of block pushing, introduced in 1999, abstracts the mechanics of many video games. It was shown NP-hard in 2000, but its final complexity remained open for 24 years. Our result uses a new framework for checkable gadgets/gizmos, extending a prior framework for checkable gadgets to handle reconfiguration problems, at the cost of requiring a stronger auxiliary gadget. We also show how to unify the motion-planning-through-gadgets framework (with an agent) with Nondeterministic Constraint Logic (with no agent), or more generally any Graph Orientation Reconfiguration Problem (GORP), by defining corresponding gadgets/gizmos.