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.
, in which each component has the following meaning: 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.
Since states are represented by sets of conditions, the transition function relative to the STRIPS instance
, 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: The function
can be extended to sequences of actions by the following recursive equations: 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.
satisfies the following two conditions: 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
In this case, actions can have free variables, which are implicitly existentially quantified.
The initial state is considered fully known in the language described above: conditions that are not in
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.
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.
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.
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.