8.1.3 The STRIPS Representation

The previous representation was feature-centric in that, for each feature, there were rules that specified its value in the state resulting from an action. An alternative is an action-centric representation which, for each action, specifies the effect of the action. One such representation is the STRIPS representation. STRIPS, which stands for "STanford Research Institute Problem Solver," was the planner used in Shakey, one of the first robots built using AI technology.

First, divide the features that describe the world into primitive and derived features. Definite clauses are used to determine the value of derived features from the values of the primitive features in any given state. The STRIPS representation is used to determine the values of primitive features in a state based on the previous state and the action taken by the agent.

The STRIPS representation is based on the idea that most things are not affected by a single action. For each action, STRIPS models when the action is possible and what primitive features are affected by the action. The effect of the action relies on the STRIPS assumption: All of the primitive features not mentioned in the description of the action stay unchanged.

The STRIPS representation for an action consists of

  • the precondition, which is a set of assignments of values to features that must be true for the action to occur, and
  • the effect, which is a set of resulting assignments of values to those primitive features that change as the result of the action.

Primitive feature V has value v after the action act if V=v was on the effect list of act or if V was not mentioned in the effect list of act, and V had value v immediately before act. Non-primitive features can be derived from the values of the primitive features for each time.

When the variables are Boolean, it is sometimes useful to divide the effects into a delete list, which includes those variables made false, and an add list, which includes those variables made true.

Example 8.5: In Example 8.1, the action of Rob to pick up coffee (puc) has the following STRIPS representation:
[cs, ¬rhc]

That is, the robot must be at the coffee shop and not have coffee. After the action, rhc holds (i.e., RHC=true), and all other feature values are unaffected by this action.

Example 8.6: The action of delivering coffee (dc) can be defined by
[off, rhc]
[ ¬rhc, ¬swc]

The robot can deliver coffee when it is in the office and has coffee. It can deliver coffee whether Sam wants coffee or not. If Sam wanted coffee before the action, Sam no longer wants it after. Thus, the effects are to make RHC=false and SWC=false.

The feature-based representation is more powerful than the STRIPS representation because it can represent anything representable in STRIPS. It can be more verbose because it requires explicit frame axioms, which are implicit in the STRIPS representation.

A STRIPS representation of a set of actions can be translated into the feature-based representation as follows. If the effects list of an action act is [e1,...,ek], the STRIPS representation is equivalent to the causal rules

ei' ←act.

for each ei that is made true by the action and the frame rules

c' ←c ∧act.

for each condition c that does not involve a variable on the effects list. The precondition of each action in the representations is the same.

A conditional effect is an effect of an action that depends on the value of other features. The feature-based representation can specify conditional effects, whereas STRIPS cannot represent these directly.

Example 8.7: Consider representing the action mc. The effect of mc depends on the robot's location before mc was carried out.

The feature-based representation is as in Example 8.4.

To represent this in the STRIPS representation, we construct multiple actions that differ in what is true initially. For example, mc_cs (move clockwise from coffee shop) has a precondition [RLoc=cs] and effect [RLoc=off].