6.1 Representing States, Actions, and Goals

6.1.2 The STRIPS Representation

The STRIPS representation is an action-centric representation which, for each action, specifies when the action can occur and the effects of the action. STRIPS, which stands for “STanford Research Institute Problem Solver,” was the planner used in Shakey, one of the first robots built using AI technology.

To represent a planning problem in STRIPS, first divide the features that describe the state of the world into primitive and derived features. The STRIPS representation is used to specify the values of primitive features in a state based on the previous state and the action taken by the agent. 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 for an action consists of

  • the precondition, a set of assignments of values to features that must hold for the action to occur, and

  • the effect, a set of assignments of values to primitive features that specifies the features that change, and the values they change to, as the result of the action.

The precondition of an action is a proposition – the conjunction of the elements of the set – that must be true before the action is able to be carried out. In terms of constraints, the robot is constrained so it can only choose an action for which the precondition holds.

Example 6.3.

In Example 6.1, the action of Rob to pick up coffee (puc) has precondition {cs,¬rhc}. That is, Rob must be at the coffee shop (cs), not carrying coffee (¬rhc) to carry out the puc action. As a constraint, this means that puc is not available for any other location or when rhc is true.

The action to move clockwise is always possible. Its precondition is the empty set, {}, which represents the proposition true.

The STRIPS representation is based on the idea that most things are not affected by a single action. The semantics relies on the STRIPS assumption: the values of all of the primitive features not mentioned in the effects of the action are unchanged by the action.

Primitive feature X has value v after action act if action act was possible (its preconditions hold) and X=v is in the effect of act or if X is not mentioned in the effect of act, and X had value v immediately before act. The values of non-primitive features can be derived from the values of the primitive features for each time.

Example 6.4.

In Example 6.1, the action of Rob to pick up coffee (puc) has the following STRIPS representation:

precondition

{cs,¬rhc}

effect

{rhc}

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

Example 6.5.

The action of delivering coffee (dc) can be defined by

precondition

{off,rhc}

effect

{¬rhc,¬swc}

The robot can deliver coffee when it is in the office and has coffee. The robot does not have coffee after the action, and Sam does not want coffee after the action. Thus, the effects are to make RHC=false and SWC=false. Note that, according this model, the robot can deliver coffee whether Sam wants coffee or not; in either case, Sam does not want coffee immediately after the action.

STRIPS cannot directly define conditional effects, where the effect of an action depends on what is true initially. However, conditional effects can be modeled by introducing new actions, as shown in the following example.

Example 6.6.

Consider representing the action mc to move clockwise. The effect of mc, where the robot ends up, depends on the robot’s location before mc was carried out.

To represent this in the STRIPS representation, we can construct multiple actions that differ in what is true initially. For example, the action mc_cs (move clockwise from coffee shop) has a precondition {RLoc=cs} and effect {RLoc=off}. The action mc_off (move clockwise from office) has a precondition {RLoc=off} and effect {RLoc=lab}. STRIPS thus requires four move clockwise actions (one for each location) and four move counterclockwise actions.