Classical Planning: STRIPS, PDDL and Planning Graphs

Search algorithms treat states as black boxes. But in many problems the state has an obvious internal structure: the robot is in room A, the box is on the table, the door is closed. Classical planning exploits this structure to solve problems far larger than blind search could handle, using domain-independent heuristics that are computed automatically from the problem description.

Representing planning problems#

The STRIPS representation (Stanford Research Institute Problem Solver, 1971), used to control the robot Shakey, describes:

• States as conjunctions of ground, positive facts (the closed-world assumption: anything not mentioned is false).
• Goals as conjunctions of facts that must hold.
• Actions as schemas with preconditions, an add list and a delete list.

Modern planners use PDDL (Planning Domain Definition Language), a standardised descendant used in the International Planning Competition:

(:action move
  :parameters (?r - robot ?from ?to - room)
  :precondition (and (at ?r ?from) (connected ?from ?to))
  :effect (and (at ?r ?to) (not (at ?r ?from))))

(:action pick-up
  :parameters (?r - robot ?b - box ?loc - room)
  :precondition (and (at ?r ?loc) (at ?b ?loc) (hand-empty ?r))
  :effect (and (holding ?r ?b) (not (at ?b ?loc)) (not (hand-empty ?r))))

Applying an action to a state $s$ gives $s' = (s \setminus \text{Del}(a)) \cup \text{Add}(a)$.

Forward (progression) planning#

Start at the initial state and apply applicable actions — ordinary search over states. Naively this looks hopeless because the number of ground actions is huge. It became the dominant approach only once good heuristics were discovered.

Backward (regression) planning#

Start from the goal and work backwards, considering only relevant actions — actions that achieve some goal fact and delete none. Regressing goal $g$ through action $a$ gives

Regression has a lower branching factor, but works with sets of states, which makes heuristics harder to design.

Domain-independent heuristics#

The magic of planning is that heuristics can be derived automatically from the action descriptions by relaxation.

• Ignore-preconditions heuristic: every action is applicable everywhere — the number of steps becomes roughly the number of unsatisfied goals (a set-cover problem).
• Ignore-delete-lists heuristic: actions never undo progress. The resulting relaxed problem is monotone and can be solved (approximately) in polynomial time. The famous FF planner uses the length of a relaxed plan as its heuristic, $h_{FF}$.
• Landmarks: facts that must be true at some point in every valid plan. Counting unachieved landmarks gives powerful heuristics (used by the LAMA planner).

Planning graphs and GraphPlan#

A planning graph is a layered structure alternating fact levels and action levels. Level $S_0$ holds the initial facts, $A_0$ all applicable actions, $S_1$ all facts they might produce, and so on. Mutex (mutual exclusion) links record pairs of actions or facts that cannot co-occur.

• The level at which all goal facts first appear, non-mutex, is an admissible estimate of plan length.
• GraphPlan (1995) extends the graph until goals appear and then searches backwards for a valid plan.

Other approaches#

• Planning as satisfiability (SATPlan): encode "is there a plan of length $T$?" as a SAT formula and hand it to a SAT solver, increasing $T$ as needed.
• Partial-order planning: build plans as partially ordered sets of actions, committing to orderings only when necessary.
• Hierarchical Task Network (HTN) planning: decompose high-level tasks ("build house") into subtasks using methods written by experts — widely used in games and industrial systems.

Beyond classical assumptions#

Classical planning assumes a fully observable, deterministic, static world with instantaneous actions. Real applications relax these:

• Temporal planning handles durations and concurrency.
• Probabilistic planning uses Markov Decision Processes (see the reinforcement-learning track).
• Contingent and conformant planning handle partial observability.
• Replanning / execution monitoring: when the world deviates from the plan, detect it and plan again.

A tiny forward planner#

from collections import deque

def plan(init, goal, actions):
    """actions: list of (name, pre, add, delete) with frozensets of facts."""
    start = frozenset(init)
    frontier, parent = deque([start]), {start: None}
    while frontier:
        s = frontier.popleft()
        if goal <= s:
            steps = []
            while parent[s]:
                s, name = parent[s]
                steps.append(name)
            return steps[::-1]
        for name, pre, add, delete in actions:
            if pre <= s:
                t = (s - delete) | add
                if t not in parent:
                    parent[t] = (s, name)
                    frontier.append(t)
    return None

A = [("move A->B", {"at A"}, {"at B"}, {"at A"}),
     ("move B->A", {"at B"}, {"at A"}, {"at B"}),
     ("pick box", {"at B", "box B", "empty"}, {"holding"}, {"box B", "empty"}),
     ("drop box", {"at A", "holding"}, {"box A", "empty"}, {"holding"})]
A = [(n, frozenset(p), frozenset(a), frozenset(d)) for n, p, a, d in A]
print(plan({"at A", "box B", "empty"}, frozenset({"box A"}), A))