# Scaling Multi-Agent Epistemic Planning through GNN-Derived Heuristics

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 68 references that are in the map.
- First posted on arXiv 18 Aug 2025.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [Strategies for Pre-training Graph Neural Networks](https://mlsanity.com/paper/1905.12265/) (2019)
- [Deep Reinforcement Learning at the Edge of the Statistical Precipice](https://mlsanity.com/paper/2108.13264/) (2021)
- [LLMs Can't Plan, But Can Help Planning in LLM-Modulo Frameworks](https://mlsanity.com/paper/2402.01817/) (2024)
- [On the Prospects of Incorporating Large Language Models (LLMs) in Automated Planning and Scheduling (APS)](https://mlsanity.com/paper/2401.02500/) (2024)
- [Planning with Learned Object Importance in Large Problem Instances using Graph Neural Networks](https://mlsanity.com/paper/2009.05613/) (2020)
- [LLMs as Planning Formalizers: A Survey for Leveraging Large Language Models to Construct Automated Planning Models](https://mlsanity.com/paper/2503.18971/) (2025)
- [Return to Tradition: Learning Reliable Heuristics with Classical Machine Learning](https://mlsanity.com/paper/2403.16508/) (2024)
- [Classical Planning with LLM-Generated Heuristics: Challenging the State of the Art with Python Code](https://mlsanity.com/paper/2503.18809/) (2025)
- [Planning in the Dark: LLM-Symbolic Planning Pipeline without Experts](https://mlsanity.com/paper/2409.15915/) (2024)
- [A General Multi-agent Epistemic Planner Based on Higher-order Belief Change](https://mlsanity.com/paper/1806.11298/) (2018)
- [Cooperative Epistemic Multi-Agent Planning for Implicit Coordination](https://mlsanity.com/paper/1703.02196/) (2017)
- [Fast Task Planning with Neuro-Symbolic Relaxation](https://mlsanity.com/paper/2507.15975/) (2025)
- [A Semantic Approach to Decidability in Epistemic Planning (Extended Version)](https://mlsanity.com/paper/2307.15485/) (2023)

## Abstract (arXiv)

Multi-agent Epistemic Planning (MEP) is an autonomous planning framework for reasoning about both the physical world and the beliefs of agents, with applications in domains where information flow and awareness among agents are critical. The richness of MEP requires states to be represented as Kripke structures, i.e., directed labeled graphs. This representation limits the applicability of existing heuristics, hindering the scalability of epistemic solvers, which must explore an exponential search space without guidance, resulting often in intractability. To address this, we exploit Graph Neural Networks (GNNs) to learn patterns and relational structures within epistemic states, to guide the planning process. GNNs, which naturally capture the graph-like nature of Kripke models, allow us to derive meaningful estimates of state quality -- e.g., the distance from the nearest goal -- by generalizing knowledge obtained from previously solved planning instances. We integrate these predictive heuristics into an epistemic planning pipeline and evaluate them against standard baselines, showing improvements in the scalability of multi-agent epistemic planning.