Planning and STRIPS

And the result of applying it is exactly:

That one line is the whole semantics of an operator and is worth memorising. Note the order: delete first, then add. A literal in both lists survives.

The frame problem, which this representation solves

Worth stating because it is the reason the add and delete lists exist and a paper can ask for it.

Suppose you describe the effect of moving a block using ordinary logic. You must say what changes, and you must also say what does not: the other blocks stay where they are, the table is still a table, the colour of everything is unchanged. Writing all of that out for every action is called the frame problem, and doing it with explicit axioms is hopeless because the list of things that did not change is enormous.

STRIPS solves it by a convention rather than by an axiom: everything not mentioned in the add or delete list is assumed unchanged. That is called the STRIPS assumption, and it is what makes the representation usable. The cost is that an action with far-reaching or conditional effects cannot be expressed.

A complete worked plan

Blocks world. Three blocks. Start with A on B, and both B and C on the table. The goal is a tower: A on B on C.

This problem is chosen because the first step must UNDO part of the goal. on A B is already true at the start and is required at the end, and yet the plan has to take A off B first, because B cannot be stacked onto C while A is sitting on it. A planner that simply worked through the goal literals in order, protecting each one once achieved, would fail here.

# STRIPS: a state is a SET OF LITERALS, an operator has a precondition, an add
# list and a delete list, and a plan is found by forward search. Blocks world.
from collections import deque

def operators():
    """Every legal instance of the three operators, over blocks A, B, C."""
    blocks = ["A", "B", "C"]
    out = []
    for b in blocks:
        for t in blocks:
            if b == t:
                continue
            # move b from the table onto t
            out.append(("stack %s on %s" % (b, t),
                        {"clear " + b, "clear " + t, "on table " + b},
                        {"on %s %s" % (b, t)},
                        {"clear " + t, "on table " + b}))
            # move b from t onto the table
            out.append(("unstack %s from %s" % (b, t),
                        {"clear " + b, "on %s %s" % (b, t)},
                        {"on table " + b, "clear " + t},
                        {"on %s %s" % (b, t)}))
        for t in blocks:
            for u in blocks:
                if len({b, t, u}) != 3:
                    continue
                # move b from t onto u
                out.append(("move %s from %s to %s" % (b, t, u),
                            {"clear " + b, "clear " + u, "on %s %s" % (b, t)},
                            {"on %s %s" % (b, u), "clear " + t},
                            {"on %s %s" % (b, t), "clear " + u}))
    return out

OPS = operators()

def applicable(state, op):
    return op[1] <= state

def apply_op(state, op):
    return (state - op[3]) | op[2]

START = frozenset({"on A B", "on table B", "on table C", "clear A", "clear C"})
GOAL = frozenset({"on B C", "on A B"})

def plan(start, goal):
    """Breadth first over states: the shortest plan, in operators."""
    seen = {start}
    queue = deque([(start, [])])
    while queue:
        state, steps = queue.popleft()
        if goal <= state:
            return steps, state
        for op in OPS:
            if not applicable(state, op):
                continue
            nxt = apply_op(state, op)
            if nxt in seen:
                continue
            seen.add(nxt)
            queue.append((frozenset(nxt), steps + [op]))
    return None, None

def show(state):
    return ", ".join(sorted(state))

print("start:", show(START))
print("goal :", show(GOAL))
print()
steps, final = plan(START, GOAL)
state = START
for i, op in enumerate(steps, 1):
    print("%d. %s" % (i, op[0]))
    print("      precondition %s" % show(op[1]))
    print("      add          %s" % show(op[2]))
    print("      delete       %s" % show(op[3]))
    state = apply_op(state, op)
    print("      state now    %s" % show(state))
print()
print("goal reached:", GOAL <= state)
print("plan length:", len(steps), "operators")

start: clear A, clear C, on A B, on table B, on table C
goal : on A B, on B C

1. unstack A from B
      precondition clear A, on A B
      add          clear B, on table A
      delete       on A B
      state now    clear A, clear B, clear C, on table A, on table B, on table C
2. stack B on C
      precondition clear B, clear C, on table B
      add          on B C
      delete       clear C, on table B
      state now    clear A, clear B, on B C, on table A, on table C
3. stack A on B
      precondition clear A, clear B, on table A
      add          on A B
      delete       clear B, on table A
      state now    clear A, on A B, on B C, on table C

goal reached: True
plan length: 3 operators

Read step 1. on A B was already true, and the plan's first act is to delete it. Then step 3 puts it back. A student asked "why is planning hard" can answer from this one example: achieving one part of a goal can require undoing another, so the order of the subgoals is itself part of the problem.

The classic version of this trap is called the Sussman anomaly: start with C on A, and A and B on the table, and ask for A on B on C. Neither subgoal can be achieved first without undoing the other, and the early planners that worked through goals one at a time and protected what they had achieved could not solve it at all.

Progression and regression

Two directions, and MU's phrase Planning basics expects both to be named.

Regression's advantage is relevance. In a world with a hundred blocks, thousands of operators apply at every state and almost none of them helps. Regression only ever considers operators that achieve something actually wanted. Its difficulty is that a regressed goal is a set of literals that may be inconsistent, or unachievable, and detecting that is not easy.

Partial-order planning, in one paragraph

Named because a paper may ask for it. A total-order plan is a sequence: step 1, then 2, then 3. A partial-order plan commits only to the orderings that matter: stack B on C before stacking A on B, and leave anything independent unordered. The benefit is that independent subproblems can be solved separately and combined, which is the least commitment principle: do not decide anything you do not yet have to. The program above produces a total order because breadth first search over states can produce nothing else.

How planning meets the rest of this book

Two links worth making explicit, because they are the kind of cross-module question Q.3 sets.

A planning problem is a search problem, so every algorithm in MU's second row applies to it. The program above uses breadth first search. Using A* needs a heuristic, and planning's structured state is what lets one be derived automatically: relax the problem by ignoring the delete lists, count how many goal literals remain, and you have an admissible heuristic obtained by exactly the relaxation method of Heuristics: Estimating What Is Left To Do. That is the whole idea of modern planning, and it is why planners got dramatically better in the 1990s.

A planner is a goal-based agent, in the sense of The Goal-Based Agent. It has a goal, a transition model, and it searches action sequences. What it adds is the structure that lets the search be guided.

Distinctions

What it does not mean

A state is not a partial description. Under the closed-world assumption it is complete: anything absent is false. A world in which something is genuinely unknown cannot be represented.

The delete list is not the negation of the add list. They are independent sets, and a literal may appear in both, in which case it survives, because the deletion happens first.

A precondition is not an effect. It is tested and changes nothing.

Planning is not a different problem from search. It is search over a structured state space, and the structure is what allows heuristics to be derived rather than invented.

Achieving the goal literals one at a time does not work. The worked plan deletes on A B, which is part of the goal, at its first step. The Sussman anomaly is the standard example where doing it one at a time fails entirely.

STRIPS does not handle conditional or far-reaching effects. The STRIPS assumption, that anything unmentioned is unchanged, is what buys the compactness and what limits the expressiveness.

Quick revision

• STRIPS: a state is a set of ground literals under the closed-world assumption; anything absent is false. An operator has a precondition, an add list and a delete list.
• new state = (old state minus delete list) union add list. Delete first, then add, so a literal in both survives.
• The frame problem is having to state what does not change. STRIPS solves it by the STRIPS assumption: anything unmentioned is unchanged. That is a convention, not an axiom, and it limits expressiveness.
• The worked plan: unstack A from B, stack B on C, stack A on B. Step 1 deletes a goal literal that step 3 restores, which is why planning is hard. The classic version is the Sussman anomaly.
• Progression searches forward from the start; regression or goal-stack planning searches backward from the goal and considers only relevant operators.
• Partial-order planning commits only to orderings that matter, following least commitment.
• Planning's structured state lets a heuristic be derived: ignore the delete lists and count unachieved goal literals. That is relaxation, and it is why modern planners work.

Test yourself

1. Describe the STRIPS representation of a state and an operator. A state is a set of ground literals, complete under the closed-world assumption so that anything not listed is false. An operator has a precondition, the literals that must be present for it to apply; an add list of literals it makes true; and a delete list of literals it makes false.

2. Give the rule for applying an operator, and say why the order of the two steps matters. The new state is the old state with the delete list removed and the add list added. The deletion happens first, so a literal appearing in both lists survives; doing it the other way round would remove it.

3. What is the frame problem and how does STRIPS deal with it? The frame problem is the need to state, for every action, everything that does not change as well as what does, which is impractical with explicit axioms. STRIPS adopts the convention that anything not mentioned in the add or delete list is unchanged, which is called the STRIPS assumption.

4. Give the three-step plan for building A on B on C from A on B with B and C on the table, and say what is instructive about it. Unstack A from B, stack B on C, stack A on B. It is instructive because the first step deletes on A B, which is part of the goal and was already true at the start: achieving one part of a goal can require undoing another, so the ordering of subgoals is itself part of the problem.

5. Distinguish progression from regression planning. Progression searches forward from the initial state, applying every operator whose precondition holds, which branches very widely. Regression searches backward from the goal: it takes an unachieved goal literal, finds an operator whose add list contains it, and makes that operator's precondition the new goal, so it only ever considers relevant operators.

6. What is a partial-order plan, and what principle does it follow? A plan that commits only to the orderings between steps that actually matter, leaving independent steps unordered. It follows the least commitment principle: do not decide anything you are not yet obliged to decide.

7. How does the STRIPS representation make it possible to derive a heuristic automatically? Because the goal is a set of literals and each operator declares what it adds, the problem can be relaxed by ignoring the delete lists, so nothing achieved is ever undone. The number of goal literals still unachieved in that relaxed problem is then an admissible estimate of the work remaining, obtained by exactly the relaxation method used for search heuristics.