Automated planning: what makes "blocksworld" a non trivial problem?

Question

Blocksworld is apparently a benchmark domain in automated planning.

This domain consists of a set of blocks, a table and a robot hand.
The blocks can be on top of other blocks or on the table;
a block that has nothing on it is clear;
and the robot hand can hold one block or be empty.
The goal is to find a plan to move from one configuration of blocks to another.

Can someone explain what makes this a non trivial problem? I can't think of a problem instance where the solution is not trivial (e.g. build desired towers bottom-up one block at a time).

Answer 1

There's a historical and two practical reasons for Blocks World being a benchmark of interest.

The historical one is that Blocks World was used to illustrate the so-called Sussman's Anomaly. It has no longer any scientific relevance, but it was used to illustrate the limitations and challenges of planning algorithms that approach the problem of planning as that of searching through the space of plans directly. The link points to a chapter of the following book, which is a good introduction into Automated Planning

Automated Planning and Acting Malik Ghallab, Dana Nau, Paolo Traverso
Cambridge University Press

It used to be the case, especially back in the mid 1990s, when SAT solving really took off, that it was an example of how limited was the state of the art in Automated Planning back in the day.

As you write in your question, solving Blocks World is easy: the algorithm you sketch is well known and is clearly in polynomial time. Finding an optimal plan, though, is not easy. I refer you to this excellent book

Understanding Planning Tasks: Domain Complexity and Heuristic Decomposition
Malte Helmert
Springer, 2006

or his shorter, classic paper

Complexity results for standard benchmark domains in planning Malte Helmert Artificial Intelligence, 2003

The second "practical" reason for the relevance of Blocks World is that, even being a "simple" problem, it can defeat planning heuristics and elaborate algorithms or compilations to other computational frameworks such as SAT or SMT.

For instance, it wasn't until relatively recently (2012) that Jussi Rintanen showed good performance on that "simple" benchmark after heavily modifying standard SAT solvers

Planning as satisfiability: Heuristics
Jussi Rintanen
Artificial Intelligence, 2012

by compiling into them heuristics as clauses that the combination of unit propagation, clause learning and variable selection heuristics can exploit to obtain deductive lower bounds quickly.

EDIT: Further details on the remark above optimal planning for blocks not being easy have been requested. From the references provided, this paper

On the complexity of blocks-world planning
Naresh Gupta and Dana S. Nau
Artificial Intelligence, 1992

has the original proof, reducing the problem of computing optimal plans for Blocks World to HITTING-SET (one of the Karp's NP-hard problems).

An easier to access paper, which looks quite deep into planning in the Blocks World domain is

Blocks World revisited
John Slaney, Sylvie Thiébaux
Artificial Intelligence, 2001

Figure 1 in the paper above shows an example of an instance that illustrates the intuition behind Gupta and Nau's complexity proof.

Answer 2

Another Blocksworld-related paper that I found quite interesting is How Good is Almost Perfect? (AAAI 2008) by Helmert and Röger.

It showed that even when using an almost perfect heuristic (a heuristic which is, for every possible state, wrong by only a constant) A* search is bound to produce an exponentially large search space. (This shows that even with almost perfect information about the goal distance, search will still get lost in the search space in this domain.)