Blocksworld (Traditional)

Our traditional Blocksworld domain does not stray far from the original Blocksworld domain. The domain consists of two types of objects, blocks and tables. The domain has exactly one table and each problem instance has some number of blocks (the number of blocks is problem specific). The actions of the domain are “pick-up-block-from” and “put-down-block-on”. For each problem instance, an initial configuration and a goal configuration of the blocks is given. The goal of the problem is to move the blocks from the initial configuration into the goal configuration. This domain comes in two flavors: a goal version and a reward version. Within the reward version, there is a cost of one unit every time the action “pick-up-block-from” is executed, and the reward is 500 for reaching the goal configuration.

As with all of the other domains used in the competition, the Blocksworld domain incorporates probabilistic effects and does so by adding a “slip” probability. That is, each time a block is picked up or put down, the block will slip and fall onto the table with probability 0.25. (Of course, if the intended action is to put the block down onto the table, then this effect will always be achieved.) The Blocksworld domain is an extremely simple domain, yet it offers a lot of insight into the planning process. Two important features of the domain are:

  1. A basic policy to solve the domain is:
    1. From the initial configuration, place all of the blocks onto the table with no block on top of another block.
    2. Starting from the bottom up, place each block into its place in the final configuration.
    Note that without noise, if there are n blocks, this policy takes 4n steps (2 steps for each block on Part 1a, and 2 steps for each block on Part 1b) and hence costs 2n units. So, there is a very basic, very inexpensive way to solve this domain.

  2. The state space of this domain increases exponentially with the number of blocks.

Thus, this domain aims at testing if planners could find the easy (maybe slightly more expensive) policy when the state space was too large to find a good policy. As far as the complexity of this domain is concerned, it is one of the easier domains to plan for and our hope was that many planners would do quite well in this domain.

A generation program for random traditional Blocksworld domains was provided to participants and the competition problems were generated from this same program. The availability of the generator allowed participants to test their planners on as many problems as they liked in advance of the evaluation.

Håkan L. S. Younes
2005-12-06