🤖 AI

Scaling Multi-Agent Epistemic Planning through GNN-Derived Heuristics

This paper proposes a scalable multi-agent epistemic planning framework that integrates Graph Neural Network-derived heuristics to effectively guide search through complex Kripke structures, significantly improving solver performance over existing baselines.

Original authors: Giovanni Briglia, Francesco Fabiano, Stefano Mariani

Published 2026-02-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Giovanni Briglia, Francesco Fabiano, Stefano Mariani

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a massive, multi-layered puzzle. But here's the twist: you aren't just moving pieces on a board; you are also trying to figure out what other people in the room think about the pieces, what they think you think, and what they think you think they think.

This is the world of Multi-Agent Epistemic Planning (MEP). It's a type of computer planning used when groups of intelligent agents (like robots or software bots) need to coordinate, but they have to do it while managing their own beliefs and what they know about each other's minds.

The problem? This mental juggling act creates a "search space" so huge and complex that computers get overwhelmed. It's like trying to find a single specific grain of sand on every beach on Earth, one by one, without any map.

The Solution: A "Smart GPS" for Beliefs

The authors of this paper, Giovanni Briglia, Francesco Fabiano, and Stefano Mariani, propose a new way to help computers navigate this chaos. They built a system that uses Graph Neural Networks (GNNs) to act like a "Smart GPS" for these complex belief puzzles.

Here is how they did it, broken down into simple steps:

1. The Map is a Web, Not a List

In traditional planning, the computer sees the world as a list of facts. But in this "epistemic" world, the state of the system is better described as a web of connections (called a Kripke structure). Imagine a spiderweb where every knot is a possible reality, and the threads connecting them represent what different agents believe about each other.

The Challenge: Standard computer tools are bad at reading these webs. They try to count every single knot, which takes forever.
The Fix: The authors used GNNs. Think of a GNN as a special kind of camera that looks at the whole web at once. Instead of counting knots, it "feels" the shape and structure of the web to understand how close it is to the solution.

2. Learning from Experience (The Training Phase)

Before the computer can solve new puzzles, it needs to learn what a "good" path looks like.

The Method: The researchers created a "training gym." They let their planning software run through thousands of practice puzzles.
The Lesson: As the software explored, it recorded every step it took and how far that step was from the finish line.
The Result: They fed this data into the GNN. The GNN learned to look at a complex web of beliefs and instantly guess: "This looks like we are 5 steps away from the goal," or "This looks like a dead end."

3. The "Heuristic" (The Intuition)

In computer science, a "heuristic" is a rule of thumb or a gut feeling that helps you make decisions faster.

Old Way: The computer would blindly explore every possible path until it got lucky (like a blindfolded person feeling every wall in a maze).
New Way: The GNN acts as a guide. Before the computer takes a step, it asks the GNN, "Is this direction promising?" The GNN gives a score. If the score is high, the computer dives in. If it's low, it skips that path. This saves the computer from wasting time on dead ends.

What They Found (The Results)

The team tested their new "Smart GPS" (which they named deep) against the old, blind methods on several standard puzzle domains:

Assembly Line: Robots building things together.
Collaboration: Agents moving boxes and talking to each other.
Grapevine: Agents sharing secrets in different rooms.

The Outcome:

Fewer Steps: The GNN-guided planner had to look at far fewer possibilities to find the solution. In some cases, it explored 10 to 20 times fewer "rooms" in the maze than the blind method.
Better at the Hard Stuff: While it wasn't perfect at every single puzzle (some were just too tricky), it consistently outperformed the old methods in finding solutions faster and more efficiently.
Generalization: Even when they trained the GNN on one type of puzzle and tested it on a completely different type, it still worked well, showing it learned the logic of the web, not just the specific answers.

The Catch (Limitations)

The authors are honest about the current limits:

Speed: While the GNN helps the computer think smarter, the GNN itself takes a little time to run. Currently, the "thinking" part is slower than the "searching" part. It's like having a brilliant navigator who gives great directions, but who takes a long time to speak.
Engineering: The authors note that if they could make the GNN run faster (using better computer hardware tricks), the whole system would be even more powerful.

The Bottom Line

This paper doesn't claim to have solved all AI problems. Instead, it proves that teaching computers to "see" the structure of beliefs using Graph Neural Networks is a powerful way to make complex multi-agent planning scalable. It turns a blind, exhausting search into a guided, intelligent journey.

Technical Summary: Scaling Multi-Agent Epistemic Planning through GNN-Derived Heuristics

Problem Statement

Multi-Agent Epistemic Planning (MEP) is a framework for reasoning about physical actions and the beliefs of multiple agents. Unlike classical planning, MEP requires states to be represented as Kripke structures (pointed, directed labeled graphs) to capture complex belief relationships and higher-order knowledge. This representation introduces two primary challenges that hinder scalability:

Intrinsic Complexity: Applying transitions and evaluating formulas within epistemic states (e-states) is computationally more demanding than in classical planning.
Lack of Effective Heuristics: Existing MEP solvers often rely on uninformed search (e.g., Breadth-First Search) because effective heuristics are scarce. As plan length increases, the search space grows exponentially, leading to intractability. While some recent work (e.g., H-EFP) has attempted to integrate heuristics using traditional planning constructs like planning graphs, few approaches address the scalability of MEP through data-driven methods.

Methodology

The authors propose a data-driven approach to generate heuristics for MEP using Graph Neural Networks (GNNs). The core idea is to train a GNN-based regressor to approximate the "perfect heuristic"—estimating the distance from any given epistemic state to the nearest goal state.

1. State Representation and Embedding

Since e-states are naturally graph-structured (Kripke models), GNNs are selected for their ability to capture relational structures. The paper investigates three strategies for encoding the "worlds" (nodes) within a Kripke structure into numerical vectors suitable for GNN input:

Symbolic ID Mapping: Assigns sequential integers to worlds based on generation order. This is computationally cheap but loses semantic similarity between worlds and is non-invariant across runs.
Hash-based Encoding: Applies a hash function to world interpretations and repetition indices. This ensures consistent identifiers across runs and offers a balance between information preservation and computational efficiency.
Bitmask Encoding: Represents worlds as binary vectors encoding fluents and repetition indices. This preserves logical information but incurs higher computational costs and requires larger models to converge.

To ensure the heuristics generalize across different goal conditions, the authors extend the state embedding to include a compact encoding of the goal. This creates a unified graph where "state nodes" and "goal nodes" are connected, allowing the model to learn dependencies between the current state and specific goal conditions.

2. Data Generation Pipeline

Training data is generated offline using a modified Depth-First Search (DFS) within the deep planner (a re-implementation of the state-of-the-art EFP planner).

The planner explores the state space up to a depth limit.
Upon reaching a goal, the algorithm backtracks, assigning each visited e-state a label corresponding to its distance to the nearest goal.
To manage the combinatorial explosion of the search space, the generation process employs probabilistic branch pruning, randomized action ordering, and duplicate state checks.
Unreachable states are discarded to prevent spurious labels, and the distribution of distance classes is balanced to avoid bias toward short plans.

3. Model Architecture

The neural regressor is implemented in PyTorch using PyTorch Geometric. The architecture consists of:

Bitwise Embedding: Node identifiers (bit-vectors) and edge attributes are projected into dense embeddings via Multi-Layer Perceptrons (MLPs).
Relational Message Passing: Two layers of GINEConv (Graph Isomorphism Network with Edge Convolution) aggregate information from neighbors, explicitly incorporating edge attributes to handle heterogeneous modal dependencies.
Graph-Level Summarization: Mean pooling aggregates node embeddings into a fixed-size graph representation.
Deep Residual Regression Head: A sequence of residual blocks processes the graph embedding, outputting a normalized distance estimate via a sigmoid function.

4. Search Integration

The trained GNN is integrated into the planning pipeline to guide a Heuristics-First Search (HFS). The authors also evaluate a variant, HFS*, which augments the predicted heuristic $h(s)$ with the search depth $d(s)$ to form a total score $f(s) = h(s) + d(s)$ , inspired by the A* algorithm.

Key Contributions

The paper outlines four primary contributions:

Embedding Comparison: A formal definition and empirical comparison of three Kripke structure embeddings (Symbolic ID, Hash, Bitmask) for GNN input, identifying hash-based encoding as the most effective trade-off.
Automated Pipeline: A fully automated system for generating training data (state-distance pairs) and training the GNN regressor specifically for the MEP setting.
Integration: The integration of the GNN regressor into the deep planner to evaluate e-states and guide the search process.
Comprehensive Evaluation: A thorough benchmarking of the approach against uninformed search (BFS) and existing heuristic-based planners (H-EFP) across multiple standard domains.

Experimental Results

The evaluation was conducted on standard MEP benchmarks (e.g., Collaboration and Communication, Selective Communication, Grapevine) using a 600-second timeout.

Scalability vs. Uninformed Search: The GNN-guided search significantly reduced the number of expanded nodes compared to Breadth-First Search (BFS) in most domains. For instance, in the Collaboration and Communication (CC) domain, the GNN approach expanded roughly 65 nodes on average compared to 610 for BFS, while solving the same number of instances.
Search Strategy: The HFS* variant (combining heuristic and depth) outperformed standard HFS, solving approximately 32% more instances and reducing the number of expanded nodes.
Generalization: Models trained on data pooled from multiple domains (CC and GR) demonstrated the ability to generalize to unseen domains, outperforming the BFS baseline in terms of node expansion.
Comparison with H-EFP: The GNN approach performed on par with the best individual heuristics in the H-EFP planner (specifically the $S\_PG$ heuristic), solving 85.33% of test instances compared to H-EFP's range of 49–82% depending on the specific heuristic used.
Runtime Limitations: The paper notes that while GNN reduces the search space (nodes expanded), the current implementation lacks batch inference optimizations (e.g., CUDA batching). Consequently, raw solving times are not yet competitive with traditional heuristics, though the authors argue that heuristic informativeness is the primary metric for scalability in this context.

Significance and Claims

The authors position this work as a foundational step in integrating Machine Learning with Multi-Agent Epistemic Planning. They claim that:

Heuristic Scarcity: MEP suffers from a lack of effective heuristics compared to classical planning. This work demonstrates that GNNs can successfully learn to approximate perfect heuristics in this complex, graph-based setting.
Data-Driven Efficiency: By treating each e-state as an independent training signal rather than relying on full trajectories, the approach generates large datasets efficiently, enabling the learning of meaningful patterns from the relational structure of Kripke models.
Complementarity: The authors do not claim GNNs will immediately replace existing heuristics. Instead, they argue that GNN-based heuristics serve as a powerful complementary tool to enhance solver coverage, particularly when integrated into portfolio-based approaches where different heuristics can compensate for one another's weaknesses.

The paper concludes that while engineering optimizations (such as batch processing) are required to make runtime performance competitive, the reduction in search space complexity proves the viability of learning-based heuristics for scaling MEP.