Classical planning is FOL reasoning applied to action sequences. State the initial conditions, the goal, and the actions; find an action sequence that achieves the goal.
STRIPS representation
Each action has:
- Preconditions: literals that must hold for the action to apply.
- Effects: add and delete lists — literals to be added or removed from the state.
Example: has preconditions and effects: add , delete .
PDDL
The Planning Domain Definition Language standardizes how planning problems are described, enabling the planning competition that has driven decades of algorithm development.
Forward search
State-space search from initial state forward to goal state. The state graph can be huge, but heuristics dramatically prune it.
Backward search
From the goal regress backward through action preconditions toward the initial state. Useful when the goal is specific and the initial state has many irrelevant facts.
Heuristics for planning
The big breakthrough of the 1990s–2000s: domain-independent heuristics that work across any planning problem.
- max over goal literals of the depth at which each becomes achievable (admissible but loose).
- sum instead of max (not admissible but more informative; works well in practice).
- (Fast Forward): extract a *relaxed plan* (planning while ignoring delete effects) and use its length. Workhorse heuristic of the late 1990s onward.
- : landmarks-based, admissible, basis of modern competition-winning planners.
SAT-based planning
Encode "is there a plan of length ?" as a SAT problem and use a SAT solver. Compete with search-based planners; sometimes better when SAT solvers are very strong on a particular problem structure.
Hierarchical planning
Decompose goals into sub-goals via task networks. HTN planners (SHOP2) trade some autonomy for huge speed-ups when domain knowledge is available.
Modern context
LLMs as planners is an active research direction. They can do remarkable things on small, common-sense planning problems but are unreliable at proving optimality, finding plans in adversarial domains, or scaling to long horizons. Classical planning's strengths — provable correctness, completeness — remain useful for high-stakes applications.