Stanford Research Institute Problem Solver

Last updated January 20, 2024

The Stanford Research Institute Problem Solver, known by its acronym STRIPS, is an automated planner developed by Richard Fikes and Nils Nilsson in 1971 at SRI International.^[1] 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 languages. 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 $\langle P,O,I,G\rangle$ , in which each component has the following meaning:

$P$ is a set of conditions (i.e., propositional variables);
$O$ is a set of operators (i.e., actions); each operator is itself a quadruple $\langle \alpha ,\beta ,\gamma ,\delta \rangle$ , 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;
$I$ is the initial state, given as the set of conditions that are initially true (all others are assumed false);
$G$ is the specification of the goal state; this is given as a pair $\langle N,M\rangle$ , 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 $\langle P,O,I,G\rangle$ is a function

\operatorname {succ} :2^{P}\times O\rightarrow 2^{P},

where $2^{P}$ is the set of all subsets of $P$ , and is therefore the set of all possible states.

The transition function $\operatorname {succ}$ for a state $C\subseteq P$ , 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:

$\operatorname {succ} (C,\langle \alpha ,\beta ,\gamma ,\delta \rangle )$	= $(C\backslash \delta )\cup \gamma$	if $\alpha \subseteq C$ and $\beta \cap C=\varnothing$
	= $C$	otherwise

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

\operatorname {succ} (C,[\ ])=C

\operatorname {succ} (C,[a_{1},a_{2},\ldots ,a_{n}])=\operatorname {succ} (\operatorname {succ} (C,a_{1}),[a_{2},\ldots ,a_{n}])

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, $[a_{1},a_{2},\ldots ,a_{n}]$ is a plan for $G=\langle N,M\rangle$ if $F=\operatorname {succ} (I,[a_{1},a_{2},\ldots ,a_{n}])$ satisfies the following two conditions:

N\subseteq F

M\cap F=\varnothing

Extensions

The above language is actually the 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 $At$ , and $At(room1)$ means that the robot is in Room1. In this case, actions can have free variables, 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 $I$ 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-complete. Various restrictions can be enforced in order to decide if a plan exists in polynomial time or at least make it an NP-complete problem.^[2]

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.^[3] 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.^[4] 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.^[5]

Related Research Articles

In computational complexity theory, bounded-error quantum polynomial time (BQP) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances. It is the quantum analogue to the complexity class BPP.

In artificial intelligence, with implications for cognitive science, the frame problem describes an issue with using first-order logic to express facts about a robot in the world. Representing the state of a robot with traditional first-order logic requires the use of many axioms that simply imply that things in the environment do not change arbitrarily. For example, Hayes describes a "block world" with rules about stacking blocks together. In a first-order logic system, additional axioms are required to make inferences about the environment. The frame problem is the problem of finding adequate collections of axioms for a viable description of a robot environment.

<span class="mw-page-title-main">Inner product space</span> Generalization of the dot product; used to define Hilbert spaces

In mathematics, an inner product space is a real vector space or a complex vector space with an operation called an inner product. The inner product of two vectors in the space is a scalar, often denoted with angle brackets such as in $. Inner products allow formal definitions of intuitive geometric notions, such as lengths, angles, and orthogonality of vectors. Inner product spaces generalize Euclidean vector spaces, in which the inner product is the dot product or scalar product of Cartesian coordinates. Inner product spaces of infinite dimension are widely used in functional analysis. Inner product spaces over the field of complex numbers are sometimes referred to as unitary spaces . The first usage of the concept of a vector space with an inner product is due to Giuseppe Peano, in 1898.$

The Riesz representation theorem, sometimes called the Riesz–Fréchet representation theorem after Frigyes Riesz and Maurice René Fréchet, establishes an important connection between a Hilbert space and its continuous dual space. If the underlying field is the real numbers, the two are isometrically isomorphic; if the underlying field is the complex numbers, the two are isometrically anti-isomorphic. The (anti-) isomorphism is a particular natural isomorphism.

The uncertainty principle, also known as Heisenberg's indeterminacy principle, is a fundamental concept in quantum mechanics. It states that there is a limit to the precision with which certain pairs of physical properties, such as position and momentum, can be simultaneously known. In other words, the more accurately one property is measured, the less accurately the other property can be known.

Distributions, also known as Schwartz distributions or generalized functions, are objects that generalize the classical notion of functions in mathematical analysis. Distributions make it possible to differentiate functions whose derivatives do not exist in the classical sense. In particular, any locally integrable function has a distributional derivative.

In mathematics, a self-adjoint operator on an infinite-dimensional complex vector space V with inner product $is a linear map A that is its own adjoint. If V is finite-dimensional with a given orthonormal basis, this is equivalent to the condition that the matrix of A is a Hermitian matrix, i.e., equal to its conjugate transpose A * . By the finite-dimensional spectral theorem, V has an orthonormal basis such that the matrix of A relative to this basis is a diagonal matrix with entries in the real numbers. This article deals with applying generalizations of this concept to operators on Hilbert spaces of arbitrary dimension.$

In computational complexity theory, the polynomial hierarchy is a hierarchy of complexity classes that generalize the classes NP and co-NP. Each class in the hierarchy is contained within PSPACE. The hierarchy can be defined using oracle machines or alternating Turing machines. It is a resource-bounded counterpart to the arithmetical hierarchy and analytical hierarchy from mathematical logic. The union of the classes in the hierarchy is denoted PH.

In quantum information theory, a quantum circuit is a model for quantum computation, similar to classical circuits, in which a computation is a sequence of quantum gates, measurements, initializations of qubits to known values, and possibly other actions. The minimum set of actions that a circuit needs to be able to perform on the qubits to enable quantum computation is known as DiVincenzo's criteria.

In quantum mechanics and computing, the Bloch sphere is a geometrical representation of the pure state space of a two-level quantum mechanical system (qubit), named after the physicist Felix Bloch.

In linear algebra and functional analysis, the partial trace is a generalization of the trace. Whereas the trace is a scalar valued function on operators, the partial trace is an operator-valued function. The partial trace has applications in quantum information and decoherence which is relevant for quantum measurement and thereby to the decoherent approaches to interpretations of quantum mechanics, including consistent histories and the relative state interpretation.

In probability theory and statistics, given a stochastic process, the autocovariance is a function that gives the covariance of the process with itself at pairs of time points. Autocovariance is closely related to the autocorrelation of the process in question.

In mathematical economics, the Arrow–Debreu model is a theoretical general equilibrium model. It posits that under certain economic assumptions there must be a set of prices such that aggregate supplies will equal aggregate demands for every commodity in the economy.

In quantum computing, quantum finite automata (QFA) or quantum state machines are a quantum analog of probabilistic automata or a Markov decision process. They provide a mathematical abstraction of real-world quantum computers. Several types of automata may be defined, including measure-once and measure-many automata. Quantum finite automata can also be understood as the quantization of subshifts of finite type, or as a quantization of Markov chains. QFAs are, in turn, special cases of geometric finite automata or topological finite automata.

Generalized context-free grammar (GCFG) is a grammar formalism that expands on context-free grammars by adding potentially non-context-free composition functions to rewrite rules. Head grammar is an instance of such a GCFG which is known to be especially adept at handling a wide variety of non-CF properties of natural language.

In logic, philosophy, and theoretical computer science, dynamic logic is an extension of modal logic capable of encoding properties of computer programs.

This is a glossary for the terminology often encountered in undergraduate quantum mechanics courses.

In computer science, a communicating finite-state machine is a finite state machine labeled with "receive" and "send" operations over some alphabet of channels. They were introduced by Brand and Zafiropulo, and can be used as a model of concurrent processes like Petri nets. Communicating finite state machines are used frequently for modeling a communication protocol since they make it possible to detect major protocol design errors, including boundedness, deadlocks, and unspecified receptions.

The Harrow–Hassidim–Lloyd algorithm or HHL algorithm is a quantum algorithm for numerically solving a system of linear equations, designed by Aram Harrow, Avinatan Hassidim, and Seth Lloyd. The algorithm estimates the result of a scalar measurement on the solution vector to a given linear system of equations.

In machine learning and computer vision, M-theory is a learning framework inspired by feed-forward processing in the ventral stream of visual cortex and originally developed for recognition and classification of objects in visual scenes. M-theory was later applied to other areas, such as speech recognition. On certain image recognition tasks, algorithms based on a specific instantiation of M-theory, HMAX, achieved human-level performance.

References

↑ Richard E. Fikes, Nils J. Nilsson (Winter 1971). "STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving" (PDF). Artificial Intelligence . 2 (3–4): 189–208. CiteSeerX 10.1.1.78.8292 . doi:10.1016/0004-3702(71)90010-5. S2CID 8623866.
↑ Tom Bylander (September 1994). "The Computational Complexity of Propositional STRIPS Planning". Artificial Intelligence. 69 (1–2): 165–204. CiteSeerX 10.1.1.23.199 . doi:10.1016/0004-3702(94)90081-7.
↑ Haslum, Patrik (2007). Reducing Accidental Complexity in Planning Problems. Proceedings of the 20th International Joint Conference on Artificial Intelligence. pp. 1898–1903.
↑ Schmid, Ute (1999). Iterative macro-operators revisited: Applying program synthesis to learning in planning (Technical report). School of Computer Science Carnegie Mellon University. doi: 10.21236/ada363524 .
↑ Sutton, Richard S and Precup, Doina and Singh, Satinder (1999). "Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning". Artificial Intelligence. Elsevier. 112 (1–2): 181–211. doi: 10.1016/s0004-3702(99)00052-1 .{{cite journal}}: CS1 maint: multiple names: authors list (link)