# Learning More Expressive General Policies for Classical Planning Domains

arXiv: https://arxiv.org/abs/2403.11734 · HTML: https://mlsanity.com/paper/2403.11734/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Mar 2024.

## Built on by (most cited first, 5 of 5)

- [Symmetries and Expressive Requirements for Learning General Policies](https://mlsanity.com/paper/2409.15892/) (2024)
- [Symmetry-Aware Transformer Training for Automated Planning](https://mlsanity.com/paper/2508.07743/) (2025)
- [Vejde: A Framework for Inductive Deep Reinforcement Learning Based on Factor Graph Color Refinement](https://mlsanity.com/paper/2509.09219/) (2025)
- [Efficient Lookahead Encoding and Abstracted Width for Learning General Policies in Classical Planning](https://mlsanity.com/paper/2605.18674/) (2026)
- [Learning to Search and Searching to Learn for Generalization in Planning](https://mlsanity.com/paper/2605.25720/) (2026)

## Abstract (arXiv)

GNN-based approaches for learning general policies across planning domains are limited by the expressive power of C2, namely; first-order logic with two variables and counting. This limitation can be overcame by transitioning to k-GNNs, for k=3, wherein object embeddings are substituted with triplet embeddings. Yet, while 3-GNNs have the expressive power of C3, unlike 1- and 2-GNNs that are confined to C2, they require quartic time for message exchange and cubic space to store embeddings, rendering them infeasible in practice. In this work, we introduce a parameterized version R-GNN[t] (with parameter t) of Relational GNNs. Unlike GNNs, that are designed to perform computation on graphs, Relational GNNs are designed to do computation on relational structures. When t=∞, R-GNN[t] approximates 3-GNNs over graphs, but using only quadratic space for embeddings. For lower values of t, such as t=1 and t=2, R-GNN[t] achieves a weaker approximation by exchanging fewer messages, yet interestingly, often yield the expressivity required in several planning domains. Furthermore, the new R-GNN[t] architecture is the original R-GNN architecture with a suitable transformation applied to the inputs only. Experimental results illustrate the clear performance gains of R-GNN[1] over the plain R-GNNs, and also over Edge Transformers that also approximate 3-GNNs.