Simple Algorithm
Artificial Intelligence · Deep Layer · 26 min

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 h+h^+ 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:

VersionYearAdds
PDDL 1.2 (McDermott et al.)1998STRIPS with typing; ADL features such as negative, disjunctive and quantified preconditions, and conditional effects
PDDL2.1 (Fox & Long)2003numeric fluents, plan metrics, durative actions
PDDL2.2 (Edelkamp & Hoffmann)2004derived predicates (axioms), timed initial literals
PDDL3 (Gerevini & Long)2005state-trajectory constraints, soft goals and preferences
PDDL+ (Fox & Long)2006continuous processes and exogenous events
PPDDL; RDDL2004; 2010probabilistic effects; factored stochastic dynamics (for the probabilistic tracks)
HDDL (Höller et al.)2020hierarchical task networks
Years are those of the defining papers or reports; each version debuted at a competition held around then.

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).

text
(: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 On(A,x)\mathit{On}(A,x) for all xx become one variable, "what is AA 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 haddh_{\mathrm{add}}. 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

DerivationProof
  1. h+(s) ≥ min⁡{c(H): H∩L≠∅  for all L∈L}h^+(s)\ \ge\ \min\{c(H):\ H\cap L\neq\varnothing\ \text{ for all }L\in\mathcal L\}

    (≥\ge) Every relaxed plan contains an action from each landmark, by definition, so its set of actions is a hitting set. Hence h+h^+ is at least the minimum hitting-set cost:

  2. L={a: pre(a)⊆R, add(a)⊈R}L=\{a:\ \mathrm{pre}(a)\subseteq R,\ \mathrm{add}(a)\not\subseteq R\}

    (≤\le) Let HH be any hitting set, and let RR be the set of facts reachable from ss using only actions of HH. Suppose the goal is not reachable, G⊈RG\not\subseteq R, and consider the actions that could leave RR:

  3. L∈LandL∩H=∅(contradiction)L\in\mathcal L\quad\text{and}\quad L\cap H=\varnothing\qquad(\text{contradiction})

    LL is a landmark: since G⊈RG\not\subseteq R, every relaxed plan must at some point add a fact outside RR, and the first action that does so has all its preconditions in RR. Yet L∩H=∅L\cap H=\varnothing, because an action of HH whose preconditions lie in RR adds only facts in RR, by the definition of RR. That contradicts HH being a hitting set:

  4. hmax⁡ ≤ hLM-cut ≤ h+h_{\max}\ \le\ h_{\text{LM-cut}}\ \le\ h^+

    So G⊆RG\subseteq R: some of the actions of HH, in a suitable order, form a relaxed plan, and h+(s)≤c(H)h^+(s)\le c(H). 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 hmax⁡h_{\max}, 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 LL; add m=min⁡a∈Lc(a)m=\min_{a\in L}c(a) to the heuristic and subtract mm from the cost of every action in LL. On the delivery task of the Hidden Layer, where hmax⁡=3h_{\max}=3, LM-cut finds the four singleton landmarks {Go(A,B)}\{\mathit{Go}(A,B)\}, {Pick}\{\mathit{Pick}\}, {Go(B,C)}\{\mathit{Go}(B,C)\} and {Drop}\{\mathit{Drop}\}, and returns 4=h+=h∗4=h^+=h^*.

Check your understanding

LM-cut first finds the landmark {a,b}\{a,b\}, with c(a)=2c(a)=2 and c(b)=3c(b)=3. After the cost reduction it finds the landmark {b,c}\{b,c\}, where c(c)=4c(c)=4. What heuristic value do these two cuts contribute?

  1. 5
  2. 2
  3. 3
  4. 9
Show the answer

C. 3

The first cut contributes min⁡(2,3)=2\min(2,3)=2 and lowers the costs to c(a)=0c(a)=0 and c(b)=1c(b)=1. The second contributes min⁡(1,4)=1\min(1,4)=1. 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 h+h^+.

Satisficing, optimal, and width

Satisficing planners want some plan, fast: greedy best-first search with inadmissible heuristics such as hFFh_{\mathrm{FF}} 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(kk) is breadth-first search that prunes every state of novelty greater than kk.

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. h+h^+ is the minimum-cost hitting set of disjunctive action landmarks, and LM-cut is an admissible approximation: hmax⁡≤hLM-cut≤h+h_{\max}\le h_{\text{LM-cut}}\le h^+.
  • 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.

Question 1

Which features did PDDL2.1 introduce?

  1. Derived predicates and timed initial literals
  2. Numeric fluents and durative actions
  3. Preferences and trajectory constraints
  4. 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.

Question 2

What does the characterization of h+h^+ as a minimum-cost hitting set of disjunctive action landmarks imply for LM-cut?

  1. LM-cut equals h+h^+ on every task
  2. LM-cut may exceed h+h^+ when landmarks overlap
  3. LM-cut is inadmissible, but more informative than hFFh_{\mathrm{FF}}
  4. Its cost-partitioned sum over landmarks is a lower bound on a minimum hitting set, so hLM-cut≤h+h_{\text{LM-cut}}\le h^+ 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 hLM-cut≤h+h_{\text{LM-cut}}\le h^+ 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 hmax⁡≤hLM-cut≤h+≤h∗h_{\max}\le h_{\text{LM-cut}}\le h^+\le h^*.

Question 3

Deciding whether a given fact is a landmark of a STRIPS task is…

  1. PSPACE-complete
  2. polynomial, by relaxed reachability
  3. NP-complete
  4. 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.

Question 4

Why do satisficing planners give priority to preferred operators (helpful actions)?

  1. To guarantee optimal plans
  2. To detect unsolvable tasks early
  3. Actions from the first step of the relaxed plan usually lead toward the goal, so expanding their successors first saves many heuristic evaluations
  4. To compute h+h^+ 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 hFFh_{\mathrm{FF}}. 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).