50 Years of Planning Algorithms (In 15 Minutes)

Post 2 gave you the language — states, actions, PDDL. Now meet the algorithms that actually find plans within those astronomical state spaces.

The planning community has been building solvers for over fifty years. Some of them are extraordinarily powerful: modern planners routinely solve problems with billions of reachable states in under a second. Before we talk about how LLMs interact with planning (Posts 4-7), we need to understand what we're integrating with.

This isn't just historical appreciation. Every approach in the second half of this series — LLM-as-heuristic, NL-to-PDDL, LLM-Modulo — relies on classical planning algorithms doing the actual search. Understanding how they work is understanding why the hybrid approaches are so effective.

If you already know A* and heuristic planning, skim the timeline and skip to the demo.

The Evolution: From Theorem Proving to Heuristic Search

Planning algorithms have gone through several paradigm shifts. Here's the trajectory that matters:

The critical shift happened around 2001. Before HSP and FF, planners used problem-independent search strategies or hand-crafted heuristics. The breakthrough was automatic heuristic derivation: given any PDDL problem, automatically compute a function that estimates how far each state is from the goal. This turned planning from "explore everything" into "search intelligently."

Heuristic Search: The Engine Behind Modern Planning

At its core, every modern planner is running a best-first search. It maintains a frontier of states to explore, and picks the most promising one next. The magic is in the evaluation function that decides "most promising."

The evaluation function typically combines two components:

• g(s) — the cost of reaching state s from the initial state. This is exact — you know how many actions you've taken.
• h(s) — the estimated cost of reaching the goal from s. This is the heuristic. It's an approximation, but a good one can make the difference between solving a problem in milliseconds and not solving it at all.

The way you combine these two values defines the search strategy:

For RoboSort's warehouse, think of it this way: g(s) counts how many move/pick/place actions the robot has taken so far. h(s) estimates how many more it needs. A* guarantees the shortest plan but might explore thousands of states. GBFS (Greedy Best-First Search) beelines for the goal using only the heuristic, finding a plan fast but not necessarily the best one.

In practice, most competition-winning planners use GBFS or wA* — finding good plans quickly matters more than finding perfect plans slowly when you have billions of states to navigate.

How Heuristics Work: The Relaxation Trick

So where do heuristics come from? You can't just guess. A bad heuristic is worse than no heuristic — it sends the search in circles.

The most influential idea in planning heuristics is the relaxation trick: solve an easier version of the problem, and use that solution's length as an estimate for the real problem. The easier version is always solvable faster, and its solution length is always ≤ the real solution (making it admissible — it never overestimates).

The most common relaxation is the delete relaxation: pretend that actions never remove facts from the state. In the real problem, picking up a piece means the shelf no longer has it. In the relaxed problem, the piece is somehow both in your gripper and still on the shelf. This sounds absurd, but it makes the problem dramatically easier to solve — and the solution length is a surprisingly good estimate of the real cost.

This is the h_FF heuristic (Hoffmann 2001), and it revolutionized planning. The heuristic doesn't need to be perfect. It just needs to point the search in roughly the right direction. A state where h(s) = 3 is probably closer to the goal than one where h(s) = 12. That's enough for greedy best-first search to find plans in seconds that blind search would take years to discover.

The Planning Stack: From PDDL to Plan

Post 2 introduced the compilation pipeline (PDDL → Grounding → FDR → Solver). Now let's see the full stack with the heuristic layer made explicit:

The critical insight: the heuristic is derived automatically from the PDDL. You don't hand-code domain-specific search guidance. The planner reads the action schemas, computes relaxations or landmarks or causal graphs, and derives a heuristic function that works for any planning problem.

What Classical Planners Are Great At (And Where They Struggle)

After 50 years of research, classical planners are remarkably capable. But they have clear boundaries:

What They Excel At

• Correctness guarantees. A sound planner never returns an invalid plan. No hallucinated actions, no constraint violations.
• Optimality (when needed). A* with an admissible heuristic proves that no shorter plan exists.
• Scaling on structured problems. Modern planners exploit problem structure to prune the search space by orders of magnitude.
• Domain independence. One planner handles logistics, manufacturing, satellite scheduling, and genome assembly.

Where They Struggle

• Someone must write the PDDL. Writing correct PDDL is a specialized skill.
• No natural language interface. The formal specification is the only input.
• Scaling on unstructured problems. Random instances remain hard even for the best planners.
• Real-world complexity. Continuous actions, partial observability, concurrent events — classical planning handles none natively.

The International Planning Competition (IPC)

How do we know which planners work best? Since 1998, the International Planning Competition has been the definitive benchmark. Every two years, planning teams submit their solvers to compete on standardized problem sets across diverse domains.

The IPC measures two things: coverage (how many problems the planner solves within time/memory limits) and plan quality (how close to optimal the plans are).

Key IPC results that shaped the field:

• IPC 2000: FF (using h_FF) dominated, proving that heuristic search was the way forward.
• IPC 2004: Fast Downward introduced the SAS+ / FDR representation and causal graph heuristic.
• IPC 2008/2011: LAMA won with landmark-based heuristics and multi-phase search.
• Recent IPCs: Portfolio planners (running multiple strategies) consistently outperform single-strategy planners.

Seeing Search in Action

Here's the same RoboSort warehouse — but now we're watching the planner's mind. Left: the physical warehouse. Right: the planner's floor map, showing which states it explores to route the robot from Home to the Build Zone. Three strategies compete on the same problem.

Interactive — click a strategy or "▶ Auto Demo" to watch all three

BFS explores the most cells but guarantees the shortest path. Greedy explores the fewest but may detour. A* is the sweet spot — fewer cells than BFS while still guaranteeing the optimal path. In the full tower assembly, the same dynamics play out across thousands of states.

Beyond the Warehouse: Planning in Agentic AI

The heuristic search principles we just covered — estimating distance to goal, balancing exploration and exploitation, pruning unpromising branches — apply directly to how agentic systems navigate multi-step tasks.

What's Ahead

These planners are powerful — extraordinarily so. The best modern solvers handle problems that no brute-force approach could touch. They provide correctness guarantees that no statistical model can match.

But they have one critical limitation: someone must write the PDDL. For decades, that meant you needed a planning expert to formalize every new problem.

Then LLMs arrived. And everyone asked the obvious question: "Can GPT-4 just do the planning?"

The answer, as rigorously tested by the planning community, is no. But the right question turned out to be different — and the answers are spectacular.