I4 · Problem Solving and Reasoning: Classical AI

Automated Planning

Automated planning finds a sequence of actions that transforms an initial state into one satisfying a goal. States are described by facts that are true, and each action has preconditions that must hold before it can be applied and effects that add or delete facts. Classical planning languages such as STRIPS and PDDL describe problems this way, and planners search for plans using heuristics derived from the problem description.

10 min Intermediate · Sublevel Intermediate Jump to the activity

What you need: The earlier topics of this module.

Definition

A warehouse robot is told: "Get box 17 onto truck B." Box 17 is under two other boxes. The robot must work out a sequence: move the top boxes, pick up 17, drive, load. Nobody wrote those steps; it planned them.

Automated planning finds a sequence of actions that transforms an initial state into one satisfying a goal. States are described by facts that are true, and each action has preconditions that must hold before it can be applied and effects that add or delete facts. Classical planning languages such as STRIPS and PDDL describe problems this way, and planners search for plans using heuristics derived from the problem description.

In simple words

Planning is writing a recipe for yourself. You know what you have (the initial state), what you want (the goal) and what each step needs and does: you can only fry onions once they are chopped, and frying makes them golden. The planner chains steps whose needs are met until the goal is reached.

Overview

  • Automated planning finds a sequence of actions that turns an initial state into a goal state.
  • Actions are described by preconditions (what must be true) and effects (what changes).
  • STRIPS (1971) introduced this representation for the Shakey robot; PDDL is today's standard language.
  • Planners use search with domain-independent heuristics to handle many problems.
  • Real plans must handle time, resources and actions that do not go as expected.
  • NASA's Remote Agent planned and controlled the Deep Space 1 spacecraft in 1999.

Why it matters

Planning is how AI systems act purposefully over many steps: robots, logistics, space missions, games and, increasingly, AI agents that use tools. Understanding preconditions and effects helps you design and debug any multi-step system.

Key terms

Plan
A sequence of actions that achieves the goal from the initial state.
Precondition
Facts that must be true before an action can be taken.
Effect
Facts an action makes true (add list) or false (delete list).
STRIPS
An early planning representation from 1971 using preconditions, add lists and delete lists.
PDDL
Planning Domain Definition Language, the standard format for describing planning problems.
Hierarchical planning
Planning with high-level tasks broken into smaller sub-tasks.

Types

Planning comes in several types, depending on how the problem is represented and how uncertain the world is.

1. Classical (STRIPS/PDDL) planning

Planning in a fully observable, deterministic world with actions defined by preconditions and effects.

  • How it works: States are sets of facts; an action can apply when its preconditions hold, adding and deleting facts; search finds the plan.
  • Example: Blocks world: stack block A on B on C by picking up and putting down blocks.
  • When to use it: Use it for well-defined tasks such as logistics, puzzles and simple robot tasks.

2. Forward (progression) and backward (regression) planning

Searching from the initial state towards the goal, or from the goal back to the initial state.

  • How it works: Forward search applies actions to states; backward search looks for actions whose effects achieve goals; both need good heuristics.
  • Example: Planning a trip forwards from home, or backwards from "be at the conference at 10 a.m.".
  • When to use it: Use forward search with heuristics in most modern planners; backward search helps when goals are few and specific.

3. Hierarchical task network (HTN) planning

Planning by breaking high-level tasks into smaller sub-tasks using methods.

  • How it works: Methods describe how to decompose a task, such as "travel" into "book ticket", "go to station" and "board train", until only primitive actions remain.
  • Example: Video-game characters and military logistics planners use HTNs.
  • When to use it: Use it when experts already know standard ways of doing tasks, which makes planning much faster.

4. Temporal and resource planning (scheduling)

Planning with action durations, deadlines and limited resources.

  • How it works: Actions take time and may overlap; constraints on machines, people and budgets must be respected; the goal is often to finish as early as possible.
  • Example: Scheduling a construction project or a satellite's observation time.
  • When to use it: Use it in manufacturing, space missions and project management.

5. Planning under uncertainty

Planning when actions can have several outcomes or the state is not fully known.

  • How it works: Contingent plans include branches ("if the door is locked, then…"); Markov decision processes compute a policy that chooses the best action in every state.
  • Example: A delivery drone that replans when wind pushes it off course.
  • When to use it: Use it in robotics and real-world operations, linking planning to reinforcement learning.

Explained in detail

Describing actions

ActionPreconditionsAddsDeletes
Unstack(X, Y): take X off YOn(X, Y), Clear(X), HandEmptyHolding(X), Clear(Y)On(X, Y), Clear(X), HandEmpty
PutDown(X)Holding(X)OnTable(X), Clear(X), HandEmptyHolding(X)
PickUp(X)OnTable(X), Clear(X), HandEmptyHolding(X)OnTable(X), Clear(X), HandEmpty
Stack(X, Y)Holding(X), Clear(Y)On(X, Y), Clear(X), HandEmptyHolding(X), Clear(Y)

This is the classic blocks world, used since the 1970s to study planning. The STRIPS representation, developed by Richard Fikes and Nils Nilsson at the Stanford Research Institute in 1971 for the Shakey robot, describes every action by these three lists. Its key simplification is that anything not mentioned in an action's effects stays the same, which avoids having to list everything that does not change. PDDL, introduced in 1998 for the International Planning Competition, generalises this and is still the standard.

How planners search

A planner can search forward from the initial state, applying actions whose preconditions hold, or backward from the goal, choosing actions whose effects achieve it. Either way the state space is huge, so modern planners compute heuristics automatically from the action descriptions. A popular trick is the relaxed problem: ignore every delete list, so facts once true stay true, and count how many actions would then be needed. That count is fast to compute and guides search remarkably well. Systems such as Fast Downward, which won planning competitions in the 2000s, combine such heuristics with A*-style search.

Planning in the real world

  • NASA's Remote Agent planned and controlled the Deep Space 1 spacecraft autonomously in 1999, a landmark for AI planning.
  • Logistics companies plan delivery routes and loading orders; factories plan machine schedules.
  • Video-game characters use goal-oriented action planning to choose believable behaviour.
  • Hierarchical planning breaks high-level tasks, such as "deliver the parcel", into sub-tasks, which matches how people plan.
  • LLM-based agents plan in natural language; combining them with classical planners that check preconditions makes their plans more reliable.

Planning also highlights an important difference between plans and reality. A plan assumes the world behaves as the action descriptions say, but real robots slip, boxes are heavier than expected and doors are locked. Practical systems therefore monitor the world while executing a plan and replan when an expected fact turns out to be false, a loop of plan, act, observe and replan.

How it works

  1. Describe the initial state as a set of true facts.
  2. Describe the goal as facts that must be true.
  3. Write each action's preconditions, add list and delete list.
  4. Search forward or backward, guided by a heuristic such as the relaxed problem.
  5. Check the plan by simulating it step by step, verifying each precondition.

In code

blocks_planner.py
from collections import deque
from itertools import permutations

BLOCKS = ["A", "B", "C"]

def actions(state):
    facts = set(state)
    holding = next((f[1] for f in facts if f[0] == "Holding"), None)
    clear = {x for x in BLOCKS if not any(f[0] == "On" and f[2] == x for f in facts) and holding != x}
    if holding is None:
        for x in clear:
            if ("OnTable", x) in facts:
                yield f"PickUp({x})", facts - {("OnTable", x)} | {("Holding", x)}
            for f in facts:
                if f[0] == "On" and f[1] == x:
                    yield f"Unstack({x},{f[2]})", facts - {f} | {("Holding", x)}
    else:
        yield f"PutDown({holding})", facts - {("Holding", holding)} | {("OnTable", holding)}
        for y in clear - {holding}:
            yield f"Stack({holding},{y})", facts - {("Holding", holding)} | {("On", holding, y)}

start = {("On", "C", "A"), ("OnTable", "A"), ("OnTable", "B")}  # C sits on A
goal = {("On", "A", "B"), ("On", "B", "C")}                     # build the tower A on B on C

frontier, seen = deque([(frozenset(start), [])]), {frozenset(start)}
while frontier:
    state, plan = frontier.popleft()
    if goal <= state:
        print("Plan:", " -> ".join(plan))
        break
    for name, nxt in actions(state):
        nxt = frozenset(nxt)
        if nxt not in seen:
            seen.add(nxt)
            frontier.append((nxt, plan + [name]))
print("States explored:", len(seen))

Output

Plan: Unstack(C,A) -> PutDown(C) -> PickUp(B) -> Stack(B,C) -> PickUp(A) -> Stack(A,B)
States explored: 22

Try it yourself

The box at the bottom

A warehouse robot must load box A onto a cart, but box C is stacked on top of it.

Build the tower

C is on A, and B is on the table. Order the actions to build A on B on C.

  1. 1PutDown(C)
  2. 2Stack(B, C)
  3. 3Unstack(C, A)
  4. 4Stack(A, B)
  5. 5PickUp(B)
  6. 6PickUp(A)

Common mistakes

  • Forgetting a delete effect, so impossible states appear true.
  • Missing a precondition, so plans include impossible steps.
  • Planning at too fine a level instead of using hierarchy.

Check yourself

Question 1

1. What are an action's preconditions?

Question 2

2. In STRIPS, what happens to facts not mentioned in an action's effects?

Question 3

3. What is the "relaxed problem" heuristic?

Summary

  • Planning finds action sequences from an initial state to a goal.
  • Actions have preconditions and add and delete effects; STRIPS and PDDL describe them.
  • Planners use automatic heuristics; planning powers robots, logistics, space missions and AI agents.

Read it. Now try it yourself.

Open the interactive activity

Finished reading?

Sources: Planning.wiki: a guide to PDDL · Russell and Norvig, Artificial Intelligence: A Modern Approach (4th edition)