On Top Of Other Thingslogician series

The Blocks World is a favourite toy domain for planning in Artificial Intelligence, because it is simple to describe, capable of supporting systematic experiments, easy enough to be solved efficiently by special-purpose software and yet difficult for general planning systems. Your assignment here is to formulate the problem of getting from one state to another with a small number of blocks. When you have done that, investigate ways of improving your encoding, adding domain-specific information if you like, so that it can solve problems with larger numbers of blocks.

Blocks World (BW) consists of a finite number of blocks (think of them as simply cubes) stacked up into towers on a surface called the “table” which is large enough to hold them all if necessary. Each block is on exactly one other block or on the table; each block has at most one other block on top of it; if there is no block on it, it is “clear”. Conventionally, the table always counts as clear, as there is always room for another block on it.

The basic BW planning problem is to change one state of the blocks into another by moving one clear block at a time from the top of a tower onto the top of another tower or onto the table. A block on the table with nothing on it counts as a short tower.

Write an encoding of BW which, when given constraints representing an initial state and a goal state, finds the shortest sequence of moves (of the form “move a to b”) converting the one state into the other.

You will probably find it useful to have “block” and “state” as sorts. To record which block is on which in a state, you can use

      function on(state,block): block {}

since this is more efficient than the traditional

      predicate on(state,block,block) {}

Of course, then the table is a special “block” which is not on anything, can have many other blocks on it but remains clear, and which cannot be moved…

In case you are interested, the definitive paper on BW planning (suspending my natural modesty for a moment) is J. Slaney and S. Thiébaux `Blocks World Revisited’, Artificial Intelligence 2001, pp. 119-153. In that paper you may find some useful information about what to encode for efficiency.

Solver

Sorts:

Vocabulary:

Constraints:

Please log in or create an account to use the solver.

Save Title:

Saved Solutions
Name	Time saved
Class Submissions
Name	Time submitted

Number of solutions:

Time limit:

Pretest limit:

Print finder job:

Print solutions:

Print statistics:

Auto Parser Results

No errors found.