STRIPS
In plain wordsAn early AI planning program, and the simple action language it introduced, in which each action lists what must be true beforehand, what becomes true and what stops being true.
- 1
Representation
A formalism for planning problems in which a state is a set of ground atomic facts, such as On(A, B), and each action schema specifies a precondition (facts that must hold), an add list (facts it makes true) and a delete list (facts it makes false). Everything not mentioned is assumed to stay the same — the STRIPS assumption, a pragmatic answer to the frame problemframe problem, n.: The difficulty of getting an AI to work out what does and does not change when something happens, without spelling out every one of the countless things that stay the same.. This simplicity turns planning into pure state space searchstate space search, n.: Solving a problem by treating every situation it could be in as a point on a map, with each possible move as a road between points, and searching for a route from the start to a goal. and lets planners derive heuristicsheuristic, n.: A rule of thumb: a quick, usually good-enough way to make a decision or to estimate how close you are to a goal, without any guarantee of finding the best answer. automatically by relaxation, for example by ignoring delete lists. STRIPS-style action models remain the core of PDDLPlanning Domain Definition Language, prop. n.: A standard computer language for describing planning problems — the available actions, the starting situation and the goal — so that any automated planner can read and solve them. and of most classical automated planningautomated planning, n.: The branch of AI that works out a sequence of actions to reach a goal, such as the steps a robot must take to assemble a part, from descriptions of what each action needs and what it changes..
- 2
Planner
The original program, the Stanford Research Institute Problem Solver, which combined means–ends analysismeans–ends analysis, n.: A problem-solving method that compares where you are with where you want to be, picks an action that shrinks the biggest difference, and sets itself smaller goals when that action cannot yet be taken. with theorem proving to find plans for the mobile robot ShakeyShakey the robot, prop. n.: A wheeled robot built at a California research institute between 1966 and 1972 that could look around, make a plan and carry it out: the first mobile robot to work out its own steps toward a goal., such as pushing boxes between rooms. A 1972 extension generalized successful plans into reusable macro-operators and monitored their execution.
Origin
Developed by Richard Fikes and Nils Nilsson at the Stanford Research Institute (now SRI International) and published in the journal Artificial Intelligence in 1971.
Related
- automated planningautomated planning, n.: The branch of AI that works out a sequence of actions to reach a goal, such as the steps a robot must take to assemble a part, from descriptions of what each action needs and what it changes.
- Planning Domain Definition LanguagePlanning Domain Definition Language, prop. n.: A standard computer language for describing planning problems — the available actions, the starting situation and the goal — so that any automated planner can read and solve them.
- Shakey the robotShakey the robot, prop. n.: A wheeled robot built at a California research institute between 1966 and 1972 that could look around, make a plan and carry it out: the first mobile robot to work out its own steps toward a goal.
- frame problemframe problem, n.: The difficulty of getting an AI to work out what does and does not change when something happens, without spelling out every one of the countless things that stay the same.
- means–ends analysismeans–ends analysis, n.: A problem-solving method that compares where you are with where you want to be, picks an action that shrinks the biggest difference, and sets itself smaller goals when that action cannot yet be taken.
- situation calculussituation calculus, n.: A logical language for describing how the world changes as actions happen, so that a program can work out what will be true after any sequence of actions.
Sources
- Fikes, R. E. & Nilsson, N. J. (1971). STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving. Artificial Intelligence 2(3–4), 189–208.
Mentioned in
automated planningautomated planning, n.: The branch of AI that works out a sequence of actions to reach a goal, such as the steps a robot must take to assemble a part, from descriptions of what each action needs and what it changes., General Problem SolverGeneral Problem Solver, prop. n.: A 1950s program meant to solve any well-defined puzzle by repeatedly comparing where it was with where it wanted to be and choosing steps that closed the gap., blocks worldblocks world, n.: A simplified pretend world of toy blocks on a table that early AI researchers used to test programs for planning, seeing and understanding language, because it was simple enough to describe completely., hierarchical task networkhierarchical task network, n.: A planning method that breaks a big task, such as 'travel to Paris', into smaller tasks, such as 'book a flight' and 'pack', using stored recipes, until only simple actions remain., means–ends analysismeans–ends analysis, n.: A problem-solving method that compares where you are with where you want to be, picks an action that shrinks the biggest difference, and sets itself smaller goals when that action cannot yet be taken., Nils NilssonNils Nilsson, prop. n.: An American computer scientist who co-created the A* search algorithm and the STRIPS planner for Shakey, the first robot to plan its own moves by reasoning, and wrote standard AI textbooks., Planning Domain Definition LanguagePlanning Domain Definition Language, prop. n.: A standard computer language for describing planning problems — the available actions, the starting situation and the goal — so that any automated planner can read and solve them., Shakey the robotShakey the robot, prop. n.: A wheeled robot built at a California research institute between 1966 and 1972 that could look around, make a plan and carry it out: the first mobile robot to work out its own steps toward a goal., situation calculussituation calculus, n.: A logical language for describing how the world changes as actions happen, so that a program can work out what will be true after any sequence of actions., SRI InternationalSRI International, prop. n.: A nonprofit research institute in California, once part of Stanford University, where the Shakey robot was built and the technology behind Apple's Siri assistant began.