# What Planning Problems Can A Relational Neural Network Solve?

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 34 references that are in the map.
- First posted on arXiv 6 Dec 2023.

## Builds on (most cited first, 14 of 14)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Code as Policies: Language Model Programs for Embodied Control](https://mlsanity.com/paper/2209.07753/) (2022)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks](https://mlsanity.com/paper/2009.11848/) (2020)
- [Grounding Large Language Models in Interactive Environments with Online Reinforcement Learning](https://mlsanity.com/paper/2302.02662/) (2023)
- [What Can Neural Networks Reason About?](https://mlsanity.com/paper/1905.13211/) (2019)
- [Neural Logic Machines](https://mlsanity.com/paper/1904.11694/) (2019)
- [Expressive Power of Invariant and Equivariant Graph Neural Networks](https://mlsanity.com/paper/2006.15646/) (2020)
- [Towards Practical Multi-Object Manipulation using Relational Reinforcement Learning](https://mlsanity.com/paper/1912.11032/) (2019)
- [Neural Logic Reinforcement Learning](https://mlsanity.com/paper/1904.10729/) (2019)
- [SizeShiftReg: a Regularization Method for Improving Size-Generalization in Graph Neural Networks](https://mlsanity.com/paper/2207.07888/) (2022)
- [Learning Sketches for Decomposing Planning Problems into Subproblems of Bounded Width: Extended Version](https://mlsanity.com/paper/2203.14852/) (2022)
- [On the Expressiveness and Generalization of Hypergraph Neural Networks](https://mlsanity.com/paper/2303.05490/) (2023)

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

- [Can Graph Learning Improve Planning in LLM-based Agents?](https://mlsanity.com/paper/2405.19119/) (2024)
- [Return to Tradition: Learning Reliable Heuristics with Classical Machine Learning](https://mlsanity.com/paper/2403.16508/) (2024)
- [Structural Generalization in Autonomous Cyber Incident Response with Message-Passing Neural Networks and Reinforcement Learning](https://mlsanity.com/paper/2407.05775/) (2024)
- [Graph Learning for Numeric Planning](https://mlsanity.com/paper/2410.24080/) (2024)
- [SLAP: Shortcut Learning for Abstract Planning](https://mlsanity.com/paper/2511.01107/) (2025)
- [WLPlan: Relational Features for Symbolic Planning](https://mlsanity.com/paper/2411.00577/) (2024)
- [Graph Learning for Planning: The Story Thus Far and Open Challenges](https://mlsanity.com/paper/2412.02136/) (2024)
- [Make Planning Research Rigorous Again!](https://mlsanity.com/paper/2505.21674/) (2025)

## Abstract (arXiv)

Goal-conditioned policies are generally understood to be "feed-forward" circuits, in the form of neural networks that map from the current state and the goal specification to the next action to take. However, under what circumstances such a policy can be learned and how efficient the policy will be are not well understood. In this paper, we present a circuit complexity analysis for relational neural networks (such as graph neural networks and transformers) representing policies for planning problems, by drawing connections with serialized goal regression search (S-GRS). We show that there are three general classes of planning problems, in terms of the growth of circuit width and depth as a function of the number of objects and planning horizon, providing constructive proofs. We also illustrate the utility of this analysis for designing neural networks for policy learning.