Planning: STRIPS and beyond

1. Planning in AI, and the two special cases in robotics

A fundamental need in robotics is to have algorithms that convert high-level specifications of tasks from humans into low-level descriptions of how to move. Two special cases:

• Motion planning — e.g. the Piano Mover's Problem: find a continuous path for a body from one configuration to another among obstacles;
• Trajectory planning — execute the actions defined by the motion planner in a sound and safe way, taking into account dynamics and other constraints (with the contribution of control theory).

Bibliographic support of the deck: S.M. LaValle, Planning Algorithms (Cambridge University Press, 2006, freely downloadable); Russell & Norvig, chapters 11–12; the SRI report on Shakey; and Fikes, Hart and Nilsson, Learning and Executing Generalized Robot Plans, Artificial Intelligence 3 (1972) — the paper of section 9.

2. Basic ingredients of planning

3. Plans: sequences, contingencies, and the three uses

A plan may simply specify a sequence of actions; however, it could be more complicated. If it is impossible to predict future states, the plan may specify actions as a function of state — contingency plans, where the appropriate action is determined from whatever information is available up to the current time (an information state, on which the actions of a plan are conditioned).

Once a plan is determined, there are three ways to use it:

1. Execution: execute it either in simulation or in a mechanical device (robot) connected to the physical world;
2. Refinement: refine it into a better and more detailed plan;
3. Hierarchical inclusion: encapsulate it as an atomic (possibly parametric) action in a higher-level plan.

4. Planning as search in state space, and A*'s limits

Classical planning problems are solved by A* (Chapter 13). But A* has limitations that planning must overcome:

• Forward search → too many useless nodes might be explored;
• language expressiveness quite limited;
• for typical planning problems, heuristics have low effectiveness;
• decomposition of problems not exploited.

A possible solution: a language tailored to planning problems, and backward search — i.e. goal oriented. The prominent case: STRIPS — the STanford Research Institute Problem Solver, developed for Shakey.

5. STRIPS: representation

States and goals

States and goals are defined as conjunctions of literals. E.g. on(alpha,beta) ∧ onTable(beta) means "block alpha is on block beta and block beta is on the table".

Actions

Each operator is described by three entities:

• Preconditions: a conjunction of literals stating what must be true in a state before the action can be executed;
• Effects: a combination of two lists — the add list (what will be true after execution) and the delete list (what will conversely be false).

putdown(Block1,Block2):
  PRECOND:  clear(Block2) ∧ holding(Block1)
  ADD LIST: on(Block1,Block2) ∧ empty
  DELETE LIST: clear(Block2) ∧ holding(Block1)

In the Shakey system (Fikes, Hart & Nilsson, 1972), the robot's knowledge of the world is stored in a model composed of well-formed formulas (wffs) in the predicate calculus — e.g. the robot knows there is a doorway D1 between rooms R1 and R2 by the presence of the wff CONNECTS-ROOMS(D1,R1,R2). Tasks are given as predicate calculus wffs; to direct the robot to go to room R2, we pose the goal wff INROOM(ROBOT,R2). Operators transform one model into another: applying an (assumed applicable) operator deletes from the model all clauses in its delete list and adds all clauses in its add list.

6. The STRIPS algorithm

The main idea: start from the goal and find a relevant action that leads to the goal, i.e. whose effects prove the goal or a subgoal; the preconditions of this action then become the new goal to be proved; the process iterates until the incumbent goal can be directly proved in the current state of the world.

Issues: the goal is in general a conjunction of subgoals → STRIPS tries to satisfy one subgoal at a time; the order in which subgoals are considered is non-deterministic and affects the efficiency, as backtracking might occur; the choice of relevant actions is also non-deterministic, so backtracking might occur there too.

Search algorithm data structures: two data structures — the current state S and a stack of goals. Init: push goal on stack. Stop: empty stack (if not, no more actions to be tried ↔ the instance has no solution with the formulation provided — e.g. because the actions are not sufficient).

1  Select a subgoal and try to establish that it is true in the current
   state. If it is so, go to Step 4. Otherwise:
2  Choose as a relevant action one whose add list specifies clauses
   that allow the incomplete proof of Step 1 to be continued.
3  The appropriately instantiated precondition of the selected
   operator constitutes a new subgoal. Go to Step 1.
4  If the subgoal is the main goal, terminate. Otherwise, remove the
   subgoal from the stack. If now an action is at the top of the
   stack, apply it and change the state S accordingly. Go to Step 1.

Observations from the deck: STRIPS gives good results on rather simple problems; in some cases it is inefficient (see Sussman's anomaly, where satisfying the subgoals one at a time in the wrong order forces backtracking); it might not terminate (in the case of a contradictory goal). Improvements: plan generalisation and failure detection and replanning.

7. Example: the blocks world

The blocks world: a world composed of blocks that can be piled up by a gripper ("hand"), with simple goals, simple actions, deterministic and with complete information.

• Initial state: e.g. block α on the table, block β on the table.
• Goal: α on β — represented as the conjunction on(alpha,beta).
• Solution: pickuptable(alpha), putdown(alpha, beta).

8. Example: fetching a box

The classic Shakey example (Fikes et al., 1972): the robot has to retrieve a box from an adjacent room. Initial model M₀:

INROOM(ROBOT, R1)
CONNECTS(D1, R1, R2)
CONNECTS(D2, R2, R3)
BOX(BOX1)
INROOM(BOX1, R2)

Goal G₀: ∃x [ BOX(x) ∧ INROOM(x, R1) ] — a box in room R1. The two operators (schema variables in lower case, constants in upper case):

GOTHRU(d, r1, r2)         robot goes through Door d from Room r1 into Room r2
  PRECOND:  INROOM(ROBOT, r1) ∧ CONNECTS(d, r1, r2)
  DELETE:   INROOM(ROBOT, $)        (any clause with this predicate form)
  ADD:      INROOM(ROBOT, r2)

PUSHTHRU(b, d, r1, r2)    robot pushes Object b through Door d from Room r1 into Room r2
  PRECOND:  INROOM(b, r1) ∧ INROOM(ROBOT, r1) ∧ CONNECTS(d, r1, r2)
  DELETE:   INROOM(ROBOT, $), INROOM(b, $)
  ADD:      INROOM(ROBOT, r2), INROOM(b, r2)

The STRIPS trace, condensed:

1. Try to prove the overall goal G₀ — fails in the current state.
2. Find a relevant action: PUSHTHRU can satisfy INROOM(BOX1,R1).
3. Push PUSHTHRU(BOX1,d,r1,R1) on the stack, then its preconditions INROOM(BOX1,r1) ∧ INROOM(ROBOT,r1) ∧ CONNECTS(d,r1,R1) — call this G₁.
4. G₁ is not globally satisfied, so satisfy one subgoal at a time: INROOM(BOX1,r1) with r1 = R2; CONNECTS(d,R2,R1) with d = D1. Hence the subgoal INROOM(ROBOT,R2) — in the add list of GOTHRU, so push GOTHRU(d,r1,R2) and its preconditions.
5. The new top goal G₂: INROOM(ROBOT,r1) ∧ CONNECTS(d,r1,R2) — provable with r1 = R1, d = D1.
6. Execute GOTHRU(D1,R1,R2); the current state changes.
7. The remaining stack [INROOM(BOX1,R2) ∧ INROOM(ROBOT,R2) ∧ CONNECTS(D1,R2,R1), PUSHTHRU(BOX1,D1,R2,R1), BOX(x) ∧ INROOM(x,R1)]: the top goal is now satisfied in the current state, so pop.
8. Execute PUSHTHRU(BOX1,D1,R2,R1). The new state satisfies the main goal with x = BOX1. Stack empty: stop.

Solution: GOTHRU(D1,R1,R2), PUSHTHRU(BOX1,D1,R2,R1).

9. Generalized plans and PLANEX

The 1972 paper describes major additions to STRIPS: a process for generalizing a plan produced by STRIPS so that problem-specific constants are replaced by problem-independent parameters. The generalized plan, stored in a convenient format called a triangle table, has two functions: as a single macro action usable by STRIPS (in whole or in part) during the solution of a subsequent problem; and as the basis of PLANEX, the process that monitors the real-world execution of a plan and allows the robot to react "intelligently" to unexpected consequences of actions.

The scenario: the robot is given the task "close window WIND1 and turn off light LITE1". It decides to push box BOX1 to the window, climb on it, close the window, then turn off the light. The system generalizes this specific plan to produce a plan that can, under certain specified conditions, close an arbitrary window and turn off an arbitrary light. During execution, suppose the robot fails to push BOX1 to the window because another box is already under it: PLANEX recognizes that the new box will serve the purpose that BOX1 was to serve, and plan execution proceeds — reexecuting the offending actions with different arguments rather than repeating identically.

Given a new problem, "close window WIND5 and lock door DOOR1", the system recognises that a portion of the old generalized plan can help: the sequence of component actions to close the window is obtained as a single macro action, and the planning time is thereby reduced. Generalisation thus becomes a powerful form of learning: it reduces planning time for similar tasks and allows the formation of much longer plans, previously beyond the combinatoric capabilities of STRIPS.

10. Planning graphs and conditional planning

Planning graphs

A planning graph consists of a sequence of levels that correspond to time steps; each level contains alternatively states or actions. Constraints among states and actions are posted, and CSP solvers are used to find a feasible plan. The graph encodes, level by level, what is possibly true and which actions are possibly applicable, plus mutual-exclusion constraints between incompatible literals/actions — a structure that both upper-bounds the plan length and prunes the search.

Conditional planning

Here the solution is a policy instead of a sequence of actions: a policy specifies what actions to take from which state. Specific actions are introduced to check the state — they are sensing actions. There is no need of replanning, as in principle all the possible plans are combined in a tree structure. Drawbacks: (a) computationally expensive, and (b) — the deck cuts off here, but the direction is clear — the tree of contingencies can grow without bound, which is exactly why conditional planning remains limited to small domains and why the course's reactive alternative (Part II) exists at all.

Check your understanding