foundations-ai-planning-search
Installation
SKILL.md
AI Planning And Search Foundations
Quick Reference
Each primitive is expanded in references/primitives-overview.md. Use references/patterns-scenarios-traps.md for scenario recipes and references/formal-theory-map.md when completeness, optimality, or complexity claims matter.
| # | Primitive | Problem It Solves | Failure Mode Addressed | Key Parameters |
|---|---|---|---|---|
| 1 | Problem Formulation | Vague tasks cannot be searched or verified | Agent cannot know what counts as legal progress | State, actions, transition model, goal test, path cost |
| 2 | Uninformed Search | Need complete baseline without domain heuristic | No baseline for completeness, optimality, or frontier explosion | Branching factor b; depth d; frontier policy |
| 3 | Heuristic Search | Large state spaces need directed exploration | State space explodes because exploration is undirected | Heuristic h(n); admissibility; consistency |
| 4 | Local Search | State is large but path is irrelevant | Path-tracking wastes memory when only final configuration matters | Neighborhood; objective; restart/schedule |
| 5 | Constraint Satisfaction | Need assignments satisfying hard constraints | Constraints are mixed into prompts instead of enforced structurally | Variables, domains, constraints, MRV/LCV, arc consistency |
| 6 | Adversarial Search | Opponent actions affect outcomes | Opponent response is ignored or treated as noise | Utility, depth, alpha-beta bounds, rollout policy |
| 7 | Classical Planning | Need valid action sequence from symbolic preconditions/effects | Preconditions and effects are implicit, so invalid plans pass review | STRIPS/PDDL, progression/regression, plan graph |
| 8 | Hierarchical Planning | Tasks decompose into reusable subplans | Repeated task decomposition is ad hoc and inconsistent | Methods, subtasks, ordering constraints |
| 9 | Contingent / Belief-State Planning | Partial observability or nondeterministic actions | Plan assumes full observability or deterministic actions | Belief state, sensing actions, policy vs sequence |
| 10 | Planner-Agent Integration | LLM agent needs explicit plan validity and search boundaries | LLM tool loop lacks plan validation, replanning, or bounded search | Planner tool, state abstraction, verifier, replanning trigger |