The Scaling Problem

Planning is sound, complete, and optimal. It is also exponentially hard. Learning is how we get past that wall — but to see why it works, we first need to feel the wall.

A simple-looking task

Consider a tiny warehouse. Four zones — A, B, C, D — arranged in a grid. A robot starts in zone A. A package sits in zone C. We want the package delivered to zone D. The robot can move between zones, pickup a package in the zone it's in, and drop the package wherever it stops.

This is a classical planning problem. Three action types, a handful of objects, four locations. A planner like A* with a good heuristic — or even a domain-independent system like Fast-Downward — solves it in milliseconds. The plan has four steps: move(A→C), pickup(pkg, C), move(C→D), drop(pkg, D). Done.

Now scale it up. Same actions, same rules. Just more zones and more packages.

The exponential wall

That counter on the right is not artistic license. With 16 zones and 3 packages, accounting for which package is where and whether the robot is carrying one of them, the reachable state space is on the order of a million configurations. The search tree the planner has to explore — branching at roughly 18 actions per state, plan length 12+ — is many orders of magnitude larger.

Classical planning is known to be PSPACE-complete. In practical terms: the algorithm doesn't care whether you used a smart heuristic or a domain expert hand-tuned the search order. The worst-case scaling is exponential in the size of the problem description. Tiny instances solve in milliseconds. Modestly larger instances take seconds. Realistic instances time out. (To be fair to the planners: a good one still cracks this particular 16-zone instance — the point of the animation is the curve it sits on. Every zone and package you add multiplies the space, and a few more doublings put you past any time budget.)

This is not a quirk. It's the central reason classical planning, despite being a beautifully principled framework, struggles to deliver on tasks people actually want — household robotics, multi-step manipulation, logistics at scale.

What if we could just learn what to do?

Here is the seductive premise of learning for planning: the small instances are easy. A classical planner can solve them — millions of them, if we want. So collect those solutions. Train a model on them. Then deploy the model on the large instances the planner can't touch.

If it works, we get the best of both worlds: soundness from the planner that generated the data, and scalability from the neural network that learned from it.

The premise has been pursued for years. It mostly hasn't worked. The standard recipe — train a value function on solved instances, then use it to guide search at test time — generalizes poorly when the test instances are bigger than the training instances. Values learned for "small warehouses" don't carry over to "large warehouses" in any useful way, because the input representation itself depends on the size of the problem. A 1000-zone warehouse needs a different network than a 4-zone one. There is no obvious way to share weights.

The rest of this series surveys what has been tried, what has worked, and what still hasn't. To structure the survey, two design axes show up in every paper:

The two axes that organize the field

Every neural method for classical planning has to make two distinct choices. The literature is best understood as a 2×3 grid spanned by these two axes, and each cell has been explored.

• Axis 1 — What to learn (the prediction target). Three families exist: learn a heuristic for search guidance (ASNets, STRIPS-HGN, GOOSE); learn a value function for greedy policies (GPL); or learn a ranking — either over states (RankSVM, GBFS-rank) or directly over actions (GRAPL, GABAR). Each family makes a different bet about what a neural network can usefully predict and inherits a different failure mode at scale.
• Axis 2 — How to represent the input (the encoding). Graph neural networks are the dominant choice because they handle variable-sized inputs naturally. But within "GNN," the design space is wide: lifted graphs vs grounded, action-as-node vs action-implicit, hypergraph vs ordinary graph, with vs without a global aggregation node. The encoding choice determines whether a single trained network can read instances of vastly different sizes.

The two axes are orthogonal. A paper makes one choice on each. GPL is GNN+value-function. ASNets is alternating-layers+heuristic. STRIPS-HGN is hypergraph+heuristic. GRAPL is GNN+action-ranking with independent parameter decoding. GABAR is GNN+action-ranking with sequential parameter decoding. Same axes, different cells.

The rest of the series follows this structure:

• Part 2 takes the first axis seriously and surveys the three learning-objective families with the papers that defined each.
• Part 3 takes the second axis seriously and surveys the graph-representation choices, with concrete contrasts between encodings.
• Part 4 reads GABAR — one specific cell in the design space — with a full understanding of why each choice was the right one given the literature.
• The epilogue closes the series and bridges to the partially-observable cousin.

The payoff at Part 4: GABAR trains on instances with 6-10 objects — the scale of the small warehouse on the left — and solves instances with 100+ objects, 8× larger than anything it saw during training, without retraining. The path to that result runs through both axes.

For now, the only thing to internalize is the visualization above. The left card is what classical planning is good at. The right card is what classical planning will never be good at. Everything that follows is about closing that gap.