## Definition **Classical planning** is the subfield of AI that finds a sequence of actions transforming an *initial state* into a *goal state* in a fully observable, deterministic, discrete environment with deterministic action effects. The framework formalised by Fikes & Nilsson (STRIPS, 1971). ## The Planning Problem A planning problem is $\langle s_0, G, A \rangle$: - $s_0$ — initial state (a set of facts). - $G$ — goal condition (a set of facts that must hold). - $A$ — set of actions, each with **preconditions** (what must hold to apply) and **effects** (what changes after). A **plan** is a sequence $a_1, a_2, \dots, a_n$ such that applying them from $s_0$ reaches a state where $G$ holds. ## STRIPS Action Schema ``` Action: Pickup(b) Preconditions: Clear(b), OnTable(b), HandEmpty Effects: Holding(b), ¬Clear(b), ¬OnTable(b), ¬HandEmpty ``` Effects partition into *add list* and *delete list* (the "STRIPS assumption"). ## Classical Assumptions The "classical" assumptions that simplify the problem: - **Fully observable.** The agent knows the complete state. - **Deterministic.** Each action has one possible outcome. - **Discrete.** Finitely many states and actions. - **Static.** No external changes between actions. - **Single agent.** No other actors. Relaxing any of these yields more general planning problems: under uncertainty, with partial observability, multi-agent. ## Algorithmic Approaches - **State-space search** — forward (from $s_0$) or backward (from $G$); see [[Heuristic Planning]]. - **Plan-space search** — search over partial plans; backbone of *partial-order planning*. - **[[GRAPHPLAN]]** — alternate phases of planning graph construction and goal extraction. - **Compilation to SAT** — encode planning as a satisfiability problem; let SAT solvers do the work. - **Compilation to CSP** — see [[Constraint Satisfaction Problem]]. - **Hierarchical planning** — decompose abstract tasks; see [[HTN Planning]]. ## Complexity Classical planning is **PSPACE-complete** in the general case. Practical solvers exploit structure with heuristics derived from problem relaxations. ## Languages - **STRIPS** — the original. - **ADL** — adds conditional effects, quantifiers, equality. - **PDDL** — the standard modern language; see [[PDDL]]. ## Connection to Modern AI Classical planning underlies: - Logistics and scheduling optimisation. - Robotics task planning. - Procedural game NPC behaviour. - Workflow systems. LLM-based "agentic" planning (see [[AI Agent]]) is *not* classical planning — it operates without preconditions/effects, in natural-language action spaces, without completeness guarantees. ## Related - [[STRIPS]] - [[PDDL]] - [[Heuristic Planning]] - [[GRAPHPLAN]] - [[HTN Planning]] - [[Combinatorial-planning-problem (CPP)]]