Blocks world

From Wikipedia, the free encyclopedia
Jump to: navigation, search
"Block World" redirects here. For the Xbox 360 video game, see CraftWorld.

The blocks world is one of the most famous planning domains in artificial intelligence. Imagine a set of cubes (blocks) sitting on a table. The goal is to build one or more vertical stacks of blocks. The catch is that only one block may be moved at a time: it may either be placed on the table or placed atop another block. Because of this, any blocks that are, at a given time, under another block cannot be moved.

The simplicity of this toy world lends itself readily to symbolic or classical A.I. approaches, in which the world is modeled as a set of abstract symbols which may be reasoned about.

Theses/projects which took place in Blocks World:

Decision problem (Gupta and Nau, 1992): Given a starting Blocks World, an ending Blocks World, and an integer L > 0, is there a way to move the blocks to change the starting position to the ending position with L or less steps?

This decision problem is NP-hard.[1]

References[edit]

  1. ^ Gupta, N.; Nau, D. "On the Complexity of Blocks-World Planning" (PDF). Artificial Intelligence 56: 223–254.