Hsts Planning Scheduling

---
license: Apache-2.0
name: hsts-planning-scheduling
description: Heuristic search-based temporal planning and scheduling for complex multi-constraint environments
category: Research & Academic
tags:
  - planning
  - scheduling
  - constraint-satisfaction
  - temporal-reasoning
  - space-systems
---

# SKILL.md: HSTS — Integrated Planning & Scheduling

Wisdom from Muscettola's HSTS framework for building intelligent systems that unify planning (what to do) and scheduling (when/how to do it). Activates when designing constraint-based agents, solving resource allocation problems, building robust execution systems, or reasoning about commitment under uncertainty.

## DECISION POINTS

### Decision 1: Unified vs. Separated Planning/Scheduling

```
IF domain has resources with time-varying availability
   AND causal goals interact with resource constraints
   AND execution environment is uncertain
   → Use unified state variable approach
   → Model as evolving constraint network

IF problem is purely causal (no resource contention)
   → Classical planning may suffice

IF problem has fixed task structure with only temporal constraints
   → Classical scheduling may suffice

IF you see "planner feeds into scheduler" architecture
   → QUESTION: Is the seam creating coordination debt?
```

### Decision 2: Commitment Level Selection

```
FOR each variable binding decision:
  IF decision is reversible AND more information is coming
    → Post ordering constraint only
    → Example: "A before B" instead of "A at 10:00, B at 11:30"
  
  IF decision resolves high-contention bottleneck (measured via simulation)
    → Commit to specific value now
    → Example: Assign spacecraft antenna to high-priority download
  
  IF tempted to fix exact times early in search
    → STOP: Can ordering relation achieve same progress?
    → Preserve temporal flexibility for executor
```

### Decision 3: Search Focus Priority

```
BEFORE resolving any disjunction:
  1. Run stochastic simulation on current partial solution
  2. Sample 100+ paths without resolving open choices
  3. Count conflicts per resource-time pair
  4. Focus next decision on highest-contention resource

IF search is thrashing (many backtracks, little progress)
  → You're attacking non-bottleneck variables first
  → Re-estimate contention distribution
  → Switch to highest-conflict resource
```

### Decision 4: Domain Modeling Approach

```
IF domain has objects with internal state evolving over time
  → Model each as state variable with transition graph
  → Example: Satellite antenna {idle, tracking, downloading, slewing}

IF domain has shared resources (consumable/reusable)
  → Model resource levels as state variables
  → Track availability windows, not just capacity numbers

IF expert rules exist ("X and Y can't overlap during Z")
  → Encode as compatibility constraints
  → NOT as search pruning hacks
```

## FAILURE MODES

### Anti-Pattern 1: "Nominal Trajectory Planning"
**Detection Rule**: If schedule output is sequence of exact times/actions with no flexibility
**Root Cause**: Confusing schedule with execution plan; over-committing temporal decisions
**Symptom**: Any runtime deviation requires full replanning
**Fix**: Output behavioral envelopes (constraint networks) not nominal sequences
**Timeline**: Becomes critical when execution uncertainty > 5% of plan duration

### Anti-Pattern 2: "Premature Value Commitment"  
**Detection Rule**: If binding variables to specific values before constraints force it
**Root Cause**: Not distinguishing between progress and commitment
**Symptom**: Search space artificially shrunk; solutions exist but aren't found
**Fix**: Post weakest constraint that enables progress; commit only when forced
**Timeline**: Shows up immediately in search statistics (solution quality drops)

### Anti-Pattern 3: "Bottleneck Ignorance"
**Detection Rule**: If resolving disjunctions without measuring which matter most
**Root Cause**: Treating all constraints as equally important
**Symptom**: Search thrashing on easy variables while hard constraints fester
**Fix**: Use stochastic simulation to estimate conflict probability before each decision
**Timeline**: Becomes exponentially worse as problem size grows

### Anti-Pattern 4: "Constraint Network Bloat"
**Detection Rule**: If propagation time grows quadratically with problem size
**Root Cause**: Not respecting module boundaries; monolithic constraint posting
**Symptom**: Solver becomes unusably slow on realistic problems
**Fix**: Decompose into state variable modules; make interaction topology explicit
**Timeline**: Hits performance wall around 50-100 activities

### Anti-Pattern 5: "Expert Knowledge as Hardcoded Heuristics"
**Detection Rule**: If domain knowledge exists as ad-hoc search pruning rules
**Root Cause**: Encoding constraints implicitly instead of declaratively
**Symptom**: Knowledge invisible to debugging; doesn't compose across modules
**Fix**: Express expert rules as formal compatibility constraints with causal semantics
**Timeline**: Maintenance nightmare emerges when domain complexity grows

## WORKED EXAMPLES

### Example 1: Satellite Mission Planning

**Scenario**: Mars orbiter with 2 instruments (camera, spectrometer), 1 antenna, 4 GB storage. Plan 8-hour observation session with data downlink.

**Novice Approach**: 
1. Plan observation sequence first
2. Schedule exact start times  
3. Add downlink at end
*Fails when storage constraint discovered late*

**Expert HSTS Approach**:
1. Model state variables: storage_level, antenna_state, instrument_states
2. Run stochastic simulation: storage fills to 95% probability by hour 3
3. **Decision**: Storage is bottleneck, not antenna time
4. Commit to downlink at hour 3 (value commitment for bottleneck)
5. Leave observation ordering flexible (constraint posting for non-bottleneck)
6. Output: behavioral envelope with storage invariant + flexible observation sequence

**Alternative Path Shown**: If simulation revealed antenna conflicts instead of storage, would commit to antenna schedule first, leave storage management flexible.

### Example 2: Manufacturing Job Shop

**Scenario**: 5 jobs, 3 machines, delivery deadlines. Machine M2 has 50% uptime, others 90%.

**Novice Approach**: Schedule assuming all machines available; handle breakdowns reactively.

**Expert HSTS Approach**:
1. Model machine_availability as time-varying state variable
2. Stochastic simulation: M2 unavailable 40% of time slots
3. **Trade-off Analysis**: 
   - Option A: Route critical jobs around M2 (safer, longer makespan)
   - Option B: Use M2 with backup plans (shorter nominal, replanning risk)
4. **Decision**: Critical path jobs avoid M2; non-critical use M2 with ordering constraints only
5. Output: schedule robust to M2 failures without pessimistic assumption about availability

**What Expert Catches**: M2 unreliability creates secondary bottleneck at other machines when jobs reroute. Plans for cascade effects.

## QUALITY GATES

Schedule is valid and complete when:

- [ ] All state variables have legal transitions throughout timeline
- [ ] No resource oversubscription in any sampled execution path  
- [ ] All goals reachable within temporal flexibility bounds
- [ ] Bottleneck resources identified with >90% confidence via simulation
- [ ] Constraint network admits multiple execution paths (not nominal trajectory)
- [ ] Module interactions explicit and bounded in complexity
- [ ] Search focused on measured conflicts, not assumed priorities
- [ ] Expert domain knowledge encoded as testable compatibility constraints
- [ ] System degrades gracefully under 20% execution deviation
- [ ] Computational cost scales linearly with number of state variables

**Automated Validation Signals**:
- Stochastic simulation runs complete without contradiction
- Constraint propagation converges in bounded time
- Multiple distinct solutions exist in final envelope
- Module coupling metrics within acceptable bounds

## NOT-FOR BOUNDARIES

**This skill should NOT be used for**:
- Pure optimization problems without temporal/resource constraints → Use mathematical programming instead
- Real-time reactive control → Use control theory instead  
- Simple project management with known task durations → Use critical path method instead
- Problems where optimal solution required → Use complete search methods instead
- Domains where expert knowledge unavailable → Use machine learning approaches instead

**Delegation Rules**:
- For route planning: use `path-planning-algorithms` instead
- For resource allocation without time: use `constraint-satisfaction-methods` instead  
- For predictive analytics: use `time-series-forecasting` instead
- For execution monitoring: use `plan-execution-monitoring` instead

**Boundary Signals**: If you're spending more effort encoding the domain than solving instances, consider whether classical OR methods might suffice for your use case.