Graph Neural Network Based Action Ranking for Planning

Traditional planners use search and heuristics. While they can find optimal solutions, they often struggle with scalability and become computationally expensive or too slow for large, complex problems.

Unlike standard Reinforcement Learning, which can require millions of examples, the relational structure of PDDL (Planning Domain Definition Language) allows Graph Neural Networks (GNNs) to learn generalizable policies from just thousands of examples generated from small, easily-solved problems.

The core idea is to train a model on small problem instances (e.g., 6-9 block problems) and then apply that learned policy to solve significantly larger instances (e.g., 40-block problems) where classical planners fail.

Many approaches try to learn a value function, V(s), that estimates the cost-to-goal from any state. This is extremely difficult because the function must be globally consistent, and since optimal planning is NP-hard, these value functions are hard to learn and often don't generalize well to larger problems.

Models like Action Schema Networks (ASNets) use a fixed-depth receptive field. This design limits their ability to reason about long-range dependencies between objects and actions, which is crucial in complex problems.

Previous GNN approaches (like GPL) focus on state representations but do not explicitly model how actions themselves relate to objects. This misses critical information about action applicability and relationships.

Instead of learning a complex, globally consistent value function V(s) for all states, GABAR learns a simpler, locally consistent function to just rank the applicable actions in the *current* state. This is a more tractable and generalizable learning problem.

Our novel graph representation includes 'action nodes' that are explicitly connected to the 'object nodes' they take as arguments. This directly encodes action applicability and relational structure into the GNN.

A Gated Recurrent Unit (GRU)-based decoder constructs the final action step-by-step. It first selects an action schema (e.g., 'stack') and then sequentially selects each parameter (e.g., 'blockA', then 'blockB'), conditioning each choice on the previous ones. This handles complex dependencies between parameters.

The graph consists of Object, Predicate, Action, and one Global node. Edges represent predicate-object and action-object relationships, encoding the state, goal, and all potential actions.

The GNN performs L rounds of message passing (we use 9) where nodes and edges update their embeddings. Attention mechanisms weight the importance of different messages, and the global node aggregates graph-level information for rapid propagation.

The final global embedding is fed into a GRU decoder. It first selects the highest-scoring action schema, then autoregressively selects each object parameter. We use a beam search (width k=2) to explore multiple high-scoring actions in parallel.

GABAR's coverage (success rate) drops minimally as problems get harder: 95.5% on Easy, 92.2% on Medium, and 89.2% on Hard. In contrast, baseline methods like GPL and GRAPL see their coverage collapse to 6.5% and 22.1% on hard problems, respectively.

In the Visitall domain, the model was trained on problems with 9-36 cells (up to 49 in validation). It successfully solved test problems with up to 400 cells, more than 8 times larger than the largest training instances, demonstrating powerful generalization.

On hard test instances, LLMs like OpenAI-O3 and Gemini-2.5-Pro solve almost no problems (0.4% and 1.5% coverage, respectively). GABAR's architecture, which explicitly learns structural relationships, maintains 89.2% coverage, highlighting the limitations of pure pattern matching for complex reasoning.

The tables below show that GABAR not only solves *more* problems (Coverage, C) but also finds solutions that are high quality (Plan Quality Ratio, P) and efficient (Plan Length, PL). Baselines that solve fewer problems often appear to have low plan lengths simply because they are only solving the easiest instances.

Our GABAR-ACT ablation removed the explicit action nodes from the graph. This caused a catastrophic performance drop, with coverage on hard problems falling from 89.2% to just 7.4%. This confirms that explicitly modeling action-object relationships is essential.

The GABAR-CD ablation selected all action parameters independently instead of sequentially. This failed to capture dependencies (e.g., in Logistics), and coverage on hard problems dropped from 89.2% to 60.0%.

The GABAR-RANK ablation used our graph but swapped the ranking objective for a traditional value-learning objective. Performance collapsed to just 12.1% on hard problems, proving that learning to rank is a more robust and generalizable strategy.

In our GABAR-G ablation (results in paper appendix), removing the global node (which aggregates graph-wide information) caused coverage on hard problems to drop from 89.2% to 42.5%. The global node is critical for rapid information propagation in large graphs.

We generate data by solving small problems (e.g., 6-9 blocks, 5-15 balls) with an optimal planner. The first action of the optimal plan is used as the training label. Training takes 1-2 hours per domain on an RTX 3080.

Node features are one-hot encodings for type (object, predicate, action) and specific schema/predicate. Edge features encode type (predicate-object, action-object) and argument/parameter position.

We use a hidden dimensionality of 64, 9 rounds of GNN message passing, and a batch size of 16. The decoder uses a beam width of 2. We use the Adam optimizer with a learning rate of 0.0005.

We generate between 3,348 (Blocks) and 6,880 (Grid) training examples (state-action pairs) per domain. All problems are generated using standard PDDL generators.

GABAR enables solving large, real-world-sized planning problems by executing a learned policy directly, bypassing the expensive search required by traditional planners.

Our results show that learning a simple, local action-ranking policy is a more tractable and scalable approach than the dominant paradigm of learning complex, global value functions.

This work demonstrates that combining the explicit relational structure of PDDL with the right GNN architecture can achieve sample efficiency and generalization that pure, data-hungry RL methods often cannot.