--- license: Apache-2.0 name: nau-au-kuter-2003-shop2 description: SHOP2 hierarchical task network planner for automated planning through recursive task decomposition category: Research & Academic tags: - htn-planning - shop2 - task-decomposition - automated-planning - hierarchical --- # SKILL: HTN Planning and Task Decomposition ## Core Mental Models ### 1. Ordered Decomposition Eliminates Uncertainty Plan tasks in execution order to transform exponential state-space reasoning into linear complexity. With known current state, you can trivially call external functions and make decisions based on actual conditions, not possibility spaces. ### 2. Methods Encode Expert Procedures Represent domain knowledge as methods that capture how experts solve problems. A method says "to accomplish X in situation Y, do subtasks A, B, C in that order"—transforming search problems into procedure selection. ### 3. Hierarchical Abstraction Drives Efficiency Work at the highest abstraction level possible. Planning "transport-person" is tractable; planning 200 atomic movements from first principles is not. Decompose only when necessary for current execution. ## Decision Points ### Task Decomposition Strategy Selection ``` IF domain has established expert procedures → Encode as HTN methods with preconditions → Use sort-by heuristics for method selection ELSE IF domain requires learning/discovery → Start with learned policies → Migrate successful patterns to methods over time ELSE IF procedures vary significantly by context → Use conditional methods with situation-specific preconditions → Maintain method libraries organized by context types ``` ### State Management Architecture Choice ``` IF execution order determinable at planning time → Use ordered decomposition for simple state reasoning → Maintain definite current state, not possibility sets ELSE IF tasks genuinely independent and parallelizable → Use partial-order planning → Accept cost of tracking state uncertainty ELSE IF complex reasoning needed (temporal, probabilistic) → First try state augmentation (add timestamps, probabilities) → Only build specialized reasoning engines if augmentation insufficient ``` ### Planning vs. Execution Integration ``` IF domain description differs from execution environment → Maintain automated translation layer → Validate translation with small test cases ELSE IF execution failures occur frequently → Check specification-vs-execution gap first → Verify operator effects match actual execution results ELSE IF performance inadequate → Add domain-specific methods to baseline capabilities → Profile for exponential search patterns ``` ### Knowledge Acquisition Strategy ``` IF domain experts exist and procedures are established → Hand-code methods encoding expert knowledge → Accept "cheating" vs pure learning for 2x performance gain ELSE IF domain exploratory or procedures unknown → Use automated learning with PDDL operators → Plan to migrate learned patterns to explicit methods ELSE IF mixed domain (some known procedures, some discovery) → Hybrid: methods for known procedures, learning for novel situations → Automated promotion of successful learned patterns to methods ``` ## Failure Modes ### Domain Description Bug (Symptom → Diagnosis → Fix) **Detection Rule**: Planner generates syntactically valid plans that fail during execution **Symptom**: Plans look correct, execute incorrectly, consistent failure pattern across similar problems **Diagnosis**: Hand-written HTN methods contain logical errors—wrong preconditions, incorrect effect specifications, missing edge cases **Fix**: Systematic testing of methods on small instances; automated validation tools; pair programming for method development ### Specification-Execution Gap (Symptom → Diagnosis → Fix) **Detection Rule**: Mysterious planning failures on problems that should be solvable **Symptom**: PDDL operators work in other planners but SHOP2 translation produces poor performance or invalid plans **Diagnosis**: Gap between what operators specify and how tasks are actually accomplished; missing procedural knowledge **Fix**: Manual enhancement of auto-translated domains; encode expert procedures as methods; validate translation with domain experts ### Search Space Explosion (Symptom → Diagnosis → Fix) **Detection Rule**: Planning time grows exponentially with problem size; solver times out on medium instances **Symptom**: Planner explores vast numbers of decompositions; thrashes between similar partial plans; memory usage grows uncontrollably **Diagnosis**: Missing domain-specific methods cause fall-back to inefficient search; no heuristic guidance for method selection **Fix**: Add methods that encode standard procedures; implement sort-by heuristics; profile search patterns to identify missing knowledge ### Method Conflict Deadlock (Symptom → Diagnosis → Fix) **Detection Rule**: Planner backtracks excessively between competing valid decompositions **Symptom**: Multiple methods applicable to same task; solver oscillates between options; search depth grows without progress **Diagnosis**: Methods lack sufficient specificity in preconditions; competing heuristics without clear priority ordering **Fix**: Refine method preconditions for better context sensitivity; implement preference ordering; add meta-methods for method selection ### Premature Optimization Trap (Symptom → Diagnosis → Fix) **Detection Rule**: Complex optimization produces worse results than simple heuristic approaches **Symptom**: Sophisticated search algorithms underperform greedy method selection; optimal planning fails on problems simple heuristics solve **Diagnosis**: Over-investment in search sophistication without adequate domain knowledge; treating domain expertise as "cheating" **Fix**: Encode domain heuristics first; start with simple greedy search; add sophistication only when domain knowledge insufficient ## Worked Examples ### Example 1: Agent Orchestration Architecture Design **Scenario**: Design coordination system for multi-agent document generation (research, outline, draft, review, edit). **Novice Approach**: Create agents for each subtask, use message passing for coordination, track all possible states. - **What They Miss**: Exponential state explosion from tracking all agent combinations; no procedural knowledge for standard workflows **Expert HTN Analysis**: 1. **Identify Natural Decomposition**: Document-generation follows established procedure: research → outline → draft → review → edit 2. **Design State Representation**: Current document state, active agent, completion status per section 3. **Encode Methods**: ``` Method: generate-document Preconditions: topic assigned, no existing document Decomposition: research-topic, create-outline, draft-sections, review-draft, finalize-document ``` 4. **Add Concurrency via State Augmentation**: Section ownership, parallel drafting with merge coordination 5. **Handle Failures**: Backtrack methods (review → redraft), not full state search **Key Decision**: Use ordered decomposition with known handoff points rather than tracking all possible agent interaction states. Reduces complexity from O(n!) to O(n). **Trade-off Navigated**: Accept constraint of sequential high-level phases (can't start drafting before research) to gain tractable coordination. Allow parallelism within phases via state augmentation. ### Example 2: Task Planning with Resource Constraints **Scenario**: Plan multi-day conference setup with limited staff, equipment conflicts, vendor dependencies. **Novice Approach**: Model as constraint satisfaction problem with all resources, times, dependencies as variables. - **What They Miss**: No procedural knowledge for conference setup; treating as pure optimization ignores expert experience **Expert HTN Analysis**: 1. **Encode Expert Procedures**: Conference planners follow standard sequences—venue setup before catering, AV testing before presentations 2. **State Augmentation for Resources**: Add resource availability, read-time/write-time to handle conflicts 3. **Method Design**: ``` Method: setup-conference-day Preconditions: venue confirmed, staff assigned, equipment list finalized Decomposition: setup-venue, test-av-systems, prepare-catering, brief-staff Sort-by: critical-path-first (AV failures block everything) ``` 4. **Handle Uncertainty**: Methods with conditional branches for common contingencies (weather, equipment failure) 5. **Resource Conflict Resolution**: Check resource state in method preconditions, not separate constraint engine **Key Decision**: Encode conference management expertise as methods rather than discovering optimal schedules through search. Expert procedures handle 95% of situations; search only needed for novel constraints. **Alternative Considered**: Pure optimization approach would find "optimal" schedules but miss critical dependencies that conference experts know (e.g., catering setup must happen after final headcount, not at optimal resource utilization time). ## Quality Gates **Task Planning Completeness:** - [ ] All high-level goals decompose to executable primitives - [ ] Every method has well-defined preconditions and effects - [ ] State representation captures all information needed for method selection - [ ] No circular dependencies in method decomposition hierarchy - [ ] Failure cases have explicit recovery methods or backtrack points **Domain Knowledge Coverage:** - [ ] Standard expert procedures encoded as methods (not rediscovered via search) - [ ] Heuristics implemented for common decision points (sort-by clauses) - [ ] Edge cases and exceptions handled with conditional methods - [ ] Resource constraints integrated into state representation - [ ] Translation layer validated between specification and execution **Performance and Scalability:** - [ ] Planning time scales linearly with problem size (not exponentially) - [ ] Method selection uses domain heuristics, not exhaustive search - [ ] State representation avoids tracking unnecessary possibility spaces - [ ] Concurrent activities handled via state augmentation, not temporal logic - [ ] Backtracking bounded by method hierarchy depth, not search space size **Correctness and Robustness:** - [ ] Generated plans execute successfully in target environment - [ ] Method preconditions match actual execution conditions - [ ] State updates correctly reflect execution results - [ ] Error handling preserves state consistency - [ ] Domain description bugs caught before deployment (testing on small instances) ## NOT-FOR Boundaries **Don't Use HTN Planning For:** - **Pure Optimization Problems**: Use mathematical optimization for minimizing cost/time with well-defined objective functions - **Reactive/Real-Time Control**: Use control systems for continuous feedback loops and millisecond response requirements - **Learning Novel Procedures**: Use reinforcement learning when domain procedures unknown and must be discovered - **Simple Sequential Tasks**: Use basic scripting for fixed sequences without conditional logic or failure recovery - **Pure Search Problems**: Use constraint satisfaction or graph search for problems without procedural structure **Delegate Instead:** - **For numerical optimization** → Use operations research methods or mathematical programming - **For real-time reactive control** → Use PID controllers or model-predictive control - **For discovering new strategies** → Use reinforcement learning or evolutionary algorithms - **For simple automation** → Use workflow engines or basic scripting - **For constraint satisfaction** → Use SAT/CSP solvers when no procedural knowledge exists **HTN Is For:** Complex tasks with established procedures, where expert knowledge exists about how to accomplish goals, and where the challenge is selecting and orchestrating appropriate methods rather than discovering optimal solutions from first principles.