Skip to content
Tutorials Center
My learning

Topics

Lesson 31 of 46 ยท Planning

Hierarchical Task Network (HTN) Planning

Build a hierarchical task network planner in Python: primitive and compound tasks, methods, preconditions, backtracking decomposition and when HTN beats STRIPS search.

Classical planners such as the ones in Classical Planning are goal-driven: they are told what must be true at the end and search for any action sequence that makes it so. That is elegant, but it ignores a huge resource: humans already know how to do most things. Nobody plans a trip by searching through every possible sequence of door-opening and step-taking actions. You know the recipe: get to the station, take the train, walk to the hotel.

Hierarchical Task Network (HTN) planning puts that recipe knowledge into the planner. Instead of a goal state, the planner is given a to-do list of tasks, and a library of methods that say how each abstract task breaks into smaller ones. Planning means decomposing tasks, level by level, until only primitive actions remain. HTN planners are used in game AI, logistics, military planning, manufacturing and robot control, wherever experts can state the procedures.

Tasks, methods and operators

An HTN domain has three ingredients:

Ingredient Meaning Example
Primitive task (operator) An action that changes the state directly, with preconditions and effects walk(home, park), call_taxi(home)
Compound task An abstract goal that cannot be executed directly travel(home, park)
Method A rule: "to do this compound task, if these conditions hold, do these subtasks in order" "to travel a short distance, walk"

A compound task can have several methods, and each method has a precondition that says when it applies. That is where the expert's knowledge goes: if the distance is short, walk; otherwise take a taxi.

graph TD
    T["travel(home, park)"] -->|method: short distance| W["walk(home, park)"]
    T -->|method: long distance| A["call_taxi(home)"]
    T --> B["ride_taxi(home, park)"]
    T --> C["pay_driver()"]
    A -.-> B -.-> C

One compound task, two methods. Which method the planner uses depends on the state.

The planner starts from the initial state and a list of tasks, for example [travel(home, park)]. It repeatedly takes the first task and:

  • if it is primitive, checks its preconditions, applies its effects to the state and appends it to the plan;
  • if it is compound, tries each applicable method in turn, replaces the task by the method's subtasks and recurses. If a choice leads to a dead end, it backtracks and tries the next method.

The process ends with a plan (a list of primitive actions) or failure when the task list is empty or no method works.

A working HTN planner

This is a compact totally ordered planner in the spirit of the SHOP family: subtasks are performed in the order listed, and each method can test the current state. The state is a dictionary, and operators return a new state (or None when they are not applicable), which makes backtracking trivial.

Python An HTN planner for travel

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For the short trip the first method (walk) applies and nothing else is tried. For the airport, walking is not allowed (distance 12), so the taxi method is used: three primitive steps in order. The two-leg trip decomposes into two travel tasks and picks a method independently for each. The last call fails because the traveller cannot afford a taxi and walking is not permitted for long distances, so plan returns None. All the expert knowledge is in travel_methods.

HTN versus STRIPS-style planning

An ordinary planner would explore every sequence of the four operators, including useless ones like paying a driver before riding. An HTN planner only considers action sequences that some method sanctions, so the search space shrinks dramatically.

Classical (STRIPS/PDDL) HTN
Input Initial state + goal Initial state + tasks
Search over Action sequences Task decompositions
Knowledge needed Operators only Operators and methods
Speed Slows down fast as the domain grows Fast when methods are good
Completeness Finds a plan if one exists Only finds plans that the methods allow
Flexibility Can find creative, unexpected plans Mostly follows the expert recipes

The trade-off is clear. HTN gains speed and produces plans that look sensible to humans, because they follow human procedures. But it needs a knowledge engineer to write the methods, and if the methods have gaps the planner cannot be creative. In practice, planners often mix both: methods for the routine parts and search for the details.

Measuring the saving

The next program makes the contrast concrete. The world is a small road map, some items can only be bought in certain places, and the goal is to reach the airport carrying a ticket plus any number of shopping items. A blind breadth-first search must try every move and purchase in every order. The method-based plan simply follows a recipe. Watch how the number of states the blind search expands grows as more items are required.

Python Blind search versus method-guided planning

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The blind search finds a shortest plan, but the work it does grows quickly with each extra item, because it has to consider every order of buying them. The recipe costs nothing at planning time and, for the shopping trips, matches the length of the blind search plan. (Strictly, the recipe for the ticket-only case adds a pointless trip to the shop, which is the price of a fixed method: it is quick, but not always optimal.) That is why HTN planners scale to large real-world problems where blind search would drown.

Partial-order tasks and real systems

The planner above is totally ordered: it always decomposes the first task, so every task list is a sequence. Many real domains allow partially ordered tasks (do A and B in any order, then C), and planners such as SIPE and O-Plan handle constraints between subtasks, resources and time. Well-known HTN systems include SHOP and SHOP2, O-Plan, UMCP and PANDA; hierarchical planners also power the NPC behaviour in some commercial games (Horizon Zero Dawn and F.E.A.R. used HTN or similar hierarchical planners) and the behaviour trees used in robotics are close cousins. The PDDL family has an HTN extension, HDDL, which makes domains portable between planners.

Note: HTN planning can handle problems that STRIPS cannot express easily, such as "do the whole assembly, in this order, and loop over every part". In its general form it is even undecidable, so practical planners limit the recursion in the methods.

Writing good methods

  • Make each method's precondition specific, so wrong methods are rejected early.
  • Order the alternatives from most preferred to least; the first one that works wins.
  • Include a fallback method (for example "if no taxi is available, take the bus") so failure is handled by decomposition and not by the caller.
  • Keep primitive operators small and reusable, and put the domain logic in the methods.
  • Test each method with its own small task before composing them.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does an HTN planner receive as its problem?

    The input is a task network. The planner decomposes tasks using methods until only primitive operators remain.
  2. 2. What is a method in HTN planning?

    Methods carry the expert knowledge: for this task, in this situation, do these subtasks.
  3. 3. When a method's decomposition leads to a dead end, the planner:

    Decomposition is a search over method choices, so failures trigger backtracking to alternatives.
  4. 4. What is the main drawback of HTN planning compared with classical planning?

    HTN gets its speed from domain knowledge. If the methods are incomplete, valid plans outside them are missed.
  5. 5. Which tasks does an HTN planner execute directly in the final plan?

    Compound tasks are always decomposed. The final plan contains only primitive operators.

Summary

  • HTN planning starts from tasks, not goal states, and decomposes compound tasks into subtasks with expert-written methods until only primitive operators remain.
  • Methods have preconditions, so the state decides which decomposition is used; failures trigger backtracking.
  • HTN prunes the search space strongly and gives human-readable plans, but depends on the quality and completeness of the methods.
  • Real systems (SHOP2, O-Plan, PANDA, HDDL) add partial ordering, resources and time, and game AI and robotics use closely related structures.

Next: Probability for AI.