Blocks WorldJohn Slaney and Sylvie Thiébaux
The Blocks World is an artificial planning domain of little direct practical significance. Nonetheless, because it is clear and simple, it has been by far the most frequently used example in the AI planning literature since the 1960s. It is therefore surprising that the domain has only recently been investigated in any real depth. We began a research project on Blocks World in 1994, found it fascinating and continued to write papers, technical reports and programs about it, intensively for two years and sporadically for several years after that. For the most thorough account of our work, see John Slaney and Sylvie Thiébaux In the introduction to a technical report in 1997 we wrote:
To be frank, it is not without trepidation that we venture once more into the Blocks World. Even our friends begin to be concerned for us, and indeed we risk being branded cranks for our sustained investigation of this domain: if we work in planning, why aren't we obsessed with truck schedules like everybody else? In our defence, we would point out that it is not enough to complain that planning problems are hard: research is needed into why they are hard and into the features in virtue of which, intractable or not, they may in many cases be coped with. Artificial domains such as the blocks offer a basis both for mathematical theorems and for systematic experiments. They are a source of clear, crisp problems; and, to paraphrase a great remark of Bob Meyer's, by solving problems we may actually learn something---even about planning. It is in that spirit that we now make available the following reports and programs, hoping that someone will find them useful.
Adventures in Blocks World (Slaney/Thiébaux, 1994).
Blocks World Tamed: Ten Thousand Blocks in Under a Second (Slaney/Thiébaux, 1995).
How Best to Put Things on Top of Other Things (Slaney/Thiébaux, 1996).
BWSTATES: A program which generates random BW states with uniform distribution, suitable for respectable scientific experiments with planning systems.
BWOPT: A program which generates optimal plans for BW problems expressed as pairs of states in the format produced by BWSTATES. It copes pretty well with up to about 150 blocks. Dr J K Slaney Phone (Aus.): (026) 125 8607 Logic and Computation Group Phone (Int.): +61 26 125 8607 School of Computer Science Fax (Aus.): (026) 125 8651 Australian National University Fax (Int.): +61 26 125 8651 Canberra, ACT, 0200, AUSTRALIAJohn.Slaney@anu.edu.au |