mlsanityData to 14 Oct 2026

What Planning Problems Can A Relational Neural Network Solve?

arXiv 2312.03682 ↗First posted 6 Dec 2023cs.LG cs.AI cs.NEcited by 8

Not on the map. Why?

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.

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

14 of 34 references.

References · 14

  1. 2017Attention Is All You Needcited by 60,361
  2. 2018How Powerful are Graph Neural Networks?cited by 4,393
  3. 2022Code as Policies: Language Model Programs for Embodied Controlcited by 1,210
  4. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 881
  5. 2020How Neural Networks Extrapolate: From Feedforward to Graph Neural Networkscited by 222
  6. 2023Grounding Large Language Models in Interactive Environments with Online Reinforcement Learningcited by 195
  7. 2019What Can Neural Networks Reason About?cited by 159
  8. 2019Neural Logic Machinescited by 145
  9. 2020Expressive Power of Invariant and Equivariant Graph Neural Networkscited by 100
  10. 2019Towards Practical Multi-Object Manipulation using Relational Reinforcement Learningcited by 55
  11. 2019Neural Logic Reinforcement Learningcited by 53
  12. 2022SizeShiftReg: a Regularization Method for Improving Size-Generalization in Graph Neural Networkscited by 37
2 more
  1. 2022Learning Sketches for Decomposing Planning Problems into Subproblems of Bounded Width: Extended Versioncited by 12
  2. 2023On the Expressiveness and Generalization of Hypergraph Neural Networkscited by 5

Built on by

Cited by year

Citing papers per year: 2024: 6; 2025: 2.

8 papers.

  1. 2024Can Graph Learning Improve Planning in LLM-based Agents?cited by 43
  2. 2024Return to Tradition: Learning Reliable Heuristics with Classical Machine Learningcited by 19
  3. 2024Structural Generalization in Autonomous Cyber Incident Response with Message-Passing Neural Networks and Reinforcement Learningcited by 7
  4. 2024Graph Learning for Numeric Planningcited by 5
  5. 2025SLAP: Shortcut Learning for Abstract Planningcited by 3
  6. 2024WLPlan: Relational Features for Symbolic Planningcited by 1
  7. 2024Graph Learning for Planning: The Story Thus Far and Open Challengescited by 0
  8. 2025Make Planning Research Rigorous Again!cited by 0