foundations-ai-planning-search

AI Planning And Search Foundations

10 applied AI planning and search primitives for turning a problem into states, actions, constraints, heuristics, and plans. Use this when the hard part is problem formulation or explicit search over alternatives, not language fluency.

Contents

• Quick Reference
• When to Apply
• Primitive Index
• Formal Supporting Theory
• Anti-Patterns
• Misuse Boundaries
• Decision Checklist
• Composition Recipes
• Workflow
• ASCII Flow
• Navigation
• Fact-Checking

Quick Reference

When to Apply

Apply this skill when:

• The task can be stated as states, actions, transitions, goals, and costs.
• You need A*, uniform-cost search, beam search, backtracking, alpha-beta, MCTS, STRIPS/PDDL, HTN, or CSP reasoning.
• An LLM agent is hallucinating action sequences that need explicit validity checks.
• The workflow needs a planner as a tool, not only prompt decomposition.
• A search or planning algorithm choice changes runtime, completeness, optimality, or failure behavior.

Skip or route elsewhere when:

• It is product search, vector retrieval, ranking, or query matching -> use software-search or ai-rag.
• It is expected utility, value of information, real options, or bandits -> use foundations-decision-theory.
• It is feedback control, setpoint tracking, or MPC -> use foundations-control-theory.
• It is strategic incentive design or equilibrium -> use foundations-game-theory.
• It is cooperative subagent allocation with shared payoff and partitioned information -> use foundations-team-theory.
• It is general agent architecture, memory, tools, or MCP/A2A orchestration -> use ai-agents after this skill defines the planner boundary.

Primitive Index

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.

Formal Supporting Theory

Anti-Patterns

Misuse Boundaries

Decision Checklist

• State model: Can you name states, legal actions, transition model, goal test, and cost? -> Problem formulation (#1)
• No heuristic: Need complete baseline over small/medium search? -> BFS/DFS/UCS/IDS (#2)
• Need optimal path with guidance: Can you design an admissible heuristic? -> A* (#3)
• Only final assignment matters: Path is irrelevant and space is huge? -> Local search (#4)
• Hard constraints dominate: Variables/domains/constraints are natural? -> CSP (#5)
• Opponent moves matter: Finite lookahead game/tree? -> Adversarial search (#6)
• Preconditions/effects matter: Need valid action sequence? -> Classical planning (#7)
• Reusable decomposition exists: Tasks break into methods/subtasks? -> HTN (#8)
• Observations are incomplete: Need sensing, contingency, or policy? -> Belief-state planning (#9)
• LLM agent is involved: Need planner/verifier/tool-loop boundary? -> Planner-agent integration (#10)

Composition Recipes

LLM Agent With Valid Plans

Failure: Agent produces plausible steps that violate tool preconditions.

• Problem formulation (#1): define typed state and legal action schema.
• Classical planning (#7): encode preconditions/effects for tools.
• Planner-agent integration (#10): LLM proposes goals or abstractions; planner validates; executor runs only valid next action.
• Replanning trigger (#10): replan after failed precondition, external state drift, or new observation.

Configuration Assistant That Respects Constraints

Failure: Recommendations violate compatibility, license, budget, or availability constraints.

• CSP (#5): model components as variables and compatibility rules as constraints.
• Local search (#4): if preferences are soft and space is too large for exact search.
• Decision theory boundary: route scoring tradeoffs to foundations-decision-theory when expected value or risk weighting matters.

Game Or Simulation Agent

Failure: Agent picks locally good moves and misses opponent responses.

• Adversarial search (#6): minimax or alpha-beta for deterministic games.
• MCTS (#6): stochastic or high-branching games with rollout evaluation.
• Heuristic search (#3): evaluate states with domain heuristic.
• Game theory boundary: route equilibrium, mechanism, or incentive design to foundations-game-theory.

Workflow Planner For Human Operations

Failure: Task decomposition is repeated manually and varies across runs.

• HTN (#8): encode standard decompositions and method selection.
• Classical planning (#7): validate preconditions for steps with tool or data dependencies.
• Grounding boundary: use foundations-grounding-communication for handoff repair and common-ground checks.

"Works In The Demo, Fails In Production"

Failure: A planner or agent loop that passed every walkthrough degrades or breaks under real traffic.

• Diagnose in order of likelihood before assuming a logic bug: production branching factor vs. demo branching factor, heuristic/verifier fit to the demo distribution, unmodeled nondeterminism, missing or unbounded replanning triggers, a validator that exists in eval but not in the production executor path, and search budget (rollouts/nodes/beam width) silently shrunk by latency or cost limits.
• Full diagnostic checklist: references/patterns-scenarios-traps.md.

Workflow

1. Formulate the problem as state, actions, transition model, goal test, and cost.
2. Classify the dominant structure: path search, assignment/CSP, game tree, symbolic plan, hierarchy, or uncertainty.
3. Choose the simplest algorithm family that preserves required guarantees: completeness, optimality, bounded memory, or good-enough solution quality.
4. Write the search/planning assumptions explicitly before implementation.
5. For LLM agents, decide what the LLM may propose and what the planner/verifier must enforce.
6. Validate with small hand-checkable cases, impossible cases, and adversarial edge cases.

ASCII Flow

Planning/search problem
  -> Define state, actions, transition, goal, cost
  -> Classify structure
     +-- path to goal -> BFS/UCS/A*/local search
     +-- variable assignment -> CSP
     +-- opponent -> minimax/alpha-beta/MCTS
     +-- symbolic action model -> STRIPS/PDDL/plan graph
     +-- reusable decompositions -> HTN
     +-- partial observability -> belief-state/contingent planning
  -> Check guarantees and constraints
  -> Integrate with agent/tool loop if needed
  -> Validate plan legality and replanning triggers

Navigation

• Primitives overview: references/primitives-overview.md
• Patterns, scenarios, and traps: references/patterns-scenarios-traps.md
• Formal theory map: references/formal-theory-map.md
• Sources: data/sources.json

Related Skills

• foundations-decision-theory - utility, value of information, regret, and bandits.
• foundations-control-theory - feedback loops, stability, and MPC.
• foundations-game-theory - incentives, equilibrium, mechanism design, and strategic actors.
• foundations-team-theory - cooperative multi-agent allocation with shared payoff.
• foundations-grounding-communication - handoff repair and common-ground checks for HTN workflow planners.

Fact-Checking

• Check data/sources.json before citing algorithm properties or source claims.
• Treat complexity and optimality guarantees as conditional on assumptions: nonnegative costs for UCS/A*, admissible/consistent heuristics for A*, finite branching for completeness, and correct action preconditions/effects for planners.
• Do not invent benchmark numbers. If a planner or solver is recommended, report assumptions, problem size, and validation cases instead of generic speed claims.
• LLM planning benchmark numbers move fast and are rarely comparable across papers: success rate depends on domain, instance size, prompt encoding, number of retries, and whether a verifier was in the loop. Cite the specific setup or state the result qualitatively; do not carry a headline percentage across domains.
• Plan validity and plan safety are distinct measurements. A reported planning success rate says nothing about whether the produced plans are safe to execute, and the two have been observed to diverge sharply. Never substitute one metric for the other.

Learnings Loop

Before applying this skill on a non-trivial task, read learnings.consolidated.md in this directory (and learnings.md if present).

After applying it, if you encountered a pattern worth remembering, a mistake worth preventing, or a domain fact that surprised you, append one dated bullet to learnings.md via agents-skills-feedback-loop/scripts/append_learning.py. Do not modify SKILL.md itself.