Adventures in Blocks World

This is the abstract of technical report TR-ARP-07-94 (dvi or ps)

Despite over 25 years of its use as as the standard example in planning, Blocks World (BW) is still little understood from a mathematical point of view. Here we report a series of investigations of this surprisingly complex structure, issuing in:

simple expressions for the number of BW states and some theorems concerning the numbers of states and partial states.

a proof that it is easy to generate BW states using exhaustive satisfiability techniques such as Davis-Putnam.

a new polynomial time algorithm for near-optimal BW planning and some notes on its behaviour.

some observations concerning the average numbers of blocks that must be moved in solving BW planning problems and the probability that all blocks must be moved.

We close with an experimental comparison between our new algorithm and certain others suggested in the recent literature. All of these algorithms have the property of being `near-optimal' in the sense that for some constant k they guarantee plans no longer than k times the minimum possible.

For more on Blocks World, including an online problem generator, see the Blocks World Page.