Technical Report TR-ARP-7-94

Automated Reasoning Project
Research School of Information Sciences and Engineering
and Centre for Information Science Research
Australian National University

September 13, 1994

ADVENTURES IN BLOCKS WORLD

John Slaney and Sylvie Thi?ebaux

Abstract 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:

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

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

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

ffl 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 ear-optimal" in the sense that for some constant k they guarantee plans no longer than k times the minimum possible.