Reliable and Efficient Multi-Agent Coordination via Graph Neural Network Variational Autoencoders

Yue Meng, Nathalie Majcherczyk, Wenliang Liu, Scott Kiesel, Chuchu Fan, Federico Pecora

Abstract

Multi-agent coordination in dense environments, such as automated warehouses and autonomous intersections, presents a significant computational challenge. While Mixed-Integer Linear Programming (MILP) provides optimal solutions, its exponential complexity limits real-time scalability. This paper presents a Graph Neural Network Variational Autoencoder (GNN-VAE) framework that achieves near-optimal coordination for up to 250 robots. By integrating structural constraints directly into the neural network architecture, the framework guarantees deadlock-free and density-compliant schedules while operating 10 to 20 times faster than traditional optimization methods.

Introduction

In modern logistics and transportation, robots frequently converge on "interfering sections" where their paths overlap. To maintain safety and efficiency, a central controller must determine the passing order and the passing pattern for every agent. Finding the mathematically optimal schedule is a classic NP-hard problem. Traditional MILP solvers find perfect solutions but suffer from runtime explosion as the number of robots increases. Conversely, fast heuristic methods often sacrifice solution quality or fail entirely in high-density traffic. This research introduces a middle ground: a deep learning approach that matches the speed of heuristics with the reliability of formal optimizers.

The Coordination Challenge

The core of the problem lies in balancing efficiency with physical constraints. A valid schedule must satisfy two primary conditions:

  1. Acyclicity: The passing order must not contain circular dependencies, which lead to deadlocks.
  2. Density Constraints: The number of robots in any given section must not exceed its physical capacity.

To address these, the authors represent robots and their potential collision points as nodes and edges in a "coordination skeleton graph," transforming the scheduling task into a graph-based inference problem.

The GNN-VAE Framework

The proposed architecture utilizes a Variational Autoencoder (VAE) to capture the distribution of optimal schedules. The model is trained via imitation learning using data generated by a high-fidelity MILP solver.

Architecture and Inference

  1. Encoding: A Graph Attention Network (GATv2) processes the coordination skeleton graph, encoding the spatial and temporal relationships into a latent space.
  2. Sampling: During inference, the model samples multiple potential solutions from this latent space. Because neural network inference is highly parallelizable on GPUs, the system can evaluate 100 different candidate schedules in milliseconds.
  3. Violation-Free Decoding: Unlike standard regressors that may predict illegal moves, this framework employs a two-branch decoder to ensure physical feasibility by construction:
  4. Acyclicity Branch: This branch predicts "node bids" to establish a ranking. By forcing agents to move according to these rankings, the system mathematically guarantees a Directed Acyclic Graph (DAG), eliminating the possibility of deadlocks.
  5. Density Branch: This branch predicts edge confidence scores and utilizes a "top-k" selection mechanism to ensure that robot density never exceeds the physical capacity of any section.

Finally, the system selects the candidate with the lowest predicted cost, such as minimum total delay.

Experimental Evaluation

The model was trained on a synthetic dataset of 10,000 coordination problems involving 2 to 8 robots. To test generalization, the authors evaluated the model on large-scale benchmarks with up to 250 robots, created by stitching smaller subgraphs together. Validation was also performed in a 2D PyBullet physics simulation to test performance against realistic obstacle configurations.

Key Results

  • Efficiency: The GNN-VAE solved coordination problems for 250 robots in under 5 seconds, significantly outperforming search-based baselines which were 10 to 20 times slower.
  • Optimality: On small-scale tasks, the model achieved an optimality ratio of approximately 0.98 compared to the MILP ground truth.
  • Scalability: While competing methods like CMA-ES saw performance degradation beyond 20 robots, the GNN-VAE maintained an optimality ratio above 0.9 even at the 250-robot scale. This demonstrates the power of GNNs to generalize from small training sets to massive, complex topologies.
  • Hybrid Refinement: The study found that using the GNN-VAE output as an initial seed for local search methods could further push results toward the theoretical optimum with negligible time penalties.

Conclusion and Future Work

This work demonstrates that deep generative models can provide rigorous guarantees for multi-agent systems. By baking physical constraints into the decoding process, the GNN-VAE framework ensures safety and deadlock-free operation without the need for expensive post-processing.

Future research will focus on addressing current limitations, including the dependency on imitation learning from MILP solvers and the assumption of perfect environmental information. Adapting the framework to handle "uncontrollable agents" (such as human workers) and allowing for dynamic cost functions will be essential for deployment in unpredictable real-world environments.

Summary updated

BibTeX
@inproceedings{meng2025reliable,
  author = {Yue Meng and Nathalie Majcherczyk and Wenliang Liu and Scott Kiesel and Chuchu Fan and Federico Pecora},
  title = {{Reliable and Efficient Multi-Agent Coordination via Graph Neural Network Variational Autoencoders}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2025},
  doi = {10.1109/icra55743.2025.11127652},
}
Figure