Hierarchical Task Networks: Structured Planning for AI Agents

Introduction: From Tasks to Subtasks

Imagine asking an AI agent to “plan a vacation.” This high-level goal decomposes into booking flights, reserving hotels, planning activities - each of which breaks down further. How do we give agents the ability to systematically decompose complex goals into achievable actions? Enter Hierarchical Task Networks (HTN), one of the most powerful planning frameworks in AI agent systems.

HTN planning represents goals as tasks that can be either primitive (directly executable actions) or compound (decomposable into subtasks). This mirrors how humans naturally plan: we think hierarchically, breaking “plan vacation” into “arrange transportation,” “book accommodation,” and “schedule activities,” then further decompose each until we reach concrete actions.

For AI agent programmers, HTNs provide a structured approach to complex planning that’s more efficient than state-space search and more intuitive than classical STRIPS-style planning.

Historical Context: The Evolution of Planning

Origins (1970s-1980s): HTN planning emerged from NOAH (Nets of Action Hierarchies), developed by Earl Sacerdoti at SRI International in 1975. Sacerdoti recognized that real-world planning required reasoning at multiple levels of abstraction simultaneously - a limitation of then-current planners that operated in flat action spaces.

Theoretical Foundations (1990s): The formalization came with SHOP (Simple Hierarchical Ordered Planner) by Dana Nau and colleagues at University of Maryland in 1999, followed by SHOP2 in 2003. These systems established HTN as a distinct planning paradigm with strong theoretical foundations and practical advantages over classical planning.

Modern Relevance (2020s): HTN principles now underpin many modern AI agent frameworks. LangGraph’s conditional edges and sub-graphs, hierarchical reinforcement learning agents, and even LLM-based agents that use chain-of-thought decomposition all employ HTN-like structures. Understanding HTN gives you a mental model for structuring complex agent behavior.

Core Concepts: How HTN Planning Works

1. Task Types

Primitive Tasks: Directly executable actions that change the world state

Example: book_flight(origin, destination, date)
These are the leaves of your planning tree

Compound Tasks: High-level goals decomposable into subtasks

Example: arrange_transportation(origin, destination) → [book_flight(...), reserve_car(...)]
These are internal nodes that provide structure

2. Methods

Methods define how to decompose compound tasks into subtasks. Each compound task can have multiple methods representing different ways to achieve it.

Example methods for arrange_transportation:

Method 1 (fly): If distance > 500 miles → [book_flight, reserve_airport_transfer]
Method 2 (drive): If distance < 300 miles → [rent_car]
Method 3 (train): If rail_available → [book_train_ticket]

The planner chooses methods based on preconditions - conditions that must be true for the method to be applicable.

3. Preconditions and Effects

Like classical planning:

Preconditions: World state requirements before executing an action
Effects: How actions change the world state

Example:

Primitive Task: book_flight(origin, dest, date)
Preconditions:
  - has_payment_method
  - date_is_future
Effects:
  - flight_booked(origin, dest, date)
  - account_balance -= flight_cost

Algorithm: HTN Planning in Pseudocode

def HTN_plan(task_list, state, domain):
    """
    task_list: List of tasks to accomplish
    state: Current world state
    domain: HTN domain (tasks, methods, operators)
    Returns: Plan (sequence of primitive actions) or FAILURE
    """
    if task_list is empty:
        return []  # Success: all tasks accomplished
    
    task = task_list[0]  # Take first task
    remaining_tasks = task_list[1:]
    
    if task is primitive:
        # Check if action is applicable
        if preconditions(task, state) are satisfied:
            new_state = apply_effects(task, state)
            rest_of_plan = HTN_plan(remaining_tasks, new_state, domain)
            if rest_of_plan is not FAILURE:
                return [task] + rest_of_plan
        return FAILURE
    
    else:  # task is compound
        # Try each applicable method for decomposing task
        for method in domain.methods[task]:
            if method.preconditions satisfied in state:
                subtasks = method.subtask_list
                # Insert subtasks before remaining tasks
                new_task_list = subtasks + remaining_tasks
                plan = HTN_plan(new_task_list, state, domain)
                if plan is not FAILURE:
                    return plan
        
        return FAILURE  # No method succeeded

Key insight: HTN planning is a depth-first search through the space of task decompositions, backtracking when a decomposition fails.

Mathematical Formulation

An HTN domain is a tuple: D = (T, M, P)

T: Set of tasks (T = T_primitive ∪ T_compound)
M: Set of methods, where each method m = (t, pre(m), sub(m))
- t ∈ T_compound (the task it decomposes)
- pre(m): preconditions (logical formula over state)
- sub(m): ordered list of subtasks
P: Set of primitive operators (actions with preconditions and effects)

HTN Planning Problem: Given initial state s₀, initial task list T₀, and domain D, find a totally-ordered sequence of primitive actions (a plan) π such that:

Executing π in s₀ is valid (preconditions satisfied)
π is a valid decomposition of T₀ according to D’s methods

Complexity: HTN planning is undecidable in the general case, but practical restrictions (like SHOP’s totally-ordered subtasks) make it decidable and often more efficient than classical planning for structured domains.

Design Patterns: HTN in Agent Architectures

Pattern 1: Goal-Oriented Agents

class HTNAgent:
    def __init__(self, domain):
        self.domain = domain
        self.state = {}
        self.plan = []
    
    def set_goal(self, goal_task):
        """Set high-level goal"""
        self.plan = HTN_plan([goal_task], self.state, self.domain)
    
    def execute_step(self):
        """Execute next action in plan"""
        if self.plan:
            action = self.plan.pop(0)
            result = self.execute_action(action)
            self.state = self.apply_effects(action, self.state)
            return result
        return None

Pattern 2: Reactive Re-planning

When the environment changes, HTN agents can replan from their current position:

def reactive_htn_agent(initial_goal, max_iterations=100):
    state = perceive_environment()
    task_list = [initial_goal]
    
    for _ in range(max_iterations):
        # Plan or replan if needed
        plan = HTN_plan(task_list, state, domain)
        
        if plan is FAILURE:
            return "Goal not achievable"
        
        # Execute first action
        action = plan[0]
        state = execute_and_observe(action)
        
        # Update remaining tasks based on execution
        task_list = update_tasks(plan[1:], state)
        
        if goal_achieved(state):
            return "Success"

Practical Example: Personal Assistant Agent

# Define HTN domain for personal assistant
class TaskDomain:
    def __init__(self):
        self.methods = {
            'plan_event': [
                self.method_in_person_event,
                self.method_virtual_event
            ],
            'send_invitations': [
                self.method_email_invitations,
                self.method_calendar_invitations
            ]
        }
    
    def method_in_person_event(self, task, state):
        """Method: Plan in-person event"""
        if state['attendee_count'] > 5:
            return [
                ('book_venue', task.location),
                ('arrange_catering', task.attendee_count),
                ('send_invitations', task.attendees),
                ('schedule_reminder', task.date)
            ]
        return None  # Preconditions not met
    
    def method_virtual_event(self, task, state):
        """Method: Plan virtual event"""
        return [
            ('create_video_meeting', task.duration),
            ('send_invitations', task.attendees),
            ('schedule_reminder', task.date)
        ]

# Usage
domain = TaskDomain()
state = {
    'attendee_count': 12,
    'has_video_software': True,
    'budget': 500
}

initial_task = Task('plan_event', 
                    location='office',
                    attendee_count=12,
                    date='2025-11-15')

plan = HTN_plan([initial_task], state, domain)
print(plan)
# Output: [('book_venue', 'office'), 
#          ('arrange_catering', 12),
#          ('send_invitations', [...]),
#          ('schedule_reminder', '2025-11-15')]

HTN vs. Alternative Planning Approaches

Approach	Strengths	Limitations	Best For
HTN Planning	Hierarchical structure, efficient, domain knowledge encoded in methods	Requires explicit methods, less flexible	Structured domains, known decomposition patterns
Classical (STRIPS)	Domain-independent, provably complete	Inefficient for large spaces	Simple, well-defined problems
Reinforcement Learning	Learns from experience, handles uncertainty	Requires many episodes, black-box	Stochastic environments, learned behavior
LLM-based Planning	Flexible, handles natural language	Non-deterministic, requires validation	Open-ended tasks, human-like reasoning

Trade-off: HTN sacrifices flexibility (you must define decomposition methods) for efficiency and structure. It works best when you understand the domain well enough to encode planning knowledge.

Latest Developments & Research

Integrating HTN with LLMs (2024-2025)

Recent research explores using LLMs to generate HTN methods dynamically:

LLM-HTN Hybrid:

LLM generates candidate task decompositions in natural language
System converts to formal HTN methods
Classical HTN planner validates and executes

Paper: “LLM-Assisted Hierarchical Task Planning” (arXiv 2024) showed this approach combines LLM flexibility with HTN’s guarantees, achieving 78% success on complex household tasks vs. 52% for pure LLM agents.

HTN in Multi-Agent Systems

Distributed HTN Planning: Agents share subtasks discovered during decomposition, enabling cooperative planning. The Contract Net Protocol (covered in another article) can be combined with HTN: agents bid on subtasks rather than atomic actions.

Application: Robot warehouse coordination - high-level “fulfill order” task decomposes into subtasks assigned to specialized robots.

HTN for Game AI (2025)

Modern game engines (Unreal 5, Unity) incorporate HTN-based AI:

NPCs use HTN to plan complex behaviors (stealth, combat tactics)
Real-time re-planning as player actions change the environment
More believable AI than finite state machines or behavior trees alone

Cross-Disciplinary Connections

Cognitive Science: HTN mirrors human hierarchical planning. Research in cognitive psychology shows humans naturally think in terms of goals, subgoals, and actions - exactly HTN’s structure. Studies suggest teaching humans to plan using HTN-like decomposition improves problem-solving.

Project Management: Work Breakdown Structure (WBS) in project management is essentially HTN planning. Large projects decompose into phases, tasks, and subtasks - identical structure. Software tools like Microsoft Project implicitly use HTN concepts.

Neuroscience: Prefrontal cortex activity during planning shows hierarchical representations - high-level goals activate different neural populations than specific action selection. HTN may model human planning more accurately than flat planning approaches.

Daily Challenge: Build a Recipe Planning Agent

Task: Implement an HTN planner for cooking recipes where:

Compound Task: make_dinner(cuisine_type, guest_count)
- Methods: italian_dinner, indian_dinner, american_dinner
Decomposition Example (italian_dinner):
- make_pasta(type='carbonara')
- make_salad(size='large')
- prepare_dessert(type='tiramisu')
Primitive Actions:
- boil_water, chop_vegetables, cook_pasta, mix_ingredients, etc.
State Requirements:
- Track ingredient availability
- Check cooking equipment
- Ensure timing constraints (parallel preparation)

Extension: Add re-planning when an ingredient is missing - choose alternative recipe or substitute ingredient.

Bonus Challenge: Optimize for parallel execution - some tasks can happen simultaneously (boiling water while chopping vegetables).

# Starter code
class RecipeHTN:
    def __init__(self):
        self.state = {
            'ingredients': ['pasta', 'eggs', 'bacon', 'cheese'],
            'equipment': ['stove', 'pot', 'pan'],
            'time_budget': 60  # minutes
        }
    
    def make_dinner(self, cuisine, guest_count):
        # Your HTN planning implementation here
        pass

# Test it
planner = RecipeHTN()
plan = planner.make_dinner(cuisine='italian', guest_count=4)
print(plan)

References & Further Reading

Classic Papers

Sacerdoti, E. (1975) “The Nonlinear Nature of Plans” - Original HTN concepts
Nau, D. et al. (1999) “SHOP: Simple Hierarchical Ordered Planner” - Formal HTN framework
Erol, K., Hendler, J., Nau, D. (1994) “HTN Planning: Complexity and Expressivity” - Theoretical foundations

Modern Applications

arXiv:2024.xxxxx “LLM-Assisted Hierarchical Task Planning” - HTN+LLM hybrids
arXiv:2023.xxxxx “Hierarchical Planning for Real-World Robotics” - HTN in robotics

Implementations

SHOP2/SHOP3: Reference HTN planner (C++, Java): https://github.com/shop-planner/shop3
PyHOP: Python HTN planner for education: https://github.com/dananau/pyhop
UnrealEngine HTN Plugin: Game AI applications

Books

Automated Planning: Theory and Practice (Ghallab, Nau, Traverso) - Chapter 11 covers HTN extensively

Online Resources

HTN Planning Tutorial: http://www.cs.umd.edu/~nau/planning/slides/
AI Planning Wiki: https://www.cs.toronto.edu/~sheila/2542/w09/

Final Thought:

HTN planning bridges the gap between the structured, domain-specific knowledge humans have about how to accomplish complex tasks and the systematic, verifiable planning capabilities computers excel at. As we build increasingly sophisticated AI agents, especially those combining LLMs with structured reasoning, HTN principles provide a proven framework for organizing complex behavior. Whether you’re building a robotic system, game AI, or personal assistant agent, thinking hierarchically about tasks will make your agents more efficient, more understandable, and more maintainable.

The future of AI agents likely isn’t choosing between learned behaviors (like RL) and structured planning (like HTN), but intelligently combining both - using learning where flexibility is needed and structure where reliability is critical.

2025-11-11

../