Reliable and Efficient Multi-Agent Coordination via Graph Neural Network
  Variational Autoencoders
Authors: name: Yue Meng, name: Nathalie Majcherczyk, name: Wenliang Liu, name: Scott Kiesel, name: Chuchu Fan, name: Federico Pecora

Multi-agent coordination is crucial for reliable multi-robot navigation in
shared spaces such as automated warehouses. In regions of dense robot traffic,
local coordination methods may fail to find a deadlock-free solution. In these
scenarios, it is appropriate to let a central unit generate a global schedule
that decides the passing order of robots. However, the runtime of such
centralized coordination methods increases significantly with the problem
scale. In this paper, we propose to leverage Graph Neural Network Variational
Autoencoders (GNN-VAE) to solve the multi-agent coordination problem at scale
faster than through centralized optimization. We formulate the coordination
problem as a graph problem and collect ground truth data using a Mixed-Integer
Linear Program (MILP) solver. During training, our learning framework encodes
good quality solutions of the graph problem into a latent space. At inference
time, solution samples are decoded from the sampled latent variables, and the
lowest-cost sample is selected for coordination. Finally, the feasible proposal
with the highest performance index is selected for the deployment. By
construction, our GNN-VAE framework returns solutions that always respect the
constraints of the considered coordination problem. Numerical results show that
our approach trained on small-scale problems can achieve high-quality solutions
even for large-scale problems with 250 robots, being much faster than other
baselines. Project page: https://mengyuest.github.io/gnn-vae-coord