Complexity Results for Blocks-World Planning

Naresh Gupta, Dana S. NauAAAI 1991

Introduction

For decades, the "Blocks World" served as the quintessential benchmark for AI planning. While simple in concept—a robotic arm moving blocks between stacks—its true computational complexity remained a subject of debate. This paper provides a formal proof that finding the shortest plan in this domain is NP-hard, identifying "deadlocks" as the primary source of difficulty.

The Problem Domain

The authors focus on the Elementary Blocks World (EBW), where a single arm can move a clear block either to the table or onto another clear block. A more specific version, the Primitive Blocks World (PBW), requires the final state to be completely specified.

Initial and goal states in a typical Blocks World problem.

The Deadlock Discovery

The core difficulty of the Blocks World does not arise from famous puzzles like Sussman’s Anomaly, which involves "deleted-condition interactions." Instead, the complexity is driven by deadlocks—circular dependencies where a set of blocks are positioned such that none can move to their final destination without another first being moved to the table.

Complexity Reduction

To prove NP-hardness, the authors perform a mathematical reduction from the Feedback Arc Set (FAS) problem in graph theory. They demonstrate that finding the minimum number of blocks to move to the table to resolve all deadlocks is equivalent to finding the minimum set of edges to remove to make a directed graph acyclic—a known NP-complete problem.

Reduction from a directed graph G to a Blocks World configuration.

Key Results

The research establishes that the decision problem "Is there a plan of length less than $L$?" is NP-complete. Consequently, finding the optimal plan is NP-hard.

The authors prove that the length of the shortest plan is $p - q + r$, where $p$ is the total number of blocks, $q$ is the number of blocks already in their final positions, and $r$ is the minimum number of "deadlock-breaking" moves to the table. Interestingly, while finding the shortest plan is difficult, finding any plan is easy; a simple strategy of moving all blocks to the table and rebuilding them yields a plan at most twice the optimal length in polynomial time.

Conclusion

The "hardness" of the Blocks World is concentrated entirely in the choice of which blocks to move to the table to resolve deadlocks. This work clarifies that even with a fully specified goal, the optimization problem remains computationally intractable, debunking previous intuitions that goal specification might simplify the search.

Summary updated

BibTeX
@inproceedings{gupta1991complexity,
  author = {Naresh Gupta and Dana S. Nau},
  title = {{Complexity Results for Blocks-World Planning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1991},
}
Figure