Planning: STRIPS, the blocks world, heuristics from relaxation and planning in AI agents

The STRIPS and PDDL languages, forward and backward planning, the hmax and hadd heuristics, the Sussman anomaly, hierarchical planning and replanning — from the robot Shakey to AI agents that write themselves a to-do list.

14 minutes Matěj Žalmánek 2026-10-15

Series AI basics Part 25 of 52

1. Map of artificial intelligence: what is what and how it all fits together
2. A brief history of artificial intelligence: from Turing to language models
3. Data, model, training, inference: the basic terms on a single example
4. How to read mathematical notation: symbols, indices, sums and quantifiers
5. Sets and relations: the building blocks of definitions in AI
6. Functions and mappings: why every AI model is a function
7. Logic and proofs: the rules AI reasons by
8. Graphs and trees: the structure that both search and neural networks stand on
9. Linear algebra for machine learning: vectors, matrices and why AI mostly multiplies
10. Derivatives, the gradient and the chain rule: how a model finds out which way to learn
11. Gradient descent: how a model learns
12. What probability is: from rolling dice to the Kolmogorov axioms
13. Conditional probability and Bayes’ theorem: how to update your estimate when you learn something new
14. Random variables and the cumulative distribution function: one function that tells you everything about a distribution
15. Probability density and probability mass functions: why a continuous variable has zero probability at a point
16. Expected value, variance and covariance: where a distribution lies, how wide it is and what goes with what
17. Overview of probability distributions: Bernoulli, binomial, Poisson, uniform, normal and exponential
18. Law of large numbers and central limit theorem: why averages behave so predictably
19. Statistics and parameter estimation: maximum likelihood, MAP and confidence intervals
20. Information theory: entropy, cross-entropy and KL divergence — where loss functions come from
21. State-space search: BFS, DFS, UCS and A* with animations
22. Games and adversaries: minimax, alpha-beta pruning and Monte Carlo tree search
23. Constraint satisfaction: backtracking, constraint propagation and AC-3 on sudoku and a map of Czech regions
24. Logic and knowledge systems: forward and backward chaining, resolution and expert systems
25. Planning: STRIPS, the blocks world, heuristics from relaxation and planning in AI agents
26. Local search and simulated annealing: a travelling salesman through the Czech regional capitals
27. Genetic algorithms: population, crossover, mutation and selection on a backpack for a hike
28. Evolution strategies and genetic programming: from the one-fifth rule to Kepler’s law
29. Ant colony optimization: how a pheromone trail finds a short path
30. Particle swarm optimisation: inertia, personal experience and the swarm’s experience
31. Neuroevolution: evolving the weights and shape of neural networks, and the NEAT algorithm
32. Fuzzy sets and membership functions: how to write down “somewhat warm”
33. Fuzzy logic and probability: why “somewhat warm” does not mean “probably warm”
34. Fuzzy logic: t-norms, implications and IF–THEN rules
35. Fuzzy control: Mamdani and Sugeno from a fan to a pole on a cart
36. Fuzzy clustering: the fuzzy c-means algorithm and points between clusters
37. Neuro-fuzzy systems (ANFIS): fuzzy rules that learn from data
38. Markov chains: the transition matrix, the stationary distribution and PageRank
39. Hidden Markov models: the Viterbi algorithm and the dishonest casino
40. Bayesian networks: why the grass is wet and what it means for the sprinkler
41. The Kalman filter: how to estimate where a car is and how fast it goes from imprecise measurements
42. Types of machine learning: supervised, unsupervised, semi-supervised and more
43. Prompts, context and RAG: how to give a model the right information
44. Variational autoencoders (VAE): new images from a continuous latent space
45. Generative adversarial networks (GAN): the forger versus the detective
46. Diffusion models: how pure noise becomes an image
47. Markov decision processes: states, actions, rewards and the Bellman equations
48. Q-learning and DQN: learning the value of actions, from a table to a neural network
49. Policy gradient and PPO: learning the policy directly
50. How an AI agent works: a language model in a loop with tools
51. Programming with AI agents: the task, tests and review
52. Evaluating and securing AI systems: how to measure and how to keep watch

Full series syllabus 52 of 83 topics published

In the late 1960s, the robot Shakey from the Stanford Research Institute rolled around a handful of rooms, pushing boxes and switching off lights. It was the first robot that reasoned about its own actions: it was given a goal (“get the box into the next room”) and worked out by itself which actions, and in what order, would get it there. The language it did this in is called STRIPS — and its ideas live on today in logistics, in computer games and in the loop of the AI agent that writes code for you.

It builds on the parts State-space search and Logic and knowledge systems.

1. Planning: search that sees inside

Planning is the search for a sequence of actions that leads to a goal — exactly as in the part on search. The difference lies in how the task is written down. In the maze, the state was a black box and the algorithm knew only where the actions from it led. A planner sees inside: a state is a list of facts about the world, and an action says which facts it needs and which it changes. Thanks to this, the planner can derive by itself an estimate of how far the goal is — you do not have to write any heuristic for it by hand.

2. The STRIPS language

Definition — a STRIPS planning task

Let F be a finite set of atoms (statements about the world). A state is any subset s ⊆ F; an atom p ∈ F holds in the state s if and only if p ∈ s (whatever is not in s does not hold).

An action is a triple a = (pre(a), add(a), del(a)) of subsets of F: the preconditions, the added atoms and the deleted atoms. The action a is applicable in the state s if and only if pre(a) ⊆ s, and for such s and a the resulting state is

T(s, a) = (s ∖ del(a)) ∪ add(a)

T(s, a)

the state after the action is executed — the transition function that the programmer supplied in the part on search; here the planner derives it from the action description by itself

s

the original state: everything the action does not mention carries over to the new state unchanged (the STRIPS assumption that deals with the frame problem — we do not have to list what stays the same)

del(a)

the atoms the action makes false; they are subtracted with the set difference ∖

add(a)

the atoms the action makes true; they are added with the union only after the deletion, so an atom that is in both lists ends up holding

A planning task is a quadruple Π = (F, A, s₀, G), where A is a finite set of actions over F, s₀ ⊆ F the initial state and G ⊆ F the goal. A state s is a goal state if and only if G ⊆ s.

A plan for Π is a sequence of actions a₁, …, a_k ∈ A (k ≥ 0) such that for the states s_i = T(s_i−1, a_i), i = 1, …, k,

1. pre(a_i) ⊆ s_i−1 for every i = 1, …, k (each action is applicable in the state after the previous ones);
2. G ⊆ s_k (the last state is a goal state).

The number k is the length of the plan; a plan of the smallest length is optimal. In words: a plan is a sequence of actions that can be executed one after another from the initial state and after which all the goal atoms hold.

Example — one action step by step

Block C is on A, B stands next to them. The action to table(C, A) has pre = {on(C, A), clear(C)}, add = {ontable(C), clear(A)}, del = {on(C, A)} (the full description of the actions is in the next section; colours as in the formula for T(s, a) above).

s = {on(C, A), ontable(A), ontable(B), clear(B), clear(C)}

pre ⊆ s?   on(C, A) ∈ s, clear(C) ∈ s → the action is applicable

s ∖ del = {ontable(A), ontable(B), clear(B), clear(C)}

T(s, a) = (s ∖ del) ∪ add = {ontable(A), ontable(B), ontable(C), clear(A), clear(B), clear(C)} — all three blocks on the table

STRIPS was created in 1971 (Fikes and Nilsson) precisely for Shakey. Its present-day successor is the PDDL language, which since 1998 has been used to specify tasks for the international planning competitions. An action is written in it as a schema with variables:

(:action to-table
  :parameters (?a ?b)
  :precondition (and (on ?a ?b) (clear ?a))
  :effect (and (ontable ?a) (clear ?b) (not (on ?a ?b))))

3. The blocks world

The classic test task of planning: blocks lie on a table, some stacked on others. With one action you pick up a block with nothing on top of it and put it on the table or on another clear block. There are three kinds of atoms: on(A, B) — A lies on B, ontable(A) and clear(A).

Actions in the blocks world

Let K be a finite set of blocks. The atoms are F = {on(x, y) : x, y ∈ K, x ≠ y} ∪ {ontable(x), clear(x) : x ∈ K}. For every choice of pairwise distinct blocks A, B, C ∈ K, the task contains the actions:

• to table(A, B): pre = {on(A, B), clear(A)}, add = {ontable(A), clear(B)}, del = {on(A, B)}
• from table(A, C): pre = {ontable(A), clear(A), clear(C)}, add = {on(A, C)}, del = {ontable(A), clear(C)}
• move(A, B, C): pre = {on(A, B), clear(A), clear(C)}, add = {on(A, C), clear(B)}, del = {on(A, B), clear(C)}

The planner first grounds a schema with variables: it substitutes every combination of blocks for the variables. For n blocks there are n(n − 1) “to table” actions, as many “from table” actions and n(n − 1)(n − 2) moves, n²(n − 1) in total. For three blocks that is 9 · 2 = 18 actions, for six 36 · 5 = 180. In any given state, though, only a few of them are applicable — there are few blocks with nothing on top.

The world looks like a toy, but it grows fast. Three blocks can be arranged in 13 ways, four in 73, five in 501 and six in as many as 4,051. Where do these numbers come from:

number of states = ∑_k=1ⁿ n! · C(n − 1, k − 1)/k!

n!

we line up all the blocks in a single row — every order is a candidate; we get towers from it by cutting

C(n − 1, k − 1)

we cut the row into k non-empty towers: we choose k − 1 of the n − 1 gaps between blocks. The order inside a tower matters (A on B is not B on A), which is why we cut an ordering, not a set

k!

the order of the towers on the table does not matter — two towers side by side are the same state, whatever order we list them in. So we have counted each state k! times

The planner counted them differently — it went through all the reachable states — and got the same result. Let us try two tasks. In the larger one, two towers A–B–C and D–E–F (written from the bottom) stand on the table and the goal is a single tower F–E–D–C–B–A:

4. Forward planning

Definition — forward planning (progression)

Let Π = (F, A, s₀, G) be a STRIPS planning task. Forward planning solves Π by searching (breadth-first, A* … — see State-space search) the state space in which

1. the states are sets s ⊆ F and the initial state is s₀;
2. the successors of a state s are Succ(s) = {T(s, a) : a ∈ A ∧ pre(a) ⊆ s}, and every transition costs 1;
3. a state s is a goal state if and only if G ⊆ s.

A path s₀ → … → s_k found to a goal state gives the plan: the actions that caused the individual transitions, in order from the start. Since there are at most 2^|F| states, search with a check of visited states always terminates.

from collections import deque

def proved(stav, akce):
    return (stav - akce.odeber) | akce.pridej

def planuj(start, cil, akce):
    okraj, rodic = deque([start]), {start: None}
    while okraj:
        stav = okraj.popleft()
        if cil <= stav:                      # all goal atoms hold
            return plan_z(rodic, stav)
        for a in akce:
            if a.predpoklady <= stav:
                dalsi = proved(stav, a)
                if dalsi not in rodic:
                    rodic[dalsi] = (stav, a)
                    okraj.append(dalsi)

On the tower task, breadth-first search finds the shortest plan of 6 actions, but along the way it expands 2,132 states — more than half of all 4,051. It simply knows nothing about which direction the goal lies in.

5. Heuristics from relaxation

In the part on search we came up with the heuristic for the maze ourselves. A planner can compute one from the action descriptions — by simplifying the task, solving it and using the cost of the simplified solution as an estimate.

Definition — delete relaxation

Let Π = (F, A, s₀, G) be a STRIPS planning task. For an action a, put a⁺ = (pre(a), add(a), ∅). The relaxed problem (without deletion) is

Π⁺ = (F, {a⁺ : a ∈ A}, s₀, G).

In Π⁺, T(s, a⁺) = s ∪ add(a) ⊇ s, so an atom that holds once holds forever.

Let s ⊆ F be a state and ⊕ ∈ {max, ∑} a chosen aggregation. We define the cost of a set of atoms P ⊆ F as c(P) = max_{q ∈ P} c(q) for ⊕ = max, or c(P) = ∑_{q ∈ P} c(q) for ⊕ = ∑ (for P = ∅ both are 0). The cost of an atom c : F → ℕ ∪ {∞} from the state s is the solution of the system

1. c(p) = 0 for p ∈ s;
2. c(p) = min_{a ∈ A : p ∈ add(a)} [1 + c(pre(a))] for p ∉ s (the minimum over the empty set is ∞),

which we obtain by iteration: we start with c(p) = 0 for p ∈ s and c(p) = ∞ otherwise, and lower the values according to the right-hand side as long as they change (code below). The heuristics of the state s are

h_max(s) = max_{g ∈ G} c(g)   (with the max aggregation),   h_add(s) = ∑_{g ∈ G} c(g)   (with the ∑ aggregation).

In words: c(p) estimates the number of actions needed to achieve the atom p in a world where nothing is deleted. h_max is admissible (theorem below), h_add is a more informative guide, but it may overestimate.

c(p) = min_{a : p ∈ add(a)} [ 1 + c(pre(a)) ]

c(p)

an estimate of how many actions are needed for the atom p to become true (for atoms that already hold, it is 0)

min over actions with p ∈ add(a)

several actions may add the atom; we pick the cheapest one, because the planner chooses its route itself

1

the cost of the action itself that finally adds p

c(pre(a))

the cost of making the action applicable at all — satisfying all its preconditions. This is where h_max and h_add differ: the maximum assumes the preconditions are achieved “together” and their preparations overlap, the sum that each one takes separate work

def ceny(stav, akce, agreguj):             # agreguj = max (hmax) or sum (hadd)
    c = {p: 0 for p in stav}
    zmena = True
    while zmena:                             # repeat while some cost improves
        zmena = False
        for a in akce:
            if all(p in c for p in a.predpoklady):
                nova = 1 + agreguj(c[p] for p in a.predpoklady)
                for p in a.pridej:           # a.odeber is ignored — relaxation
                    if nova < c.get(p, float("inf")):
                        c[p], zmena = nova, True
    return c

def h(stav, cil, akce, agreguj):
    c = ceny(stav, akce, agreguj)
    return agreguj(c[g] for g in cil)        # unreachable goal: h = ∞

Example — h_max and h_add for the Sussman anomaly

Start: C is on A, B stands next to them; goal G = {on(A, B), on(B, C)} (we analyse the task below). Atom costs by layer:

cost 0 (holds): ontable(A), ontable(B), on(C, A), clear(B), clear(C)

cost 1: to table(C, A) → ontable(C), clear(A);   from table(B, C) → on(B, C);   move(C, A, B) → on(C, B)

cost 2: from table(A, B) needs ontable(A), clear(A), clear(B) with costs 0, 1, 0

   h_max: 1 + max(0, 1, 0) = 2,   h_add: 1 + (0 + 1 + 0) = 2 → on(A, B) has cost 2 (colours as in the formula for c(p) above)

h_max(s₀) = max(2, 1) = 2,   h_add(s₀) = 2 + 1 = 3,   actually needed: h* = 3

h_max underestimates because it counts only the most expensive goal: on(A, B) costs two actions, but on(B, C) needs a third one of its own, and the maximum swallows it. The sum counts it and here hits the mark exactly. On the tower task the effect is more pronounced: from the start h* = 6, h_max = 3, the number of unsatisfied goals is 5 and h_add = 15 — the sum counts the shared preparation (uncovering blocks) again for every goal and overestimates the real cost two and a half times.

Theorem — h_max and the number of unsatisfied goals are admissible

Let Π = (F, A, s₀, G) be a STRIPS planning task and, for a state s ⊆ F, let h*(s) be the length of the shortest plan from s to the goal G (∞ if none exists). A heuristic h is admissible (as in the part on search) if and only if h(s) ≤ h*(s) for every state s.

Theorem. (1) For every STRIPS task, h_max is admissible. (2) Let Π be a blocks-world task whose goal contains only atoms of the form on(x, y). Then the heuristic h_#(s) = |G ∖ s| (the number of unsatisfied goals) is admissible.

Proof (1). If h*(s) = ∞, there is nothing to prove. Otherwise take a shortest plan a₁, …, a_k of the real task. It is also a plan for the relaxed problem (without deletion, at every step at least the same atoms hold, so the preconditions remain satisfied). By induction on i: every atom that holds after i actions has c_max ≤ i — either it held earlier, or it was added by the action a_i, whose preconditions held after i − 1 actions and therefore have cost ≤ i − 1, so 1 + max ≤ i. All goal atoms hold after k actions, hence h_max(s) = max_{g ∈ G} c(g) ≤ k = h*(s).

Proof (2). The goals are on(·, ·) atoms, and each action adds at most one such atom. Satisfying m missing goals therefore takes at least m actions.

For h_add the proof fails at the last step: the sum of costs can be greater than k, because the same plan actions are counted for several goals.

Three heuristics on the tower task, all with the A* algorithm:

The admissible h_max finds the optimum and saves over 90% of the work. The number of unsatisfied goals is also admissible in our world (each action places just one block, so it satisfies at most one goal) and here it works even better. h_add expands the fewest, but pays for it: the plan is one step longer than necessary. No heuristic always wins — and real planners such as FF or Fast Downward have whole sets of heuristics that they combine.

How A* with h_max works is best seen on a small task — the Sussman anomaly, which we analyse two sections later. Each row is one expanded state (towers from the bottom); A* always takes the state with the smallest f = g + h, where g is the number of actions from the start, and on a tie the one it discovered earlier:

Breadth-first search on the same task expands all 13 states, A* with h_max only 5. In the third step it takes a wrong turn — it puts C on B — because the state has f = 3, just like the correct path, and was discovered earlier. The very next step fixes it. The first goal state expanded has a shortest plan — A* guarantees that when the heuristic is admissible (and h_max is even consistent, so it never has to go back to closed states).

6. Backward planning

Definition — backward planning (regression)

Let Π = (F, A, s₀, G) be a STRIPS planning task. A subgoal is a set of atoms g ⊆ F that still have to hold. An action a ∈ A is relevant for the subgoal g if and only if

add(a) ∩ g ≠ ∅   ∧   del(a) ∩ g = ∅,

i.e. the action brings about at least one atom of the subgoal and destroys none. The regression of the subgoal g through a relevant action a is the subgoal

g′ = (g ∖ add(a)) ∪ pre(a)

g′

what must hold before the action a so that g holds after it — a new, earlier subgoal

g

the current subgoal; atoms the action does not mention must already hold beforehand, because the action does not bring them about itself (and thanks to the relevance condition it does not destroy them either)

add(a)

we subtract them, because the action takes care of these atoms itself — they need not hold beforehand

pre(a)

we add them, because the action cannot be executed without its preconditions — they become new subgoals

Backward planning searches the space of subgoals in which

1. the initial subgoal is g₀ = G;
2. the successors of a subgoal g are the regressions g′ through all actions a ∈ A relevant for g;
3. a subgoal g is terminal if and only if g ⊆ s₀.

If it finds a path g₀ → g₁ → … → g_k ⊆ s₀ through the actions b₁, …, b_k, the plan is the sequence b_k, …, b₁ — the actions found, in reverse order.

Example — regressing the goal of the Sussman anomaly

Goal g = {on(A, B), on(B, C)}, start s₀ = {on(C, A), ontable(A), ontable(B), clear(B), clear(C)}. We take the actions from the last one (colours as in the formula for regression above):

from table(A, B): add = {on(A, B)} intersects g, del = {ontable(A), clear(B)} does not → relevant

   g′ = {on(B, C)} ∪ {ontable(A), clear(A), clear(B)}

from table(B, C): add = {on(B, C)}, del = {ontable(B), clear(C)} → relevant

   g″ = {ontable(A), clear(A), clear(B)} ∪ {ontable(B), clear(B), clear(C)} = {ontable(A), ontable(B), clear(A), clear(B), clear(C)}

to table(C, A): add = {ontable(C), clear(A)}, del = {on(C, A)} → relevant

   g‴ = {ontable(A), ontable(B), clear(B), clear(C)} ∪ {on(C, A), clear(C)} = {on(C, A), ontable(A), ontable(B), clear(B), clear(C)} ⊆ s₀ ✓

The plan read backwards: to table(C, A), from table(B, C), from table(A, B). But if we had tried from table(B, C) as the last action, we would have got the subgoal {on(A, B), ontable(B), clear(B), clear(C)} — A is on B and B is clear at the same time. No such state exists, but regression cannot tell by itself; backward planners therefore need extra rules that detect impossible combinations.

7. The Sussman anomaly

The simplest idea of how to plan: split the goal into parts and achieve them one after another. It often works — and it fails on as few as three blocks. The task is named after Gerald Sussman, who analysed it in the 1970s: C is on A, B stands next to them, and the goal is A on B and at the same time B on C.

The shortest plan for “A on B” takes C off and puts A on B. But then B is under A, and getting B onto C means taking A off again. At the end only the second goal holds, and it took 4 steps. The opposite order turns out the same: we put B on C, but in doing so we bury A under C and B — and freeing it destroys the first goal again. The goals undo each other, whichever one you start with.

The solution needs to interleave the steps of both goals: first free A (a step for the first goal), then B on C (the second goal), and only then A on B (the first goal). A planner that searches the space of whole states finds this by itself — here it went through all 13 states of the three-block world. A planner that assembles partial plans has to be able to untangle them and join them again. That is the topic of a whole family of “plan-space planning” methods.

8. Hierarchical planning

Definition — HTN

We present the totally ordered variant of HTN (hierarchical task network) used by the SHOP2 planner and by the code below. Let F be a finite set of atoms and A a finite set of STRIPS actions over F. Tasks are of two kinds: primitive — these are the actions a ∈ A — and compound, from a finite set U (U ∩ A = ∅).

A method for a compound task u ∈ U is a pair m = (pre(m), (u₁, …, u_j)), where pre(m) ⊆ F is a condition and u₁, …, u_j ∈ A ∪ U (j ≥ 0) are subtasks. An HTN task is (F, A, U, M, s₀, w₀), where M is a finite set of methods, s₀ ⊆ F the initial state and w₀ the initial sequence of tasks (usually a single top-level task).

We process a pair (state s, sequence of tasks w = (t, w′)) as follows:

1. if t is primitive and pre(t) ⊆ s, we move to (T(s, t), w′) and append t to the end of the plan;
2. if t is compound and m ∈ M is one of its methods with pre(m) ⊆ s, we move to (s, (u₁, …, u_j, w′)) — we replace the task t with the subtasks of the method.

A solution is a plan (a sequence of primitive actions) obtained by finitely many such steps from (s₀, w₀) down to the empty sequence of tasks. In words: planning starts with a top-level task and decomposes it according to the methods until only primitive actions remain that can be executed.

def rozloz(ukoly, stav):                   # ukoly: list of remaining tasks
    if not ukoly:
        return []                            # everything decomposed
    u, zbytek = ukoly[0], ukoly[1:]
    if u.primitivni:                         # an ordinary STRIPS action
        if not u.predpoklady <= stav:
            return None
        plan = rozloz(zbytek, proved(stav, u))
        return None if plan is None else [u] + plan
    for metoda in u.metody:                  # try the recipes one by one
        if metoda.podminka <= stav:
            plan = rozloz(metoda.podukoly + zbytek, stav)
            if plan is not None:
                return plan
    return None                              # no method worked — backtrack

Here the search runs in the space of decompositions, not states: it branches only on which method to choose for a compound task. Tasks are decomposed in the order in which they will be executed, so the planner always knows the current state — the SHOP2 planner, for example, works the same way.

Hierarchical planning is used wherever experts have proven procedures: in logistics, in production control and a lot in computer games. The action game F.E.A.R. (2005) became famous for soldiers who planned their tactics on the fly in a STRIPS-style language — and planners in a number of other games grew out of the same idea.

9. Planning in an uncertain world

STRIPS assumes that the world is exactly as we think it is, and that actions turn out exactly as described. But a real robot drops a block and a real server does not respond. The most common answers to this are three:

• Monitoring and replanning. After each action, check whether the world looks the way the plan expected. If not, plan again from what is there. Simple and surprisingly effective (the loop is below).
• Conditional plans have branches: “if the door opens, go on, otherwise use the other entrance”.
• Probabilistic planning. When an action has several possible outcomes with given probabilities, we do not look for a sequence of actions but for a policy for every situation — Markov decision processes have their own part in the syllabus.

def proved_s_dohledem(cil, akce, svet):
    plan = planuj(svet.pozoruj(), cil, akce)
    while plan:
        a = plan.pop(0)
        cekany = proved(svet.pozoruj(), a)   # what should hold according to the model
        svet.udelej(a)
        skutecny = svet.pozoruj()
        if cil <= skutecny:
            return True
        if skutecny != cekany:               # the world behaved differently
            plan = planuj(skutecny, cil, akce)   # replan from what is there
    return cil <= svet.pozoruj()

It is enough to watch only what the rest of the plan depends on: when an atom changes that is neither a precondition of any further action nor part of the goal, the plan still holds. This saving was introduced as early as the PLANEX system, which executed Shakey’s plans (Fikes, Hart and Nilsson, 1972).

10. Planning in AI agents

A language agent fixing a bug in code is planning too: it breaks the task down into a list of steps, after each step it looks at the result (did the tests pass? does the file exist?) and adjusts the plan accordingly. It is monitoring and replanning, only the actions are terminal commands and the preconditions and effects are not formally written down anywhere — the model estimates them from text.

And that is exactly the weak spot. Research on blocks-world tasks (for example the PlanBench suite) has shown that language models often make mistakes in classical planning, especially when the blocks are renamed to nonsense words, so the model cannot draw on examples it has learned. Newer models with longer reasoning do much better, but they give no guarantee of correctness. A division of labour has therefore proven itself: the model translates the task into PDDL or proposes a plan, and a classical planner or validator checks it — each does what it is good at.

11. Summary

• Planning is the search for a sequence of actions leading to a goal; STRIPS describes a state as a set of atoms and an action by its preconditions, added atoms and deleted atoms.
• Forward planning is state-space search; backward planning regresses the goal through relevant actions.
• A planner computes its heuristic by itself from the relaxed problem without deletion: h_max is admissible, h_add is faster but may lead to a longer plan.
• The Sussman anomaly shows that subgoals cannot always be achieved one after another — the steps have to be interleaved.
• Hierarchical planning decomposes tasks using proven methods; in an uncertain world the plan is monitored and replanned — exactly what today’s AI agents do.

Want to try it hands-on? Have an AI agent write the blocks world in PDDL and run the freely available Fast Downward planner on it — and then see how many blocks the model can handle on its own without it.

Do you see it differently? Write to support@coden-app.com.