Landmark Generation in HTN Planning Revisited

Victor Scherer Putrich, Felipe Meneguzzi, André G. PereiraProceedings of the International Conference on Automated Planning and Scheduling 2025 · DOI

Abstract: In Hierarchical Task Network (HTN) planning, landmarks are facts that must hold true, and tasks or methods that must be included in every solution. Existing landmark generation techniques for HTN planning rely on the Delete and Ordering Free (DOF) relaxation and are known to be sound but incomplete, primarily due to the limitations introduced by Task Insertion. This paper presents a new landmark generation method that builds on a previous AND/OR graph-based approach, extending it to capture additional hierarchical dependencies among tasks and methods. We prove that our approach is sound and dominates existing techniques, though it remains incomplete under the DOF relaxation. Experimental results on IPC benchmarks for totally ordered problems show that our method identifies significantly more task and method landmarks across most domains, improving coverage with minimal computational overhead.

Introduction

In automated planning, landmarks serve as essential milestones—facts, tasks, or methods that must occur in every valid solution. Identifying these landmarks early in the planning process provides a roadmap for the planner, allowing it to prune the search space effectively and reach solutions more efficiently.

In Hierarchical Task Network (HTN) planning, the objective is to decompose a high-level initial task into primitive actions using predefined methods. Unlike classical planning, where the focus is primarily on state transitions, HTN planning is governed by a strict hierarchy. While landmarks are powerful tools, existing generation techniques often fail to capture the full complexity of these hierarchical constraints.

The Limitations of Bottom-Up Analysis

Historically, landmark generation in HTN planning has relied on a Bottom-Up (BU) graph approach. This method propagates information from facts and primitive actions up to the high-level tasks. While this approach is sound, it suffers from a significant "blind spot" due to a relaxation known as Task Insertion.

Bottom-Up (BU) landmark generation analysis on a sample HTN graph.

As shown in Figure 2, the BU approach identifies reachability but often ignores whether an action is permitted by the specific task hierarchy. It may conclude that an action is possible because its preconditions are met, even if the hierarchy dictates that the action is not part of any valid decomposition for the current goal. This leads to missing landmarks that are mandatory solely because of the structural requirements of the HTN.

A Bidirectional Approach to Landmarks

To address these limitations, this research introduces a novel Top-Down (TD) graph analysis and combines it with the traditional BU method into a Bidirectional (BID) algorithm.

The Top-Down (TD) Graph

Unlike the BU graph, the TD graph begins at the initial compound task and flows downward through the hierarchy. It enforces hierarchical justification: a task is identified as a landmark only if it is required by every possible method decomposition of the tasks above it. To manage scenarios where multiple methods might produce the same action, the authors utilize "merge nodes" to identify the intersection of required components.

Top-Down (TD) landmark generation analysis, highlighting hierarchical dependencies.

Bidirectional Synergy

The core technical contribution is a fix-point algorithm that alternates between these two perspectives. Landmarks discovered by the BU graph are used to seed the TD graph, which in turn uncovers new hierarchical landmarks. These new findings are fed back into the BU graph, and the process repeats until no further landmarks can be identified. The authors formally prove that this BID approach is sound and strictly dominates previous techniques, finding a superset of all previously detectable landmarks.

Experimental Evaluation

The researchers evaluated the BID approach using benchmarks from the IPC-2023 (International Planning Competition) for totally ordered HTN problems. The test suite included 22 domains, such as Barman-BDI, Blocksworld, Satellite, and Transport.

The results demonstrate a dramatic increase in landmark detection compared to the BU baseline:

  • Fact Landmarks: Increased by 8%.
  • Task Landmarks: Increased by 87%.
  • Method Landmarks: Increased by a staggering 5,094% (from 380 to over 19,000 total landmarks).

Crucially, this increased detection translated into superior planning performance. When used with a landmark-count heuristic in a Weighted A* search, the BID method solved more problems and required significantly fewer node expansions. Furthermore, the computational overhead was negligible, with the bidirectional analysis taking less than 5 seconds on average per problem instance.

Conclusion

By recognizing that the HTN hierarchy is a rich source of mandatory milestones, this work significantly advances the state-of-the-art in landmark generation. While the method remains incomplete under the DOF relaxation—as it does not yet account for delete effects or specific ordering constraints—it provides a much more robust roadmap for HTN planners. Future work will explore extending this analysis to partially ordered problems and identifying disjunctive landmarks to further improve search guidance.

Summary updated

Abstract

In Hierarchical Task Network (HTN) planning, landmarks are facts that must hold true, and tasks or methods that must be included in every solution. Existing landmark generation techniques for HTN planning rely on the Delete and Ordering Free (DOF) relaxation and are known to be sound but incomplete, primarily due to the limitations introduced by Task Insertion. This paper presents a new landmark generation method that builds on a previous AND/OR graph-based approach, extending it to capture additional hierarchical dependencies among tasks and methods. We prove that our approach is sound and dominates existing techniques, though it remains incomplete under the DOF relaxation. Experimental results on IPC benchmarks for totally ordered problems show that our method identifies significantly more task and method landmarks across most domains, improving coverage with minimal computational overhead.
BibTeX
@inproceedings{putrich2025landmark,
  author = {Victor Scherer Putrich and Felipe Meneguzzi and André G. Pereira},
  title = {{Landmark Generation in HTN Planning Revisited}},
  booktitle = {Proceedings of the International Conference on Automated Planning and Scheduling},
  year = {2025},
  doi = {10.1609/icaps.v35i1.36123},
}

Loading related content...

Figure