> For the complete documentation index, see [llms.txt](https://neurosymbolicai.gitbook.io/neuro-symbolic-ai-in-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://neurosymbolicai.gitbook.io/neuro-symbolic-ai-in-practice/part-ii-background/chapter-3/3-4-htn.md). # 3.4 Hierarchical Task Network Planning Classical STRIPS/PDDL planning finds sequences of primitive actions to achieve goals. **Hierarchical Task Network (HTN) planning** takes a different approach: it reasons at multiple levels of abstraction, decomposing high-level tasks into subtasks until primitive actions are reached (Erol et al., 1994a). This mirrors how humans actually plan: "prepare dinner" decomposes into "make pasta" and "make salad"; "make pasta" decomposes into "boil water," "cook pasta," "drain pasta," "add sauce." This hierarchical structure is natural to encode, efficient to search, and directly connects to how LLMs decompose tasks through chain-of-thought and multi-step agent behaviors. ## The HTN Formalism An **HTN planning problem** is a triple: $$\Pi\_\text{HTN} = \langle d, w, \text{tn}\_0 \rangle$$ where $d$ is an HTN domain, $w$ is an initial world state, and $\text{tn}\_0$ is an **initial task network** — the top-level task to be accomplished (Erol et al., 1994a). The domain $d$ contains two kinds of **tasks**: * **Primitive tasks** — tasks that correspond directly to executable actions (as in STRIPS: they have preconditions and effects). * **Compound tasks** — abstract tasks that must be *decomposed* into subtask networks using **methods**. A **method** $m$ for compound task $\tau$ specifies: under what conditions (preconditions) $\tau$ can be decomposed, and what the resulting **subtask network** (an ordered or partially-ordered set of sub-tasks) is. ``` compound-task: prepare-dinner method: pasta-dinner precondition: (has-pasta) (has-sauce) subtasks: (ordered boil-water cook-pasta make-salad serve) method: simple-dinner precondition: (has-microwave-meal) subtasks: (microwave-meal) ``` Planning proceeds by **decomposition**: repeatedly replacing a compound task in the task network with the subtask network of an applicable method, until all tasks are primitive. The result is a sequence (or schedule) of primitive actions. ## Formal Properties The expressive power of HTN planning and its relationship to classical planning has been thoroughly characterized (Erol et al., 1994a; Erol et al., 1994b; Alford et al., 2016): * **HTN planning is undecidable in general** when methods can be recursively defined (unlike classical STRIPS which is PSPACE-complete). This follows from a reduction to the halting problem: recursive HTN method libraries can simulate arbitrary Turing machine computation (Erol et al., 1994a). * **Total-order HTN planning** (where all subtask orderings are strict sequences) is decidable and EXPTIME-complete (Alford et al., 2016). Specifically, this result holds for grounded (propositional) total-order HTN; lifted HTN with variables over large object sets may be harder in practice. * **Partial-order HTN planning** (where subtask constraints form a partial order rather than a strict sequence) is also EXPTIME-complete (Alford et al., 2016) — matching the total-order result, since the additional flexibility of partial ordering does not reduce the worst-case complexity class. * **HTN planning is strictly more expressive than classical planning**: there exist plan libraries (sets of desired plans) that can be represented as HTN methods but cannot be captured by any PDDL domain/goal formulation. ## SHOP2 — The Canonical HTN System **SHOP2** (Simple Hierarchical Ordered Planner 2) by Nau et al. (2003)(Nau et al., 2003) is the most widely deployed and extensively studied HTN planner. It uses a **top-down, total-order decomposition** approach: the planner selects the first task in the task network, finds an applicable method, decomposes it, and continues — analogous to a Prolog-style depth-first search over the method library. SHOP2's key technical contributions over predecessor systems include the ability to interleave planning and execution (planning steps can call external procedures that query the current world state), support for axioms (derived predicates defined by Horn clauses), and the ability to efficiently handle ordered task networks with pruning. **Real-world deployments of SHOP2 include:** * **Military logistics:** SHOP2 was used in the SPAR (Scheduling, Planning, and Replanning) system for US Army logistics planning, managing supply chain operations across thousands of actions per plan. * **Web service composition:** SHOP2's method decomposition maps naturally to web service orchestration, where compound tasks are business processes and primitive tasks are individual service calls. * **Game AI:** SHOP2's hierarchical structure was adopted for NPC behavior planning in several commercial games, where behavior trees (a closely related formalism) are now standard. **Note on completeness:** SHOP2 uses depth-first search over method decompositions without maintaining a visited-state list. This means SHOP2 is **sound** (every plan it returns is valid) but **not complete in general** — on domains with cyclic method structures, SHOP2 may loop indefinitely. For *well-founded* HTN domains (where every decomposition strictly reduces task complexity and no cyclic decompositions are possible), SHOP2 is complete within the total-order HTN fragment. The Nau et al. (2003) paper proves soundness; completeness is conditional on well-foundedness of the method library. **Note on SHOP3:** SHOP3 is the actively maintained open-source successor to SHOP2, extending it with improved Common Lisp portability, a richer plugin API, and support for HDDL-style input. The canonical SHOP2 algorithm and formal properties are documented in the Nau et al. (2003) JAIR paper; the SHOP3 codebase at the link below implements those semantics with ongoing maintenance. *Reference:* Nau, Dana, Tsz-Chiu Au, Okhtay Ilghami, Ugur Kuter, J. William Murdock, Dan Wu, and Fusun Yaman. "SHOP2: An HTN Planning System." *Journal of Artificial Intelligence Research* 20 (2003): 379–404. | Code (SHOP3, maintained successor): ## HDDL — Hierarchical Domain Definition Language For two decades, HTN planning lacked a standard input language analogous to PDDL for classical planning. **HDDL** (Hierarchical Domain Definition Language), introduced at AAAI 2020 by Höller et al. (Höller et al., 2020) in the paper "HDDL: An Extension to PDDL for Expressing Hierarchical Planning Problems," standardizes HTN problem specification and enables cross-planner evaluation at the International Planning Competition. HDDL extends PDDL syntax to support task definitions and method specifications: ```pddl (:task prepare-dinner :parameters (?agent - agent)) (:method pasta-dinner :parameters (?agent - agent) :task (prepare-dinner ?agent) :precondition (and (has-pasta ?agent) (has-sauce ?agent)) :ordered-subtasks (and (boil-water ?agent) (cook-pasta ?agent) (serve ?agent))) ``` The HDDL specification introduced benchmarks (38 problem domains, competition tracks for total-order and partial-order HTN), enabling rigorous empirical comparison of HTN planners for the first time. *Reference:* Höller, Daniel, Gregor Behnke, Pascal Bercher, Susanne Biundo, Humbert Fiorino, Damien Pellier, and Ron Alford. "HDDL: An Extension to PDDL for Expressing Hierarchical Planning Problems." *Proceedings of AAAI*, 2020, pp. 9883–9891. ## Connection to Hierarchical Reinforcement Learning For practitioners approaching neuro-symbolic planning from a reinforcement learning background, the structural parallel to the **Options framework** (Sutton, Precup & Singh, 1999) is foundational.(Sutton et al., 1999) An *option* in hierarchical RL consists of: an initiation set (conditions under which the option can begin), a policy (the option's behavior), and a termination condition — structurally identical to an HTN method (its applicability precondition, the decomposition it applies, and the conditions under which it completes). An HTN method library is thus a *hand-crafted option set*; learning HTN methods from data (§2.1) is the data-driven equivalent of option discovery; LLM-based HTN domain induction is the language-model analogue of option generation from demonstrations. This correspondence is more than analogical: the planning efficiency gains from HTN decomposition and the sample efficiency gains from hierarchical RL both derive from the same principle — *temporal abstraction reduces the effective planning horizon*, enabling reasoning at the appropriate level of granularity. The key practical difference: HTN methods are human-interpretable, verifiable, and directly encodable in HDDL; learned options are opaque representations in neural parameter space. Neuro-symbolic planners that combine learned option policies with HTN task structure — using neural networks to learn option initiation and termination conditions while maintaining HTN soundness guarantees — represent an active research frontier at the intersection of ICAPS and NeurIPS.(Sutton et al., 1999) > \[!TIP] **When to use HTN planning:** Prefer HTN over classical PDDL when (1) domain experts can articulate the task decomposition hierarchy — e.g., "a surgery decomposes into preparation, incision, and closure" — (2) the resulting plans must be interpretable to non-experts, or (3) the domain has a clear procedural structure that classical goal-regression planning would rediscover from scratch at each run. HTN methods encode organizational knowledge that classical planners must search for. > \[!WARNING] **Limitation:** HTN planning requires a manually authored method library. Constructing and maintaining this library is an engineering cost that classical PDDL avoids. When domain procedures are unknown, unstable, or highly variable, classical planning or a hybrid approach (LLM-proposed methods validated by an HTN solver) is preferable. ## HTN Planning and LLM Decomposition The structural similarity between HTN planning and LLM-based task decomposition is not coincidental — it reflects a deep organizational principle. When an LLM reasons about a complex task ("plan a product launch"), it produces a hierarchical decomposition: the compound task is broken into subgoals ("market research," "product announcement," "sales training"), each of which may be further decomposed. This is precisely the structure of HTN methods. But unlike a formal HTN system, the LLM's decomposition lacks three properties that HTN planning provides: a formal termination guarantee, a correctness condition (the decomposition achieves the original task specification), and a verified applicability condition (the method's preconditions are actually met). This observation motivates a family of neuro-symbolic architectures (discussed in Chapter 4) that use HTN planning as the formal substrate for LLM-guided decomposition — getting the LLM to propose methods while the HTN solver verifies their correctness and manages the decomposition tree. > \[!IMPORTANT] **Design principle:** When an LLM is given a "task decomposition" prompt, it is performing approximate HTN planning. Replacing the LLM's ad hoc decomposition with a verified HTN method library converts an approximate, fragile behavior into a formal, verifiable one. --- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter: ``` GET https://neurosymbolicai.gitbook.io/neuro-symbolic-ai-in-practice/part-ii-background/chapter-3/3-4-htn.md?ask=&goal= ``` `ask` is the immediate question: it should be specific, self-contained, and written in natural language. `goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.