Classical planning: actions, preconditions and plans

Search over raw states works for small problems, but many agent tasks involve many objects and many possible actions: a logistics company moving parcels between cities with trucks and planes, a robot assembling furniture, a spacecraft scheduling observations, or a software agent setting up a development environment. Classical planning describes such problems in a structured language of objects, properties and actions with preconditions and effects, so that general-purpose planners can solve them without problem-specific code. This lesson introduces STRIPS and PDDL representations, forward and backward planning, planning heuristics, hierarchical task networks, and the gap between classical assumptions and the real world, including how replanning and execution monitoring bridge it.

Representing the world with facts

Planning represents a state as a set of facts (propositions) that are true, such as On(A, C), Clear(B), OnTable(C) and HandEmpty. Anything not listed is assumed false, the closed-world assumption. Goals are sets of facts that must be true, such as On(A, B) and On(B, C), leaving other facts unconstrained. This factored representation is far more compact than enumerating states: a world with 30 boolean facts has more than a billion possible states, but describing a state takes only 30 bits, and actions can be described once in general form.

Actions: preconditions and effects

In the STRIPS representation, introduced at Stanford Research Institute for the Shakey robot in 1971, each action schema has parameters, preconditions that must hold for it to be applied, and effects that add and delete facts. For example:

• Action: Move(b, x, y), moving block b from x onto y.
• Preconditions: On(b, x), Clear(b), Clear(y).
• Effects: add On(b, y) and Clear(x); delete On(b, x) and Clear(y).

PDDL, the Planning Domain Definition Language, standardizes this style of description and extends it with typed objects, numeric fluents, durations and costs. A planning task in PDDL is split into a domain file, describing types and action schemas, and a problem file, listing objects, the initial state and the goal. International planning competitions use PDDL, and many robotics and logistics systems use it or similar languages to describe tasks to general planners.

Forward and backward planning

Forward (progression) planning searches from the initial state, applying any action whose preconditions hold, until a state satisfying the goal is reached. Backward (regression) planning starts from the goal and works backward, choosing actions that achieve part of the goal and adding their preconditions as new subgoals, which can focus the search on relevant actions. Either can use the search algorithms of Lesson 2.

from collections import deque
# Forward state-space planning in a three-block world (STRIPS-style actions)
# a state is a tuple of stacks, each stack listed bottom to top
start = (("C", "A"), ("B",), ())            # A on C, B alone, one empty spot
goal = (("A", "B", "C"),)                   # tower with C on B on A
def canon(state):
    return tuple(sorted(s for s in state if s))
def moves(state):
    stacks = [list(s) for s in state] + [[]]
    for i, src in enumerate(stacks):
        if not src:
            continue
        for j, dst in enumerate(stacks):
            if i == j or (not dst and len(src) == 1):
                continue
            new = [list(s) for s in stacks]
            block = new[i].pop(); new[j].append(block)
            target = "table" if not dst else dst[-1]
            yield f"move {block} onto {target}", canon(tuple(tuple(s) for s in new))
def plan(start, goal):
    start, goal = canon(start), canon(goal)
    frontier = deque([start]); parent = {start: None}; explored = 0
    while frontier:
        s = frontier.popleft(); explored += 1
        if s == goal:
            steps = []
            while parent[s] is not None:
                s, act = parent[s]; steps.append(act)
            return steps[::-1], explored
        for act, nxt in moves(s):
            if nxt not in parent:
                parent[nxt] = (s, act); frontier.append(nxt)
    return None, explored
steps, explored = plan(start, goal)
print(f"states explored: {explored}")
for k, a in enumerate(steps, 1):
    print(f"{k}. {a}")

states explored: 10
1. move A onto table
2. move B onto A
3. move C onto B

The planner explores 10 states and returns the shortest plan: move A onto the table to clear C, put B on A, then put C on B. With three blocks the state space is tiny, but it grows explosively: with 10 blocks there are tens of millions of arrangements, and uninformed search becomes hopeless. Practical planners therefore rely on heuristics.

Planning heuristics

Domain-independent heuristics are computed automatically from the action descriptions. The most famous idea is to solve a relaxed problem that ignores delete effects: if actions only add facts and never remove them, a relaxed plan is easy to compute, and its length estimates the difficulty of the real problem. The FF planner's heuristic, the length of a relaxed plan, and related heuristics such as hmax and hadd made forward search planners vastly faster in the early 2000s. Landmark heuristics count facts that must become true at some point in every plan; pattern database heuristics solve abstractions of the problem exactly and store the results. With such heuristics, modern planners solve problems with hundreds of objects in seconds.

Hierarchical task networks

Humans rarely plan at the level of primitive actions. We decompose tasks: to move house, we pack, hire movers and arrange utilities, each of which decomposes further. Hierarchical task network (HTN) planning encodes this knowledge as methods that decompose compound tasks into subtasks, down to primitive actions. HTN planners such as SHOP2 are widely used in practice, for example in game AI, military logistics and manufacturing, because methods let experts encode reliable ways of doing things and restrict search to sensible plans. The trade-off is that someone must write the methods, and the planner cannot find solutions the methods do not allow. Task decomposition by language model agents (Lesson 8) is an informal version of the same idea.

When classical assumptions break

Classical planning assumes a known, fully observable, deterministic, static world in which only the agent acts. Real environments violate every one of these: actions fail, sensors are noisy, objects move, other agents interfere, and the agent's knowledge is incomplete. Several techniques bridge the gap:

• Execution monitoring checks after each action whether its expected effects actually occurred and whether the remaining plan is still valid.
• Replanning creates a new plan from the current state when monitoring detects a problem, which works well when planning is fast.
• Contingent (conditional) planning includes sensing actions and branches for different observations, such as "if the door is locked, use the key".
• Conformant planning finds plans that work whatever the unknown initial conditions, useful when sensing is impossible.
• Probabilistic planning treats outcomes as uncertain and optimizes expected results, leading to Markov decision processes in Lesson 4.

A common practical pattern is a plan–execute–monitor–replan loop, which also describes how robust language model agents behave: make a plan, take a step, observe the result, and revise.

Planning and language models

Language models can produce plausible plans for everyday tasks from instructions alone, drawing on vast knowledge of how things are done. Studies have shown, however, that on formal planning benchmarks they often produce plans that violate preconditions or fail to achieve goals, especially as problems grow, and that they struggle to verify their own plans. Hybrid approaches combine strengths: the language model translates a natural language task into PDDL, a classical planner finds a correct plan, and the language model or executor carries it out; or a validator checks each proposed plan against action models and feeds errors back to the model. Such combinations bring the reliability of formal planning to flexible natural language interfaces.

Temporal and resource planning

Many real planning problems involve time and resources. Actions have durations, some can run in parallel, deadlines must be met, and resources such as fuel, money, machine capacity or battery charge are consumed. Temporal planners extend PDDL with durative actions and constraints on when facts hold, and schedulers assign start times to tasks subject to precedence and resource limits. Space missions provide classic examples: NASA's Remote Agent experiment in 1999 autonomously planned and executed spacecraft operations on Deep Space 1, and planning and scheduling systems continue to manage observations for telescopes and rovers, where communication delays make onboard autonomy essential. In industry, scheduling factories, crews and deliveries combines planning with optimization techniques such as constraint programming and integer programming.

Plan verification and explanation

Because plans are explicit, they can be checked and explained. A plan validator simulates a plan step by step, confirming that each action's preconditions hold when it is applied and that the goal holds at the end, catching errors before execution. Plans can also be explained to humans: why an action is needed (which later precondition or goal it supports), why another plan was not chosen, and what would change if circumstances changed. This transparency is one of the main advantages of symbolic planning over opaque policies, and it is valuable when agents must justify their actions to operators, regulators or users. Combining language models with planners can provide both natural language explanations and formal guarantees.

Planning knowledge in practice

Writing accurate action models is often the hardest part of applying classical planning. Real actions have many conditions and side effects, and missing one can produce plans that fail in execution. Practitioners therefore validate domain models carefully, learn action models from observed traces where possible, and use execution monitoring to discover discrepancies. Language models are increasingly used to draft domain models from documentation, with human review and automated testing against example problems, which lowers the cost of building planning systems for new domains.

Planning and learning together

Classical planning and machine learning are increasingly combined. Learned models can provide heuristics that guide planners, predict action outcomes where hand-written models are incomplete, or recognize objects and states from sensor data so that symbolic planners can reason about them. Conversely, planners can generate training data and structured goals for learning agents. In robotics, task and motion planning systems use symbolic planners for high-level decisions, such as which objects to move in which order, and continuous motion planners and learned controllers for the movements themselves. This layered combination of symbolic reasoning and learned perception and control is likely to remain important as agents take on longer and more structured tasks.

Finally, remember that a plan is only as good as the model of the world behind it. When a plan fails, the cause is often an action model that left out a precondition or side effect. Treating execution failures as information about the model, and updating the model accordingly, turns each failure into an improvement for future planning.