Sussman Anomaly

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. In the problem, three blocks (labeled A, B, and C) rest on a table. The agent must stack the blocks such that A is atop B is atop C. However, it may only move one block at a time. The problem starts with B on the table, C atop A, and A on the table:

However, noninterleaved planners typically separate the goal (stack A atop B atop C) into subgoals, such as:
# get A atop B
# get B atop C

Suppose the planner starts by pursuing Goal 1. The straightforward solution is to move C out of the way, then move A atop B. But while this sequence accomplishes Goal 1, the agent cannot now pursue Goal 2 without undoing Goal 1, since both A and B must be moved atop C:

If instead the planner starts with Goal 2, the most efficient solution is to move B. But again, the planner cannot pursue Goal 1 without undoing Goal 2:

The problem was first identified by Sussman as a part of his PhD research. Sussman (and his supervisor, Marvin Minsky) believed that intelligence requires a list of exceptions or tricks, and developed a modular planning system for "debugging" plans. Most modern planning systems can handle this anomaly, but it is still useful for explaining why planning is non-trivial.

ee also

*STRIPS
*Automated planning

ources

*Russell Norvig 2003 | pages = 414
*G.J. Sussman (1975) "A Computer Model of Skill Acquisition" Elsevier Science Inc. New York, NY, USA. Book version of his PhD thesis.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Outline of artificial intelligence — The following outline is provided as an overview of and topical guide to artificial intelligence: Artificial intelligence (AI) – branch of computer science that deals with intelligent behavior, learning, and adaptation in machines. Research in AI …   Wikipedia

  • List of Star Trek regions of space — Several films and episodes of the science fiction franchise Star Trek were set in distinct regions of space. Some of these fictional locations exhibited anomalous physical properties. Others were defined as sensitive buffer zones under political… …   Wikipedia

  • Jupiter — This article is about the planet. For other uses, see Jupiter (disambiguation). Jupiter   …   Wikipedia

  • Pluto — This article is about the dwarf planet. For other uses, see Pluto (disambiguation). Pluto   …   Wikipedia

  • Charles Fort — For other uses of Charles Fort , see Charles Fort (disambiguation). Charles Fort Charles Fort in 1920. Born Charles Hoy Fort August 6, 1874(1874 08 06) …   Wikipedia

  • T'Pol — Star Trek character|if=|Title = T Pol bgcolor = #ccccff imagesize = 220px Caption = Sub Commander T Pol Species = Vulcan Gender = Female Birth = circa 2088 Planet = Vulcan Affiliation = Starfleet (formerly Vulcan High Command) Rank = Sub… …   Wikipedia

  • List of Star Trek novels — This is a list of the various Star Trek novels, novelisations, and short story collections that have been published since 1968. Through this time, three main companies have published Star Trek fiction: Bantam Books (from 1967 to 1981), Ballantine …   Wikipedia

  • Big Bang Theory — Seriendaten Originaltitel: The Big Bang Theory Produktionsland: USA Produktionsjahr(e): seit 2007 Episodenlänge: etwa 22 Minuten Episodenanzahl: 38+ in 2+ Staffeln Originalsprache …   Deutsch Wikipedia

  • Tbbt — Seriendaten Originaltitel: The Big Bang Theory Produktionsland: USA Produktionsjahr(e): seit 2007 Episodenlänge: etwa 22 Minuten Episodenanzahl: 39+ in 2+ Staffeln Originalsprache …   Deutsch Wikipedia

  • Natural computing — For the scientific journal, see Natural Computing (journal). Natural computing, also called Natural computation, is a terminology introduced to encompass three classes of methods: 1) those that take inspiration from nature for the development of… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”