Akule speeds up multi-robot motion planning for large teams
Akule: Fast and Scalable Multi-Robot Motion Planning via Sparse Interaction Diffusion
RoboticsArtificial IntelligenceMultiagent Systems
Summary
Planning paths for many robots moving together can be very slow because the interactions between robots need complex calculations. The authors present Akule, a method that uses a pre-learned model for single robots and adds smart modules to predict which robot interactions matter and how to combine them efficiently. This approach lets Akule plan group movements much faster, even for very large teams of robots, while still checking and fixing paths to avoid collisions. Akule works well on various tests and can handle hundreds of robots with less computational effort.
What this means in practice
- •For robotics engineers: Speed up motion planning for large fleets of robots in warehouses or factories using Akule’s sparse interaction model.
- •For drone fleet operators: Plan collision-free paths efficiently for large groups of drones performing coordinated tasks outdoors with Akule’s scalable approach.
Authors
Manav Vora, Gokul Puthumanaillam, Aditya Penumarti, Jane Shin, Melkior Ornik
Abstract
Diffusion models provide expressive trajectory priors for multi-robot motion planning (MRMP), but scaling them to large teams requires coordinating individual motions without expensive joint computation. We introduce Akule, a sparse interaction diffusion framework that augments a frozen single-robot prior with three learned modules: a reusable pairwise correction model $R_φ$, a contextual selector $U_ψ$ that determines which corrections to evaluate, and a composer $G_ω$ that combines their effects through context-dependent signed weights. This decomposition separates which interactions merit computation from how their effects should be combined into coordinated denoising updates. We train $R_φ$ using matched pairwise trajectory optimizations, then learn $G_ω$ and $U_ψ$ from physically optimized joint trajectories without requiring a prescribed ground-truth interaction graph. The resulting joint proposals are passed to a downstream search-based planner for validation and repair. Across diverse MRMP benchmarks, Akule achieves competitive planning success, complete-planner speedups of up to $25\times$, zero-shot population transfer, and successful planning with up to $256$ robots. Ablations further demonstrate that learned selection and composition reduce pre-repair conflicts and downstream repair effort relative to heuristic selection and uniform summation.