PSPACE-completeness of Pulling Blocks to Reach a Goal

Joshua Ani, Sualeh Asif, Erik D. Demaine, Jenny Diomidova, Dylan H. Hendrickson, Jayson Lynch, Sarah Scheffler, Adam Suhl

TL;DR

This paper proves that most variants of the "pulling blocks" puzzle, where an agent must move blocks by pulling them to reach a goal, are PSPACE-complete. This is significant because it establishes a high level of computational difficulty for these puzzles, even in simplified forms, suggesting that efficient general solutions are unlikely.

What Problem Does This Paper Address?

The paper tackles the computational complexity of a class of puzzles involving an agent (robot) and movable blocks on a grid. These puzzles are inspired by popular video games like Sokoban, Legend of Zelda, and Portal. While the related "pushing blocks" problem has been extensively studied, this paper focuses on the "pulling blocks" mechanic. The core question is to determine the computational complexity of various configurations of pulling block problems, specifically when the agent needs to reach a target destination. The authors explore how factors like optional pulling, the number of blocks that can be pulled simultaneously, the presence of fixed obstacles or walls, and gravity affect the problem's difficulty.

Methods

The paper employs a common strategy in computational complexity theory: reductions. They reduce known hard problems to their pulling-block problems to prove hardness. Specifically, they reduce from:

  • Asynchronous Nondeterministic Constraint Logic (NCL): This is a known PSPACE-complete problem used to prove PSPACE-hardness for variants without gravity. They construct gadgets (special configurations of blocks and walls) that simulate NCL components like edges, AND gates, and OR gates.
  • 1-player motion planning with specific gadgets (locking 2-toggle, nondeterministic locking 2-toggle, door gadget, 3-port self-closing door): These are used to prove PSPACE-hardness for variants with gravity. The "motion-planning-through-gadgets" framework is key here, where complex gadgets are built from simpler ones.
  • 1-player planar motion planning with the crossing NAND gadget: This is used to prove NP-hardness for the specific case of PULL?-1FG.

For proving that the problems are in PSPACE, they rely on Savitch's Theorem, which states that any problem solvable in nondeterministic polynomial time (NPSPACE) is also solvable in polynomial space (PSPACE). They argue that a configuration of the pulling-block puzzle can be represented and checked in polynomial space.

Datasets

Not discussed in the paper. The paper focuses on theoretical complexity and does not involve empirical evaluation on datasets.

Key Insights and Ideas

  • Pulling is surprisingly hard: Even simple variants of pulling blocks are computationally complex, often matching or exceeding the complexity of pushing blocks. This suggests that the mechanics of pulling, which can feel more constrained than pushing, lead to significant computational challenges.
  • Gravity adds complexity, but not always to PSPACE: While gravity introduces new dynamics, the paper shows that for many variants, the complexity remains PSPACE-complete. However, the specific case of PULL?-1FG with gravity is only shown to be NP-hard, leaving a gap.
  • Gadget engineering is crucial: The paper showcases sophisticated "gadget" designs within the grid-based pulling-block environment. These gadgets are cleverly constructed to mimic logical gates or state transitions from known hard problems, demonstrating the power of this reduction technique.
  • "Unrecoverable configurations" as a trap: A recurring theme is the creation of situations where the agent gets "trapped" if it makes a wrong move, leading to an unrecoverable state. This is a key mechanism used in the reductions to enforce constraints.

Key Results

The paper establishes the following complexity results:

  • PSPACE-completeness for most variants of PULL problems that include fixed blocks or walls, with or without gravity, and with optional or forced pulling. This includes PULL?-kF, PULL!-kF, PULL?-kW, PULL!-kW, PULL?-kFG (for k ≥ 2), PULL?-FG, PULL!-kFG (for k ≥ 1), PULL!-FG, and their thin-wall equivalents (PULL?-kWG, PULL!-kWG).
  • NP-hardness for the specific problem PULL?-1FG (optional pulling, strength 1, fixed blocks, with gravity). The paper leaves open whether this problem is in NP or PSPACE-hard.

Limitations and Future Work

  • PULL?-1FG complexity gap: The paper explicitly leaves open the question of whether PULL?-1FG is in NP or PSPACE-hard. This is the only problem from their table that doesn't have a PSPACE-complete or NP-hard classification.
  • Pulling without fixed blocks: The complexity of pulling-block puzzles without any fixed blocks (on a rectangular board) is an open problem.
  • Storage and reconfiguration variants: The paper poses questions about the complexity of variants where the goal is not just reachability but also storage (placing blocks in specific areas) or reconfiguration (arranging distinguishable blocks into a target configuration).
  • PUSHPULL and PULLPULL: The complexity of variations of pushing and pulling combined, especially with mandatory pulling or gravity, remains open.

Summary updated

BibTeX
@article{ani2020pspace,
  author = {Joshua Ani and Sualeh Asif and Erik D. Demaine and Jenny Diomidova and Dylan H. Hendrickson and Jayson Lynch and Sarah Scheffler and Adam Suhl},
  title = {{PSPACE-completeness of Pulling Blocks to Reach a Goal}},
  journal = {J. Inf. Process.},
  year = {2020},
  doi = {10.2197/ipsjjip.28.929},
}
Figure