Automated Planning
STRIPS, PDDL and searching over actions.
Give a planner a description of what actions do, a start and a goal, and it must invent the sequence itself. Deciding whether any plan exists is PSPACE-complete, yet modern planners routinely solve tasks with astronomically large state spaces. Their trick is to estimate distances by solving an easier problem: one in which nothing is ever deleted.
What you’ll learn
- Define a STRIPS planning task and its state space, and compute successor states and regressed subgoals.
- Derive the delete-relaxation heuristics and , and prove .
- Explain planning graphs, and encode bounded planning as propositional satisfiability.
- Read a PDDL domain and problem, and relate them to the ground STRIPS task that a planner actually searches.
Planning tasks, precisely
The Input Layer described actions by preconditions and effects. To reason about automated planning we need the formal version. In STRIPS, a state is a set of facts read under the closed-world assumption: a fact not in the set is false.
Domains are written with action schemas, which planners ground by substituting objects for parameters. In the blocks world, has precondition , adds and deletes . A schema with parameters over objects has up to ground instances, so is polynomial for fixed arity, while the state space can have up to states.
Three labeled blocks can be arranged on a table in stacks of any height and order. How many distinct states does this blocks world have?
Show the answer
13 states
One tower of three: orders. A tower of two plus a single block: 3 choices for the single block times 2 orders, so 6. Three single blocks: 1. Total: 13. The count grows faster than exponentially: 73 states for 4 blocks, 501 for 5, and 58,941,091 for 10. Planning is search in spaces like these, which no planner enumerates.
Searching forward and backward
Progression searches forward from : the successors of are the states for the applicable actions , and any graph search, from breadth-first search to A*, applies. Regression searches backward from over subgoals, sets of facts that stand for all the states containing them. An action is relevant to a subgoal if it achieves part of it, , and consistent with it if it destroys none of it, . The subgoal that must hold before is then:
Goal: on on . Let move from the table onto :
is relevant (it adds ) and consistent (it deletes nothing in ), so:
Regress instead through , which moves from the table onto . It is relevant, and consistent because does not mention , yet the result is a subgoal that no reachable state satisfies: if is on , then is not clear.
Regression planners prune such subgoals with state invariants (mutexes), sets of facts that never hold together. Discovering invariants automatically is a standard preprocessing step of modern planners.
has precondition , adds and deletes . What is for ?
- Undefined: the action is inconsistent with , because it deletes
Show the answer
B.
Remove what the action achieves, , and add its precondition: . The action is consistent with because it deletes nothing in .
Heuristics from the delete relaxation
Delete lists are what make planning hard: achieving one goal can destroy another. The delete relaxation drops them. Facts then only accumulate, so a relaxed plan never has to re-achieve anything, and every real plan is also a relaxed plan. The cost of an optimal relaxed plan from is therefore an admissible heuristic, . Deciding whether a relaxed plan exists takes polynomial time, but computing is NP-hard (Bylander, 1994). Bonet & Geffner (2001) approximate it by pretending that subgoals are independent:
A robot at , a package at , a corridor ––, and the goal of having the package at . The actions , and cost 1 each. Facts that are true now cost 0:
Moving: needs , and needs :
Picking up at needs and ; the two versions agree here:
Dropping at needs and :
The optimal plan costs . underestimates; overestimates, because it pays for the move twice, once inside and once inside :
FF (Hoffmann & Nebel, 2001) extracts an explicit relaxed plan backward from the goals and counts each action once, so the shared move above is paid for only once; the plan's cost is the heuristic . FF also treats the relaxed plan's first actions as helpful actions to try first. Combined with a greedy local search (enforced hill-climbing), this made FF the most successful fully automatic planner at the AIPS-2000 competition. Like , is not admissible: planners that use it trade optimality for speed.
Planning graphs and planning as satisfiability
Graphplan (Blum & Furst, 1997) builds a planning graph: alternating layers of facts and actions , where holds the actions whose preconditions appear in , and adds their effects (no-op actions carry facts forward). It also records mutexes. Two actions are mutex if one deletes a precondition or an add effect of the other, or if their preconditions are mutex; two facts are mutex if every pair of their achievers is.
Facts and actions only accumulate from layer to layer and mutexes only disappear, so the graph levels off after polynomially many layers, each of polynomial size. If the goals are not all present and pairwise non-mutex at layer , no plan with parallel steps exists, which makes the first layer where they are an admissible estimate. Graphplan searches backward for a plan from that layer, and extends the graph when the search fails.
SATPlan (Kautz & Selman, 1992, 1996) turns "is there a plan with steps?" into a propositional satisfiability problem, with a variable for each fact at each time and a variable for each action at each step :
| Clauses | Meaning |
|---|---|
| for ; for ; for | initial state and goal |
| for | preconditions |
| for ; for | effects |
| , and dually for deletes | explanatory frame axioms: facts change only for a reason |
| for interfering actions | no conflicting actions in parallel |
PDDL, and where to go deeper
PDDL (McDermott et al., 1998), created for the first International Planning Competition, separates a domain (types, predicates and action schemas) from a problem (objects, initial state and goal). Later versions added numeric fluents and durative actions (PDDL2.1, 2003), derived predicates and timed initial literals (PDDL2.2, 2004), preferences and trajectory constraints (PDDL3, for the 2006 competition), and continuous processes and events (PDDL+, 2006). Here is this lesson's delivery task:
(define (domain delivery)
(:requirements :strips :typing)
(:types room box)
(:predicates (robot-at ?r - room) (at ?b - box ?r - room)
(connected ?x ?y - room) (holding ?b - box) (hand-empty))
(:action go
:parameters (?x ?y - room)
:precondition (and (robot-at ?x) (connected ?x ?y))
:effect (and (robot-at ?y) (not (robot-at ?x))))
(:action pick
:parameters (?b - box ?r - room)
:precondition (and (robot-at ?r) (at ?b ?r) (hand-empty))
:effect (and (holding ?b) (not (at ?b ?r)) (not (hand-empty))))
(:action drop
:parameters (?b - box ?r - room)
:precondition (and (robot-at ?r) (holding ?b))
:effect (and (at ?b ?r) (hand-empty) (not (holding ?b)))))
(define (problem deliver-1) (:domain delivery)
(:objects A B C - room pkg - box)
(:init (robot-at A) (at pkg B) (hand-empty)
(connected A B) (connected B A) (connected B C) (connected C B))
(:goal (at pkg C)))Planners first ground the schemas. The action go has groundings, but only the 4 whose static precondition connected holds in the initial state survive: static facts never change, so they are evaluated once, during grounding. Any domain-independent planner, Fast Downward for instance, reads exactly these two definitions.
Key takeaways
- A STRIPS task is , with states as sets of facts and . State spaces explode: 59 million states for just 10 blocks.
- Planners search forward (progression) or backward over subgoals (regression, ), guided by heuristics; plan existence is PSPACE-complete.
- The delete relaxation gives , admissible but NP-hard. , and FF's relaxed-plan heuristic powers fast but suboptimal search.
- Planning graphs (Graphplan) and SAT encodings (SATPlan) attack bounded planning through mutex reasoning and satisfiability; explanatory frame axioms stop facts from changing without a cause.
- PDDL separates domain from problem, and planners ground its schemas into a STRIPS-like task before searching.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
An action has a fact in both its add list and its delete list. Under the semantics , what holds after applying it?
- is false
- keeps its value from
- is true
- The result is undefined
Show the answer
C. is true
Deletes are applied first and adds second, so the add wins: whatever was. PDDL uses the same convention.
Why is STRIPS plan existence in PSPACE, even though it is not known to be in NP?
- Because the number of ground actions is exponential
- Because checking whether a given plan works is PSPACE-hard
- Because the state space is infinite
- Shortest plans can be exponentially long, so a plan cannot serve as a short certificate, but a search can keep just the current state and a step counter
Show the answer
D. Shortest plans can be exponentially long, so a plan cannot serve as a short certificate, but a search can keep just the current state and a step counter
A nondeterministic search guesses one action at a time, storing only the current state ( bits) and a counter up to : polynomial space. Savitch's theorem removes the nondeterminism. The Deep Layer proves the problem PSPACE-complete.
Which of these heuristics is admissible on every STRIPS task?
Show the answer
B.
. The other three can overestimate.
In the delivery example, while the optimal plan costs 4. Why does overestimate?
- It adds up the costs of and independently, so the shared move is counted twice
- It ignores delete effects
- It takes a maximum over preconditions
- Unit action costs make sums inexact
Show the answer
A. It adds up the costs of and independently, so the shared move is counted twice
Both subgoals need the robot at , and charges for getting there in each sum. FF's relaxed-plan extraction counts each action once and gets 4 here.
In a SATPlan encoding, which clauses stop facts from becoming true for no reason?
- The precondition clauses
- The action mutex clauses
- The explanatory frame axioms
- The goal clauses
Show the answer
C. The explanatory frame axioms
says that a fact can become true only if some action that adds it is executed. Without these axioms, a solver can satisfy the goal by "miracles".
Go deeper
- Classical Planning & Its Complexity · Why planning is PSPACE-complete, and heuristics that help.
- PDDL & Modern Planners · Fast Downward, landmarks and heuristic search planners.
- Hierarchical & Probabilistic Planning · HTN planning and planning under uncertainty.
Further reading
- S. Russell & P. Norvig, Artificial Intelligence: A Modern Approach, 4th ed. (Pearson, 2020), chapter 11.
- M. Ghallab, D. Nau & P. Traverso, Automated Planning: Theory and Practice (Morgan Kaufmann, 2004).
- B. Bonet & H. Geffner, "Planning as heuristic search," Artificial Intelligence 129(1–2) (2001), 5–33.
- J. Hoffmann & B. Nebel, "The FF planning system: fast plan generation through heuristic search," Journal of Artificial Intelligence Research 14 (2001), 253–302.