foundations of computational agents
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.
In Example 6.1, the action of Rob to pick up coffee () has precondition . That is, Rob must be at the coffee shop (), not carrying coffee () to carry out the action. As a constraint, this means that is not available for any other location or when is true.
The action to move clockwise is always possible. Its precondition is the empty set, , which represents the proposition .
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 has value after action if action was possible (its preconditions hold) and is in the effect of or if is not mentioned in the effect of , and had value immediately before . The values of non-primitive features can be derived from the values of the primitive features for each time.
In Example 6.1, the action of Rob to pick up coffee () has the following STRIPS representation:
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, holds (i.e., ). All other feature values are unaffected by this action.
The action of delivering coffee () can be defined by
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 and . 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.
Consider representing the action to move clockwise. The effect of , where the robot ends up, depends on the robot’s location before 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 (move clockwise from coffee shop) has a precondition and effect . The action (move clockwise from office) has a precondition and effect . STRIPS thus requires four move clockwise actions (one for each location) and four move counterclockwise actions.