Classical planning

Intelligent Systems for Robotics · Week 6

Syllabus · Home

Week 2 gave every skill declared preconditions and effects. Week 5 gave the robot a map and a belief graph of the drinks it has seen. This week a planner puts the skills in order. You turn the skill catalogue into a planning domain and the graph into a planning problem, solve a fetch, and measure how much a heuristic saves over blind search.

Objectives

What the planner sees

A classical planner takes two inputs. The domain states the actions, each with its parameters, preconditions and effects. The problem states the objects, the initial state and the goal. You already have both. The domain comes from the skill catalogue in isfr/skills/catalogue.py. The problem comes from the map and the belief graph of week 5, and from a task that says where the robot starts and who wants which drink.

Not every skill becomes an action. SkillSpec has a field plannable, and the catalogue sets it false for three skills. go-to drives one edge of the map, and the planner never chooses edges. navigate-to runs week 5's route search and drives each edge of the route with go-to. ik-solve declares no effects, and no skill's precondition uses the one atom detect makes true. The six that remain are navigate-to, place-base-for, reach-to, grasp, release and hand-over. The planner sees navigate-to and never go-to, so the route search stays outside the planning problem.

navigate-to has the preconditions (at ?from) and (reachable ?from ?to). The planner has no map, so it cannot decide reachability itself. The generator decides it when it writes the problem. reachable(kg) returns every ordered pair of places joined by a route of unblocked edges, and the generator writes one reachable fact for each pair. This week the pairs include each place with itself. Week 7's meta-actions start by driving to the drink, and with the reflexive pair they still apply when the robot already stands there. The price is one navigate-to from each place to itself. It changes nothing, and no shortest plan contains it.

STRIPS

In STRIPS a state is a set of ground atoms. An atom such as (at worktop_place) is true when it is in the set. An atom outside the set is false, and the section on the closed world returns to that.

Fikes and Nilsson (1971), section 3.2, describe an operator by its preconditions and two lists. The delete list holds the clauses that might no longer be true after the operator is applied. The add list holds the clauses that are true afterwards. Their example is the operator push(k, m, n). An operator applies in a state when its preconditions hold there.

A skill's declaration already has this shape. Its preconditions are the operator's preconditions. Its positive effects are the add list, and its negated effects the delete list. For navigate-to the add list is (at ?to) and the delete list is (at ?from).

Poole and Mackworth, section 6.1.2, state the STRIPS assumption. A feature that an action does not mention is unchanged by it. That is why a skill can declare two effects and leave the rest of the apartment alone. navigate-to says nothing about the gripper, so the gripper holds what it held before the drive.

The catalogue's entries contain variables, so each is an action schema. Grounding substitutes an object of the right type for each variable, and each substitution gives one ground action. The planner grounds the schemas over the problem's objects before it searches. navigate-to has two place parameters, and the apartment's map has 22 places. Grounding gives $22 \times 22 = 484$ navigate-to actions, and 22 of them drive from a place to itself. The registry is a set of schemas. The search runs over their groundings.

PDDL

PDDL, the Planning Domain Definition Language, writes STRIPS down in two files. Fox and Long (2003) credit it to McDermott and the committee of the 1998 planning competition. The domain file declares types, predicates and actions. The problem file declares objects, the initial state and the goal. One domain serves many problems.

Here is Gripper, the domain of this week's example, after the 1998 competition. A robot with two grippers carries balls between two rooms.

(define (domain gripper)
  (:requirements :strips :typing)
  (:types room ball gripper)
  (:predicates (at-robby ?r - room) (at ?b - ball ?r - room)
               (free ?g - gripper) (carry ?b - ball ?g - gripper))
  (:action move
    :parameters (?from - room ?to - room)
    :precondition (at-robby ?from)
    :effect (and (at-robby ?to) (not (at-robby ?from))))
  (:action pick
    :parameters (?b - ball ?r - room ?g - gripper)
    :precondition (and (at ?b ?r) (at-robby ?r) (free ?g))
    :effect (and (carry ?b ?g) (not (at ?b ?r)) (not (free ?g))))
  (:action drop
    :parameters (?b - ball ?r - room ?g - gripper)
    :precondition (and (carry ?b ?g) (at-robby ?r))
    :effect (and (at ?b ?r) (free ?g) (not (carry ?b ?g)))))

:requirements names the parts of the language the domain uses, here STRIPS and types. Each parameter has a type, and grounding substitutes only objects of that type. Without types, pick would also be grounded with a room in the place of the ball. Each (not ...) in an effect is an entry in the delete list. pick deletes (at ?b ?r) and (free ?g), so the ball leaves the room and the gripper is no longer free. Here is the problem for two balls.

(define (problem gripper-problem)
  (:domain gripper)
  (:objects rooma roomb - room left right - gripper ball1 ball2 - ball)
  (:init (at ball1 rooma) (at ball2 rooma) (free left) (free right) (at-robby rooma))
  (:goal (and (at ball1 roomb) (at ball2 roomb))))

The fetch domain is yours to write in the micro-project, so one skill stands for the rest here. The catalogue declares release as follows:

SkillSpec(
    name="release",
    parameters=("obj",),
    preconditions=(Atom("holding", ("?obj",)),),
    effects=(Atom("gripper-empty"), Atom("holding", ("?obj",), negated=True)),
    ...
)

As a PDDL action it reads:

(:action release
  :parameters (?obj - drink)
  :precondition (holding ?obj)
  :effect (and (gripper-empty) (not (holding ?obj))))

The parameter's type follows from its name. In the catalogue obj is always a drink, and from, to and place are always places.

The original definition of PDDL gave its syntax without a formal semantics (Fox and Long, 2003, page 64). Fox and Long supply one. Their Definition 13, in section 7.1, gives the state that follows a set of actions executed together. For one action $a$ executed in a state $s$ it reduces to

$$s' = (s \setminus \mathit{Del}(a)) \cup \mathit{Add}(a)$$

The deletes apply first, then the adds. The order decides what happens when one atom is on both lists. Take (navigate-to p p), which the reflexive reachable pairs allow. Its add list and its delete list are both $\{(\mathit{at}\ p)\}$. Deletes first give $(s \setminus \{(\mathit{at}\ p)\}) \cup \{(\mathit{at}\ p)\}$, which contains $(\mathit{at}\ p)$, so the robot stays where it was. Applied in the order the catalogue lists them, the add and then the delete, the same effects would leave $(\mathit{at}\ p)$ false, and the robot would be nowhere. Week 5's derivation applied a step's effects in listed order. It now applies the deletes first, for the same reason.

The closed world

Poole and Mackworth, section 5.7, describe the complete knowledge assumption. An agent concludes that an atom is false when it cannot derive that the atom is true. They name this the closed-world assumption, and contrast it with the open-world assumption, under which the agent cannot draw conclusions from a lack of knowledge.

The OWL reasoner of week 4 works in the open world. When no sink has been seen from any of a room's places, the room's type is unknown. A PDDL initial state works in the closed world. Every atom the problem file does not state is false. A state is a set of atoms, and a set has no third value for an atom the file left out.

The generator is therefore where the assumption is made. It reads an open-world graph and writes a closed-world state, and every atom it leaves out becomes an atom the planner treats as false. A drink the robot has not grounded has no object-at atom, so no plan fetches it. A person the task does not name is at no place, so no plan hands them anything.

A blocked edge is an absent fact. The fetch domain has no predicate for a blocked edge. When the belief graph marks an edge blocked, reachable(kg) skips it, and any pair of places that only that edge joined loses its reachable fact. Task c of the micro-project shuts off the kitchen, and the third written question asks you which fact the problem then lacks.

The example shows the same on Gripper. It removes (at-robby rooma) from the initial state, and Fast Downward reports no plan. Every action needs the robot in a room, and no action can put it in one from nowhere.

State-space search

Poole and Mackworth, section 6.2, describe forward planning as search in the state space. Each node is a state. Its neighbours are the states that the actions applicable in it lead to, each computed by the transition above. The search starts at the initial state and stops at a state that satisfies the goal, and the path to that state is the plan.

Breadth-first search expands nodes in order of depth. It expands every state one action from the start, then every state two actions away, and so on. When every action costs the same, the first goal state it reaches ends a shortest plan. Uniform-cost search orders the frontier by path cost instead. Poole and Mackworth, section 3.5.4, describe it as lowest-cost-first search, and week 5 used it for routes. With every action at cost 1, path cost equals depth, and the two searches differ only in how they break ties. Both are blind. Neither uses the goal to choose which node to expand next.

The branching factor is the number of actions applicable in a state. The apartment's map is connected, so 22 navigate-to actions apply wherever the robot stands, one to each place, its own included. The manipulation skills add a few more where a drink or a person is. With the reference encoding of the apartment problem, blind search expands 2583 nodes on the one-drink task and 95770 on the two-drink task. Your own counts depend on your encoding. Part 3 of the micro-project asks you why the second count is so much larger.

Gripper shows the growth in a domain small enough to read whole. The example runs blind search for 2 to 10 balls. The shortest plans have 5, 11, 17, 23 and 29 steps, six more for every two balls, since each trip carries two. Blind search expands 253 nodes for 4 balls, 1853 for 6, 11773 for 8 and 68605 for 10, a factor of 5.8 to 7.3 for every two balls added. Each ball is in one of four positions, either room or either gripper, and at most one ball is in each gripper, so the number of states grows exponentially with the number of balls. Blind search has nothing to tell it which of those states lead towards the goal.

Forward search is one way to plan among several. Poole and Mackworth's chapter 6 also covers regression planning in section 6.3, planning as a CSP in section 6.4, and partial-order planning in section 6.5. The planners you run this week all search forwards, and the course uses forward search only.

Heuristics by relaxation

A heuristic for a state estimates the cost of solving the goal from that state (Poole and Mackworth, section 6.2). On the map of week 5 the route search had straight-line distance to use. A planner has no distance of any kind between its states, since no geometry relates them. The estimate therefore has to come from the domain itself. The recipe is always the same. Make the problem easier, solve the easier problem, and use its cost.

Hoffmann and Nebel (2001), Definition 4, make the problem easier by ignoring the delete lists of all actions. In the relaxed task an atom, once true, stays true. Applying (move rooma roomb) in the real task deletes (at-robby rooma) and adds (at-robby roomb). In the relaxed task it adds (at-robby roomb) and deletes nothing, so the robot is in both rooms at once. A gripper that picks a ball is still free, and a ball that is picked up is still on the floor. Nothing an action does can undo another action's work.

Solve the relaxed task by hand. Take Gripper with 10 balls in rooma, the robot in rooma and both grippers free, and the goal of all 10 balls in roomb. Pick all 10 balls, since a gripper that picks a ball never stops being free. Move once. Drop all 10 balls, since the robot is still in roomb after each drop. That is 10 picks, 1 move and 10 drops, so the optimal relaxed plan has 21 steps.

Write $h^{+}$ for the length of an optimal relaxed plan. Every plan for the real task is also a plan for the relaxed one, since ignoring deletes only ever leaves more atoms true. So $h^{+}$ never exceeds the length of an optimal real plan, $h^{*}$. A heuristic with that property is called admissible: it never overestimates. The shortest real plan for this state has 29 steps, and $21 \le 29$.

Hoffmann and Nebel, section 4, citing Bylander (1994), note that computing $h^{+}$ is NP-hard. A planner that used it would solve an NP-hard problem at every state it evaluates, only to decide which state to look at next. Planners therefore estimate $h^{+}$. There are two ways to do it, and the course names three heuristics between them.

The first way costs each atom, and then combines the costs of a set of atoms. From the state above, every pick in rooma applies, so each (carry b g) costs 1. move applies, so (at-robby roomb) costs 1. A drop in roomb needs both of those, and the two ways of paying for a set of preconditions are the two heuristics. Taking the worse one gives $1 + \max(1, 1) = 2$, which is $h_{\max}$. Adding them up gives $1 + (1 + 1) = 3$, which is $h_{\mathrm{add}}$. Everything else in the two definitions is the same.

Now take all 10 goal atoms. Under $h_{\max}$ the goal costs the largest of ten 2s, which is 2. Under $h_{\mathrm{add}}$ it costs the sum of ten 3s, which is 30. Each ball's cost includes the move, and the sum walks down all ten branches, so it pays for one shared move ten times. The maximum walks down one branch, and ten identical branches look like one.

EstimateValueAgainst the shortest plan of 29
$h_{\max}$2Below. It counts one ball.
$h^{+}$21Below. It counts one move.
$h_{\mathrm{add}}$30Above. It counts the move once for every ball.

One state above 29 is enough to show that $h_{\mathrm{add}}$ is not admissible, since admissibility is a promise about every state. $h_{\max}$ is admissible, and it reports 2 here whatever the number of balls, because the goal atoms are independent and equally cheap and the maximum sees one of them. An admissible heuristic that reports 2 for a 29-step problem barely orders the frontier at all, and the example's table measures what that costs.

The second way finds a relaxed plan without insisting that it is the shortest. Hoffmann and Nebel's FF heuristic, $h_{\mathrm{FF}}$, works back from the goal, extracts one relaxed plan and counts its actions, counting a shared action once. On the state above it extracts the 21 steps found by hand, so $h_{\mathrm{FF}} = 21$. Its relaxed plan is not guaranteed to be optimal, so $h_{\mathrm{FF}}$ is not admissible (Hoffmann and Nebel, footnote 2). Being below 29 on one state shows nothing to the contrary.

A* orders the frontier by the cost so far plus the heuristic. With an admissible heuristic it returns a shortest plan whenever a plan exists, by Poole and Mackworth's Proposition 3.1, which week 5 stated. Greedy best-first search orders the frontier by the heuristic alone. It ignores the cost so far, and it gives no guarantee on plan length. FF itself searches by enforced hill-climbing, and when that fails it starts again with complete greedy best-first search (Hoffmann and Nebel, section 5.1 and page 267). The pairing that matters for part 3 of the micro-project is an admissible heuristic with A*, and an inadmissible one with greedy best-first search.

The example's table shows the three searches on Gripper. A* with $h_{\max}$ returns the shortest plan for every number of balls. For 10 balls it expands 68368 nodes, against blind search's 68605, and takes 17.73 s, against 0.59 s. It computes $h_{\max}$ at every state it evaluates, and blind search computes nothing. A heuristic costs time at every node, and it has to save more nodes than that time is worth. Greedy best-first search with $h_{\mathrm{FF}}$ expands at most 134 nodes up to 10 balls. For 10 balls it returns 37 steps where the shortest plan has 29.

Further reading on the two cost rules

The two rules above are usually written as one recursion, and the lecture does not use it. Give each atom $p$ a cost in the relaxed task from state $s$. An atom true in $s$ costs 0. Any other atom costs one more than the cheapest action that adds it, where an action costs as much as its set of preconditions:

$$h(p; s) = \begin{cases} 0 & \text{if } p \in s \\ \min\limits_{a \,:\, p \in \mathit{Add}(a)} \bigl(1 + h(\mathit{Pre}(a); s)\bigr) & \text{otherwise} \end{cases}$$

What remains is the cost of a set of atoms $C$, such as a set of preconditions or the goal. Bonet and Geffner (2001), section 4, give the two answers worked above.

$$h_{\mathrm{add}}(C; s) = \sum_{p \in C} h(p; s) \qquad h_{\max}(C; s) = \max_{p \in C} h(p; s)$$

Each heuristic applies its own rule inside the recursion as well, so $h(\mathit{Pre}(a); s)$ is a sum under $h_{\mathrm{add}}$ and a maximum under $h_{\max}$. Bonet and Geffner, section 5.3.3, report that with $h_{\max}$ in place of $h_{\mathrm{add}}$, the HSP planners show the same exponential growth on Gripper as the Graphplan-based planners, since $h_{\max}$ is almost useless where subgoals are mostly independent. That is their finding on their own planners, and the example's table is a separate measurement of pyperplan on one machine. Ghallab, Nau and Traverso (2025), section 3.2, cover all three heuristics in one place, with the algorithm that computes $h_{\mathrm{FF}}$ in section 3.2.2. None of this subsection is examined.

Planners as tools

You do not write a search this week. The micro-project is four functions with a planner in the middle of them, and three tools do the searching.

FunctionReadsReturns
domainThe skill catalogueThe PDDL domain
problemThe map, the belief graph and the taskThe PDDL problem
solveBoth files, and an engine nameThe plan, or nothing
stepsThe plan, the graph and the taskSkill calls bound to IRIs

domain never sees the map, and problem never sees a skill's body. It sees the catalogue's names, parameters, preconditions and effects, which is all a planning action is.

unified-planning (Micheli et al., 2025) is a Python library. It builds a planning problem as Python objects, reads and writes PDDL with PDDLReader and PDDLWriter, and calls planners through one interface. OneshotPlanner(name=...) chooses a planner by name. Reading Gripper's two files and solving them takes six lines.

from unified_planning.io import PDDLReader
from unified_planning.shortcuts import OneshotPlanner, get_environment

get_environment().credits_stream = None
problem = PDDLReader().parse_problem("gripper.pddl", "gripper-2.pddl")

with OneshotPlanner(name="fast-downward") as planner:
    result = planner.solve(problem, output_stream=None)

The credits line stops each engine printing its banner. parse_problem takes the domain file first and the problem file second, and swapping them gives a parse error that reads as though the domain is broken. parse_problem_string takes the two as text instead, which is what you want once you generate them.

The result carries three things worth reading. result.status names the outcome, such as SOLVED_SATISFICING, SOLVED_OPTIMALLY or UNSOLVABLE_PROVEN. result.plan is None when no plan exists, so check it before you loop over it. result.log_messages holds the engine's own output, and Fast Downward's holds the line Expanded N state(s), which is where compare.py reads its node count. pyperplan's unified-planning engine reports no count at all, so part 3 runs pyperplan directly and reads its INFO log instead.

if result.plan is None:
    print("unsolvable")
else:
    for step in result.plan.actions:
        print(step.action.name, [p.object().name for p in step.actual_parameters])

Each step carries the action's name and the objects bound to its parameters, and that pair is what steps turns back into a skill and its IRIs.

What you seeWhat it means
result.plan is NoneThe planner proved there is no plan. That is a result, not an error.
A PDDLReader parse errorThe file you wrote is malformed. check.py names it and skips that task.
A step whose precondition fails on replayYour action dropped a precondition the skill declares.
No such engineThe engine name is wrong, or the package is not installed.
A configuration past its limitcompare.py stops it and prints timeout.

Task c of the micro-project is unsolvable by design, so a traceback there is a defect in your code rather than in the planner. The third row is the one worth dwelling on. An action that is missing a precondition still produces a plan, and that plan is one the robot cannot run, which is why check.py replays every plan against the catalogue rather than against your encoding.

pyperplan (Alkhazraji et al., 2020) is a planner written in Python, small enough to read. The course installs version 2.1. It names its searches and its heuristics separately, so you can combine them. Its searches include bfs, astar and gbf, and its heuristics include blind, hmax, hadd and hff. If you want to see how a heuristic is computed, its source is the place to read it.

Fast Downward (Helmert, 2006) is a progression planner based on heuristic search. It translates the PDDL task into a multi-valued planning task before it searches, and computes its causal graph heuristic from hierarchical decompositions of that task. It runs in configurations that have names. Through unified-planning, the engine fast-downward runs the configuration lama-first, which returns a plan without a guarantee that it is the shortest. The engine fast-downward-opt runs A* with the LM-cut heuristic and guarantees a shortest plan, and check.py uses it by default.

A configuration is a choice of search and heuristic, and the choice decides what the planner guarantees. Part 3 runs four. Breadth-first search guarantees a shortest plan when every action costs the same, and A* with $h_{\max}$ guarantees one. Greedy best-first search with $h_{\mathrm{FF}}$ and lama-first guarantee none. The guarantee comes from the heuristic being admissible, and not from the search being clever.

What a plan is not, and the project

A plan is a sequence of skill calls with their arguments. The planner assumed that each call has its declared effects. On the robot, any call can terminate in failure, as the skill model of week 2 allows, and the rest of the plan then rests on a state that does not hold. Week 8 executes plans, detects the failure and repairs it.

While the course's planner was being built, grasp(?obj ?place) had only the preconditions (gripper-at ?obj) and (gripper-empty), so nothing bound ?place. The planner returned a fetch that placed the base at the drink, drove away, and reached and grasped with ?place bound to a place the robot was not at. The plan was valid for the domain and useless for the robot, and adding (at ?place) and (object-at ?obj ?place) to grasp's preconditions fixed it. A replay against the same model cannot find such a gap, since it checks the plan against the preconditions that let it through.

Week 7 adds meta-actions, fixed compositions of skills, each one action in the domain with its preconditions and effects derived from its steps, and compares plans with and without them. This week varies the search with the domain fixed. Week 7 varies the domain with the search fixed.

In the micro-project you write the domain from the six plannable skills, and the problem from the apartment's map, its belief graph and a task file. You solve four fetch tasks, map each plan step back to a registered skill with its arguments as IRIs, and let a provided script replay every plan against the catalogue. One task shuts off the kitchen and has no plan. You then run four search configurations on two of the tasks and explain what the table shows.

The project is marked on the two things the course page has stated since week 1. The first is integration, meaning how far separately built parts have been made into one system. The second is the understanding you can demonstrate of why your system is put together the way it is. The rest of the project's detail follows separately.

Before week 7, run the example, read Poole and Mackworth, sections 6.1 and 6.2, and start the micro-project with the domain.

Slides

Deck for this week

Example

Run from the repository root:

PYTHONPATH=. python3 examples/06-classical-planning/main.py

It solves Gripper for two balls with Fast Downward and prints the plan. It then runs blind, admissible and greedy search for 2 balls upwards and prints each plan's length, the nodes expanded and the seconds taken. Last, it removes (at-robby rooma) and asks for a plan again. Nothing in it needs Webots, and it does not use the fetch domain. Read gripper.pddl before main.py.

Micro-project

This week's exercise is exercises/06-classical-planning/. Its README.md states the task and ends in a Self Check list you can verify unaided. The instructor's version is published in data/reference/week-06/ after the deadline.

The micro-project runs from the inputs it provides. It does not need any earlier week's output.

Reading

Further, optional, and not examined:

The tools:

More background, optional: further reading.


Intelligent Systems for Robotics · course materials