Learning Multi-Agent Coordination through Connectivity-driven Communication

Emanuele Pesce, Giovanni Montana

TL;DR

Researchers have developed a new multi-agent reinforcement learning (MARL) approach called Connectivity Driven Communication (CDC). By modeling agent communication as a heat diffusion process on a dynamic graph, the system learns which messages are structurally important, allowing agents to coordinate complex tasks far more effectively than standard attention-based methods.

What Problem Does This Paper Address?

In multi-agent systems—think a swarm of drones or a fleet of autonomous delivery robots—cooperation is everything. However, teaching agents to cooperate is notoriously difficult. As agents learn and change their behavior, the environment becomes "non-stationary" from the perspective of any single agent.

Communication is the standard solution, but it creates a "signal-to-noise" problem: if every agent broadcasts everything to everyone, the system is overwhelmed with irrelevant data. Previous attempts used "attention mechanisms" to filter messages, but these often look at agents in isolation or simple pairs. They fail to capture the global structure of the network—how information actually flows through the group to reach the agents who need it most.

Methods

The authors introduce Connectivity Driven Communication (CDC), which treats the agent network as a weighted graph where the "topology" (who is connected to whom) changes dynamically based on what the agents see.

The core innovation is the use of the Heat Kernel (HK) from spectral graph theory. Imagine placing a heat source on one agent; the Heat Kernel describes how that heat spreads across the network over time.

  • Dynamic Graph Construction: Agents encode their private observations into "local messages" and "connectivity weights."
  • Heat Diffusion as Attention: Instead of a standard softmax attention, CDC uses the Heat Kernel to weight incoming messages. This allows the system to identify "bridge" agents—those who might have a weak connection but are structurally vital for passing information between two different sub-groups.
  • End-to-End Learning: The entire process—encoding observations, inferring the graph, calculating heat diffusion, and taking actions—is differentiable. This means the agents learn how to communicate specifically to maximize their shared reward.
  • CLDE Framework: The model uses Centralized Learning with Decentralized Execution. During training, a "critic" sees everything to provide better feedback, but during the actual task, agents act autonomously based only on their own observations and the messages they receive.

Datasets

The researchers evaluated CDC using the Multi-Agent Particle Environment (MAPE), a standard 2D physics simulator for MARL. They tested on four distinct benchmarks:

  1. Navigation Control: Agents must reach landmarks without colliding.
  2. Formation Control: Agents must arrange themselves into a specific geometric shape around a landmark.
  3. Line Control: Agents must form a straight line between two landmarks.
  4. Dynamic Pack Control (New): A more challenging task where "leader" agents can see the goal, but "member" agents are "blind" and must rely entirely on communication from leaders to find the target.

Key Insights and Ideas

  • Structure Over Weight: A major "aha moment" is that an edge with a low weight can still be the most important part of a network if it acts as a bridge between two clusters. Standard attention mechanisms often discard these "weak" signals, but the Heat Kernel preserves them because it understands the global topology.
  • Self-Adapting Topology: The communication patterns aren't fixed. In "Formation Control," the graph starts dense (lots of chatter to find positions) and becomes sparse once the shape is held. In "Pack Control," the system naturally evolves into a bipartite-like graph where leaders feed information to members.
  • Scalability: Because the model focuses on the flow of information rather than just the number of agents, it scales significantly better. While baselines often crashed or failed when moving from 3 agents to 10, CDC maintained high success rates.

Key Results

CDC consistently outperformed state-of-the-art baselines like MADDPG, CommNet, and MAAC across all metrics (reward, distance traveled, and success rate).

  • Success Rates: In the "Line Control" task with 10 agents, CDC achieved a 91% success rate, while almost all other baselines (including MAAC and TarMAC) dropped to 0% or near-zero.
  • Efficiency: In "Formation Control," CDC reached the target configuration in roughly half the time required by the next-best algorithm.
  • Robustness: In the "blind" Pack Control task, CDC was one of the only methods capable of consistently guiding the blind members to the target, outperforming CommNet on the number of targets caught.

Limitations and Future Work

While powerful, the current implementation relies on an LSTM-based centralized critic. The authors suggest that replacing this with a Graph Neural Network (GNN) could provide even more tailored feedback to individual agents.

Additionally, the current model assumes undirected graphs (information flows equally both ways). Future work could explore directed graphs to model more complex hierarchies. Finally, the authors mention adding "flow conservation" constraints—mathematical rules to ensure information isn't "lost" as it moves through the graph—to further refine the communication protocol.

Summary updated

Abstract

In artificial multi-agent systems, the ability to learn collaborative policies is predicated upon the agents' communication skills: they must be able to encode the information received from the environment and learn how to share it with other agents as required by the task at hand. We present a deep reinforcement learning approach, Connectivity Driven Communication (CDC), that facilitates the emergence of multi-agent collaborative behaviour only through experience. The agents are modelled as nodes of a weighted graph whose state-dependent edges encode pair-wise messages that can be exchanged. We introduce a graph-dependent attention mechanisms that controls how the agents' incoming messages are weighted. This mechanism takes into full account the current state of the system as represented by the graph, and builds upon a diffusion process that captures how the information flows on the graph. The graph topology is not assumed to be known a priori, but depends dynamically on the agents' observations, and is learnt concurrently with the attention mechanism and policy in an end-to-end fashion. Our empirical results show that CDC is able to learn effective collaborative policies and can over-perform competing learning algorithms on cooperative navigation tasks.
BibTeX
@article{pesce2023learning,
  author = {Emanuele Pesce and Giovanni Montana},
  title = {{Learning Multi-Agent Coordination through Connectivity-driven Communication}},
  journal = {Machine Learning},
  year = {2023},
  doi = {10.1007/s10994-022-06286-6},
}
Figure