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.
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:
- Computing temporal requirements for each mission independently.
- Combining these at the top level with global constraints.
- Propagating results back down the hierarchy only when necessary.
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