The Fast Downward Planning System

Malte Helmert

article2006JAIR2,127 citationsWinner of the classical track of the 4th International Planning Competition at ICAPS 2004

Presents the Fast Downward classical planning system, which translates propositional planning tasks into multi-valued representations to enable causal graph heuristics, preferred operators, and multi-heuristic search control techniques.

Listen

Automated planning systems are essential for coordinating complex logistics, scheduling operations, and directing autonomous systems. However, traditional planning approaches struggle to solve large-scale real-world problems because standard binary representations obscure natural problem structure, creating massive search spaces that exhaust available computing time and memory.

The article demonstrates the design, algorithmic framework, and empirical effectiveness of Fast Downward, a classical forward-search planning system. The primary objective is to show that translating standard planning tasks into structured multi-valued representations and exploiting hierarchical problem dependencies dramatically improves search efficiency across diverse benchmark domains.

The system operates via a three-phase pipeline comprising translation, knowledge compilation, and search. It automatically translates binary problem inputs into multi-valued planning tasks, extracts domain transition graphs and causal graphs, and generates optimized data structures to rapidly evaluate states. To navigate the search space, the article evaluates multiple search mechanisms, including a novel causal graph heuristic, multi-heuristic best-first search, deferred heuristic evaluation, preferred operators, and an experimental focused iterative-broadening algorithm. The evaluation tests six planner configurations against state-of-the-art systems across 1,442 benchmark tasks from four international planning competitions, measuring total runtime and task completion under strict resource limits.

The experimental findings show that Fast Downward matches or outperforms the leading state-of-the-art planning systems across a broad range of benchmarks. Multi-heuristic best-first search combined with preferred operators emerged as the top-performing configuration, achieving the best results in 23 out of 29 evaluated domains. Incorporating preferred operators yielded decisive performance gains, solving more tasks in 15 domains and performing worse in only two. Across 550 standard benchmark tasks, this leading configuration left only 22 tasks unsolved compared to 101 for the established LPG planner. Additionally, running configurations in parallel or selecting the best configuration per domain left only 10 unsolved tasks across early competition suites and 54 in the ICAPS 2004 suite, confirming that complementary search algorithms maximize overall problem-solving coverage.

These results establish that multi-valued variable representations provide a significantly better foundation for automated reasoning than classical binary encodings. By shifting problem abstractions into heuristic search, the system avoids the brittleness of earlier hierarchical methods, allowing practical decomposition even in the presence of cyclic dependencies. Organizations relying on complex task planning can achieve substantial reductions in computing time and higher success rates on difficult operational instances without requiring manual problem tuning.

To maximize practical planning performance, deployers should configure the system to use multi-heuristic best-first search with preferred operators as the primary engine. In environments where tasks have varied structural characteristics, implementing a portfolio or scheduler approach that runs heuristic search alongside focused iterative-broadening search is recommended. Future development should incorporate automated goal-ordering techniques to address domain bottlenecks, investigate heuristics that handle causal cycles without pruning, and establish domain-specific guidelines for when alternative planners are preferable.

The conclusions are backed by extensive comparative benchmarks across hundreds of standard test problems, providing high confidence in the robustness of the system. However, readers should note that performance degrades in domains with dense, highly cyclic causal structures—such as block manipulation and certain scheduling tasks—especially when goals require a strict achievement order that the current heuristic does not explicitly model.

Institut für Informatik University of Freiburg automated reasoning engine heuristic evaluation Fast Downward planning system hierarchical planning classical planning system

arXiv: 1109.6051

Paper: STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving, Richard E. Fikes et al. (1971). Read STRIPS first to understand the classical action-precondition and effect representation that Fast Downward translates into its multi-valued planning tasks.
Paper: The FF Planning System: Fast Plan Generation Through Heuristic Search, Jörg Hoffmann et al. (2011). The FF system introduces helpful actions and heuristic forward search, concepts that prepare you to understand Fast Downward’s preferred operators and its comparisons with earlier planners.

No sufficiently relevant recommendations were found.

Cover for The Fast Downward Planning System

Abstract

Fast Downward is a classical planning system based on heuristic search. It can deal with general deterministic planning problems encoded in the propositional fragment of PDDL2.2, including advanced features like ADL conditions and effects and derived predicates (axioms). Like other well-known planners such as HSP and FF, Fast Downward is a progression planner, searching the space of world states of a planning task in the forward direction. However, unlike other PDDL planning systems, Fast Downward does not use the propositional PDDL representation of a planning task directly. Instead, the input is first translated into an alternative representation called multi-valued planning tasks, which makes many of the implicit constraints of a propositional planning task explicit. Exploiting this alternative representation, Fast Downward uses hierarchical decompositions of planning tasks for computing its heuristic function, called the causal graph heuristic, which is very different from traditional HSP-like heuristics based on ignoring negative interactions of operators.

In this article, we give a full account of Fast Downward’s approach to solving multi-valued planning tasks. We extend our earlier discussion of the causal graph heuristic to tasks involving axioms and conditional effects and present some novel techniques for search control that are used within Fast Downward’s best-first search algorithm: preferred operators transfer the idea of helpful actions from local search to global best-first search, deferred evaluation of heuristic functions mitigates the negative effect of large branching factors on search performance, and multi-heuristic best-first search combines several heuristic evaluation functions within a single search algorithm in an orthogonal way. We also describe efficient data structures for fast state expansion (successor generators and axiom evaluators) and present a new non-heuristic search algorithm called focused iterative-broadening search, which utilizes the information encoded in causal graphs in a novel way.

Fast Downward has proven remarkably successful: It won the “classical” (i. e., propositional, non-optimising) track of the 4th International Planning Competition at ICAPS 2004, following in the footsteps of planners such as FF and LPG. Our experiments show that it also performs very well on the benchmarks of the earlier planning competitions and provide some insights about the usefulness of the new search enhancements.

Topics

automated reasoning engine heuristic evaluation logistics reasoning scheduling tasks tabu search task planning

Keywords

Fast Downward planning system hierarchical planning classical planning system incremental planning multi-valued planning relaxed planning Fast Downward configurations planning benchmarks PDDL planning propositional planning

1 Introduction
2 Related Work
2.1 Causal Graphs and Abstraction
2.2 Causal Graphs and Unary STRIPS Operators
2.3 Multi-Valued Planning Tasks
3 Fast Downward
4 Multi-Valued Planning Tasks
5 Knowledge Compilation
5.1 Domain Transition Graphs
5.2 Causal Graphs
5.2.1 Acyclic Causal Graphs
5.2.2 Generating and Pruning Causal Graphs
5.2.3 Causal Graph Examples
5.3 Successor Generators and Axiom Evaluators
5.3.1 Successor Generators
5.3.2 Axiom Evaluators
6 Search
6.1 The Causal Graph Heuristic
6.1.1 Conceptual View of the Causal Graph Heuristic
6.1.2 Computation of the Causal Graph Heuristic
6.1.3 States with Infinite Heuristic Value
6.1.4 Helpful Transitions
6.2 The FF Heuristic
6.3 Greedy Best-First Search in Fast Downward
6.3.1 Preferred Operators
6.3.2 Deferred Heuristic Evaluation
6.4 Multi-Heuristic Best-First Search
6.5 Focused Iterative-Broadening Search
7 Experiments
7.1 Benchmark Set
7.2 Experimental Setup
7.3 Translation and Knowledge Compilation vs. Search
7.4 STRIPS Domains from IPC1–3
7.5 ADL Domains from IPC1–3
7.6 Domains from IPC4
7.7 Conclusions from the Experiment
8 Summary and Discussion
References

Knowls

Knowl 1 — Multi-Valued Planning Task Formalism and Semantics
definition
A Multi-Valued Planning Task (MPT) is a 5-tuple $\Pi = \langle V, s_0, s_*, A, O \rangle$ extending the $\text{SAS}^+$ planning model with axioms and conditional effects:
- $V$ is a finite set of state variables, where each $v \in V$ has a finite domain $\mathcal{D}_v$ . Variables are partitioned into fluents (affected by operators) and derived variables (computed by axioms). The domain of every derived variable contains the undefined value $\bot$ .
- A partial variable assignment $s$ assigns values $s(v) \in \mathcal{D}_v$ to a subset of $V$ . A partial state defined on all fluents is a state (or reduced state); a partial state defined on all variables in $V$ is an extended state.
- $s_0$ is a state over $V$ called the initial state.
- $s_*$ is a partial variable assignment over $V$ called the goal.
- $A$ is a finite set of axioms of the form $\text{cond} \to v := d$ , where $\text{cond}$ is a partial assignment, $v$ is a derived variable, and $d \in \mathcal{D}_v$ . The axiom set is partitioned into totally ordered layers $A_1 \prec \dots \prec A_k$ . Under the layering property, within each layer, an affected variable may be associated with only a single derived value across all heads and bodies.
- $O$ is a finite set of operators $\langle \text{pre}, \text{eff} \rangle$ , where $\text{pre}$ is a partial variable assignment (precondition) and $\text{eff}$ is a finite set of conditional effects of the form $\text{cond} \to v := d$ , where $v$ is a fluent and $d \in \mathcal{D}_v$ .
Given a state $s$ , the extended state $\mathcal{A}(s)$ is computed by initializing all derived variables to $\bot$ and sequentially evaluating each axiom layer $A_1, \dots, A_k$ to a fixed point: whenever $\text{cond} \subseteq s'$ for an axiom $\text{cond} \to v := d$ , $s'(v)$ is set to $d$ .

An operator $\langle \text{pre}, \text{eff} \rangle \in O$ is applicable in state $s$ if $\text{pre} \subseteq \mathcal{A}(s)$ . Applying it produces a successor state $s'$ where $s'(v) = d$ for all effects $\text{cond} \to v := d \in \text{eff}$ with $\text{cond} \subseteq \mathcal{A}(s)$ , and $s'(v) = s(v)$ for all other fluents. Deciding plan existence (MPT-PLANEX) is PSPACE-complete.
Knowl 2 — Causal Graph Heuristic Computation
algorithm
The causal graph heuristic $h^{\text{CG}}(s)$ estimates the distance from state $s$ to the goal $s_*$ in an MPT $\Pi$ by summing the estimated costs of achieving each individual goal variable condition:

$h^{\text{CG}}(s) = \sum_{v \in \text{dom}(s_*)} \text{cost}_v(s(v), s_*(v))$

For a variable $v$ and source value $d \in \mathcal{D}_v$ , $\text{cost}_v(d, d')$ is computed for all $d' \in \mathcal{D}_v$ using a modified Dijkstra search over the pruned domain transition graph $\text{DTG}(v)$ , recursively solving subproblems for causal predecessors in a top-down traversal:
algorithm compute-costs(Π, s, v, d):
  Input: MPT task Π, state s, variable v, source value d
  Output: cost array cost_v(d, ·)
  Let V' be the set of immediate predecessors of v in the pruned causal graph of Π
  Let DTG be the pruned domain transition graph of v
  cost_v(d, d) := 0
  for each d' in D_v \ {d}:
    cost_v(d, d') := \infty
  local-state_d := s restricted to V'
  unreached := D_v
  while unreached contains a value d' in D_v with cost_v(d, d') < \infty:
    Choose d' in unreached minimizing cost_v(d, d')
    unreached := unreached \ {d'}
    for each transition t in DTG leading from d' to some d'' in unreached:
      if v is a derived variable:
        transition-cost := 0
      else:
        transition-cost := 1
      for each condition v' = e' in the label of t:
        e := local-state_{d'}(v')
        call compute-costs(Π, s, v', e)
        transition-cost := transition-cost + cost_{v'}(e, e')
      if cost_v(d, d') + transition-cost < cost_v(d, d''):
        cost_v(d, d'') := cost_v(d, d') + transition-cost
        local-state_{d''} := local-state_{d'}
        for each condition v' = e' in the label of t:
          local-state_{d''}(v') := e'
Computed cost values are cached locally per state and in a global cache shared across the search for variables with few ancestors in the causal graph.
Knowl 3 — Causal Graph Construction and Acyclic Pruning
algorithm
The causal graph $\text{CG}(\Pi)$ of an MPT $\Pi$ is a directed graph with vertex set $V$ . An arc $(v, v')$ exists if $v \neq v'$ and either:
1. The domain transition graph of $v'$ contains a transition conditioned on $v$ (induced by a transition condition), or
2. Some operator includes both $v$ and $v'$ in its list of affected effect variables (induced by co-occurring effects).
Variables that are not ancestors of any goal variable in $\text{CG}(\Pi)$ are pruned as irrelevant along with their associated operators and axioms.

To allow hierarchical heuristic decomposition, cycles in $\text{CG}(\Pi)$ are removed using a greedy arc-pruning procedure on each strongly connected component (SCC):
algorithm prune-causal-graph(CG):
  Input: Causal graph CG with vertex set V
  Output: Acyclic pruned causal graph CG_pruned
  Compute strongly connected components of CG
  for each strongly connected component C of CG:
    Assign weight n to each arc in C induced by n operators or axioms
    remaining := vertices of C
    while remaining is not empty:
      Select vertex v in remaining with minimal cumulated incoming arc weight
      Assign v the next lowest priority in total order ≺
      remaining := remaining \ {v}
      Remove v and its incident arcs from C
  Retain in CG_pruned only arcs (v, v') where v ≺ v'
After pruning the causal graph, domain transition graphs $\text{DTG}(v)$ are pruned by removing all conditions on variables $v'$ where $v \prec v'$ . Finally, dominated transitions (transitions whose conditions are supersets of other transitions between the same values) and duplicate transitions are removed.
Knowl 4 — Domain Transition Graphs and Extended DTGs for Derived Variables
definition
The domain transition graph $\text{DTG}(v)$ of a state variable $v \in V$ in an MPT $\Pi$ is a directed labelled graph with vertex set $\mathcal{D}_v$ :
- If $v$ is a fluent, an arc from $d$ to $d'$ labelled with $(\text{pre} \cup \text{cond}) \setminus \{v = d\}$ is added for each operator effect $\text{cond} \to v := d'$ with precondition $\text{pre}$ containing $v = d$ . If $\text{pre} \cup \text{cond}$ contains no condition on $v$ , arcs from every $d \in \mathcal{D}_v \setminus \{d'\}$ to $d'$ labelled with $\text{pre} \cup \text{cond}$ are added. Fluent transitions have weight 1.
- If $v$ is a derived variable, transitions are derived from axioms $\text{cond} \to v := d'$ labelled with $\text{cond} \setminus \{v = d\}$ (or from all other values if unconstrained) and assigned weight 0.
Under negation-as-failure semantics, derived variables default to $\bot$ when no deriving axiom triggers. For derived variables used negatively in conditions ( $v = \bot$ ), standard DTGs lack transitions leading to $\bot$ . Knowledge compilation generates an extended domain transition graph for every negatively used derived variable:
1. The conditions under which axioms derive a value are represented as a Disjunctive Normal Form (DNF) formula.
2. The negation of this formula is computed in Conjunctive Normal Form (CNF), inequalities are replaced by positive equalities over $\mathcal{D}_v$ , and the result is converted back to DNF while pruning dominated and duplicate disjuncts.
3. Arcs from non- $\bot$ values to $\bot$ are added to $\text{DTG}(v)$ , labelled with the conditions corresponding to each surviving disjunct.
Knowl 5 — Multi-Heuristic Best-First Search
algorithm
Multi-heuristic best-first search combines multiple heuristic estimators (such as the causal graph heuristic $h^{\text{CG}}$ and the FF relaxed-plan heuristic $h^{\text{FF}}$ ) without aggregating their estimates into a single scalar value. It maintains a separate open list for each heuristic evaluator:
algorithm multi-heuristic-best-first-search(s_0, s_*, {h_1, ..., h_k}):
  Input: Initial state s_0, goal condition s_*, set of heuristics {h_1, ..., h_k}
  Output: Plan reaching s_* or failure
  Initialize k open lists: Open_1, ..., Open_k
  Initialize closed list Closed := ∅
  for i := 1 to k:
    Insert s_0 into Open_i with priority h_i(s_0)
  current_queue := 1
  while not all open lists are empty:
    while Open_{current_queue} is empty:
      current_queue := (current_queue mod k) + 1
    Pop state s with minimal heuristic value from Open_{current_queue}
    if s in Closed:
      continue
    Closed := Closed ∪ {s}
    if s_* ⊆ A(s):
      return reconstructed plan leading to s
    Compute applicable operators for s
    for each applicable operator o:
      Generate successor state s' := apply(o, s)
      if s' not in Closed:
        for i := 1 to k:
          Insert s' into Open_i with priority h_i(s')
    current_queue := (current_queue mod k) + 1
  return failure
When combined with preferred operators, each heuristic maintains two open lists (one for all successors and one for preferred successors), resulting in $2k$ alternating open queues.
Knowl 6 — Deferred Heuristic Evaluation in Best-First Search
model/method
In standard greedy best-first search, when a search node $s$ is expanded, the heuristic evaluation $h(s')$ is immediately computed for every generated successor $s'$ before inserting $s'$ into the open queue. In planning tasks with high branching factors, this evaluates millions of frontier nodes that may never be expanded.

Under deferred heuristic evaluation:
1. Successors $s'$ of an expanded state $s$ are placed into the open list sorted by the heuristic value of their parent state, $h(s)$ , rather than their own heuristic values.
2. The heuristic evaluation $h(s')$ is computed only when $s'$ is actually removed from the open list for expansion.
3. In the open list, states are stored as compact references consisting of a pointer to the parent state and the operator used to reach the successor, deferring full state instantiation until extraction.
While deferred evaluation slightly decreases heuristic guidance accuracy (by using parent heuristic values for queue sorting), it eliminates heuristic computations on the vast majority of fringe states, yielding orders-of-magnitude search speedups in wide-branching domains.
Knowl 7 — Preferred Operators via Alternating Dual Open Lists
model/method
Preferred operators (such as helpful transitions from $h^{\text{CG}}$ or helpful actions from $h^{\text{FF}}$ ) provide action pruning and search biasing in global best-first search. To exploit preferred operators without sacrificing completeness:
1. The search engine maintains two separate open lists: a standard open list containing all generated successors and a preferred open list containing only successors reached via preferred operators.
2. Node expansion alternates strictly between the two lists: on even iterations, a node is popped from the standard open list; on odd iterations, a node is popped from the preferred open list.
3. When expanding any state, all generated successors are added to the standard open list, and the subset generated by preferred operators is additionally added to the preferred open list.
4. Duplicate node expansions across the two open lists are intercepted and discarded using a shared closed list.
5. Within equal heuristic values (plateaus), open lists operate in a First-In-First-Out (FIFO) queue order (breadth-first exploration), enabling fast escape from plateaus by expanding preferred operators first.
Knowl 8 — Helpful Transitions Extraction from the Causal Graph Heuristic
algorithm
Helpful transitions are the causal graph heuristic's analogue to FF's helpful actions. They identify a focused subset of applicable operators likely to make progress towards the goal:
algorithm extract-helpful-transitions(Π, s, s_*):
  Input: MPT task Π, current state s, goal condition s_*
  Output: Set of preferred operators H
  H := ∅
  for each variable v in dom(s_*):
    Let π_v = (t_1, ..., t_m) be the shortest transition path in DTG(v) from s(v) to s_*(v)
      computed during cost_v(s(v), s_*(v))
    if π_v is not empty:
      Add extract-transition-operators(t_1, s) to H
  return H
algorithm extract-transition-operators(t, s):
  Let o be the operator associated with transition t
  if o is applicable in s:
    return {o}
  else:
    H_sub := ∅
    for each condition v' = e' in the label of t that is not satisfied in s (s(v') ≠ e'):
      Let π_{v'} be the shortest path in DTG(v') from s(v') to e' computed during cost_{v'}(s(v'), e')
      if π_{v'} is not empty:
        Add extract-transition-operators(first transition of π_{v'}, s) to H_sub
    return H_sub
Unlike FF helpful actions, this set can be empty if an operator's preconditions were eliminated during acyclic causal graph pruning.
Knowl 9 — Successor Generator Tree Data Structure
definition
A successor generator for an MPT $\Pi = \langle V, s_0, s_*, A, O \rangle$ is a decision-tree data structure used to determine all applicable operators in a state $s$ without linearly scanning $O$ :
- Selector nodes (internal nodes): Associated with a selection variable $v \in V$ . A selector node has $|\mathcal{D}_v| + 1$ outgoing edges: one edge labelled $v = d$ for each value $d \in \mathcal{D}_v$ , and one 'don't care' edge labelled $\top$ .
- Generator nodes (leaf nodes): Contain a list of operators.
- Invariant: Each operator $o = \langle \text{pre}, \text{eff} \rangle \in O$ appears in exactly one generator node, reached by following the sequence of edge labels from the root that matches $\text{pre}$ . Variables not mentioned in $\text{pre}$ are bypassed via $\top$ edges.
To find applicable operators in state $s$ :
1. Start at the root node.
2. At a selector node with variable $v$ , traverse both the child corresponding to edge $v = s(v)$ and the child corresponding to the don't care edge $\top$ .
3. At a generator node, output all contained operators as applicable.
Knowl 10 — Focused Iterative-Broadening Search
algorithm
Focused iterative-broadening search is a non-heuristic progression planning algorithm that restricts search branching using causal graph distance metrics.

The modification distance of operator $o$ with respect to variable $v$ is: $\text{mod-dist}(o, v) = \min_{v' \in \text{affected}(o)} \text{dist}_{\text{CG}(\Pi)}(v', v)$
algorithm reach-one-goal(Π, v, d, cond):
  Input: MPT Π, target goal variable v, target value d, protected conditions cond
  Output: Plan achieving {v = d} ∪ cond
  for threshold ϑ := 0 to max-threshold:
    Let O_ϑ be all operators o with mod-dist(o, v) ≤ ϑ that do not affect any variable in cond
    Assign step cost c := mod-dist(o, v) to each operator o in O_ϑ
    Execute uniform-cost search with closed list using O_ϑ to find a state satisfying {v = d} ∪ cond
    if search succeeds:
      return generated plan
  for threshold ϑ := 0 to max-threshold:
    Let O_ϑ be all operators o with mod-dist(o, v) ≤ ϑ
    Assign step cost c := mod-dist(o, v) to each operator o in O_ϑ
    Execute uniform-cost search with closed list using O_ϑ to find a state satisfying {v = d} ∪ cond
    if search succeeds:
      return generated plan
  return failure
The overall planner runs reach-one-goal concurrently for all unachieved goals. As soon as the first goal is reached, the search commits to that plan prefix, updates the initial state, adds the satisfied goal to $\text{cond}$ (goal protection), and repeats until all goals are achieved.
Knowl 11 — Empirical Performance of Fast Downward Across IPC Benchmarks
empirical result
Fast Downward was evaluated across all 1442 propositional planning tasks from the first four International Planning Competitions (IPC 1–4) under a 300-second timeout and 1 GB RAM limit on a 3.066 GHz Intel Xeon CPU. Evaluated configurations included greedy best-first search without preferred operators (G), with helpful transitions (G+P), with helpful transitions and fallback to FF helpful actions (G+P $^+$ ), multi-heuristic best-first search without preferred operators (M), multi-heuristic with both preferred operator types (M+P), and focused iterative-broadening (F).

Key performance results (number of unsolved instances by benchmark suite):
- IPC 1–3 STRIPS domains (550 tasks total): G left 24 unsolved; G+P left 21; G+P $^+$ left 32; M left 32; M+P left 22; F left 148; CG left 25; FF left 32; LPG left 101; a virtual meta-planner selecting the best Fast Downward configuration per task ('Any') left only 10 unsolved.
- IPC 1–3 ADL domains (480 tasks total): G left 171 unsolved; G+P left 128; G+P $^+$ left 127; M left 144; M+P left 36; F left 233; FF left 12; 'Any' left 31 unsolved.
- IPC 4 domains (432 tasks total): G left 166 unsolved; G+P left 158; G+P $^+$ left 146; M left 160; M+P left 109; F left 162; competition version FD left 89; competition version FDD left 73; LPG-TD left 137; Macro-FF left 257; SGPlan left 110; YAHSP left 188; 'Any' left 54 unsolved.
Configuration M+P was the top individual configuration across all benchmarks, solving the most tasks in 23 out of 29 domains. Preferred operators consistently improved search performance across both greedy and multi-heuristic search algorithms.

Coverage note — The translation algorithm from propositional PDDL2.2 to MPTs and the sound dead-end detection routine were deliberately omitted because the paper explicitly excludes detailed descriptions of these procedures, citing previous work.

References

1.Bacchus, F., & Yang, Q. (1994). Downward refinement and the efficiency of hierarchical problem solving. Artificial Intelligence, 71(1), 43–100.
2.Bäckström, C., & Nebel, B. (1995). Complexity results for SAS $^+$ planning. Computational Intelligence, 11(4), 625–655.
3.Bonet, B., & Geffner, H. (2001). Planning as heuristic search. Artificial Intelligence, 129(1), 5–33.
4.Brafman, R. I., & Domshlak, C. (2003). Structure and complexity in planning with unary operators. Journal of Artificial Intelligence Research, 18, 315–349.
5.Bylander, T. (1994). The computational complexity of propositional STRIPS planning. Artificial Intelligence, 69(1–2), 165–204.
6.Domshlak, C., & Brafman, R. I. (2002). Structure and complexity in planning with unary operators. In Ghallab, M., Hertzberg, J., & Traverso, P. (Eds.), Proceedings of the Sixth International Conference on Artificial Intelligence Planning and Scheduling (AIPS 2002), pp. 34–43. AAAI Press.
7.Domshlak, C., & Dinitz, Y. (2001). Multi-agent off-line coordination: Structure and complexity. In Cesta, A., & Borrajo, D. (Eds.), Pre-proceedings of the Sixth European Conference on Planning (ECP’01), pp. 277–288, Toledo, Spain.
8.Dowling, W. F., & Gallier, J. H. (1984). Linear-time algorithms for testing the satisfiability of propositional Horn formulae. Journal of Logic Programming, 1(3), 367–383.
9.Edelkamp, S., & Helmert, M. (1999). Exhibiting knowledge in planning problems to minimize state encoding length. In Fox, M., & Biundo, S. (Eds.), Recent Advances in AI Planning. 5th European Conference on Planning (ECP’99), Vol. 1809 of Lecture Notes in Artificial Intelligence, pp. 135–147, New York. Springer-Verlag.
10.Edelkamp, S., & Hoffmann, J. (2004). PDDL2.2: The language for the classical part of the 4th International Planning Competition. Tech. rep. 195, Albert-Ludwigs-Universität Freiburg, Institut für Informatik.
11.Fox, M., & Long, D. (2003). PDDL2.1: An extension to PDDL for expressing temporal planning domains. Journal of Artificial Intelligence Research, 20, 61–124.
12.Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability — A Guide to the Theory of NP-Completeness. Freeman.
13.Gerevini, A., Saetti, A., & Serina, I. (2003). Planning through stochastic local search and temporal action graphs in LPG. Journal of Artificial Intelligence Research, 20, 239–290.
14.Ginsberg, M. L., & Harvey, W. D. (1992). Iterative broadening. Artificial Intelligence, 55, 367–383.
15.Helmert, M. (2004). A planning heuristic based on causal graph analysis. In Zilberstein, S., Koehler, J., & Koenig, S. (Eds.), Proceedings of the Fourteenth International Conference on Automated Planning and Scheduling (ICAPS 2004), pp. 161–170. AAAI Press.
16.Hoffmann, J. (2001). Local search topology in planning benchmarks: An empirical analysis. In Nebel, B. (Ed.), Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI’01), pp. 453–458. Morgan Kaufmann.
17.Hoffmann, J. (2002). Local search topology in planning benchmarks: A theoretical analysis. In Ghallab, M., Hertzberg, J., & Traverso, P. (Eds.), Proceedings of the Sixth International Conference on Artificial Intelligence Planning and Scheduling (AIPS 2002), pp. 92–100. AAAI Press.
18.Hoffmann, J. (2005). Where ‘ignoring delete lists’ works: Local search topology in planning benchmarks. Journal of Artificial Intelligence Research, 24, 685–758.
19.Hoffmann, J., & Edelkamp, S. (2005). The deterministic part of IPC-4: An overview. Journal of Artificial Intelligence Research, 24, 519–579.
20.Hoffmann, J., & Nebel, B. (2001). The FF planning system: Fast plan generation through heuristic search. Journal of Artificial Intelligence Research, 14, 253–302.
21.Jonsson, P., & Bäckström, C. (1995). Incremental planning. In Ghallab, M., & Milani, A. (Eds.), New Directions in AI Planning: EWSP ’95 — 3rd European Workshop on Planning, Vol. 31 of Frontiers in Artificial Intelligence and Applications, pp. 79–90, Amsterdam. IOS Press.
22.Jonsson, P., & Bäckström, C. (1998a). State-variable planning under structural restrictions: Algorithms and complexity. Artificial Intelligence, 100(1–2), 125–176.
23.Jonsson, P., & Bäckström, C. (1998b). Tractable plan existence does not imply tractable plan generation. Annals of Mathematics and Artificial Intelligence, 22(3), 281–296.
24.Joslin, D., & Roach, J. (1989). A theoretical analysis of conjunctive-goal problems. Artificial Intelligence, 41(1), 97–106. Research Note.
25.Knoblock, C. A. (1994). Automatically generating abstractions for planning. Artificial Intelligence, 68(2), 243–302.
26.Korf, R. E. (1987). Planning as search: A quantitative approach. Artificial Intelligence, 33(1), 65–88.
27.Lowerre, B. T. (1976). The HARPY Speech Recognition System. Ph.D. thesis, Computer Science Department, Carnegie-Mellon University, Pittsburgh, Pennsylvania.
28.Newell, A., & Simon, H. A. (1963). GPS: A program that simulates human thought. In Feigenbaum, E. A., & Feldman, J. (Eds.), Computers and Thought, pp. 279–293. Oldenbourg.
29.Russell, S., & Norvig, P. (2003). Artificial Intelligence — A Modern Approach. Prentice Hall.
30.Sacerdoti, E. D. (1974). Planning in a hierarchy of abstraction spaces. Artificial Intelligence, 5, 115–135.
31.Tenenberg, J. D. (1991). Abstraction in planning. In Allen, J. F., Kautz, H. A., Pelavin, R. N., & Tenenberg, J. D., Reasoning About Plans, chap. 4, pp. 213–283. Morgan Kaufmann, San Mateo.
32.van den Briel, M., Vossen, T., & Kambhampati, S. (2005). Reviving integer programming approaches for AI planning: A branch-and-cut framework. In Biundo, S., Myers, K., & Rajan, K. (Eds.), Proceedings of the Fifteenth International Conference on Automated Planning and Scheduling (ICAPS 2005), pp. 310–319. AAAI Press.
33.Williams, B. C., & Nayak, P. P. (1997). A reactive planner for a model-based executive. In Pollack, M. E. (Ed.), Proceedings of the 15th International Joint Conference on Artificial Intelligence (IJCAI’97), pp. 1178–1195. Morgan Kaufmann.
34.Yoshizumi, T., Miura, T., & Ishida, T. (2000). A $^*$ with partial expansion for large branching factor problems. In Kautz, H., & Porter, B. (Eds.), Proceedings of the Seventeenth National Conference on Artificial Intelligence (AAAI-2000), pp. 923–929. AAAI Press.

Citation

MLA

Helmert, M. “The Fast Downward Planning System”. Journal of Artificial Intelligence Research, vol. 26, 2006, pp. 191–246, https://doi.org/10.1613/jair.1705.

APA

Helmert, M. (2006). The Fast Downward Planning System. Journal of Artificial Intelligence Research, 26, 191–246. https://doi.org/10.1613/jair.1705

Chicago

Helmert, M. 2006. “The Fast Downward Planning System”. Journal of Artificial Intelligence Research 26: 191–246. https://doi.org/10.1613/jair.1705.

Harvard

Helmert, M. (2006) “The Fast Downward Planning System”, Journal of Artificial Intelligence Research, 26, pp. 191–246. Available at: https://doi.org/10.1613/jair.1705.

Vancouver

1. Helmert M (2006) The Fast Downward Planning System. Journal of Artificial Intelligence Research 26:191–246

BibTeX

@article{Helmert_2006, title={The Fast Downward Planning System}, volume={26}, ISSN={1076-9757}, url={http://dx.doi.org/10.1613/jair.1705}, DOI={10.1613/jair.1705}, journal={Journal of Artificial Intelligence Research}, publisher={AI Access Foundation}, author={Helmert, M.}, year={2006}, month=July, pages={191–246} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

The Fast Downward Planning System

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Multi-Valued Planning Task Formalism and Semantics

Knowl 2 — Causal Graph Heuristic Computation

Knowl 3 — Causal Graph Construction and Acyclic Pruning

Knowl 4 — Domain Transition Graphs and Extended DTGs for Derived Variables

Knowl 5 — Multi-Heuristic Best-First Search

Knowl 6 — Deferred Heuristic Evaluation in Best-First Search

Knowl 7 — Preferred Operators via Alternating Dual Open Lists

Knowl 8 — Helpful Transitions Extraction from the Causal Graph Heuristic

Knowl 9 — Successor Generator Tree Data Structure

Knowl 10 — Focused Iterative-Broadening Search

Knowl 11 — Empirical Performance of Fast Downward Across IPC Benchmarks

References

Citation

BibTeX

Access the Paper