TLDR: This research introduces a novel method to improve the scalability of Multi-Agent Epistemic Planning (MEP) by using Graph Neural Networks (GNNs) to learn effective heuristics. By training GNNs on Kripke structures (representing epistemic states), the system can estimate the distance to a goal, guiding search algorithms like A*. This data-driven approach significantly reduces the number of explored states, demonstrating improved scalability and generalization across various planning domains.
Multi-Agent Epistemic Planning (MEP) is a complex area of artificial intelligence that deals with how multiple intelligent agents can plan actions while also considering what they know and believe about the world and each other. This is crucial in scenarios where information sharing and awareness among agents are vital. However, the richness of MEP makes it computationally challenging, as the “states” of the system, which include both the physical world and agents’ beliefs, are represented as intricate Kripke structures—essentially, directed labeled graphs. This complex representation often limits the applicability of existing heuristics, hindering the scalability of epistemic solvers and leading to a vast search space that is hard to navigate efficiently.
A new research paper, “Scaling Multi-Agent Epistemic Planning through GNN-Derived Heuristics,” addresses this scalability challenge by introducing a novel approach that leverages Graph Neural Networks (GNNs). GNNs are a type of machine learning model particularly well-suited for processing graph-structured data, making them a natural fit for analyzing Kripke structures. The core idea is to use GNNs to learn patterns and relationships within these epistemic states, allowing the system to estimate the “quality” of a state—for example, how close it is to a desired goal. This learned estimation acts as a heuristic, a guiding function that helps the planning process.
Traditionally, planning heuristics are either manually designed or derived from structural features of the search space. This new work takes a data-driven approach, using machine learning to approximate what is known as the “perfect heuristic”—a function that would tell you the exact shortest distance from any given state to a goal state. By training GNNs on previously solved planning instances, the system can generalize this knowledge to new, unseen problems, providing valuable guidance to search algorithms like A*.
The researchers developed a fully automated pipeline for generating the necessary training data. This involves exploring the reachable state space of MEP problems using a depth-limited Depth-First Search (DFS) and then backtracking from goal states to assign distances to other states. To make this process efficient despite the combinatorial explosion of possible states, they incorporated techniques like branch discard probability, randomized action ordering, and limits on explored nodes. This allows for the creation of informative datasets in a manageable timeframe.
The trained GNN-based regressor is then integrated into an epistemic planning pipeline, specifically within a new implementation called ‘deep’, which is a modernized version of the state-of-the-art EFP planner. This integration allows the GNN to evaluate epistemic states by assigning heuristic scores, which in turn guide the A* search algorithm. The experimental results demonstrate significant improvements in scalability. For instance, the GNN-based approach (GNN) showed an average reduction of 48% in the number of explored nodes compared to an uninformed Breadth-First Search (BFS) on test sets, with improvements reaching up to 91% in some domains.
Also Read:
- Landmarks Enhance Monte Carlo Planning for Uncertain Environments
- Navigating Complexity: How AI Language Models Are Enhancing Classical Planning
The paper also highlights the GNN’s ability to generalize to domains it has not seen during training, further underscoring its robustness. While the current implementation does not use batch computation during planning, which affects real-time performance, the authors note that this is a straightforward addition for future work. This research represents a foundational step towards bridging machine learning and multi-agent epistemic planning, offering a promising direction for developing more scalable and adaptable planning systems in complex multi-agent environments. You can read the full paper here.
