Skip to content
Tutorials Center
My learning

Topics

Lesson 29 of 46 ยท Planning

Classical Planning with STRIPS and PDDL

Learn classical AI planning: states as sets of facts, actions with preconditions and effects, PDDL syntax, the blocks world, and a forward state-space planner in Python.

Search algorithms such as A* find paths through a state space that somebody has already written down. Planning asks a bigger question: how do you describe the world and its actions in a general way, so that one program can solve many different problems? A planner receives a description of the world, a set of things the agent can do, and a goal, and it returns a sequence of actions that achieves the goal.

In this lesson you will learn the standard way to describe such problems (STRIPS), see how the same idea is written in the planning language PDDL, and build a working forward planner for the blocks world in about thirty lines of Python.

What makes a problem "classical"

Classical planning makes a set of simplifying assumptions. They are what allow general-purpose planners to be fast.

  • Fully observable: the agent knows the complete current state.
  • Deterministic: every action has exactly one outcome.
  • Static: nothing changes except through the agent's own actions.
  • Discrete: states, actions and time are discrete steps.
  • Sequential, one action at a time: the answer is a list of actions.

These are the same properties you met in Types of Environments and Agents, picked so that planning becomes a pure reasoning problem. Later chapters relax them: probabilistic reasoning handles uncertainty, and decision making handles stochastic outcomes.

States as sets of facts

In Formulating Search Problems a state was an opaque object, such as a board. Planning instead describes a state as a set of facts (also called atoms or fluents) that are currently true. Everything not in the set is assumed false. This is the closed-world assumption.

For the blocks world, with a robot hand that moves one block at a time, we use these facts:

Fact Meaning
on(x,y) block x sits directly on block y
ontable(x) block x sits on the table
clear(x) nothing is on top of x
holding(x) the hand holds x
handempty the hand holds nothing

A state with block C on block A, and block B alone on the table, looks like this:

TEXT
{ on(C,A), ontable(A), ontable(B), clear(C), clear(B), handempty }

A goal is also a set of facts, but only the ones you care about. A state satisfies the goal when the goal set is a subset of the state. The goal {on(A,B), on(B,C)} does not mention the hand at all, so every state with those two facts qualifies.

Actions: preconditions and effects

A STRIPS action (named after the Stanford Research Institute Problem Solver from 1971) has three parts:

  • Preconditions: facts that must hold for the action to be applicable.
  • Add list: facts that become true.
  • Delete list: facts that become false.

Applying an action to a state s gives (s โˆ’ delete) โˆช add. Anything not mentioned stays unchanged, which neatly avoids the frame problem (having to state everything that does not change).

The four blocks-world actions are:

Action Preconditions Adds Deletes
pickup(x) clear(x), ontable(x), handempty holding(x) clear(x), ontable(x), handempty
putdown(x) holding(x) clear(x), ontable(x), handempty holding(x)
stack(x,y) holding(x), clear(y) on(x,y), clear(x), handempty holding(x), clear(y)
unstack(x,y) on(x,y), clear(x), handempty holding(x), clear(y) on(x,y), clear(x), handempty

x and y are variables. To run a planner, the action schemas are grounded: every variable is replaced by every block, producing concrete actions such as stack(B,C). With three blocks there are 3 pickups, 3 putdowns, 6 stacks and 6 unstacks, 18 actions in total.

graph LR
    S0["Start<br/>C on A, B on table"] -- "unstack(C,A)" --> S1["holding(C)"]
    S1 -- "putdown(C)" --> S2["A, B, C on table"]
    S2 -- "pickup(B)" --> S3["holding(B)"]
    S3 -- "stack(B,C)" --> S4["B on C"]

Each action turns one fact-set into the next; a plan is a path through these states.

The same problem in PDDL

Real planners read problems in PDDL, the Planning Domain Definition Language. A PDDL description has two files: a domain (predicates and action schemas, reusable) and a problem (objects, initial state, goal). This block is read-only; the planner we build below uses the same ideas in Python.

LISP
(define (domain blocks)
  (:requirements :strips)
  (:predicates (on ?x ?y) (ontable ?x) (clear ?x) (holding ?x) (handempty))

  (:action pickup
    :parameters (?x)
    :precondition (and (clear ?x) (ontable ?x) (handempty))
    :effect (and (holding ?x)
                 (not (clear ?x)) (not (ontable ?x)) (not (handempty))))

  (:action stack
    :parameters (?x ?y)
    :precondition (and (holding ?x) (clear ?y))
    :effect (and (on ?x ?y) (clear ?x) (handempty)
                 (not (holding ?x)) (not (clear ?y)))))

(define (problem three-blocks)
  (:domain blocks)
  (:objects a b c)
  (:init (on c a) (ontable a) (ontable b) (clear c) (clear b) (handempty))
  (:goal (and (on a b) (on b c))))

In PDDL a negated effect is the delete list and a positive effect is the add list. Newer versions of the language add numbers, durations, conditional effects and more, but the STRIPS core above is what almost every planner understands. Programs such as Fast Downward read this format.

Building a planner in Python

We represent a state as a frozenset of strings, so it is hashable and can sit in a set or dictionary. An action is a named tuple with its three fact sets. The first example grounds the schemas and shows which actions are applicable in the start state.

Python Grounding actions and applying one

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Only two of the 18 actions are applicable at the start: the hand can pick up B or unstack C from A. Block A is buried, so pickup(A) fails its precondition clear(A).

Forward state-space planning

The simplest planner is plain breadth-first search over states, starting from the initial state. It tries every applicable action, builds the successor states, and stops when a state contains all the goal facts. Because breadth-first search is optimal for equal step costs, the first plan it finds has the fewest actions. A dictionary of parents both prevents revisiting states and lets us rebuild the plan at the end.

Python A breadth-first forward planner

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The planner finds a six-step plan: put C aside, pick up B, stack it on C, then pick up A and stack it on B. The impossible goal returns None, but only after the planner has explored every reachable state, which shows why a complete search can be expensive when no plan exists.

Why planners need heuristics

Three blocks are trivial. The next experiment grows the problem: all blocks start on the table and the goal is a single tower. Watch the number of expanded states.

Python How fast does the search space grow?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each extra block adds roughly a factor of six or seven to the expanded states (4, 20, 119, 842), even though the plan only grows by two steps. This combinatorial explosion is why the next lesson introduces planning heuristics and planning graphs: they estimate the distance to the goal automatically from the STRIPS description, with no human-written heuristic.

Note: Forward search is not the only direction. Backward (regression) search starts from the goal and works out which actions could have produced it. It can avoid irrelevant actions, but the states it manipulates are partial descriptions, which makes it harder to implement. Most modern planners search forward with strong heuristics.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. How is a state represented in STRIPS-style planning?

    A state is the set of true facts. Anything not listed is assumed false (the closed-world assumption).
  2. 2. What is the result of applying an action to state s?

    Delete-list facts are removed, add-list facts are inserted, and everything else stays the same. That is how STRIPS avoids the frame problem.
  3. 3. In the blocks world above, why is pickup(A) not applicable at the start?

    pickup needs clear(A), ontable(A) and handempty. Block C is on A, so clear(A) does not hold.
  4. 4. Why does a breadth-first forward planner return a shortest plan?

    Breadth-first search reaches shallower states first, so with unit-cost actions the first goal state it finds is at minimal depth.
  5. 5. What does the PDDL domain file contain compared with the problem file?

    The domain is reusable across problems. Each problem file instantiates it with objects, an initial state and a goal.

Summary

  • Classical planning assumes a fully observable, deterministic, static world and returns a sequence of actions.
  • STRIPS describes a state as a set of true facts and an action by preconditions, an add list and a delete list.
  • Applying an action computes (state - delete) | add; schemas are grounded into concrete actions.
  • PDDL separates a reusable domain (predicates, action schemas) from a problem (objects, initial state, goal).
  • A breadth-first forward planner over fact sets finds shortest plans but explodes as problems grow.
  • Domain-independent heuristics are the key to scaling up planners.

Next: Planning Heuristics and Planning Graphs.