The Formal Planning Primer

If you already know what PDDL is, skip to Post 3. If "heuristic search" sounds like a fancy way to say "guessing," this post is for you.

In Post 1, we saw RoboSort fail catastrophically when an LLM planned its tower assembly without checking constraints. The beam went last, the roof fell through, and two pieces crashed. The planning-enhanced agent got it right by formalizing support constraints and searching for a valid sequence.

But we hand-waved over a critical question: what does "formalizing" actually mean? How do you take a vague task description — "build a tower from these five pieces" — and turn it into something a computer can reason about with mathematical guarantees?

That's what this post answers. We'll take the RoboSort warehouse and turn it into a formal planning problem, piece by piece. By the end, you'll understand the mathematical model, read real PDDL code, and know why planning is computationally hard — the essential vocabulary for everything that follows.

The Planning Problem, Through the Warehouse

Every planning problem answers the same three questions: Where are we now? What can we do? Where do we want to be?

For RoboSort, those questions become concrete. Where are we now? The robot is at its home position, five pieces sit on shelves, the build zone is empty. What can we do? Move to a shelf, pick up a piece, move to the build zone, place a piece — but only if constraints are met (gripper must be empty to pick, piece must have support underneath to stay). Where do we want to be? All five pieces assembled into a stable tower: legs on the platform, beam on legs, roof on beam, flag on top.

The planning community captures this with a precise mathematical model. A planning problem is a tuple:

Let's map each symbol to the warehouse:

• S — State space: Every possible configuration of the warehouse. Where is the robot? What's in the gripper? Which pieces are on shelves? Which are in the build zone? Which are supported? Each unique combination is a state.
• s₀ — Initial state: Robot at home, gripper empty, L1 and L2 on Shelf A, Beam on Shelf B, Roof and Flag on Shelf C, build zone empty.
• S_G — Goal states: Any state where all five pieces form a stable tower — legs on platform, beam spanning both legs, roof on beam, flag on roof.
• A — Actions: move(from, to), pick(piece, location), place(piece, location). Each has preconditions (gripper must be empty to pick) and effects (after picking, gripper holds the piece and the shelf no longer does).
• f — Transition function: Given a state and an action, produces the next state. If RoboSort is at Shelf A with an empty gripper and executes pick(L1), the new state has L1 in the gripper and no longer on Shelf A.
• c — Cost function: How expensive each action is. For RoboSort, each move or manipulation might cost 1 unit. An optimal planner minimizes total cost.

This model is deceptively simple. Six symbols. But it's powerful enough to represent everything from warehouse logistics to spacecraft operations to the multi-step agentic tasks we care about. The question is: how do you write it down in a way a computer can process?

PDDL: The Map Format for Planning

The planning community's answer is PDDL — the Planning Domain Definition Language. Think of it as the structured data format that turns the mathematical model into something a solver can read. Just as SQL lets you describe database queries without specifying how to search, PDDL lets you describe planning problems without specifying how to solve them.

A PDDL problem has two files: a domain file (what's possible — the types, predicates, and actions) and a problem file (what's specific — the objects, initial state, and goal). Let's build both for RoboSort's tower assembly.

The Domain File: Types, Predicates, Actions

The domain file defines the "physics" of the warehouse — what kinds of things exist, what properties they can have, and what actions the robot can perform.

; RoboSort Tower Assembly Domain
(define (domain robosort-tower)
  (:requirements :strips :typing)

  ; What kinds of things exist
  (:types
    location piece - object
  )

  ; Properties that can be true or false
  (:predicates
    (robot-at ?loc - location)         ; robot is at this location
    (piece-at ?p - piece ?loc - location) ; piece is at location
    (holding ?p - piece)                 ; robot is holding piece
    (gripper-empty)                      ; gripper has nothing
    (supports ?lower ?upper - piece)     ; lower supports upper
    (on-platform ?p - piece)              ; piece is on the base platform
    (placed ?p - piece)                   ; piece is in the build zone
  )

  ; Action 1: Move between locations
  (:action move
    :parameters (?from ?to - location)
    :precondition (and (robot-at ?from))
    :effect (and (robot-at ?to)
                 (not (robot-at ?from)))
  )

  ; Action 2: Pick up a piece
  (:action pick
    :parameters (?p - piece ?loc - location)
    :precondition (and (robot-at ?loc)
                       (piece-at ?p ?loc)
                       (gripper-empty))
    :effect (and (holding ?p)
                 (not (piece-at ?p ?loc))
                 (not (gripper-empty)))
  )

  ; Action 3: Place piece (needs support!)
  (:action place-on-platform
    :parameters (?p - piece ?loc - location)
    :precondition (and (robot-at ?loc)
                       (holding ?p))
    :effect (and (on-platform ?p)
                 (placed ?p)
                 (gripper-empty)
                 (not (holding ?p)))
  )

  ; Action 4: Place piece on top of another (must be supported)
  (:action place-on-piece
    :parameters (?p ?support - piece ?loc - location)
    :precondition (and (robot-at ?loc)
                       (holding ?p)
                       (placed ?support)
                       (supports ?support ?p))
    :effect (and (placed ?p)
                 (gripper-empty)
                 (not (holding ?p)))
  )
)

Read through the actions. Notice how each one has explicit preconditions (what must be true before the action can execute) and effects (what changes after it executes). The pick action requires the robot to be at the piece's location with an empty gripper. After picking, the robot holds the piece, the piece is no longer at that location, and the gripper is no longer empty. No ambiguity. No room for misinterpretation.

The key constraint is in place-on-piece: it requires (supports ?support ?p) to be true and the support piece to already be (placed ...). This is what prevents the naive ordering. You can't place the roof without the beam being placed first, because the domain says the beam supports the roof.

The Problem File: Objects, Init, Goal

The problem file describes this specific scenario — our particular warehouse with its particular pieces and target tower.

; RoboSort Tower Assembly Problem — 5 pieces
(define (problem tower-5)
  (:domain robosort-tower)

  ; The specific objects in this scenario
  (:objects
    shelf-a shelf-b shelf-c build-zone home - location
    leg1 leg2 beam roof flag - piece
  )

  ; Where everything starts
  (:init
    (robot-at home)
    (gripper-empty)
    (piece-at leg1 shelf-a)
    (piece-at leg2 shelf-a)
    (piece-at beam shelf-b)
    (piece-at roof shelf-c)
    (piece-at flag shelf-c)
    ; Support constraints (the "physics")
    (supports leg1 beam)    ; legs support beam
    (supports leg2 beam)
    (supports beam roof)    ; beam supports roof
    (supports roof flag)    ; roof supports flag
  )

  ; What we want to achieve
  (:goal (and
    (placed leg1)
    (placed leg2)
    (placed beam)
    (placed roof)
    (placed flag)
  ))
)

The supports facts in the :init block are the crucial difference. They encode the physical reality that legs support the beam, the beam supports the roof, and the roof supports the flag. These aren't suggestions — they're hard constraints. A planner working with this model will never generate a plan that places the roof before the beam, because the precondition for place-on-piece(roof, beam) requires (placed beam) to be true.

This is exactly what the naive LLM missed in Post 1. It had the right pieces and the right goal, but no formal model of support constraints. It treated "assemble a tower" as a sequence of independent actions rather than a constraint-satisfaction problem with ordering dependencies.

Why This is Hard: State Space Explosion

You might think: "Okay, so write the PDDL and feed it to a solver. Problem solved." And for five pieces, yes — the solver finds the optimal plan almost instantly. But planning gets hard fast.

Consider what happens as we scale RoboSort's warehouse. With 5 pieces, each either on a shelf, in the gripper, or in the build zone, we have a manageable state space. But every piece we add roughly doubles the number of possible states, because each new piece can independently be in any of several locations.

With 5 pieces: a few hundred reachable states. A modern solver handles this in milliseconds.

With 10 pieces: tens of thousands of states. Still fast.

With 30 pieces: millions of states. The solver needs good heuristics to avoid exploring them all.

With 50 pieces: more reachable states than atoms in the observable universe. Brute-force search is impossible.

This exponential blowup is inherent. Classical planning is PSPACE-hard — which means that in the worst case, determining whether a valid plan even exists is at least as hard as any problem solvable with polynomial memory. Optimal planning (finding the shortest or cheapest plan) is even harder.

This is why just having PDDL isn't enough. You need sophisticated search algorithms that can navigate enormous state spaces without exploring every state. The planning community has spent 50 years developing exactly these algorithms — and the best ones solve problems with billions of reachable states in seconds. How? That's the next post.

The Broader Landscape: Beyond Classical Planning

Everything we've covered so far is classical planning — deterministic, fully observable, single-agent. But the planning community has extended the framework in many directions. You don't need to learn all of these now, but knowing the landscape helps you appreciate how general the planning framework really is.

Classical planning covers RoboSort as described: deterministic actions, one robot, full knowledge of the world. But imagine extending the warehouse: the robot's gripper might slip (probabilistic), two robots work simultaneously (temporal), or the manager decomposes "organize aisle 3" into subtasks (HTN). Each formalism extends the mathematical model with new capabilities.

For this series, we'll focus primarily on classical planning — it's the foundation everything builds on, and it's where most LLM-planning research operates today. But when we reach Posts 6 and 7, you'll see how LLMs are being used to handle natural language descriptions that implicitly require temporal, probabilistic, or hierarchical reasoning.

From PDDL to Plan: The Compilation Pipeline

When a solver receives your PDDL files, it doesn't search the PDDL directly. There's a compilation pipeline that transforms the lifted, human-readable PDDL into increasingly optimized representations.

Step 1: Grounding. PDDL actions use variables like ?p and ?loc. Grounding replaces every variable with every possible object. The action pick(?p, ?loc) becomes pick(leg1, shelf-a), pick(leg2, shelf-a), pick(beam, shelf-b), and so on. With 5 pieces and 5 locations, one action schema becomes 25 ground actions.

Step 2: FDR (Finite Domain Representation). PDDL uses Boolean predicates — (robot-at shelf-a) is either true or false. FDR compresses these into multi-valued variables. Instead of five separate Boolean facts for the robot's location, FDR uses a single variable robot-location ∈ {home, shelf-a, shelf-b, shelf-c, build-zone}. This is more compact and enables more efficient search.

Step 3: Search. The solver explores the grounded, compressed state space using heuristic search. How these heuristics work — and why they're the key to handling billion-state problems — is the focus of Post 3.

Seeing the Formal Model in Action

Let's bring the formalization full circle. Here's the same PackBot Warehouse from Post 1 — but this time, the interactive demo shows how the formal PDDL model maps onto the physical warehouse scene. Watch as each action fires with its preconditions checked and effects applied.

Interactive — click "▶ Auto Demo" to watch the PDDL model formalize the warehouse step by step

The warehouse is the same one you saw in Post 1 — same shelves, same five pieces, same RoboSort. But now you can see the formal model underneath: every action has a name, preconditions, and effects. Every state is a set of facts. The plan is a sequence of ground actions, and a solver can mathematically prove it reaches the goal.

This is the foundation everything else builds on. In Post 3, we'll see how heuristic search algorithms navigate the enormous state spaces these models create. In Posts 4-7, we'll see how LLMs interact with these formal models — sometimes helping to solve them, sometimes generating them from scratch.

Beyond the Warehouse: Planning in Agentic AI

The formalization we just walked through — states, actions, preconditions, effects — isn't unique to warehouse robots. Every agentic system that decomposes tasks into steps is implicitly building a plan. The formal framework just makes it explicit and verifiable.

What's Ahead

Now you know what a plan is — formally. A planning problem is a tuple of states, actions, transitions, and goals. PDDL is the language that encodes it. And the state space explosion is why finding plans is computationally hard.

But knowing the formalism is only half the story. The other half is solving it. With five pieces, brute-force search works fine. With fifty, you need heuristics — functions that estimate how far you are from the goal and guide the search toward promising paths. The planning community has spent five decades developing these algorithms, and the best modern solvers can handle problems with billions of reachable states.

Next, we'll see how.