Your Planning State Is a Graph

Why fixed-size vectors can't represent a planning problem, and what to do instead.

Part 2 ended with a claim: if you score actions instead of states, you can sidestep the "states have different sizes in different problems" issue — as long as your network can read variable-size inputs.

This post is about the input. The whole trick of GABAR — and a recent wave of papers in learning-for-planning — is that a planning state is naturally a graph, and graph neural networks naturally process variable-size graphs with the same weights. The hard work is making the conversion principled, so that a 4-zone warehouse and a 4000-zone warehouse become graphs the same network can read.

Why a vector won't do

The temptation is always to flatten things. The state of a warehouse with k zones and m packages is "just" the position of the robot, the positions of all packages, and which (if any) the robot is holding. That's a vector of length m+2 if you allow integer-valued zone IDs.

Two problems with this. First, the length of the vector depends on m — the network trained on 1-package warehouses cannot read a 3-package warehouse's input. Second, even if you padded to a fixed maximum, the network has to learn that "the integer 3 in position 5" means "package 5 is in zone 3" — an entirely arbitrary indexing convention. There is nothing about the integers per se that tells the network zones C and D are physically adjacent.

The graph view fixes both. A planning state is relational: it's a set of objects with properties and binary relationships among them. That structure transfers across instance sizes intact — only the cardinality of the object set changes.

Building the graph, one piece at a time

The construction below is the one used in GABAR (the next post's subject). Each stage adds one type of node or edge. But first — here is the task itself. Press Watch Task to see the robot carry out the delivery; then, below, watch that same state turn into its graph form.

What you just saw, conceptually

The graph has four kinds of nodes, by design:

• Objects — the things in the problem (robot, packages, zones).
• Predicates — the facts that hold right now, each connected to the objects it concerns.
• Goal predicates — the facts that should hold at the end, drawn separately.
• Action schemas — ungrounded actions (move, pickup, drop), each connected to the objects that fit their parameter types.

Crucially, the structure of this graph is determined by the PDDL domain, not by the instance. A 4-zone warehouse and a 4000-zone warehouse have the same node types, the same edge types, the same action schemas. The graphs differ only in size — the 4000-zone version has more Zone object nodes, more At predicates, more Move schemas grounded over more parameters.

A graph neural network processes this. Briefly: each node has a learned embedding, and on each "round" of message passing, every node updates its embedding by aggregating its neighbors'. After a few rounds, the action-schema nodes have absorbed enough context to rank themselves — which action looks most useful in this state? That ranking is the policy.

The number of rounds is fixed; the depth of the network is fixed. What scales with the problem is the width of each round — how many nodes get updated — which is handled by the graph framework, not by adding parameters to the model. The same weights work on any size warehouse.

The animation above shows GABAR's specific graph encoding, but it's only one of many possible constructions. The rest of this post is a survey of the choices the field has explored, organized along three concrete sub-decisions every graph-based L4P method has to make.

Sub-decision 1: lifted vs grounded

The first design choice is how much instantiation to put into the graph. There are two extremes.

A lifted graph encodes objects and the relations among them, but not the full set of instantiated atoms. For a warehouse with 50 packages and 100 zones, the lifted graph has nodes for each object (the robot, each package, each zone) and edges encoding their relationships, but does not have a separate node for every ground atom like at(robot, zone-37). The action schemas appear as well, but ungrounded — the schema for move, not all the move(?from, ?to) instantiations.

A grounded graph instantiates the propositional structure: every ground atom that holds in the current state (or could hold) gets its own node. Every ground action (every instantiation of every schema) also gets its own node. The graph is much larger — for the same warehouse it might have thousands of ground-atom nodes and hundreds of ground-action nodes — but the structure is much closer to what the planner actually reasons about.

The lifted-vs-grounded debate has been open for years. Lifted graphs are smaller and faster to construct; grounded graphs are more expressive. Chen, Thiébaux, Trevizan 2024 in GOOSE tested both head-to-head and found grounded graphs outperform lifted ones on benchmark IPC domains when paired with standard message-passing networks. The follow-up survey by Chen, Hao, Thiébaux, Trevizan 2024 formalizes this: grounded encodings are strictly more expressive in a precise sense, though they incur higher per-instance computational cost.

The expressivity result connects to a deeper limitation. Barceló, Kostylev, Monet, Pérez, Reutter, Silva 2020 proved that standard message-passing GNNs are expressively bounded by the C₂ fragment of first-order logic (graded modal logic). This means there are planning problems where the relationships needed to pick the right action cannot be expressed by vanilla GNNs over a lifted graph; the message-passing limit is the bottleneck, not the data. Going grounded gives the graph richer structure that partially side-steps this. Going beyond GNNs to architectures with more expressive aggregations is the other escape route (Ståhlberg, Bonet, Geffner 2024).

GABAR sits at the grounded end of this spectrum, with one notable variant: it grounds predicates (instantiated atoms get nodes) but keeps action schemas ungrounded. The action schema nodes connect to the objects that could serve as parameters, with edge features encoding which parameter slot. This hybrid keeps the action-side graph small while the predicate-side gets the expressivity benefit of grounding.

Sub-decision 2: how to represent actions

The single most consequential design choice in the field — and the central technical contribution of GABAR — is whether actions appear in the graph at all, and if so, how.

Three patterns exist in the literature:

Pattern 1: actions are implicit (no action nodes)

Most graph-based L4P methods represent only objects and predicates as nodes. The model must infer action-relevant information from the predicate and object nodes, essentially reverse-engineering each action schema's preconditions from the current state. Ståhlberg, Bonet, Geffner 2022a (GPL) and Karia, Srivastava 2021 (GRAPL, in its base form) both fall here.

The cost: the network has to learn the preconditions implicitly, which requires more training data and more model capacity. For domains with many action schemas (Logistics, IPC composite domains), the implicit approach scales poorly because each schema's precondition pattern needs to be re-discovered.

Pattern 2: actions woven in via alternating layers

ASNets (Toyer, Thiébaux, Trevizan, Xie 2020) takes a structurally distinct approach: alternate action layers and proposition layers, with weight sharing across all groundings of the same schema. An action layer has one unit per ground action; a proposition layer has one unit per ground atom. Each action unit attends to its precondition propositions; each proposition unit attends to the actions that affect it. After several alternations, action units have absorbed information from a fixed-depth neighborhood.

This is more inductive-bias-rich than the implicit pattern — actions are first-class — but the fixed alternation depth caps the network's receptive field. Long-horizon dependencies (effects rippling through many propositions) exceed what a small stack can model. ASNets does well on local domains but struggles on long-chain reasoning.

Pattern 3: actions as graph nodes (explicit)

GABAR represents action schemas as first-class nodes in the graph, connected by edges to the objects that could serve as their parameters. The edges encode both the parameter position (which role the object plays) and the predicate satisfaction (which of the object's properties make the action applicable).

The advantage: the model directly reads the relationships between actions and the objects they manipulate, rather than inferring them. This is particularly powerful when paired with the action-ranking objective from Part 2 — the action schema nodes' final embeddings serve as the scoring vectors for each candidate action.

The cost: more nodes per graph, more edges, larger memory footprint. In practice this is dominated by the gain in learning efficiency.

Pattern 4: hypergraphs

STRIPS-HGN (Shen, Trevizan, Thiébaux 2020) is a separate point in this space: actions are hyperedges connecting multiple proposition nodes (one per precondition or effect), and message passing operates over the hypergraph. This naturally captures the multi-precondition structure of STRIPS actions without the alternation depth limit of ASNets.

Hypergraph networks are more expressive than ordinary GNNs for certain planning patterns, but the architectural machinery is heavier and less well-supported by standard tooling. STRIPS-HGN's empirical results are strong on small instances but it has not scaled to the largest IPC problem sizes that grounded GNN approaches like GOOSE have hit.

Sub-decision 3: how to construct grounded actions from the graph

Even once action information is in the graph, there is a remaining question: how does the model produce a fully grounded action — schema plus all its parameters — at execution time? The output is structured: an action like transport(package-7, vehicle-3, city-2) has multiple slots that must be filled coherently.

Two approaches exist.

Independent parameter selection

GRAPL (Karia, Srivastava 2021) decomposes a multi-parameter action into independent decisions: "pick the best package," "pick the best source zone," "pick the best destination" — three separate scorings whose results are concatenated to form the grounded action. Each parameter is selected without conditioning on the others.

This is computationally simple but loses parameter dependencies. In the warehouse, the correct source zone for a transport action depends on which package was selected (it has to be the zone that package is actually in). Under independent decoding, the model has no way to express this: the package and source-zone decisions happen in parallel and can be inconsistent.

Sequential conditional decoding

GABAR's GRU-based decoder fixes this. The decoder picks the action schema first, then iterates over parameter positions, conditioning each choice on what came before. After picking the package, the GRU state encodes "given this package," and the next parameter choice respects that condition. The output is a fully grounded action where the parameters are mutually consistent.

This is the GABAR-specific contribution that ranking methods before it lacked. Without it, the action-ranking framing from Part 2 stops working on domains with parameter coupling — exactly the kinds of domains where size generalization matters most.

Representations at a glance

Looking down the columns: GABAR's cell is a genuinely new combination. No prior method combined explicit action-schema nodes with sequential conditional decoding. ASNets has actions explicit (via alternation) but does not condition parameter selection. GRAPL is closer in spirit (also action-ranking) but uses canonical abstraction with independent decoding. STRIPS-HGN has actions explicit (via hyperedges) but is a heuristic, not a policy.

The grid is sparse for reasons beyond just "no one had time": each cell requires a specific combination of architectural choices that don't fall out of any single design philosophy. GABAR's cell only makes sense once you've committed to (i) action ranking as the objective (Part 2's Family 3), (ii) action-centric graphs as the encoding (this post), and (iii) sequential decoding as the way to handle parameter coupling. Three choices, all justified by specific limitations of prior work.

Beyond GNNs: transformers and other alternatives

One more thread worth flagging: not everyone uses GNNs. Müller, Sánchez, Hoffmann, Wolf, Gros 2024 recently benchmarked standard off-the-shelf GNNs against transformers for general policy learning, finding the trade-offs subtle: transformers handle larger context well but lose the size-generalization properties GNNs get from message passing's permutation invariance. The field has not converged on a winner.

For now, GNNs remain the dominant choice for L4P because the relational structure of planning problems is exactly what they were designed for. Transformers may eventually catch up, particularly as architectures evolve to incorporate relational inductive biases, but as of 2025 the strongest L4P systems all use GNNs.

References