Abstract
Multi-agent reinforcement learning (MARL) faces significant challenges in coordination due to environmental non-stationarity and communication overhead. This paper proposes Connectivity-driven Communication (CDC), a framework that leverages spectral graph theory—specifically the Heat Kernel—to model information diffusion among agents. By treating agents as nodes in a dynamic graph, CDC enables agents to prioritize communication based on global topological importance rather than just local signal strength. Experimental results across various cooperative tasks demonstrate that CDC significantly outperforms existing baselines in success rate, efficiency, and scalability.
Introduction
In multi-agent systems, such as drone swarms or autonomous vehicle fleets, agents must coordinate to achieve shared objectives. However, coordination is hindered by the "non-stationary" nature of the environment: as individual agents learn and adapt, the environment effectively changes for all others. While communication is a standard remedy, it often suffers from a low signal-to-noise ratio. If every agent broadcasts all information, the system becomes saturated with irrelevant data. Existing attention-based methods attempt to filter this noise but often treat agents as isolated individuals rather than a structured network. This work argues that communication should be driven by the system's underlying topology—the dynamic graph of relationships between agents.
Methodology: Connectivity-driven Communication (CDC)
The core innovation of the CDC framework is the use of a diffusion process on a graph to weight communication dynamically. The architecture follows a Centralized-Learning, Decentralized-Execution (CLDE) paradigm.
1. Dynamic Graph Construction
At each time step, agents process private observations through a neural network to predict "connectivity weights" ($s_{i,j}$) between themselves and others. This results in a weighted, undirected graph representing the potential for communication.
2. The Heat Kernel (HK)
Instead of standard softmax attention, CDC employs the Heat Kernel: $H(p) = \exp[-p\hat{L}]$, where $\hat{L}$ is the normalized Laplacian of the graph. In physics, the heat kernel describes heat dissipation over time; here, it represents the flow of information through the agent network. By capturing global structural properties, such as "bridge" agents that connect disparate clusters, the Heat Kernel provides a more nuanced priority mechanism than local attention.
3. Topology-Dependent Attention
The stable values derived from this diffusion process serve as attention weights ($h_{i,j}$). An agent’s received message is a linear combination of neighbor messages weighted by these heat kernel values. This ensures that information flow respects the structural importance of each node in the current configuration.
Experimental Evaluation
The researchers evaluated CDC on four cooperative navigation environments using the Multi-Agent Particle Environment (MAPE):
- Navigation Control: Agents move to landmarks while avoiding collisions.
- Formation Control: Agents arrange into geometric shapes around a landmark.
- Line Control: Agents form a straight line between two landmarks.
- Dynamic Pack Control: A leader-follower task where "blind" member agents must rely on "informed" leaders to find a target landmark.
Key Insights and Results
Structure over Strength
A critical advantage of the Heat Kernel is its ability to recognize structural importance. While simple thresholding might ignore a "bridge" agent with a weak individual signal, the Heat Kernel identifies its essential role in maintaining network connectivity.
Performance and Scalability
CDC consistently outperformed baselines such as MADDPG, CommNet, and MAAC. In the 10-agent Formation Control task, CDC achieved a near-perfect success rate of 0.99, while most baselines failed entirely. Furthermore, CDC demonstrated superior scalability; as the number of agents increased from 3 to 10, the performance gap between CDC and traditional methods widened significantly.
Robustness and Interpretability
The model learns logical communication patterns. In the Pack Control task, the heat kernel heatmaps revealed the emergence of bipartite-like structures where blind members prioritized signals from informed leaders. Additionally, models trained with 4 agents generalized to 8 agents with minimal performance loss, showcasing the robustness of the graph-based prior.
Conclusion
Connectivity-driven Communication introduces a novel way to structure multi-agent interaction using spectral graph theory. By modeling communication as a diffusion process, CDC captures the global topology of agent networks, leading to more efficient and scalable coordination. Future work may explore replacing the centralized RNN critic with a Graph Neural Network (GNN) to provide more localized feedback and incorporating physical flow constraints to further regulate information exchange.
Summary updated