The blocks world is a
planning domain in
artificial intelligence
Artificial intelligence (AI) is intelligence—perceiving, synthesizing, and inferring information—demonstrated by machines, as opposed to intelligence displayed by animals and humans. Example tasks in which this is done include speech re ...
. The algorithm is similar to a set of wooden blocks of various shapes and colors sitting on a table. The goal is to build one or more vertical stacks of blocks. 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. Moreover, some kinds of blocks cannot have other blocks stacked on top of them.
The simplicity of this toy world lends itself readily to classical
symbolic artificial intelligence
In artificial intelligence, symbolic artificial intelligence is the term for the collection of all methods in artificial intelligence research that are based on high-level symbolic (human-readable) representations of problems, logic and search. S ...
approaches, in which the world is modeled as a set of abstract symbols which may be reasoned about.
Motivation
Artificial Intelligence can be researched in theory and with practical applications. The problem with most practical application is, that the engineers don't know how to program an AI system. Instead of rejecting the challenge at all the idea is to invent an easy to solve domain which is called a
toy problem
In scientific disciplines, a toy problem or a puzzlelike problem is a problem that is not of immediate scientific interest, yet is used as an expository device to illustrate a trait that may be shared by other, more complicated, instances of the p ...
. Toy problems were invented with the aim to program an AI which can solve it. The blocks world domain is an example for a toy problem. Its major advantage over more realistic AI applications is, that many algorithms and software programs are available which can handle the situation. This allows to compare different theories against each other.
In its basic form, the blocks world problem consists of cubes in the same size which have all the color black. A mechanical robot arm has to pick and place the cubes. More complicated derivatives of the problem consist of cubes in different sizes, shapes and colors. From an algorithm perspective, blocks world is an
np-hard
In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
search
Searching or search may refer to:
Computing technology
* Search algorithm, including keyword search
** :Search algorithms
* Search and optimization for problem solving in artificial intelligence
* Search engine technology, software for findi ...
and planning problem. The task is to bring the system from an initial state into a goal state.
Automated planning and scheduling
Automation describes a wide range of technologies that reduce human intervention in processes, namely by predetermining decision criteria, subprocess relationships, and related actions, as well as embodying those predeterminations in machines ...
problem are usually described in the Planning Domain Definition Language (
PDDL
The Planning Domain Definition Language (PDDL) is an attempt to standardize Automated planning and scheduling, Artificial Intelligence (AI) planning languages. It was first developed by Drew McDermott and his colleagues in 1998 (inspired by Stanf ...
) notation which is an AI planning language for symbolic manipulation tasks. If something was formulated in the PDDL notation, it is called a domain. Therefore, the task of stapling blocks is a blocks world domain which stays in contrast to other planning problems like the
dock worker robot
A dock (from Dutch ''dok'') is the area of water between or next to one or a group of human-made structures that are involved in the handling of boats or ships (usually on or near a shore) or such structures themselves. The exact meaning vari ...
domain and the monkey and banana problem.
Example setup in blocks world
Theses/projects which took place in a blocks world
*
Terry Winograd
Terry Allen Winograd (born February 24, 1946) is an American professor of computer science at Stanford University, and co-director of the Stanford Human–Computer Interaction Group. He is known within the philosophy of mind and artificial intell ...
's
SHRDLU
SHRDLU was an early natural-language understanding computer program, developed by Terry Winograd at MIT in 1968–1970. In the program, the user carries on a conversation with the computer, moving objects, naming collections and querying the st ...
*
Patrick Winston
Patrick Henry Winston (February 5, 1943 – July 19, 2019) was an American computer scientist and professor at the Massachusetts Institute of Technology. Winston was director of the MIT Artificial Intelligence Laboratory from 1972 to 1997, succe ...
'
Learning Structural Descriptions from Examplesan
Copy Demo*
Gerald Jay Sussman
Gerald Jay Sussman (born February 8, 1947) is the Panasonic Professor of Electrical Engineering at the Massachusetts Institute of Technology (MIT). He received his S.B. and Ph.D. degrees in mathematics from MIT in 1968 and 1973 respectively. ...
's
Sussman anomaly
The Sussman anomaly is a problem in artificial intelligence, first described by Gerald Sussman, that illustrates a weakness of noninterleaved planning algorithms, which were prominent in the early 1970s. Most modern planning systems are not restri ...
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
In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
.
See also
*
Blocksworld
Blocksworld was a physics-based 3D sandbox video game developed by BoldaiAB and Linden Lab released originally for the iPad on 21st November, 2012 in Nordic countries and later worldwide on 6 July 2013. It was later released for the iPhone o ...
from
Linden Lab
Linden Research, Inc., doing business as Linden Lab, is an American technology company that is best known as the creator of ''Second Life''.
The company's head office is in San Francisco, with additional offices in Boston, Seattle, Virginia an ...
*
Toy problem
In scientific disciplines, a toy problem or a puzzlelike problem is a problem that is not of immediate scientific interest, yet is used as an expository device to illustrate a trait that may be shared by other, more complicated, instances of the p ...
References
Sources
*
{{compu-AI-stub
History of artificial intelligence