The FF Planning System: Fast Plan Generation Through Heuristic Search

Jörg HoffmannBernhard Nebel

article2011JAIR2,451 citations

Introduces the FF planning system, showing how combining relaxed plan distance heuristics with enforced hill-climbing search dramatically accelerates domain-independent forward state-space planning.

Listen

Automated planning systems are essential for coordinating complex operations such as logistics routing, manufacturing scheduling, and robotics. However, general planning is computationally intractable in the worst case, making scalability a major hurdle for practical deployment. While earlier research suggested translating planning problems into propositional satisfiability formulas, specialized heuristic search methods have re-emerged as a practical alternative. The article addresses the challenge of building a general-purpose, fully automatic planning system that generates valid solutions rapidly across a broad spectrum of domains without requiring human domain-tailoring.

The article set out to introduce and comprehensively evaluate the Fast-Forward (FF) planning system, demonstrating how coupling relaxed plan heuristics with a novel local search strategy achieves superior empirical runtime performance across standard benchmarks.

The authors developed an algorithmic architecture that evaluates forward search states by constructing relaxed planning graphs that ignore action delete effects, enabling polynomial-time distance estimation that accounts for positive action interactions. The search engine relies primarily on enforced hill-climbing, which performs breadth-first local exploration to reach states with strictly better heuristic values, complemented by a complete best-first search fallback when local search hits dead ends. Additionally, the system prunes candidate moves by extracting helpful actions from the relaxed plans. The approach was evaluated across twenty benchmark domains, including standard competition suites and hard satisfiability-encoded tasks, using formal performance comparisons and non-parametric statistical tests across hundreds of problem instances.

The evaluation yielded several key findings. First, FF achieved superior runtime performance compared to competing automatic systems, earning top honors at the AIPS-2000 competition and solving large industrial instances in fractions of a second where other planners timed out. Second, the combination of enforced hill-climbing and helpful actions pruning provided exponential search-space reductions, often filtering out over 95% of irrelevant branches and keeping local exploration depths shallow. Third, FF produced solution plan lengths that were competitive with and often very close to optimal planners, averaging within 5% to 15% of the shortest known plans across multiple domains. Finally, statistical comparisons against baseline heuristic planners showed that FF's explicit relaxed-plan extraction and pruning significantly improved speed and solution quality across sixteen of the twenty tested domains.

These findings demonstrate that real-world planning benchmarks often exhibit relatively simple underlying structures that can be exploited effectively without exhaustive search. This challenges the assumption that domain-independent planning should be superseded entirely by general propositional satisfiability solvers. For decision-makers and technical leaders, the results indicate that heuristic search planning can dramatically cut computational costs, reduce execution latency in operational planning, and handle expressive problem definitions, including complex conditional effects.

Organizations developing automated scheduling, logistics, or control tools should consider adopting relaxed-graph heuristic estimation and enforced local search as baseline design patterns. Practitioners must account for trade-offs: while the method provides massive speed advantages for standard sequential workflows, it is not designed to guarantee mathematically optimal plans and can struggle on combinatorial tasks with heavy dead-end densities, such as resource-constrained routing. Future work should focus on formally classifying domain structures to automatically predict whether a problem is well-suited for enforced local search before planning begins.

The main limitation of the study is that the empirical advantages rely on benchmark domains that are predominantly free of unrecoverable dead ends and complex cyclic dependencies. Confidence in the system is very high for standard sequential planning and logistics benchmarks, but caution is warranted when applying it to domains with severe resource scarcity or unguided combinatorial constraints.

University of Freiburg state space tabu search search process FF Planning System heuristic search classical planning

arXiv: 1106.0675

Paper: Fast Planning Through Planning Graph Analysis, Avrim L. Blum et al. (1995). Graphplan’s layered planning graphs provide the key conceptual foundation for understanding how FF derives useful distance estimates from relaxed planning graphs.
Paper: STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving, Richard E. Fikes et al. (1971). STRIPS introduces the classical action-and-state representation that FF’s forward search assumes and uses to generate plans.

No sufficiently relevant recommendations were found.

Cover for The FF Planning System: Fast Plan Generation Through Heuristic Search

Abstract

We describe and evaluate the algorithmic techniques that are used in the FF planning system. Like the HSP system, FF relies on forward state space search, using a heuristic that estimates goal distances by ignoring delete lists. Unlike HSP's heuristic, our method does not assume facts to be independent. We introduce a novel search strategy that combines hill-climbing with systematic search, and we show how other powerful heuristic information can be extracted and used to prune the search space. FF was the most successful automatic planner at the recent AIPS-2000 planning competition. We review the results of the competition, give data for other benchmark domains, and investigate the reasons for the runtime performance of FF compared to HSP.

Topics

state space tabu search search process heuristic approaches

Keywords

FF Planning System heuristic search classical planning planning graphs relaxed planning STRIPS planning heuristic function fast plan generation goal orderings

1. Introduction
2. System Architecture
3. Notational Conventions
4. GRAPHPLAN as a Heuristic Estimator
4.1 Planning Graphs for Relaxed Tasks
4.2 Solution Length Optimization
4.2.1 NOOPs-first
4.2.2 Difficulty Heuristic
4.2.3 Action Set Linearization
4.3 Efficient Implementation
5. A Novel Variation of Hill-climbing
5.1 Enforced Hill-climbing
5.2 Completeness
6. Pruning Techniques
6.1 Helpful Actions
6.1.1 Completeness
6.1.2 Integration into Search
6.2 Added Goal Deletion
6.2.1 Completeness
6.2.2 Integration into Search
7. Extension to ADL
7.1 Preprocessing an ADL Planning Task
7.2 Relaxed GRAPHPLAN with Conditional Effects
7.2.1 Relaxed Planning Graphs with Conditional Effects
7.2.2 Relaxed Plan Extraction with Conditional Effects
7.3 ADL Pruning Techniques
7.3.1 Helpful Actions
7.3.2 Added Goal Deletion
7.4 ADL State Transitions
8. Performance Evaluation
8.1 The AIPS-2000 Planning Systems Competition
8.1.1 The Logistics Domain
8.1.2 The Blocksworld Domain
8.1.3 The Schedule Domain
8.1.4 The Freecell Domain
8.1.5 The Miconic Domain
8.2 Some more Examples
8.2.1 The Mystery and Mprime Domains
8.2.2 Random SAT Instances
8.3 What Makes the Difference to HSP?
8.3.1 Experimental Setup
8.3.2 Running Time
8.3.3 Solution Length
9. Related Work
10. Conclusion and Outlook
Acknowledgments
References

Knowls

Knowl 1 — Enforced Hill-Climbing Search Algorithm
algorithm
Enforced Hill-Climbing (EHC) is a local search strategy for state space planning that greedily advances from an intermediate state $S$ to the nearest strictly better successor state $S'$ (a state with a strictly smaller heuristic value $h(S') < h(S)$ ) found via breadth-first search.
Input: Planning task $P = (O, I, G)$ , heuristic function $h$ , helpful action generator $H$
Output: Solution plan $P_{sol}$ or "Fail"
$plan \leftarrow \langle \rangle$
$S \leftarrow I$
while $h(S) \neq 0$ do
     $queue \leftarrow \text{empty FIFO queue}$
     $visited \leftarrow \text{empty hash table}$
     $queue.\text{enqueue}(S)$
     $visited.\text{insert}(S)$
     $found\_better \leftarrow \text{false}$
     $S' \leftarrow \text{null}$
     $path \leftarrow \langle \rangle$
    while $queue$ is not empty and not $found\_better$ do
         $curr \leftarrow queue.\text{dequeue}()$
        for each action $o \in H(curr)$ applicable in $curr$ do
             $succ \leftarrow \text{Result}(curr, o)$
            if $succ \notin visited$ then
                 $visited.\text{insert}(succ)$
                if $h(succ) < h(S)$ then
                     $found\_better \leftarrow \text{true}$
                     $S' \leftarrow succ$
                     $path \leftarrow \text{action path from } S \text{ to } succ$
                    break
                else
                     $queue.\text{enqueue}(succ)$
                end if
            end if
        end for
    end while
    if not $found\_better$ then
        return "Fail"
    end if
     $plan \leftarrow plan \circ path$
     $S \leftarrow S'$
end while
return $plan$
The algorithm starts at the initial state $I$ . At each state $S$ , it initiates an exhaustive breadth-first search over successors (optionally restricted to helpful actions $H(curr)$ ) until it encounters the first state $S'$ satisfying $h(S') < h(S)$ . The sequence of actions leading from $S$ to $S'$ is permanently appended to the accumulated plan prefix, $S$ is updated to $S'$ , and the process iterates until reaching a goal state ( $h(S) = 0$ ). If breadth-first search exhausts reachable states without finding an improvement, EHC terminates with failure.
Knowl 2 — Relaxed GraphPlan Heuristic Computation
algorithm
The heuristic value $h(S)$ for a state $S$ in a planning task $P = (O, I, G)$ is computed by solving the relaxed task $P'_S = (O', S, G)$ , where every action $o = (pre(o), add(o), del(o)) \in O$ has its delete list stripped: $O' = \{ (pre(o), add(o), \emptyset) \mid o \in O \}$ .

The calculation proceeds in two phases:
1. Forward Graph Construction: A relaxed planning graph without mutual exclusion relations is built forward from fact layer 0 (initialized to $S$ ). Successive action layers contain all actions whose preconditions are satisfied, and each action adds its add effects to the next fact layer until a layer $m$ is reached where all goals $G$ appear.
2. Backward Relaxed Plan Extraction: Starting from fact layer $m$ down to layer 1, achievers are selected for all unscheduled goals and preconditions.
Input: Relaxed planning task $P'_S = (O', S, G)$ , fact layer memberships, goal layer index $m$
Output: Relaxed plan $\langle O_0, \dots, O_{m-1} \rangle$ , heuristic estimate $h(S)$
for $i \leftarrow 1$ to $m$ do
     $G_i \leftarrow \{ g \in G \mid \text{layer-membership}(g) = i \}$
end for
for $i \leftarrow m$ down to 1 do
     $O_{i-1} \leftarrow \emptyset$
    for each fact $g \in G_i$ not marked TRUE at time $i$ do
        select action $o \in O'$ with $g \in add(o)$ and $\text{layer-membership}(o) = i - 1$ minimizing $difficulty(o)$
         $O_{i-1} \leftarrow O_{i-1} \cup \{ o \}$
        for each precondition $f \in pre(o)$ with $\text{layer-membership}(f) \neq 0$ and $f$ not marked TRUE at time $i - 1$ do
             $G_{\text{layer-membership}(f)} \leftarrow G_{\text{layer-membership}(f)} \cup \{ f \}$
        end for
        for each fact $f \in add(o)$ do
            mark $f$ as TRUE at times $i - 1$ and $i$
        end for
    end for
end for
$h(S) \leftarrow \sum_{i=0}^{m-1} |O_i|$
return $\langle O_0, \dots, O_{m-1} \rangle$ , $h(S)$
The resulting heuristic estimate $h(S) = \sum_{i=0}^{m-1} |O_i|$ measures the total number of actions in the extracted sequential relaxed plan. Unlike heuristics based on summing sub-goal costs under an independence assumption, $h(S)$ accounts for positive interactions where an action simultaneously supports multiple sub-goals.
Knowl 3 — Polynomial-Time Tractability and Non-Backtracking of Relaxed Planning Graphs
theoretical result
Let $P' = (O', I, G)$ be a relaxed STRIPS planning task where all actions have empty delete lists ( $del(o) = \emptyset$ for all $o \in O'$ ), and let $l$ denote the length of the longest add list of any action in $O'$ .
1. Absence of Mutual Exclusions: GraphPlan executed on $P'$ marks no pair of facts or actions as mutually exclusive at any layer.
2. Absence of Backtracking: Backward search during relaxed plan extraction on $P'$ never backtracks, because every fact in layer $i$ has at least one achieving action in layer $i-1$ and no action exclusions exist.
3. Polynomial Complexity: If $P'$ is solvable, GraphPlan finds a relaxed solution in time polynomial in $l$ , $|O'|$ , and $|I|$ . Specifically, graph building terminates within at most $|O'|$ time steps, and plan extraction requires $O(|O'| \cdot (l \cdot |O'| + |I|))$ operations.
Knowl 4 — Helpful Actions Pruning
definition
For a state $S$ evaluated by relaxed GraphPlan on the task $(O', S, G)$ , let $G_1(S)$ denote the set of goal facts scheduled at time step 1 (one step ahead of the initial layer) during the backward plan extraction phase.

For STRIPS actions, the set of helpful actions $H(S)$ is defined as all actions applicable in $S$ that achieve at least one goal in $G_1(S)$ :

$H(S) := \{ o \in O \mid pre(o) \subseteq S \land add(o) \cap G_1(S) \neq \emptyset \}$

For ADL planning tasks with conditional effects, where each action $o$ has precondition $pre(o)$ and conditional effects $(pre^i(o), add^i(o), del^i(o))$ , an action is helpful if it is applicable in $S$ and has at least one active effect whose condition is satisfied in $S$ that adds a fact in $G_1(S)$ :

$H(S) := \{ o \in O \mid pre(o) \subseteq S \land \exists i: (pre^i(o) \subseteq S \land add^i(o) \cap G_1(S) \neq \emptyset) \}$

During forward search, successor generation is restricted to actions in $H(S)$ , substantially reducing the search branching factor.
Knowl 5 — Added Goal Deletion Pruning Heuristic
definition
The added goal deletion heuristic prunes intermediate states where a target goal appears to have been achieved prematurely relative to required goal orderings.

Let $S$ be a state generated by applying an action $o$ that achieves an original goal atom $g \in G$ ( $g \in add(o)$ ). Let $P_{rel}$ be the relaxed plan extracted by relaxed GraphPlan starting from $S$ . If $P_{rel}$ contains an action $o' \in P_{rel}$ whose full (non-relaxed) definition deletes $g$ ( $g \in del(o')$ ), state $S$ is pruned from the forward search space and no successors are generated from it.

For ADL tasks with conditional effects, $S$ is pruned if any conditional effect selected in the relaxed plan $P_{rel}$ deletes the newly achieved goal $g$ .
Knowl 6 — Completeness of Enforced Hill-Climbing on Dead-End Free Tasks and Complexity of Dead-End Freeness
theoretical result
Let $P = (O, I, G)$ be a planning task.
1. Dead End: A state $S$ is a dead end if $S$ is reachable from $I$ ( $\exists P_{init}: S = \text{Result}(I, P_{init})$ ) and no action sequence can achieve the goal from $S$ ( $\nexists P': G \subseteq \text{Result}(S, P')$ ). A planning task $P$ is dead-end free if it contains no dead end states.
2. Completeness of Enforced Hill-Climbing: If $P$ is dead-end free and $h$ is a heuristic function where $h(S) = 0 \iff G \subseteq S$ , Enforced Hill-Climbing is guaranteed to find a solution plan.
3. PSPACE-Completeness: Deciding whether an arbitrary STRIPS planning task $P$ is dead-end free (the DEADEND-FREE decision problem) is PSPACE-complete.
Knowl 7 — NP-Completeness of Optimal Action Linearization
theoretical result
The OPTIMAL ACTION LINEARIZATION problem is defined as follows: Given a set $O$ of relaxed STRIPS actions (where delete lists are empty) and a positive integer $K$ , decide whether there exists a bijection $f: O \to \{1, 2, \dots, |O|\}$ such that executing the sequence $\langle f^{-1}(1), f^{-1}(2), \dots, f^{-1}(|O|) \rangle$ results in at most $K$ unsatisfied action preconditions.

Theorem: Deciding OPTIMAL ACTION LINEARIZATION is NP-complete (proven by polynomial reduction from Directed Optimal Linear Arrangement).

Because computing an optimal sequential linearization of parallel relaxed actions is NP-complete, heuristic planners linearize actions in the simple order they are selected during plan extraction without attempting combinatorial optimization.
Knowl 8 — Relaxed Plan Minimization via NOOPs-First and Precondition Difficulty
model/method
To obtain cautious (shorter) relaxed plan lengths for more accurate heuristic estimation, two minimization techniques are applied during plan extraction:
1. NOOPs-First Strategy: During backward plan extraction, if a fact $f$ in fact layer $i$ is already present at layer $i-1$ , a NOOP dummy action (which preserves $f$ without adding preconditions) is selected before any operator. This ensures that the extracted relaxed plan contains each action at most once.
2. Difficulty Heuristic: When a fact $f$ at layer $i$ cannot be satisfied by a NOOP and multiple achieving actions exist at action layer $i-1$ , the extractor selects an action $o$ that minimizes the difficulty of its preconditions:
$difficulty(o) := \sum_{p \in pre(o)} \min \{ j \mid p \text{ is a member of fact layer } j \}$

This chooses achievers whose preconditions emerged earlier in the planning graph, favoring actions requiring less estimated effort.
Knowl 9 — Compilation of ADL Planning Tasks to Propositional Normal Form
model/method
To evaluate ADL tasks with arbitrary first-order formulas and conditional effects, actions are compiled into a propositional normal form with ground atomic preconditions and conditional effects:
$\text{Precondition: } & pre(o) \\ \text{Effects: } & (pre^0(o), add^0(o), del^0(o)) \land \dots \land (pre^m(o), add^m(o), del^m(o)) \end{aligned}$$ where $pre(o)$ and each effect condition $pre^i(o)$ are sets of ground atoms. The preprocessing pipeline: 1. Detect static predicates (predicates never modified by any action) via a syntactic sweep. 2. Expand quantifiers and translate negations into quantifier-free formulas. 3. Instantiate action and effect parameters with type-consistent constants, simplifying static predicate literals to $\text{true}$ or $\text{false}$. 4. Transform remaining formulas into Disjunctive Normal Form (DNF). 5. Split operators or effects with multiple DNF disjuncts into separate single-conjunct structures. The deterministic state transition function $Res(S, o)$ on a fully specified state $S$ is computed as: $$Res(S, o) = (S \cup A(S, o)) \setminus D(S, o) \quad \text{if } pre(o) \subseteq S$$ where $A(S, o) = \bigcup_{pre^i(o) \subseteq S} add^i(o)$ and $D(S, o) = \bigcup_{pre^i(o) \subseteq S} del^i(o)$.$
Knowl 10 — Two-Tier Search Architecture with Greedy Best-First Fallback
model/method
The overall planning system architecture employs a two-tier search strategy combining incomplete local search with complete global search:
1. Primary Tier (Enforced Hill-Climbing): The planner runs Enforced Hill-Climbing guided by the relaxed GraphPlan heuristic $h(S)$ , using Helpful Actions pruning and Added Goal Deletion pruning.
2. Secondary Tier (Greedy Best-First Fallback): If Enforced Hill-Climbing fails (because breadth-first search encounters a dead end and exhausts the queue without finding an improving state), all previous progress is discarded. The planner restarts from the initial state $I$ using complete Greedy Best-First Search, expanding nodes in increasing order of $h(S)$ . In this fallback phase, pruning heuristics (Helpful Actions and Added Goal Deletion) are completely disabled to guarantee completeness on solvable tasks.

Knowl 11 — Empirical Comparison of FF and HSP Architectural Components

data/table

An ablation study evaluated the combinations of the three core algorithmic features distinguishing the FF system from HSP1 across 939 benchmark instances in 20 planning domains. The switches are:

H: Helpful Actions pruning (enabled vs. expanding all node successors).
E: Enforced Hill-Climbing (enabled vs. standard hill-climbing with restarts).
F: FF Relaxed GraphPlan heuristic (enabled vs. HSP weight-sum heuristic).

The table below reports the average running time in seconds (with a 150-second cutoff per instance) for each configuration across all 20 domains:

Domain	—	–F	-E-	-EF	H–	H-F	HE-	HEF
Assembly	117.39	31.75	92.95	61.10	47.81	20.25	20.34	16.94
Blocksworld-3ops	4.06	2.53	8.37	30.11	1.41	0.83	0.27	6.11
Blocksworld-4ops	0.60	8.81	80.02	56.20	1.21	10.13	25.19	40.65
Briefcaseworld	16.35	5.84	66.51	116.24	150.00	150.00	150.00	150.00
Bulldozer	4.47	3.24	31.02	15.74	81.90	126.50	128.40	141.04
Freecell	65.73	46.05	54.15	51.27	57.35	42.68	43.99	41.44
Fridge	28.52	53.58	31.89	52.60	0.85	0.69	1.88	2.77
Grid	138.06	119.53	115.05	99.18	115.00	95.10	18.73	11.73
Gripper	2.75	1.21	15.16	1.00	1.17	0.48	0.17	0.11
Hanoi	93.76	75.05	6.29	3.91	150.00	78.82	4.47	2.70
Logistics	79.27	102.09	79.77	111.47	36.88	39.69	10.18	11.94
Miconic-ADL	150.00	150.00	102.54	54.23	142.51	128.28	95.45	59.00
Miconic-SIMPLE	2.61	2.01	2.47	1.93	1.35	0.86	0.55	0.56
Miconic-STRIPS	2.71	2.32	4.84	1.53	1.44	1.01	0.64	0.36
Movie	0.02	0.02	0.02	0.02	0.02	0.02	0.02	0.02
Mprime	73.09	69.27	82.89	81.43	47.09	58.45	18.56	26.62
Mystery	78.54	90.55	71.60	86.01	75.73	95.24	85.13	86.21
Schedule	135.50	131.12	143.59	141.42	77.58	38.23	12.23	13.77
Tireworld	135.30	110.38	119.22	121.34	121.13	105.67	97.41	85.64
Tsp	4.11	0.82	2.45	0.75	2.48	0.57	0.15	0.07

The data shows that the primary driver of performance speedup is the synergy between Helpful Actions pruning (H) and Enforced Hill-Climbing (E). By pruning unhelpful branch successors, Helpful Actions exponentially reduces the state evaluation burden during the breadth-first search phases of EHC, enabling HE- and HEF to outperform other configurations by orders of magnitude on domains like Logistics, Schedule, Grid, and Gripper.

Coverage note — All primary algorithmic, theoretical, and empirical contributions are covered; detailed runtime plots for competing planners across specific AIPS-2000 competition tracks are omitted in favor of the full 20-domain comparative ablation dataset.

References

1.Anderson, C. R., Smith, D. E., & Weld, D. S. (1998). Conditional effects in Graphplan. In Simmons, R., Veloso, M., & Smith, S. (Eds.), Proceedings of the 4th International Conference on Artificial Intelligence Planning Systems (AIPS-98), pp. 44–53. AAAI Press, Menlo Park.
2.Bacchus, F. (2000). Subset of PDDL for the AIPS2000 Planning Competition. The AIPS-00 Planning Competition Comitee.
3.Bacchus, F., & Nau, D. (2001). The 2000 AI planning systems competition. The AI Magazine. Forthcoming.
4.Blum, A. L., & Furst, M. L. (1995). Fast planning through planning graph analysis. In Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI-95), pp. 1636–1642 Montreal, Canada. Morgan Kaufmann.
5.Blum, A. L., & Furst, M. L. (1997). Fast planning through planning graph analysis. Artificial Intelligence, 90 (1-2), 279–298.
6.Bonet, B., & Geffner, H. (1998). HSP: Heuristic search planner. In AIPS-98 Planning Competition Pittsburgh, PA.
7.Bonet, B., & Geffner, H. (1999). Planning as heuristic search: New results. In Biundo, S., & Fox, M. (Eds.), Recent Advances in AI Planning. 5th European Conference on Planning (ECP'99) Durham, UK. Springer-Verlag.
8.Bonet, B., & Geffner, H. (2001). Planning as heuristic search. Artificial Intelligence. Forthcoming.
9.Bonet, B., Loerincs, G., & Geffner, H. (1997). A robust and fast action selection mechanism for planning. In Proceedings of the 14th National Conference of the American Association for Artificial Intelligence (AAAI-97), pp. 714–719. MIT Press.
10.Bylander, T. (1994). The computational complexity of propositional STRIPS planning. Artificial Intelligence, 69 (1–2), 165–204.
11.Cheng, J., & Irani, K. B. (1989). Ordering problem subgoals. In Sridharan, N. S. (Ed.), Proceedings of the 11th International Joint Conference on Artificial Intelligence (IJCAI-89), pp. 931–936 Detroit, MI. Morgan Kaufmann.
12.Drummond, M., & Currie, K. (1989). Goal ordering in partially ordered plans. In Sridharan, N. S. (Ed.), Proceedings of the 11th International Joint Conference on Artificial Intelligence (IJCAI-89), pp. 960–965 Detroit, MI. Morgan Kaufmann.
13.Edelkamp, S. (2000). Heuristic search planning with BDDs. In ECAI-Workshop: PuK.
14.Even, S., & Shiloach, Y. (1975). NP-completeness of several arrangement problems. Tech. rep. 43, Department of Computer Science, Haifa, Israel.
15.Fikes, R. E., & Nilsson, N. (1971). STRIPS: A new approach to the application of theorem proving to problem solving. Artificial Intelligence, 2, 189–208.
16.Fox, M., & Long, D. (1998). The automatic inference of state invariants in tim. Journal of Artificial Intelligence Research, 9, 367–421.
17.Fox, M., & Long, D. (2001). Hybrid STAN: Identifying and managing combinatorial optimisation sub-problems in planning. In Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI-01) Seattle, Washington, USA. Morgan Kaufmann. Accepted for publication.
18.Frank, J., Cheeseman, P., & Stutz, J. (1997). When gravity fails: Local search topology. Journal of Artificial Intelligence Research, 7, 249–281.
19.Gazen, B. C., & Knoblock, C. (1997). Combining the expressiveness of UCPOP with the efficiency of Graphplan. In Steel, S., & Alami, R. (Eds.), Recent Advances in AI Planning. 4th European Conference on Planning (ECP'97), Vol. 1348 of Lecture Notes in Artificial Intelligence, pp. 221–233 Toulouse, France. Springer-Verlag.
20.Hoffmann, J. (2000). A heuristic for domain independent planning and its use in an enforced hill-climbing algorithm. In Proceedings of the 12th International Symposium on Methodologies for Intelligent Systems (ISMIS-00), pp. 216–227. Springer-Verlag.
21.Hoffmann, J. (2001). Local search topology in planning benchmarks: An empirical analysis. In Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI-01) Seattle, Washington, USA. Morgan Kaufmann. Accepted for publication.
22.Hölldobler, S., & Störr, H.-P. (2000). Solving the entailment problem in the fluent calculus using binary decision diagrams. In Proceedings of the First International Conference on Computational Logic (CL). To appear.
23.Irani, K. B., & Cheng, J. (1987). Subgoal ordering and goal augmentation for heuristic problem solving. In McDermott, J. (Ed.), Proceedings of the 10th International Joint Conference on Artificial Intelligence (IJCAI-87), pp. 1018–1024 Milan, Italy. Morgan Kaufmann.
24.Jonsson, P., Haslum, P., & Bäckström, C. (2000). Planning - a randomized approach. Artificial Intelligence, 117 (1), 1–29.
25.Joslin, D., & Roach, J. W. (1990). A theoretical analysis of conjunctive-goal problems. Artificial Intelligence, 41, 97–106.
26.Kambhampati, S., Parker, E., & Lambrecht, E. (1997). Understanding and extending Graphplan. In Steel, S., & Alami, R. (Eds.), Recent Advances in AI Planning. 4th European Conference on Planning (ECP'97), Vol. 1348 of Lecture Notes in Artificial Intelligence, pp. 260–272 Toulouse, France. Springer-Verlag.
27.Kautz, H., & Selman, B. (1999). Unifying SAT-based and graph-based planning. In Proceedings of the 16th International Joint Conference on Artificial Intelligence (IJCAI-99), pp. 318–325 Stockholm, Sweden. Morgan Kaufmann.
28.Kautz, H. A., & Selman, B. (1996). Pushing the envelope: Planning, propositional logic, and stochastic search. In Proceedings of the 13th National Conference of the American Association for Artificial Intelligence (AAAI-96), pp. 1194–1201. MIT Press.
29.Koehler, J. (1998). Solving complex planning tasks through extraction of subproblems. In Simmons, R., Veloso, M., & Smith, S. (Eds.), Proceedings of the 4th International Conference on Artificial Intelligence Planning Systems (AIPS-98), pp. 62–69. AAAI Press, Menlo Park.
30.Koehler, J., & Hoffmann, J. (2000a). On reasonable and forced goal orderings and their use in an agenda-driven planning algorithm. Journal of Artificial Intelligence Research, 12, 338–386.
31.Koehler, J., & Hoffmann, J. (2000b). On the instantiation of ADL operators involving arbitrary first-order formulas. In Proceedings ECAI-00 Workshop on New Results in Planning, Scheduling and Design.
32.Koehler, J., Nebel, B., Hoffmann, J., & Dimopoulos, Y. (1997). Extending planning graphs to an ADL subset. In Steel, S., & Alami, R. (Eds.), Recent Advances in AI Planning. 4th European Conference on Planning (ECP'97), Vol. 1348 of Lecture Notes in Artificial Intelligence, pp. 273–285 Toulouse, France. Springer-Verlag.
33.Koehler, J., & Schuster, K. (2000). Elevator control as a planning problem. In Chien, S., Kambhampati, R., & Knoblock, C. (Eds.), Proceedings of the 5th International Conference on Artificial Intelligence Planning Systems (AIPS-00). AAAI Press, Menlo Park.
34.Long, D., & Fox, M. (1999). Efficient implementation of the plan graph in stan. Journal of Artificial Intelligence Research, 10, 87–115.
35.McAllester, D. A., & Rosenblitt, D. (1991). Systematic nonlinear planning. In Proceedings of the 9th National Conference of the American Association for Artificial Intelligence (AAAI-91), pp. 634–639 Anaheim, CA. MIT Press.
36.McDermott, D. (1996). A heuristic estimator for means-ends analysis in planning. In Proceedings of the 3rd International Conference on Artificial Intelligence Planning Systems (AIPS-96), pp. 142–149. AAAI Press, Menlo Park.
37.McDermott, D., et al. (1998). The PDDL Planning Domain Definition Language. The AIPS-98 Planning Competition Comitee.
38.McDermott, D. V. (1999). Using regression-match graphs to control search in planning. Artificial Intelligence, 109 (1-2), 111–159.
39.Mitchell, D., Selman, B., & Levesque, H. J. (1992). Hard and easy distributions of SAT problems. In Proceedings of the 10th National Conference of the American Association for Artificial Intelligence (AAAI-92), pp. 459–465 San Jose, CA. MIT Press.
40.Nebel, B. (2000). On the compilability and expressive power of propositional planning formalisms. Journal of Artificial Intelligence Research, 12, 271–315.
41.Nebel, B., Dimopoulos, Y., & Koehler, J. (1997). Ignoring irrelevant facts and operators in plan generation. In Steel, S., & Alami, R. (Eds.), Recent Advances in AI Planning. 4th European Conference on Planning (ECP'97), Vol. 1348 of Lecture Notes in Artificial Intelligence, pp. 338–350 Toulouse, France. Springer-Verlag.
42.Pednault, E. P. (1989). ADL: Exploring the middle ground between STRIPS and the situation calculus. In Brachman, R., Levesque, H. J., & Reiter, R. (Eds.), Principles of Knowledge Representation and Reasoning: Proceedings of the 1st International Conference (KR-89), pp. 324–331 Toronto, ON. Morgan Kaufmann.
43.Refanidis, I., & Vlahavas, I. (1999). GRT: a domain independent heuristic for STRIPS worlds based on greedy regression tables. In Biundo, S., & Fox, M. (Eds.), Recent Advances in AI Planning. 5th European Conference on Planning (ECP'99) Durham, UK. Springer-Verlag.
44.Refanidis, I., & Vlahavas, I. (2000). Exploiting state constraints in heuristic state-space planning. In Chien, S., Kambhampati, R., & Knoblock, C. (Eds.), Proceedings of the 5th International Conference on Artificial Intelligence Planning Systems (AIPS-00), pp. 363–370. AAAI Press, Menlo Park.
45.Russell, S., & Norvig, P. (1995). Artificial Intelligence: A Modern Approach. Prentice-Hall, Englewood Cliffs, NJ.
46.Siegel, S., & N. J. Castellan, J. (1988). Nonparametric Statistics for the Behavioral Sciences (2nd edition). McGraw-Hill.
47.Slaney, J., & Thiebaux, S. (2001). Blocks world revisited. Artificial Intelligence, 125, 119–153.

Citation

MLA

Hoffmann, J., and B. Nebel. “The FF Planning System: Fast Plan Generation Through Heuristic Search”. Journal of Artificial Intelligence Research, vol. 14, 2001, pp. 253–302, https://doi.org/10.1613/jair.855.

APA

Hoffmann, J., & Nebel, B. (2001). The FF Planning System: Fast Plan Generation Through Heuristic Search. Journal of Artificial Intelligence Research, 14, 253–302. https://doi.org/10.1613/jair.855

Chicago

Hoffmann, J., and B. Nebel. 2001. “The FF Planning System: Fast Plan Generation Through Heuristic Search”. Journal of Artificial Intelligence Research 14: 253–302. https://doi.org/10.1613/jair.855.

Harvard

Hoffmann, J. and Nebel, B. (2001) “The FF Planning System: Fast Plan Generation Through Heuristic Search”, Journal of Artificial Intelligence Research, 14, pp. 253–302. Available at: https://doi.org/10.1613/jair.855.

Vancouver

1. Hoffmann J, Nebel B (2001) The FF Planning System: Fast Plan Generation Through Heuristic Search. Journal of Artificial Intelligence Research 14:253–302

BibTeX

@article{Hoffmann_2001, title={The FF Planning System: Fast Plan Generation Through Heuristic Search}, volume={14}, ISSN={1076-9757}, url={http://dx.doi.org/10.1613/jair.855}, DOI={10.1613/jair.855}, journal={Journal of Artificial Intelligence Research}, publisher={AI Access Foundation}, author={Hoffmann, J. and Nebel, B.}, year={2001}, month=May, pages={253–302} }

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 FF Planning System: Fast Plan Generation Through Heuristic Search

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Enforced Hill-Climbing Search Algorithm

Knowl 2 — Relaxed GraphPlan Heuristic Computation

Knowl 3 — Polynomial-Time Tractability and Non-Backtracking of Relaxed Planning Graphs

Knowl 4 — Helpful Actions Pruning

Knowl 5 — Added Goal Deletion Pruning Heuristic

Knowl 6 — Completeness of Enforced Hill-Climbing on Dead-End Free Tasks and Complexity of Dead-End Freeness

Knowl 7 — NP-Completeness of Optimal Action Linearization

Knowl 8 — Relaxed Plan Minimization via NOOPs-First and Precondition Difficulty

Knowl 9 — Compilation of ADL Planning Tasks to Propositional Normal Form

Knowl 10 — Two-Tier Search Architecture with Greedy Best-First Fallback

Knowl 11 — Empirical Comparison of FF and HSP Architectural Components

References

Citation

BibTeX

Access the Paper