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