Planning with Certainty

Shakey the Robot

Shakey was one of the first robots built using AI technology at the Artificial Intelligence Center at SRI International (then Stanford Research Institute) in the early 1970s, . Endowed with a limited ability to perceive and model its environment, Shakey could perform tasks that required planning, route-finding, and the rearranging of simple objects. In 1969, the demonstrations of Shakey were collected in a 24-minute film (see the video below to check out Shaky in action). Shakey is now on display at the Computer History Museum in Mountain View, California.

In the context of planning under certainty, what is interesting is the that the planning system of Shakey was built using the STRIPS (Stanford Research Institute Problem Solver) representation. The problem-solving program STRIPS creates a plan consisting of a sequence of actions, and the PLANEXI [4] program carries out the plan by executing the actions. STRIPS is an automated planner developed by Richard Fikes and Nils Nilsson in 1971 at SRI International. Though the STRIPS representation is fairly simple to learn and understand, it is very powerful. We briefly describe the STRIPS representation[1 2 3].

STRIPS representation

STRIPS is an action-centric classical planning language, representing plan components as states, goals, and actions, allowing algorithms to parse the logical structure of the planning problem to provide a solution. In STRIPS, state is represented as a conjunction of positive literals. Positive literals may be a propositional literal(e.g., Big ^ Tall) or a first-order literal (e.g., At(Billy, Desk)). The positive literals must be grounded – may not contain a variable (e.g., At(x, Desk)) – and must be function-free – may not invoke a function to calculate a value (e.g.,At(Father(Billy), Desk)). Any state conditions that are not mentioned are assumed false. The goal is also represented as a conjunction of positive, ground literals. A state satisfies a goal if the state contains all of the conjuncted literals in the goal. Actions (or operators) are defined by action schemas, each consisting of three parts: 1. The action name and any parameters.
2. Preconditions which must hold before the action can be executed. Preconditions are represented as a conjunction of function-free, positive literals. Any variables in a precondition must appear in the action’s parameter list.
3. Effects which describe how the state of the environment changes when the action is executed. Effects are represented as a conjunction of function-free literals. Any variables in a precondition must appear in the action’s parameter list. Any world state not explicitly impacted by the action schema’s effect is assumed to remain unchanged.

The following simple example describes one of Shakey's actions namely - pushing a box from location x to location y:
Action: PushBox(x, y)
Precond: BoxAt(x)
Effect: BoxAt(y), ¬ BoxAt(x)

If an action is applied, but the current state of the system does not meet the necessary preconditions, then the action has no effect. But if an action is successfully applied, then any positive literals, in the effect, are added to the current state of the world; correspondingly, any negative literals, in the effect, result in the removal of the corresponding positive literals from the state of the world. For example, in the action schema above, the effect would result in the proposition BoxAt(y) being added to the known state of the world, while BoxAt(x) would be removed from the known state of the world. (Recall that state only includes positive literals, so a negation effect results in the removal of positive literals.) Note also that positive effects can not get duplicated in state; likewise, a negative of a proposition that is not currently in state is simply ignored. For example, if Open(x) was not previously part of the state, ¬ Open(x) would have no effect. A STRIPS problem includes the complete (but relevant) initial state of the world, the goal state(s), and action schemas. A STRIPS algorithm should then be able to accept such a problem, returning a solution. The solution is simply an action sequence that, when applied to the initial state, results in a state which satisfies the goal.

Now that we have understood the STRIPS representation, we can formulate a STRIPS representation for Shakey's world. Chapter 9 of [5] describes the world for Shakey and the associated STRIPS operators. It also describes two tasks and the plan generated using the STRIPS representation to achieve each of them.

References

1. Russell, Stuart Jonathan, et al. Artificial intelligence: a modern approach. Vol. 74. Englewood Cliffs: Prentice hall, 1995
2. Poole, David, Alan Mackworth, and Randy Goebel. Computational Intelligence. Oxford: Oxford University Press, 1998.
3. Fikes, Richard E., and Nils J. Nilsson. "STRIPS: A new approach to the application of theorem proving to problem solving." Artificial intelligence 2.3 (1972): 189-208.3.
4. Fikes, Richard E. Monitored execution of robot plans produced by STRIPS. No. SRI-TR-55. SRI INTERNATIONAL MENLO PARK CA ARTIFICIAL INTELLIGENCE CENTER, 1971.
5. Nilsson, Nils J. Shakey the robot. SRI INTERNATIONAL MENLO PARK CA, 1984.