Temporal Milestones in HTNs

Fusun Yaman, Brett Benyo, Alice M. MulvehillAAAI 2013 · DOI

Abstract

Hierarchical Task Networks (HTNs) are powerful tools for planning complex operations, yet they traditionally lack the ability to synchronize intermediate task events across disparate branches of a hierarchy. This paper proposes the integration of "temporal milestones"—user-defined intermediate events—into HTN frameworks. By decoupling internal task decomposition from external synchronization requirements, milestones preserve task abstraction while enabling complex coordination. Furthermore, we introduce the DelayedPropagation (D-PC) algorithm, which exploits hierarchical structure to provide quadratic speedups in temporal reasoning. Empirical results in a large-scale aviation domain confirm the scalability and efficiency of this approach.

The Challenge of Cross-Hierarchy Synchronization

In AI planning, HTNs decompose high-level goals into executable subtasks. However, standard HTN models typically only track the start and end times of these tasks. Real-world scenarios often require "middle-of-the-task" synchronization, where an event halfway through one mission must align with an event in another.

Traditionally, linking these intermediate events required breaking task abstraction—forcing a parent task to know the internal details of its children—or creating computationally expensive, monolithic temporal networks. Without a way to reference internal stages, coordinating independent missions (e.g., a surveillance orbit and a strike mission) becomes brittle and difficult to scale.

Figure 3: Synchronization challenges between independent mission hierarchies. Red dashed lines represent required temporal dependencies between internal subtasks of different missions.

Methodology: Temporal Milestones and Selective Visibility

The authors introduce temporal milestones as a solution. These are user-defined intermediate events (e.g., a "strike window" or "refueling point") associated with a task. They act as "hooks" that allow external tasks to synchronize with internal stages without needing to expose the entire subtask decomposition. This "selective visibility" ensures that the hierarchy remains modular and manageable.

To handle the resulting temporal constraints efficiently, the authors developed the DelayedPropagation (D-PC) Algorithm. Standard consistency checking (like Floyd-Warshall) scales poorly ($O(n^3)$). D-PC instead leverages the hierarchical structure by:

  1. Computing temporal requirements for each mission independently.
  2. Combining these at the top level with global constraints.
  3. Propagating results back down the hierarchy only when necessary.
Figure 6: A milestone-augmented Simple Temporal Network (STN). The additional nodes (milestones) allow for cross-hierarchy constraints (red arrows) to be established without flattening the task structure.

Experimental Results

The approach was evaluated using a specialized Air Tasking Order (ATO) domain, featuring complex military aviation scenarios with up to 100 simultaneous missions. Each mission involved approximately 58 tasks and a decomposition depth of 12.

Key findings include:

  • Computational Efficiency: The D-PC algorithm achieved a quadratic speedup in reasoning time compared to naive path consistency methods.
  • Linear Scalability: Memory requirements for D-PC grew linearly with the number of missions, making it suitable for large-scale operations.
  • Robustness: In a 100-mission scenario, the system successfully managed over 800 milestone nodes and 600 goal constraints, demonstrating its viability for real-world industrial or military applications.

Conclusion and Future Work

Temporal milestones provide a robust interface for cross-hierarchy synchronization while maintaining the benefits of task abstraction. The D-PC algorithm further ensures that this added complexity does not come at the cost of performance. Future research will focus on refining the automatic conversion of standard STNs into milestone-augmented versions and testing the algorithm's performance across a broader range of hierarchical planning domains.

Summary updated

BibTeX
@inproceedings{yaman2013temporal,
  author = {Fusun Yaman and Brett Benyo and Alice M. Mulvehill},
  title = {{Temporal Milestones in HTNs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2013},
  doi = {10.1609/aaai.v27i1.8616},
}
Figure