Abstract: We discuss the problem of learning collaborative behaviour through communication in multi-agent systems using deep reinforcement learning. A connectivity-driven communication (CDC) algorithm is proposed to address three key aspects: what agents to involve in the communication, what information content to share, and how often to share it. The multi-agent system is modelled as a weighted graph with nodes representing agents. The unknown edge weights reflect the degree of communication between pairs of agents, which depends on a diffusion process on the graph - the heat kernel. An optimal communication strategy, tightly coupled with overall graph topology, is learned end-to-end concurrently with the agents' policy so as to maximise future expected returns. Empirical results show that CDC is capable of superior performance over alternative algorithms for a range of cooperative navigation tasks, and that the learned graph structures can be interpretable.
Introduction
In multi-agent systems, such as drone swarms or autonomous vehicle fleets, agents must coordinate to achieve collective goals. However, multi-agent reinforcement learning (MARL) faces significant challenges: non-stationarity, where the environment changes as agents learn, and information overload, where excessive communication creates noise and hinders scalability. While attention mechanisms have been used to filter messages, they often neglect the underlying structural topology of the agent network. The authors propose Connectivity-driven Communication (CDC) to create a self-adapting, differentiable communication protocol grounded in graph theory.
Methodology
The core innovation of CDC is treating agent communication as a diffusion process on a dynamic graph. The architecture follows the Centralized Learning, Decentralized Execution (CLDE) paradigm.
- Dynamic Graph Construction: At each timestep, agents encode local observations to predict connectivity weights between themselves and others, forming a state-dependent weighted graph where edges represent communication potential.
- The Heat Kernel (HK): Instead of standard attention, CDC employs the Heat Kernel from spectral geometry. This describes how information ("heat") spreads across the network, identifying structurally influential agents by solving the heat equation on the graph.
- Differentiable Attention: The Heat Kernel is differentiable, allowing the entire communication strategy to be trained end-to-end via backpropagation. The system identifies a "critical time point" where information flow stabilizes to weight incoming messages.
- Execution and Training: During training, a centralized critic (implemented as an LSTM) provides feedback. At execution time, agents rely solely on local observations and the learned communication protocol.
Experimental Setup
The model was evaluated using the Multi-Agent Particle Environment (MAPE) across four cooperative tasks:
- Navigation Control: Reaching landmarks without collisions.
- Formation Control: Arranging into specific geometric shapes.
- Line Control: Forming a straight line between landmarks.
- Dynamic Pack Control: A challenging benchmark where "leader" agents see the goal, but "member" agents are "blind" and must rely entirely on communicated signals.
Results and Discussion
CDC demonstrated superior scalability, maintaining a 0.99 success rate in Formation and Line tasks as agent counts increased from 3 to 10, whereas baselines like MADDPG and MAAC saw performance declines. In Formation Control ($N=4$), CDC reached goals in roughly half the time required by the next-best algorithm.
Key insights include:
- Topology Over Weight: The Heat Kernel recognizes the structural importance of "bridge" edges that standard attention might discard.
- Emergent Interpretability: Visualization of learned heatmaps showed that the model naturally discovers roles, such as distinct communities forming around leaders in the Pack Control task.
- Zero-Shot Transfer: Models trained with 4 agents were successfully deployed with 3 to 8 agents at test time, significantly outperforming standard DDPG.
Conclusion
CDC offers a robust, graph-theoretic approach to multi-agent communication that prioritizes structural importance over simple message weighting. While the computational complexity of matrix exponentiation for the Heat Kernel is a consideration (mitigated by Padé approximants), the gains in scalability and interpretability are significant. Future work may explore directed graphs to model one-way communication and incorporate flow conservation constraints.
Summary updated