Nau Au Kuter 2003 Shop2

---
license: Apache-2.0
name: nau-au-kuter-2003-shop2
description: SHOP2 hierarchical task network planner for automated planning through recursive task decomposition
metadata:
  category: Research & Academic
  tags:
    - htn-planning
    - shop2
    - task-decomposition
    - automated-planning
    - hierarchical
  io-contract:
    kind: deliverable
    produces:
      - kind: design-doc
        description: >-
          HTN domain specification with task hierarchy, methods, preconditions, and decomposition strategy for a given
          planning problem
        format: markdown
      - kind: refactor-plan
        description: >-
          Analysis of planning failures with diagnosis (domain bugs, specification gaps, search explosion) and concrete
          fixes to method definitions or state management
        format: markdown
      - kind: code
        description: >-
          SHOP2-compatible PDDL domain and problem files, or method library encoding expert procedures for task
          decomposition
        language: lisp
        format: text
      - kind: critique
        description: >-
          Evaluation of a proposed planning architecture against HTN principles (ordered decomposition, method
          specificity, abstraction levels, specification-execution alignment)
        format: markdown
allowed-tools: Read,Write,Edit,Glob,Grep
---

# 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).

## Reference Files

- `diagrams/01_flowchart_htn_planning_decision_framewor.md` — Decision tree for HTN planning challenges (execution order, decomposition, concurrency, search explosion). **Read when** choosing between ordered decomposition, partial-order planning, or specialized reasoning.

- `diagrams/02_mindmap_htn_planning_core_mental_model.md` — Mental models for ordered decomposition, method encoding, hierarchical abstraction with application patterns and pitfalls. **Read when** designing task decomposition strategy or debugging planning failures.

- `diagrams/03_stateDiagram-v2_agent_task_decomposition_state.md` — State machine for goal decomposition, method selection, subtask execution, and backtracking. **Read when** implementing agent control flow or understanding decomposition lifecycle.

- `references/ordered-decomposition-eliminates-uncertainty.md` — How execution-order planning transforms exponential state reasoning into linear complexity by maintaining definite current state. **Read when** justifying ordered decomposition vs. classical planning approaches.

- `references/htn-methods-as-expert-procedures.md` — HTN methods encode standard operating procedures; comparison with classical planning and learning-based approaches. **Read when** deciding whether to hand-code methods or learn from data.

- `references/sort-by-and-search-control.md` — Heuristic guidance for method selection via sort-by without hard commitments; handling nondeterministic choice points. **Read when** optimizing search performance or implementing method ranking.

- `references/gap-between-specification-and-execution.md` — Translation problem between PDDL specifications and SHOP2 execution; why automated translation requires validation. **Read when** debugging specification-vs-execution mismatches or building translators.

- `references/failure-modes-in-complex-planning.md` — AIPS-2000 failure case: incorrect domain descriptions causing invalid plans; lessons on domain validation. **Read when** diagnosing planning failures or establishing domain verification procedures.

- `references/hand-tailorable-vs-automated-tradeoff.md` — Competition results comparing hand-tailorable (SHOP2, TLPlan) vs. fully-automated planners; performance and knowledge engineering tradeoffs. **Read when** evaluating whether to invest in domain-specific knowledge encoding.

- `references/multi-timeline-temporal-reasoning.md` — State augmentation for handling concurrency without explicit temporal reasoning; preprocessing approach for durative actions. **Read when** extending SHOP2 to temporal/concurrent domains.

## 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.