Planning finds a sequence of actions that achieves a goal, using a factored representation: states are sets of facts and actions are schemas with preconditions and effects. That structure allows domain-independent heuristics that make planners scale to huge problems.

The STRIPS representation

Part	Meaning	Blocks world
State	Conjunction of ground facts (fluents); everything else is false (closed world)	`On(C, A) ∧ OnTable(A) ∧ OnTable(B) ∧ Clear(C) ∧ Clear(B)`
Goal	Conjunction of facts that must hold (a partial state)	`On(A, B) ∧ On(B, C)`
Action schema	Name, preconditions, add list, delete list	`Move(b, x, y)`

An action is applicable when its preconditions hold; its result is (state − delete list) ∪ add list. Facts not mentioned stay unchanged — this is how STRIPS sidesteps the frame problem. PDDL (Planning Domain Definition Language) is the standard modern syntax:

PDDL

(:action move
  :parameters (?b ?x ?y)
  :precondition (and (on ?b ?x) (clear ?b) (clear ?y))
  :effect (and (on ?b ?y) (clear ?x)
               (not (on ?b ?x)) (not (clear ?y))))

Forward (progression) planning

Treat planning as search: states are fact sets, successors come from applicable ground actions. Here is the Sussman anomaly — start with C on A; goal A on B on C:

Python

from collections import deque

BLOCKS = ["A", "B", "C"]
PLACES = BLOCKS + ["Table"]

def ground_actions():                               # every instance of Move(b, x, y)
    for b in BLOCKS:
        for x in PLACES:
            for y in PLACES:
                if len({b, x, y}) == 3:
                    pre = {("On", b, x), ("Clear", b)} | ({("Clear", y)} if y != "Table" else set())
                    add = {("On", b, y)} | ({("Clear", x)} if x != "Table" else set())
                    delete = {("On", b, x)} | ({("Clear", y)} if y != "Table" else set())
                    yield f"Move({b},{x},{y})", frozenset(pre), frozenset(add), frozenset(delete)

ACTIONS = list(ground_actions())

def plan(start, goal):                              # breadth-first progression search
    frontier, seen = deque([(start, [])]), {start}
    while frontier:
        state, steps = frontier.popleft()
        if goal <= state:
            return steps, len(seen)
        for name, pre, add, delete in ACTIONS:
            if pre <= state:
                nxt = (state - delete) | add
                if nxt not in seen:
                    seen.add(nxt)
                    frontier.append((nxt, steps + [name]))

start = frozenset({("On", "C", "A"), ("On", "A", "Table"), ("On", "B", "Table"), ("Clear", "C"), ("Clear", "B")})
goal = {("On", "A", "B"), ("On", "B", "C")}
print(len(ACTIONS))           # 18 ← ground actions from one schema
print(plan(start, goal))      # (['Move(C,A,Table)', 'Move(B,Table,C)', 'Move(A,Table,B)'], 13)

Search strategies and heuristics

Approach	Idea
Forward (progression) search	From the initial state apply applicable actions. Many irrelevant actions — needs a good heuristic.
Backward (regression) search	From the goal, consider only relevant actions (that add a goal fact without deleting another); regress the goal through them. Smaller branching factor.
Ignore-delete-lists heuristic	Solve the relaxed problem where actions never remove facts (the basis of FF and HSP planners). Admissible variants give A*-optimal plans.
Ignore-preconditions heuristic	Count how many actions are needed if any action could always be applied — roughly the number of unsatisfied goals.
Planning graphs / GraphPlan	Layered graph of reachable facts and actions with mutex links; the level where all goals first appear is a heuristic estimate.
SAT planning	Encode “is there a plan of length `T`?” as a Boolean formula and hand it to a SAT solver.

Partial-order planning

A partial-order planner (POP) searches in the space of plans, not states, and commits to an ordering only when necessary (least commitment). A plan has actions, ordering constraints A ≺ B, and causal links A →p→ B (A achieves precondition p of B). A threat is an action that could delete p between A and B — resolved by ordering it before A (demotion) or after B (promotion).

Beyond classical planning	Handles
Hierarchical task networks (HTN)	High-level actions refined into sub-plans — how most real planners (and games' NPCs) work
Scheduling with resources	Durations, deadlines, limited machines/crew — critical-path method
Contingent / conformant planning	Partial observability: plans with sensing actions and branches
Replanning & execution monitoring	Detect when the world deviates from the plan and repair it
MDPs (next group)	Stochastic action outcomes — a policy instead of a fixed sequence

What is STRIPS?

Forward vs backward state-space planning?

Why can planning use domain-independent heuristics while plain search cannot?