
Technical Report TRARP794
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 DavisPutnam.
ffl a new polynomial time algorithm for nearoptimal 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 earoptimal" in the sense that for some constant k they guarantee plans no longer than k times the minimum possible.