PDDL & Modern Planners
Fast Downward, landmarks and heuristic search planners.
Since 1998, the International Planning Competition has pitted planners against tasks they have never seen, written in one shared language. The winners are not domain experts but domain-independent search engines, and the ideas that won (finite-domain variables, relaxed plans, landmarks, multiple heuristics) are now standard equipment. This lesson takes them apart.
What you’ll learn
- Trace PDDL's versions, and the semantics and complexity of their features: conditional effects, numeric fluents and durative actions.
- Explain Fast Downward's pipeline: translation to finite-domain (SAS⁺) variables, causal graphs, and heuristic search with preferred operators.
- Define landmarks, prove that is the minimum-cost hitting set of disjunctive action landmarks, and compute LM-cut on an example.
- Compare satisficing and optimal planning, including width-based search and its guarantees.
PDDL, version by version
PDDL fixes a common syntax and semantics, so that a planner's input describes a task without saying anything about how to solve it. Each version extended what can be said:
| Version | Year | Adds |
|---|---|---|
| PDDL 1.2 (McDermott et al.) | 1998 | STRIPS with typing; ADL features such as negative, disjunctive and quantified preconditions, and conditional effects |
| PDDL2.1 (Fox & Long) | 2003 | numeric fluents, plan metrics, durative actions |
| PDDL2.2 (Edelkamp & Hoffmann) | 2004 | derived predicates (axioms), timed initial literals |
| PDDL3 (Gerevini & Long) | 2005 | state-trajectory constraints, soft goals and preferences |
| PDDL+ (Fox & Long) | 2006 | continuous processes and exogenous events |
| PPDDL; RDDL | 2004; 2010 | probabilistic effects; factored stochastic dynamics (for the probabilistic tracks) |
| HDDL (Höller et al.) | 2020 | hierarchical task networks |
Expressiveness has a price. Conditional effects can be compiled away, but only at the cost of exponentially many actions or of longer plans. Numeric planning is undecidable in general (Helmert, 2002). Temporal planning with durative actions is EXPSPACE-complete when an action may overlap with copies of itself, and PSPACE-complete when it may not (Rintanen, 2007).
(:durative-action fly
:parameters (?p - plane ?from ?to - city)
:duration (= ?duration (/ (distance ?from ?to) (speed ?p)))
:condition (and (at start (at ?p ?from))
(at start (>= (fuel ?p) (distance ?from ?to))))
:effect (and (at start (not (at ?p ?from)))
(at end (at ?p ?to))
(at end (decrease (fuel ?p) (distance ?from ?to)))))A PDDL2.1 durative action. Its duration depends on numeric fluents, its conditions are checked at the start, and its effects happen at the start or at the end. A temporal planner must schedule such actions in time as well as order them.
Inside Fast Downward
Fast Downward (Helmert, 2006), the code base behind many of today's strongest planners, works in phases. Translation grounds the task and discovers mutex groups by invariant synthesis: sets of facts of which at most one is true in any reachable state, such as the possible locations of one truck. Each group becomes a single finite-domain variable (Helmert, 2009), so the facts for all become one variable, "what is on?". The result is a task in the SAS⁺ formalism (Bäckström & Nebel, 1995).
Search then runs heuristic best-first search over SAS⁺ states. Heuristics can exploit the structure: the causal graph heuristic (Helmert, 2004) solves subproblems along an acyclic causal graph, and the context-enhanced additive heuristic (Helmert & Geffner, 2008) generalizes it together with . Satisficing configurations add three enhancements: preferred operators, the helpful actions of a relaxed plan, are expanded first; heuristics are evaluated lazily, only when a state is expanded; and several open lists, one per heuristic plus preferred-operator lists, are used in alternation.
Landmarks
() Every relaxed plan contains an action from each landmark, by definition, so its set of actions is a hitting set. Hence is at least the minimum hitting-set cost:
() Let be any hitting set, and let be the set of facts reachable from using only actions of . Suppose the goal is not reachable, , and consider the actions that could leave :
is a landmark: since , every relaxed plan must at some point add a fact outside , and the first action that does so has all its preconditions in . Yet , because an action of whose preconditions lie in adds only facts in , by the definition of . That contradicts being a hitting set:
So : some of the actions of , in a suitable order, form a relaxed plan, and . LM-cut computes a family of landmarks with a cost partitioning among them, which lower-bounds every hitting set:
LM-cut (Helmert & Domshlak, 2009) finds such landmarks greedily. Repeat: compute , and stop if the goal costs 0; let each action point to its most expensive precondition; cut the resulting justification graph between the initial facts and the goal; the actions that cross the cut form a landmark ; add to the heuristic and subtract from the cost of every action in . On the delivery task of the Hidden Layer, where , LM-cut finds the four singleton landmarks , , and , and returns .
LM-cut first finds the landmark , with and . After the cost reduction it finds the landmark , where . What heuristic value do these two cuts contribute?
- 5
- 2
- 3
- 9
Show the answer
C. 3
The first cut contributes and lowers the costs to and . The second contributes . Total: 3. Since no unit of an action's cost is spent twice, the sum stays a lower bound on every hitting set, and hence on .
Satisficing, optimal, and width
Satisficing planners want some plan, fast: greedy best-first search with inadmissible heuristics such as or landmark counts, preferred operators and restarts. Optimal planners want a cheapest plan: A* with admissible heuristics (LM-cut, pattern databases, merge-and-shrink abstractions and cost-partitioned combinations of them), or symbolic search, which represents sets of states as binary decision diagrams. The symbolic bidirectional planner SymBA* won the optimal track of the 2014 competition.
Width-based search (Lipovetzky & Geffner, 2012) explores by novelty rather than by estimated distance. The novelty of a newly generated state is the size of the smallest set of facts that it makes true for the first time in the search, and IW() is breadth-first search that prunes every state of novelty greater than .
Key takeaways
- PDDL grew from STRIPS and ADL (1998) to numeric and temporal planning (2.1), derived predicates (2.2), preferences (3), hybrid dynamics (PDDL+) and hierarchy (HDDL); numeric planning is undecidable in general, and temporal planning EXPSPACE-complete.
- Fast Downward translates PDDL into finite-domain SAS⁺ variables using mutex invariants, then runs heuristic search with preferred operators, lazy evaluation and alternating queues; LAMA added landmarks and anytime weighted A*.
- Landmark detection is PSPACE-complete in general. is the minimum-cost hitting set of disjunctive action landmarks, and LM-cut is an admissible approximation: .
- Satisficing planners trade optimality for speed (greedy search, novelty and width); optimal planners pair A* with admissible heuristics or use symbolic search.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Which features did PDDL2.1 introduce?
- Derived predicates and timed initial literals
- Numeric fluents and durative actions
- Preferences and trajectory constraints
- Probabilistic effects
Show the answer
B. Numeric fluents and durative actions
PDDL2.1 (Fox & Long, 2003) added numeric fluents, plan metrics and durative actions, the basis of numeric and temporal planning.
What does the characterization of as a minimum-cost hitting set of disjunctive action landmarks imply for LM-cut?
- LM-cut equals on every task
- LM-cut may exceed when landmarks overlap
- LM-cut is inadmissible, but more informative than
- Its cost-partitioned sum over landmarks is a lower bound on a minimum hitting set, so and LM-cut is admissible
Show the answer
D. Its cost-partitioned sum over landmarks is a lower bound on a minimum hitting set, so and LM-cut is admissible
Each cut is a landmark, and the cost partitioning never spends an action's cost twice, so every hitting set costs at least the sum. Hence .
Deciding whether a given fact is a landmark of a STRIPS task is…
- PSPACE-complete
- polynomial, by relaxed reachability
- NP-complete
- undecidable
Show the answer
A. PSPACE-complete
It is as hard as plan existence itself (Hoffmann, Porteous & Sebastia, 2004). The relaxed-reachability test is sound, so every fact it reports is a landmark, but it is incomplete.
Why do satisficing planners give priority to preferred operators (helpful actions)?
- To guarantee optimal plans
- To detect unsolvable tasks early
- Actions from the first step of the relaxed plan usually lead toward the goal, so expanding their successors first saves many heuristic evaluations
- To compute exactly
Show the answer
C. Actions from the first step of the relaxed plan usually lead toward the goal, so expanding their successors first saves many heuristic evaluations
Preferred operators come from the relaxed plan that is computed anyway for . Searching their successors first focuses the search, and keeping the other successors in a separate queue preserves completeness.
Further reading
- D. McDermott, M. Ghallab, A. Howe, C. Knoblock, A. Ram, M. Veloso, D. Weld & D. Wilkins, "PDDL: the Planning Domain Definition Language," technical report, Yale Center for Computational Vision and Control (1998).
- M. Fox & D. Long, "PDDL2.1: an extension to PDDL for expressing temporal planning domains," Journal of Artificial Intelligence Research 20 (2003), 61–124.
- M. Helmert, "The Fast Downward planning system," Journal of Artificial Intelligence Research 26 (2006), 191–246.
- S. Richter & M. Westphal, "The LAMA planner: guiding cost-based anytime planning with landmarks," Journal of Artificial Intelligence Research 39 (2010), 127–177.
- P. Haslum, N. Lipovetzky, D. Magazzeni & C. Muise, An Introduction to the Planning Domain Definition Language (Morgan & Claypool, 2019).