View source for Stanford Research Institute Problem Solver

{{Short description|Automated planner}}
{{Use mdy dates|date=February 2024}} {{Use American English|date=February 2024}}
The '''Stanford Research Institute Problem Solver''', known by its acronym '''STRIPS''', is an [[automated planning|automated planner]] developed by [[Richard Fikes]] and [[Nils Nilsson (researcher)|Nils Nilsson]] in 1971 at [[SRI International]].<ref>{{cite journal|author=Richard E. Fikes, Nils J. Nilsson|title=STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving|url=https://ai.stanford.edu/~nilsson/OnlinePubs-Nils/PublishedPapers/strips.pdf|journal=[[Artificial Intelligence (journal)|Artificial Intelligence]]|doi=10.1016/0004-3702(71)90010-5|date=Winter 1971|volume=2|issue=3–4|pages=189–208|citeseerx=10.1.1.78.8292|s2cid=8623866 }}</ref> The same name was later used to refer to the [[formal language]] of the inputs to this planner. This language is the base for most of the languages for expressing [[automated planning]] problem instances in use today; such languages are commonly known as [[action language]]s. This article only describes the language, not the planner.

==Definition==
A STRIPS instance is composed of:

* An initial state;
* The specification of the goal states – situations that the planner is trying to reach;
* A set of actions. For each action, the following are included:
** preconditions (what must be established before the action is performed);
** postconditions (what is established after the action is performed).

Mathematically, a STRIPS instance is a  quadruple <math>\langle P,O,I,G \rangle</math>, in which each component has the following meaning:

# <math>P</math> is a set of ''conditions'' (i.e., [[propositional variable]]s);
# <math>O</math> is a set of ''operators'' (i.e., actions); each operator is itself a quadruple <math>\langle \alpha, \beta, \gamma, \delta \rangle</math>, each element being a set of conditions. These four sets specify, in order, which conditions must be true for the action to be executable, which ones must be false, which ones are made true by the action and which ones are made false;
# <math>I</math> is the initial state, given as the set of conditions that are initially true (all others are assumed false);
# <math>G</math> is the specification of the goal state; this is given as a pair <math>\langle N,M \rangle</math>, which specify which conditions are true and false, respectively, in order for a state to be considered a goal state.

A plan for such a planning instance is a sequence of operators that can be executed from the initial state and that leads to a goal state.

Formally, a state is a set of conditions: a state is represented by the set of conditions that are true in it. Transitions between states are modeled by a transition function, which is a function mapping states into new states that result from the execution of actions. Since states are represented by sets of conditions, the transition function relative to the STRIPS instance <math>\langle P,O,I,G \rangle</math> is a function

: <math>\operatorname{succ}: 2^P \times O \rightarrow 2^P,</math>

where <math>2^P</math> is the set of all subsets of <math>P</math>, and is therefore the set of all possible states.
 
The transition function <math>\operatorname{succ}</math> for a state <math>C \subseteq P</math>, can be defined as follows, using the simplifying assumption that actions can always be executed but have no effect if their preconditions are not met:

{|
|-
| <math>\operatorname{succ}(C,\langle \alpha,\beta,\gamma,\delta \rangle)</math>
| = <math>(C \backslash \delta) \cup \gamma</math> &nbsp; &nbsp; &nbsp; &nbsp; 
| if <math>\alpha \subseteq C</math> and <math>\beta \cap C = \varnothing</math>
|-
| &nbsp;
| = <math>C</math>
| otherwise
|}

The function <math>\operatorname{succ}</math> can be extended to sequences of actions by the following recursive equations:

:<math>\operatorname{succ}(C,[\ ]) = C</math>
:<math>\operatorname{succ}(C,[a_1,a_2,\ldots,a_n])=\operatorname{succ}(\operatorname{succ}(C,a_1),[a_2,\ldots,a_n])</math>

A plan for a STRIPS instance is a sequence of actions such that the state that results from executing the actions in order from the initial state satisfies the goal conditions. Formally, <math>[a_1,a_2,\ldots,a_n]</math> is a plan for <math>G = \langle N,M \rangle</math> if <math>F=\operatorname{succ}(I,[a_1,a_2,\ldots,a_n])</math> satisfies the following two conditions:

:<math>N \subseteq F</math>
:<math>M \cap F = \varnothing</math>

==Extensions==

The above language is actually the [[propositional logic|propositional]] version of STRIPS; in practice, conditions are often about objects: for example, that the position of a robot can be modeled by a [[Predicate (mathematics)|predicate]] <math>At</math>, and <math>At(room1)</math> means that the robot is in Room1. In this case, actions can have [[free variable]]s, which are implicitly existentially quantified. In other words, an action represents all possible propositional actions that can be obtained by replacing each free variable with a value.
 
The initial state is considered fully known in the language described above: conditions that are not in <math>I</math> are all assumed false. This is often a limiting assumption, as there are natural examples of planning problems in which the initial state is not fully known. Extensions of STRIPS have been developed to deal with partially known initial states.

==A sample STRIPS problem==

A monkey is at location A in a lab. There is a box in location C. The monkey wants the bananas that are hanging from the ceiling in location B, but it needs to move the box and climb onto it in order to reach them.

 Initial state: At(A), Level(low), BoxAt(C), BananasAt(B)
 Goal state:    Have(bananas)

 Actions:
                // move from X to Y
                _Move(X, Y)_
                Preconditions:  At(X), Level(low)
                Postconditions: not At(X), At(Y)
                
                // climb up on the box
                _ClimbUp(Location)_
                Preconditions:  At(Location), BoxAt(Location), Level(low)
                Postconditions: Level(high), not Level(low)
                
                // climb down from the box
                _ClimbDown(Location)_
                Preconditions:  At(Location), BoxAt(Location), Level(high)
                Postconditions: Level(low), not Level(high)
                
                // move monkey and box from X to Y
                _MoveBox(X, Y)_
                Preconditions:  At(X), BoxAt(X), Level(low)
                Postconditions: BoxAt(Y), not BoxAt(X), At(Y), not At(X)
                
                // take the bananas
                _TakeBananas(Location)_
                Preconditions:  At(Location), BananasAt(Location), Level(high)
                Postconditions: Have(bananas)

==Complexity==

Deciding whether any plan exists for a propositional STRIPS instance is [[PSPACE|PSPACE-complete]]. Various restrictions can be enforced in order to decide if a plan exists in [[P (complexity)|polynomial time]] or at least make it an [[NP-complete]] problem.<ref>{{cite journal|author= Tom Bylander|title=The Computational Complexity of Propositional STRIPS Planning|url=http://www.cs.utsa.edu/~bylander/pubs/artificial-intelligence94.ps.gz|journal=Artificial Intelligence|doi=10.1016/0004-3702(94)90081-7|date=September 1994|volume=69|issue=1–2|pages=165–204|citeseerx=10.1.1.23.199}}</ref>

== Macro operator ==

In the [[monkey and banana problem]], the robot monkey has to execute a sequence of actions to reach the banana at the ceiling. A single action provides a small change in the game. To simplify the planning process, it make sense to invent an abstract action, which isn't available in the normal rule description.<ref>{{cite conference |title=Reducing Accidental Complexity in Planning Problems |author=Haslum, Patrik |conference=Proceedings of the 20th International Joint Conference on Artificial Intelligence |pages=1898–1903 |year=2007}}</ref> The super-action consists of low level actions and can reach high-level goals. The advantage is that the [[computational complexity]] is lower, and longer tasks can be planned by the solver. 

Identifying new macro operators for a domain can be realized with [[genetic programming]].<ref>{{cite tech report |title=Iterative macro-operators revisited: Applying program synthesis to learning in planning |author=Schmid, Ute|author-link= Ute Schmid |year=1999 |publisher=School of Computer Science Carnegie Mellon University |doi=10.21236/ada363524|doi-access=free }}</ref> The idea is, not to plan the domain itself, but in the pre-step, a heuristics is created that allows the domain to be solved much faster. In the context of [[reinforcement learning]], a macro-operator is called an option. Similar to the definition within AI planning, the idea is, to provide a temporal abstraction (span over a longer period) and to modify the game state directly on a higher layer.<ref>{{cite journal |title=Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning |author=Sutton, Richard S and Precup, Doina and Singh, Satinder |journal=Artificial Intelligence |volume=112 |number=1–2 |pages=181–211 |year=1999 |publisher=Elsevier |doi=10.1016/s0004-3702(99)00052-1|doi-access=free }}</ref>

==See also==

* [[Action description language]] (ADL)
* [[Automated planning]]
* [[Hierarchical task network]]
* [[Planning Domain Definition Language]] (PDDL)
* [[Sussman anomaly]]

==References==
{{Reflist}}

==Further reading==
* C. Bäckström and B. Nebel (1995). Complexity results for SAS+ planning. ''Computational Intelligence'', 11:625-656.
* T. Bylander (1991). Complexity results for planning. In ''Proceedings of the Twelfth [[International Joint Conference on Artificial Intelligence]] (IJCAI'91)'', pages 274-279.
* {{Russell Norvig 2003}}

[[Category:History of artificial intelligence]]
[[Category:Automated planning and scheduling]]
[[Category:SRI International software]]
[[Category:1971 software]]