Fast and Scalable Multi-Robot Motion Planning via Sparse Interaction Diffusion

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×, 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. Project website: https://akule-diff.github.io/