Exploding Blocksworld

The exploding Blocksworld domain is a “dead-end” version of the traditional Blocksworld domain described earlier. As in the traditional Blocksworld domain, there are two types of objects (tables and blocks) and two actions (“pick-up-block-from” and “put-down-block-on”). An initial configuration and a goal configuration of the blocks are given and the goal of the domain is to move the blocks from the initial configuration to the goal configuration.

The key difference between this domain and the traditional Blocksworld domain is that every block in the exploding Blocksworld domain is initially set to “detonate”. Every time a “put-down-block” action is executed, if the block that is being put down has not yet detonated it will detonate with probability 0.3; this is the only noise in the domain. If a block detonates when executing a “put-down-block” action, the object beneath the block (whether it is the table or another block) is destroyed and is no longer accessible within the domain. Once a block detonates, it is safe and can no longer detonate.

The exploding Blocksworld domain aims at testing a planner's ability to “think ahead”. More formally, as actions are executed it is possible to reach a state from which the goal cannot be reached. Consider, for example, executing the standard Blocksworld approach in which all blocks are unstacked to the table before the goal configuration is constructed. After seven blocks have been unstacked, there is a 92% ( 1 − (1 − 0.3)⁷) probability that the table is destroyed, rendering the problem unsolvable.

One strategy for solving an exploding Blocksworld problem is to never place an unsafe block on top of something valuable (the table or a block needed in the final stack). Instead, a block should first be “disarmed”, by placing it on top of some block that is not needed for the final configuration, if such a block exists.

We illustrate this strategy on the problem instance that was used in the planning competition, shown in Figure 5. Four blocks are not needed for the goal configuration: 4, 8, 9, and 10. We start by repeatedly picking up Block 0 and placing it on Block 9 until Block 0 detonates. Next, we detonate Block 1 in the same way using Block 10. With both Block 0 and Block 1 safe, we place Block 1 on the table and Block 0 on top of Block 1. This completes the left-most tower. At this stage, there are no safe moves because Blocks 4 and 8 are not clear. We pick up Block 6 and put it on Block 2. The last action leads to failure with probability 0.3. If successful, the right-most tower is completed. Block 8 is now clear and we use it to detonate Block 3. Block 3 is then safely placed on top of Block 5. Finally, the center tower is completed by placing Block 7 on top of Block 3, which can result in failure with probability 0.3. In total, the success probability of the given plan is (1 − 0.3)² = 0.49, which, in fact, is optimal for the given problem (there are no action costs).

Figure 5: Exploding Blocksworld problem used in the planning competition. Note that the goal condition does not require Block 2 to be on the table.

Along with several other test domains, exploding Blocksworld was specifically designed so that a replanning strategy performs suboptimally (gets stuck with high probability). A replanning strategy would be to ignore the 0.3 probability of detonation and try to replan if something unexpected happens. However, there is a high probability that this approach will render the goal state unreachable.