Reliable and Efficient Multi-Agent Coordination via Graph Neural Network Variational Autoencoders
Yue Meng, Nathalie Majcherczyk, Wenliang Liu, Scott Kiesel, Chuchu Fan, Federico Pecora
2025-03-06
Summary
This paper talks about a new way to help multiple robots work together in crowded spaces like warehouses, using a special type of artificial intelligence called Graph Neural Network Variational Autoencoders (GNN-VAE)
What's the problem?
When lots of robots are working in the same area, it's hard to keep them from bumping into each other or getting stuck. The current method of having a central computer tell all the robots what to do takes too long when there are many robots
What's the solution?
The researchers created a system that turns the robot coordination problem into a graph, which is like a map of connections. They then used GNN-VAE to learn from examples of good solutions. When it's time to coordinate the robots, their system can quickly come up with a good plan by sampling from what it learned, even for situations with up to 250 robots
Why it matters?
This matters because it could make warehouses and other places with lots of robots work much more efficiently. The system can handle many more robots than before and still keep them from getting in each other's way, all while working much faster than older methods. This could lead to smoother operations in places that use lots of robots, like Amazon warehouses
Abstract
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