The FF Heuristic for Lifted Classical Planning

Augusto B. Corrêa, Florian Pommerening, Malte Helmert, Guillem FrancèsAAAI 2022 · OpenReview

Abstract

Heuristics for lifted planning are not yet as informed as the best heuristics for ground planning. Recent work introduced the idea of using Datalog programs to compute the additive heuristic over lifted tasks. Based on this work, we show how to compute the more informed FF heuristic in a lifted manner. We extend the Datalog program with executable annotations that can also be used to define other delete-relaxation heuristics. In our experiments, we show that a planner using the lifted FF implementation produces state-of-the-art results for lifted planners. It also reduces the gap to state-of-the-art ground planners in domains where grounding is feasible.

Introduction

In classical planning, the objective is to determine a sequence of actions that transitions a system from an initial state to a goal state. Modern planners rely heavily on heuristics to guide their search through the state space. Among the most successful are heuristics based on delete-relaxation, such as the FF heuristic ($h^{FF}$), which simplifies the problem by assuming that facts, once true, never become false.

Traditionally, computing these heuristics requires grounding: the process of instantiating high-level schematic rules into every possible specific instance. However, for large-scale or complex problems, the number of ground instances can explode, leading to memory exhaustion before the search even begins. Lifted planners circumvent this by working directly with high-level rules. Historically, lifted heuristics have been less "informed" (accurate) than their ground counterparts. This research bridges that gap by implementing the highly effective FF heuristic within a lifted framework.

Methodology: Annotated Datalog

The authors introduce Annotated Datalog, a framework that extends the logic programming language Datalog to compute complex heuristics efficiently. This approach involves several key components:

  1. Annotations: Datalog rules are associated with executable instructions. When the Datalog engine derives a fact (e.g., goal reachability), it executes these instructions to perform additional computations, such as back-chaining to extract a relaxed plan.
  2. Plan Extraction: By tracing the logic of the derivation, the planner collects a set of actions that form a relaxed plan. The size of this set is the $h^{FF}$ value.
  3. Rule-Based FF ($h^{R-FF}$): A simpler variant is proposed that counts every instance an action's effect is utilized. While it may overcount, it is computationally faster and serves as a robust baseline.
  4. Program Transformations: To maintain efficiency, the authors implement optimizations like rule merging, predicate collapsing, and variable renaming, which simplify the logic program without altering the heuristic output.

Experimental Evaluation

The proposed methods were implemented in the Powerlifted planner and evaluated against standard benchmarks from the International Planning Competitions (IPC) and a set of Hard-to-Ground (HTG) tasks.

Table 1: Coverage comparison across various domains. The proposed hFF heuristic (Lazy + PO) achieves the highest total coverage of 1516 tasks.

As shown in Table 1, the lifted $h^{FF}$ implementation achieves state-of-the-art coverage. Notably, in HTG domains where grounding is prohibitive, the lifted approach significantly outperforms industry-standard ground planners like Fast Downward. For instance, in the visitall domain, the lifted planner solved 143 tasks compared to the ground planner's 72.

Figure 1: Solved tasks over total time. The proposed lifted hFF (red line) scales effectively, demonstrating superior performance as the search time increases.

Figure 1 illustrates the efficiency of the heuristic. While computing a lifted heuristic is more expensive per state than simpler methods, the superior guidance it provides results in fewer states explored and more tasks solved overall within the time limit.

Key Insights and Conclusion

This work demonstrates that Datalog is an exceptionally powerful engine for computing fixed points in AI planning. The Annotated Datalog framework is general-purpose, offering a path toward implementing other advanced techniques, such as landmark-based heuristics, in a lifted setting.

While computing lifted heuristics remains theoretically complex, this research proves that the practical benefits of high-quality guidance can outweigh the computational overhead. By closing the performance gap between lifted and ground planners, this work opens new possibilities for solving large-scale planning problems that were previously considered intractable.

Summary updated

Abstract

Heuristics for lifted planning are not yet as informed as the best heuristics for ground planning. Recent work introduced the idea of using Datalog programs to compute the additive heuristic over lifted tasks. Based on this work, we show how to compute the more informed FF heuristic in a lifted manner. We extend the Datalog program with executable annotations that can also be used to define other delete-relaxation heuristics. In our experiments, we show that a planner using the lifted FF implementation produces state-of-the-art results for lifted planners. It also reduces the gap to state-of-the-art ground planners in domains where grounding is feasible.
BibTeX
@inproceedings{correa2022ff,
  author = {Augusto B. Corrêa and Florian Pommerening and Malte Helmert and Guillem Francès},
  title = {{The FF Heuristic for Lifted Classical Planning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  url = {https://openreview.net/forum?id=pbAGr3oHkE},
}
Figure