htn planning (hierarchical task network)

**HTN planning (Hierarchical Task Network)** is a planning approach that **decomposes high-level tasks into networks of subtasks hierarchically** — using domain-specific knowledge about how complex tasks break down into simpler ones, enabling efficient planning for complex domains by exploiting task structure and procedural knowledge. **What Is HTN Planning?** - **Hierarchical**: Tasks are organized in a hierarchy from abstract to concrete. - **Task Network**: Tasks are connected by ordering constraints and dependencies. - **Decomposition**: High-level tasks are recursively decomposed into subtasks until primitive actions are reached. - **Domain Knowledge**: Decomposition methods encode expert knowledge about how to accomplish tasks. **HTN Components** - **Primitive Tasks**: Directly executable actions (like STRIPS actions). - **Compound Tasks**: High-level tasks that must be decomposed. - **Methods**: Recipes for decomposing compound tasks into subtasks. - **Ordering Constraints**: Specify execution order of subtasks. **HTN Example: Making Dinner** ``` Compound Task: make_dinner Method 1: cook_pasta_dinner Subtasks: 1. boil_water 2. cook_pasta 3. make_sauce 4. combine_pasta_and_sauce Ordering: 1 < 2, 3 < 4, 2 < 4 Method 2: order_takeout Subtasks: 1. choose_restaurant 2. place_order 3. wait_for_delivery Ordering: 1 < 2 < 3 Planner chooses method based on context (time, ingredients available, etc.) ``` **HTN Planning Process** 1. **Start with Goal**: High-level task to accomplish. 2. **Select Method**: Choose decomposition method for current task. 3. **Decompose**: Replace task with subtasks from method. 4. **Recurse**: Repeat for each compound subtask. 5. **Primitive Actions**: When all tasks are primitive, plan is complete. 6. **Backtrack**: If decomposition fails, try alternative method. **Example: Robot Assembly Task** ``` Task: assemble_chair Method: standard_assembly Subtasks: 1. attach_legs_to_seat 2. attach_backrest_to_seat 3. tighten_all_screws Ordering: 1 < 3, 2 < 3 Task: attach_legs_to_seat Method: four_leg_attachment Subtasks: 1. attach_leg(leg1) 2. attach_leg(leg2) 3. attach_leg(leg3) 4. attach_leg(leg4) Ordering: none (can be done in any order) Task: attach_leg(L) Primitive action: screw(L, seat) ``` **HTN vs. Classical Planning** - **Classical Planning (STRIPS/PDDL)**: - **Search**: Searches through state space. - **Domain-Independent**: General search algorithms. - **Flexibility**: Can find novel solutions. - **Scalability**: May struggle with large state spaces. - **HTN Planning**: - **Decomposition**: Decomposes tasks hierarchically. - **Domain-Specific**: Uses expert knowledge in methods. - **Efficiency**: Exploits task structure for faster planning. - **Constraints**: Limited to decompositions defined in methods. **Advantages of HTN Planning** - **Efficiency**: Hierarchical decomposition reduces search space dramatically. - **Domain Knowledge**: Encodes expert knowledge about how tasks are typically accomplished. - **Natural Representation**: Matches how humans think about complex tasks. - **Scalability**: Handles complex domains that classical planning struggles with. **HTN Planning Algorithms** - **SHOP (Simple Hierarchical Ordered Planner)**: Total-order HTN planner. - **SHOP2**: Extension with more expressive methods. - **SIADEX**: HTN planner for real-world applications. - **PANDA**: Partial-order HTN planner. **Applications** - **Manufacturing**: Plan assembly sequences, production workflows. - **Military Operations**: Plan missions with hierarchical command structure. - **Game AI**: Plan NPC behaviors with complex goal hierarchies. - **Robotics**: Plan manipulation tasks with subtask structure. - **Business Process Management**: Plan workflows with task decomposition. **Example: Military Mission Planning** ``` Task: conduct_reconnaissance_mission Method: aerial_reconnaissance Subtasks: 1. prepare_aircraft 2. fly_to_target_area 3. perform_surveillance 4. return_to_base 5. debrief Ordering: 1 < 2 < 3 < 4 < 5 Task: prepare_aircraft Method: standard_preflight Subtasks: 1. inspect_aircraft 2. fuel_aircraft 3. load_equipment 4. brief_crew Ordering: 1 < 2, 1 < 3, 4 < (all others complete) ``` **Partial-Order HTN Planning** - **Flexibility**: Subtasks can be partially ordered — only specify necessary orderings. - **Advantage**: More flexible than total-order plans — allows parallel execution. - **Example**: attach_leg(leg1) and attach_leg(leg2) can be done in any order or in parallel. **HTN with Preconditions and Effects** - **Hybrid Approach**: Combine HTN decomposition with STRIPS-style preconditions and effects. - **Benefit**: Ensures plan feasibility while exploiting hierarchical structure. - **Example**: Check that preconditions are satisfied when selecting methods. **Challenges** - **Method Engineering**: Defining good decomposition methods requires domain expertise. - **Completeness**: HTN planning may miss solutions not captured by defined methods. - **Flexibility**: Limited to predefined decompositions — less flexible than classical planning. - **Verification**: Ensuring methods are correct and complete is challenging. **LLMs and HTN Planning** - **Method Generation**: LLMs can generate decomposition methods from natural language descriptions. - **Task Understanding**: LLMs can interpret high-level tasks and suggest decompositions. - **Method Refinement**: LLMs can refine methods based on execution feedback. **Example: LLM Generating HTN Method** ``` User: "How do I organize a conference?" LLM generates HTN method: Task: organize_conference Method: standard_conference_organization Subtasks: 1. select_venue 2. invite_speakers 3. promote_event 4. manage_registrations 5. arrange_catering 6. conduct_conference 7. follow_up Ordering: 1 < 3, 1 < 4, 2 < 6, 5 < 6, 6 < 7 ``` **Benefits** - **Efficiency**: Dramatically reduces search space through hierarchical decomposition. - **Knowledge Encoding**: Captures expert knowledge about task structure. - **Scalability**: Handles complex domains with many actions. - **Natural**: Matches human problem-solving approach. **Limitations** - **Method Dependency**: Quality depends on quality of decomposition methods. - **Less Flexible**: Cannot find solutions outside defined methods. - **Engineering Effort**: Requires significant effort to define methods. HTN planning is a **powerful approach for complex, structured domains** — it exploits hierarchical task structure and domain knowledge to achieve efficient planning, making it particularly effective for real-world applications where expert knowledge about task decomposition is available.