## Definition **Hierarchical Task Network (HTN) planning** decomposes an abstract task into sub-tasks until only primitive (directly executable) tasks remain. Instead of searching state space directly, HTN searches the *space of task decompositions* guided by expert-authored methods. ## The Core Idea Classical planners reason about preconditions and effects, hunting for plans from scratch. HTN encodes *how experts solve problems* — recipes for breaking tasks down. ## Components - **Primitive tasks** — directly executable actions with preconditions and effects (like STRIPS operators). - **Compound tasks** — abstract tasks that must be decomposed. - **Methods** — rules that decompose a compound task into a (possibly ordered) set of sub-tasks. A single compound task may have multiple methods (different ways to achieve it). ## Decomposition Example Compound task: *make pizza*. Method 1 — *from scratch*: - Sub-tasks: make dough, prepare sauce, add toppings, bake. Method 2 — *from a frozen pizza*: - Sub-tasks: unwrap, place on tray, bake. The planner picks a method based on context (e.g., availability of dough vs frozen pizza). ## The Algorithm ``` plan(tasks, state): if all tasks are primitive: return their sequence pick a compound task t for each method m that decomposes t: if m's preconditions hold in state: recurse on (tasks with t replaced by m's sub-tasks) if recursion succeeds: return plan return failure ``` Variants exist for ordered, partially-ordered, and unordered task networks. ## Properties - **Sound** — if a plan is returned, it achieves the abstract goal. - **Complete only relative to the method library** — if the library lacks decompositions for some situation, the planner fails even if a primitive-action plan exists. - **Often dramatically faster than classical planning** — domain knowledge prunes huge swaths of state space. ## When HTN Wins - Tasks have well-understood structure (recipes, procedures). - Expert knowledge is available to encode methods. - The same abstract goal recurs in many slightly different contexts. Examples: logistics, military operations planning, robot task planning, computer game NPC behaviour. ## When HTN Loses - Truly novel problems where no methods are pre-encoded. - Domains where the right decomposition strategy isn't known. ## Notable Systems - **SHOP / SHOP2** — ordered task decomposition; widely deployed for military, manufacturing planning. - **PANDA** — partially ordered HTN. ## Connection to LLM Agents LLM-driven "planning" often mimics HTN decomposition in natural language: an agent breaks a high-level goal into sub-goals, then sub-sub-goals, until each step is a tool call. The structural similarity is striking — though LLM decomposition has no formal completeness guarantee. ## Related - [[Classical Planning]] - [[STRIPS]] - [[PDDL]] - [[Agentic Loop]]