Abstract
Landmark generation is a powerful technique in classical planning, yet its application to Hierarchical Task Network (HTN) planning has remained fragmented. This paper introduces a unified approach that represents both task hierarchies and state-based constraints within a single AND/OR graph. By propagating requirements through this structure, the proposed algorithm identifies a broader set of landmarks in polynomial time. Empirical evaluations demonstrate that this method discovers more than twice as many landmarks as existing baselines, significantly reducing search effort across standard HTN benchmarks.
Introduction
In automated planning, a "landmark" is a feature—such as a specific state being true or a task being performed—that is guaranteed to be part of every possible solution. These landmarks act as a roadmap, guiding solvers toward the goal. While landmark generation is a mature field in classical planning, it is less developed in HTN planning. HTN planning is inherently more complex due to its hierarchical nature, where high-level abstract tasks are decomposed into sub-tasks until only basic actions remain.
Previous HTN landmark methods were often narrow, focusing either on the hierarchy while ignoring state-based constraints (preconditions and effects) or vice versa. This paper bridges that gap with a unified approach that integrates both elements.
Methodology: Unified AND/OR Graphs
The core contribution of this work is a novel method based on AND/OR graphs. The entire HTN problem—including abstract tasks, decomposition methods, primitive actions, and state facts—is represented as a single directed graph.
- AND Nodes: Represent requirements that must all be met (e.g., a "method" requires all its sub-tasks to be completed).
- OR Nodes: Represent choices where at least one must be met (e.g., an abstract task can be solved by any one of several different methods).
By propagating requirements through this graph, the algorithm identifies nodes that are "unavoidable" on the path from the initial task to a valid plan. Unlike previous work that only looked at mandatory tasks, this method integrates fact landmarks and method landmarks into the same process. Crucially, while finding all landmarks is coNP-hard, this specific generation method runs in polynomial time (P), making it practical for real-world use.
Experimental Evaluation
The researchers evaluated their approach using a benchmark set of 144 problem instances across 8 different domains (e.g., Satellite, Rover, and Transport) within the standard PANDA framework.
Key Results
- Quantity of Landmarks: The new method found 13% more task landmarks and more than double the total number of landmarks (including facts and methods) compared to the previous state-of-the-art baseline. As shown in the comparison below, the AND/OR method consistently outperforms the previous MT method across nearly all tested domains.
- Efficiency: Despite the increased complexity of the graph, generation time remained negligible, averaging just 1.3 milliseconds per problem.
- Search Performance: When used to guide a planner, the additional landmarks reduced the number of search nodes required to find a solution by a median of 13%, with some instances seeing a reduction of over 99%.
Discussion and Future Work
The most significant insight is that HTN decomposition and classical state-transitions are structurally similar enough to be handled by the same AND/OR logic. This allows the discovery of "hidden" landmarks where a task becomes essential only because it is the sole way to satisfy a state-based precondition of another landmark.
However, the method remains "incomplete" because it utilizes delete-relaxation, ignoring actions that make facts false. Future work will explore accounting for specific task orderings and integrating these landmarks into more sophisticated planning systems, such as those using cost-based optimization or landmark-based restarts.
Summary updated