HTN-MAKER: Learning HTNs with Minimal Additional Knowledge Engineering Required

Chad Hogg, Héctor Muñoz-Avila, Ugur KuterAAAI 2008

Introduction

In the field of automated planning, a significant divide exists between classical "flat" planners and Hierarchical Task Network (HTN) planners. While classical planners are easier to configure—requiring only basic action definitions—they often fail to scale to complex, real-world problems due to the vastness of the search space. Conversely, HTN planners offer superior performance by utilizing domain-specific knowledge to decompose high-level goals into manageable sub-tasks. However, this performance comes at the cost of intensive "knowledge engineering," where human experts must manually author complex hierarchical methods.

HTN-MAKER addresses this bottleneck by introducing an algorithm capable of automatically learning HTN methods from successful plan examples and minimal high-level task annotations. This approach bridges the gap, providing the efficiency of hierarchical planning without the prohibitive manual labor.

The HTN-MAKER Algorithm

The core innovation of HTN-MAKER is its ability to construct hierarchical structures by analyzing the relationship between actions in a flat plan and the intended effects of high-level tasks. The algorithm requires three primary inputs: a set of basic planning operators, a collection of solution plans, and a set of "annotated tasks" (task names paired with the state changes they achieve).

Bottom-Up Construction and Regression

Unlike previous learning systems that focused solely on how individual actions achieve goals, HTN-MAKER employs both horizontal and vertical regression. It scans a plan to identify segments that satisfy the requirements of an annotated task. Once a segment is identified, the algorithm creates a "method" where those segments—which may consist of basic actions or previously learned sub-methods—become the sub-tasks.

Figure 1: An example of a hierarchical task decomposition for a delivery task learned by HTN-MAKER.

To ensure the validity of these learned methods, the algorithm incorporates "verifier tasks." These act as semantic checkpoints at the end of a method to confirm that the world state matches the task's intended effects, preventing the planner from applying incorrect hierarchical logic during future problem-solving.

Experimental Evaluation

The authors evaluated HTN-MAKER across three standard International Planning Competition (IPC) benchmarks: Logistics (transporting packages), Blocks-World (stacking blocks), and Satellite (scheduling observations).

Key Results and Convergence

The results demonstrate that HTN-MAKER can rapidly acquire the knowledge necessary to solve complex problems. In the Logistics and Satellite domains, the algorithm showed exceptional convergence rates. For instance, in Logistics, the planner reached near-perfect performance after observing only 25 training examples and solved 100% of test problems after 60 examples.

Figure 2: Learning curves showing the percentage of problems solved as the training size increases across the Logistics, Blocks-World, and Satellite domains.

Blocks-World presented a greater challenge due to high goal interdependence; moving one block often negates a previously achieved goal. While learning was slower in this domain, the authors established a theoretical proof of "completeness": given a sufficient number of examples, HTN-MAKER will eventually learn all methods required to solve any solvable problem within a "classically-partitionable" domain.

Theoretical Insights and Future Work

A significant contribution of this research is the definition of "classically-partitionable" problems. This new class of problems is more expressive than standard classical planning but remains more constrained than general HTNs. The authors proved that HTN-MAKER is guaranteed to learn to solve any problem within this class, provided it is given the appropriate task annotations.

Despite its success, the requirement for human-provided "annotated tasks" remains a minor bottleneck. While significantly less demanding than writing full HTN methods, future research could focus on discovering these high-level tasks automatically. Additionally, while the current algorithm focuses on finding any valid solution, integrating Reinforcement Learning could help the system prioritize the most efficient methods when multiple hierarchical paths are discovered for the same task.

Summary updated

BibTeX
@inproceedings{hogg2008htn,
  author = {Chad Hogg and Héctor Muñoz-Avila and Ugur Kuter},
  title = {{HTN-MAKER: Learning HTNs with Minimal Additional Knowledge Engineering Required}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
}
Figure