# Symmetries and Expressive Requirements for Learning General Policies

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 50 references that are in the map.
- First posted on arXiv 24 Sep 2024.

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

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [The Logic of Graph Neural Networks](https://mlsanity.com/paper/2104.14624/) (2021)
- [ASNets: Deep Learning for Generalised Planning](https://mlsanity.com/paper/1908.01362/) (2019)
- [Learning General Optimal Policies with Graph Neural Networks: Expressive Power, Transparency, and Limits](https://mlsanity.com/paper/2109.10129/) (2021)
- [Learning Features and Abstract Actions for Computing Generalized Plans](https://mlsanity.com/paper/1811.07231/) (2018)
- [Generalized Planning With Deep Reinforcement Learning](https://mlsanity.com/paper/2005.02305/) (2020)
- [Features, Projections, and Representation Change for Generalized Planning](https://mlsanity.com/paper/1801.10055/) (2018)
- [Learning Generalized Policies Without Supervision Using GNNs](https://mlsanity.com/paper/2205.06002/) (2022)
- [Transfer of Deep Reactive Policies for MDP Planning](https://mlsanity.com/paper/1810.11488/) (2018)
- [PG3: Policy-Guided Planning for Generalized Policy Generation](https://mlsanity.com/paper/2204.10420/) (2022)
- [Learning More Expressive General Policies for Classical Planning Domains](https://mlsanity.com/paper/2403.11734/) (2024)
- [Hierarchical Decomposition and Analysis for Generalized Planning](https://mlsanity.com/paper/2212.02823/) (2022)

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

- [First-Order Representation Languages for Goal-Conditioned RL](https://mlsanity.com/paper/2512.19355/) (2025)
- [Sketch Decompositions for Classical Planning via Deep Reinforcement Learning](https://mlsanity.com/paper/2412.08574/) (2024)
- [Learning Efficiency Meets Symmetry Breaking](https://mlsanity.com/paper/2504.19738/) (2025)
- [Weisfeiler-Leman Features for Planning: A 1,000,000 Sample Size Hyperparameter Study](https://mlsanity.com/paper/2508.18515/) (2025)
- [Revisiting Landmarks: Learning from Previous Plans to Generalize over Problem Instances](https://mlsanity.com/paper/2508.21564/) (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)

State symmetries play an important role in planning and generalized planning. In the first case, state symmetries can be used to reduce the size of the search; in the second, to reduce the size of the training set. In the case of general planning, however, it is also critical to distinguish non-symmetric states, i.e., states that represent non-isomorphic relational structures. However, while the language of first-order logic distinguishes non-symmetric states, the languages and architectures used to represent and learn general policies do not. In particular, recent approaches for learning general policies use state features derived from description logics or learned via graph neural networks (GNNs) that are known to be limited by the expressive power of C_2, first-order logic with two variables and counting. In this work, we address the problem of detecting symmetries in planning and generalized planning and use the results to assess the expressive requirements for learning general policies over various planning domains. For this, we map planning states to plain graphs, run off-the-shelf algorithms to determine whether two states are isomorphic with respect to the goal, and run coloring algorithms to determine if C_2 features computed logically or via GNNs distinguish non-isomorphic states. Symmetry detection results in more effective learning, while the failure to detect non-symmetries prevents general policies from being learned at all in certain domains.