Abstract
This paper introduces the first comprehensive framework for solving Fully Observable Non-Deterministic (FOND) Hierarchical Task Network (HTN) planning problems. By compiling non-deterministic problems into deterministic relaxations, we enable the use of existing high-performance grounding and heuristic techniques to find "strong" plans—policies that guarantee reaching a goal despite uncertain action outcomes. We present the Koala system, which utilizes an AO* search algorithm and generic heuristics to solve these complex problems. Our evaluation on a new benchmark suite of 75 instances demonstrates the viability and efficiency of this approach.
Introduction
Automated planning typically follows two distinct paradigms: Hierarchical Task Network (HTN) planning, which uses task hierarchies to guide search based on expert knowledge, and Fully Observable Non-Deterministic (FOND) planning, which addresses uncertainty in action outcomes. While HTN planning excels at encoding complex procedural constraints, it traditionally assumes a deterministic environment. Conversely, FOND planning finds robust policies for uncertain worlds but often lacks the guidance provided by hierarchical structures.
This research bridges the gap by providing the formal foundations—grounding, search algorithms, and heuristics—to solve FOND HTN problems while strictly adhering to hierarchical constraints. Unlike previous attempts that treated hierarchy as mere "advice," our approach, implemented in the Koala system, treats the task network as a formal requirement, ensuring that resulting policies follow intended expert logic.
The Koala System
The Koala system is built upon three main pillars designed to handle the intersection of hierarchy and non-determinism.
All-Outcome Determinization
The core theoretical contribution is the transformation of a non-deterministic HTN problem into a deterministic "relaxation." A non-deterministic action with $n$ possible outcomes is converted into a compound task with $n$ distinct deterministic methods. This allows the system to leverage existing deterministic planning tools for non-deterministic problems.
Grounding and Search
Grounding in HTN is notoriously difficult; Koala addresses this by using a "black-box" deterministic grounder on the relaxed problem and re-infers a valid grounding for the original FOND problem. For search, the system employs an adapted AO* algorithm to navigate the AND/OR graph structure of FOND problems. The goal is to find "strong" solutions: policies guaranteed to reach the goal in finite time regardless of which non-deterministic outcomes occur.
Generic Heuristics
By utilizing the determinized relaxation, Koala can incorporate standard deterministic HTN heuristics, such as $RC^{Max}$, $RC^{FF}$, and $RC^{Add}$. This "free lunch" allows the system to benefit from decades of research in deterministic planning without requiring the development of specialized FOND heuristics from scratch.
Benchmarking FOND HTN
To evaluate the system, the authors extended the Hierarchical Domain Definition Language (HDDL) to support non-deterministic effects via a new oneof keyword. They introduced a benchmark suite of 75 instances across five domains derived from the 2020 International Planning Competition (IPC): Depots, Rover, Childsnack, Satellite, and Transport. These domains introduce various forms of uncertainty, such as equipment failure or environmental changes.
Results and Analysis
Experimental results indicate that Koala successfully solves a significant portion of the benchmarks within standard time limits. Grounding overhead was found to be negligible, typically under one second and never exceeding eight seconds, confirming that the search space, rather than domain description complexity, is the primary bottleneck.
The choice of heuristic significantly impacts performance. As shown in the results table, $RC^{Max}$ was particularly effective in the Depots and Satellite domains. In the Transport domain, $RC^{Add}$ and $RC^{FF}$ showed higher coverage than $RC^{Max}$, with $RC^{Add}$ being uniquely capable of solving specific difficult instances within that domain.
Conclusion and Future Work
This work establishes a robust foundation for FOND HTN planning. Key insights include the effectiveness of deterministic relaxations and the viability of using deterministic oracles for grounding. However, limitations remain: the current AO* search is restricted to acyclic spaces, precluding "strong cyclic" solutions. Future work will focus on expanding search capabilities to handle cycles and developing more specialized heuristics that account for the double-relaxation currently employed.
Summary updated