Skip to main content
Back

Universitat Pompeu Fabra's CG-CMARL Teaches 10 Robots to Coordinate Without Crashing

CG-CMARL combines coordination graphs with Lagrangian duality so a single trained model navigates the full safety-performance tradeoff for teams of up to 10 agents.

  • CG-CMARL combines coordination graphs with Lagrangian duality to solve constrained multi-agent RL, scaling to 10-agent teams where centralized approaches are intractable.
  • A two-head Q-network separates coverage and collision learning, enabling a single trained model to sweep the full safety-performance Pareto front by varying λ at evaluation time.
  • Max-Sum message passing coordinates joint actions in O(N²) time instead of O(|A|^N), reducing the 10-agent action space from 9.5×10¹³ to ~280,000 operations per step.
  • CG-CMARL's Pareto front dominates IQL, QMIX, DCG, MAPPO, and MAPPO-Lagrangian across all team sizes on the Simple Spread benchmark.
  • Convergence guarantees are provided for both Q-heads and the dual multiplier, with a four-source compositional error bound (structural, coordination, sampling, representation).
  • Key limitations: requires independent agent transitions, pairwise graph becomes dense at large N, and no public code has been released yet.

Teaching a team of robots to cover ground efficiently while never crashing into each other sounds straightforward until you realize that both problems get exponentially harder as the team grows. A new paper from researchers at Universitat Pompeu Fabra introduces CG-CMARL, a framework that tackles both challenges simultaneously by marrying two powerful ideas: coordination graphs for scalable action selection, and Lagrangian duality for principled constraint handling.

Two problems, one framework

Multi-agent reinforcement learning (MARL) has a well-known scaling problem. If each of N agents has 25 possible actions, the joint action space grows as 25^N. With 10 agents that is roughly 10^13 combinations , completely intractable to search over directly. Coordination graphs address this by exploiting the fact that most agent interactions are local: only nearby pairs of agents need to reason about each other's actions. The global Q-function is decomposed into a sum of pairwise regional Q-functions, and a message-passing algorithm called Max-Sum finds the approximately optimal joint action in time polynomial in N.

But coordination graphs, as they existed before this work, had no mechanism for enforcing constraints. Safety requirements like "keep collisions below a threshold" couple agents in ways that reward shaping alone cannot capture. If each agent independently tries to satisfy a global constraint, the team can collectively fail even when every individual thinks it is doing fine. The core difficulty is that constraints couple agents in ways that reward structure alone does not capture.

The two-head Q-network

The central innovation in CG-CMARL is a two-head Q-network shared across all pairwise agent regions. Rather than learning a single Q-function for a combined reward signal, the network maintains two separate output heads:

  • Primary head (Q_prim): learns the optimal Q-values for the coverage objective via standard Q-learning.
  • Cost head (Q_cost): evaluates the expected collision cost under the primary head's greedy policy , not under its own greedy policy. This is a subtle but critical design choice.

At action selection time, the two heads are combined via a Lagrangian multiplier λ:

Q_aug = Q_prim + λ * Q_cost

The key insight is that λ is not baked into training. Because the two heads are trained independently with fixed reward signals, you can sweep λ at evaluation time to trace the full Pareto front of coverage versus safety , all from a single trained model. The system utilizes a two-head Q-network architecture to decouple primary objective learning from constraint satisfaction, allowing a single trained model to trace a Pareto front by varying the Lagrangian multiplier at evaluation time. Every competing baseline in the paper requires a separately trained model for each operating point on the tradeoff curve.