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

Manav Vora; Gokul Puthumanaillam; Aditya Penumarti; Jane Shin; Melkior Ornik

cs.ROOct 9, 2026

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

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.

Figures & tables

Figure 1. Akule architecture. At each reverse-diffusion step, the frozen unary prior produces independent intent, $U_{\psi}$ selects a directed interaction graph, $R_{\phi}$ computes corrections only for the selected pairs, and $G_{\omega}$ composes them using context-dependent signed weights. Repeating this update produces a joint trajectory proposal that is passed to downstream hard repair. Overview of the Akule planning architecture. A frozen unary diffusion prior generates independent robot intent. A selector chooses directed robot interactions, pairwise interaction corrections are computed only for selected pairs, and a context-aware composer combines them with signed weights. The coordinated correction is applied during reverse diffusion, producing a joint trajectory proposal that is passed to a hard repair planner.

Figure 2. Contextual interaction selection. As reverse diffusion sharpens trajectory intent,

U_{\psi}

can revise the directed interaction graph, removing interactions that become irrelevant while admitting others that become important. Three snapshots of the same multi-robot planning scene during reverse diffusion. Early in diffusion several directed interactions are selected because robot intent is uncertain. As trajectories become more defined, the selector removes interactions that become irrelevant and admits others that become important.

Figure 3. Context-aware signed composition. A blind sum of useful pairwise corrections can produce a conflicting joint update.

G_{\omega}

uses team context to amplify, attenuate, or reverse selected corrections before the reverse update. Comparison of naive and context-aware composition for one robot. Several pairwise interaction corrections are shown. Naively summing them produces a conflicting next state, whereas the context-aware composer assigns positive and negative weights that amplify, attenuate, or reverse individual corrections to produce a coordinated next state.

Panel of Table 1 — Table 1. Canonical Weave: complete-planner results on matched panels and the three planners’ saved trajectories on one $N{=}28$ task. Scarlet brackets mark selected collisions.

Panel of Table 2 — Table 2. Projected-diffusion map families: MPD, MMD, SMD, and DGD are published DGD-benchmark values. Below, one $N{=}18$ task per map family, the same task for SMD and Akule; scarlet brackets mark selected collisions.

Panel of Table 3 — Table 3. Highways and Conveyor (10 tasks per $N$ ; all methods share the environment-specific unary prior and Akule is adapted at $N{=}20$ only), with one $N{=}20$ task per environment shown below. Scarlet brackets mark selected collisions.

Panel of Table 4 — Table 4. ScaledWeave (10 scenes per $N$ ): the Weave geometry scaled to very large teams, with Akule trained at $N{=}256$ and evaluated unchanged at smaller $N$ .

Panel of Figure 4 — Figure 4. (a) Sparse against dense Akule on 44 matched tasks: (i) fraction of $R_{\phi}$ evaluations skipped, (ii) complete planning time. (b) Success against population relative to the single training population ( $N_{\rm train}=28$ on Weave, $18$ on the map families, $20$ on Highways and Conveyor). (c) Pre-repair collisions per scene with and without Akule’s corrections, on matched scenes and noise before any repair (39 populations, 2,000 paired scenes); dotted guides mark 50/75/90% reductions.

Figure 5. ScaledWeave (10 scenes per

N

): (a) complete planning time, with MPD and MMD-xECBS timing out on every scene from

N{=}64

; (b) planning time per robot.

Panel of Table 5 — Table 5. Ablation of $U_{\phi}$ and $G_{\omega}$ on Weave and Shelf. Conf. is mean pre-repair collision pair-times, and $R_{\rm ft}$ save is the fraction of pairwise corrections avoided relative to dense.

Appendix figures & tables19 assets

Supplementary material from the paper’s appendix.

Appendix

Module	Output per directed pair	Parameters
$R_{\phi}$ (width 64)	$64\times 2$ correction	84,226
$U_{\psi}$ (width 48)	one logit	87,938
$G_{\omega}$ (width 112)	eight signed coefficients	509,601

Appendix

Table 6. Frozen canonical interaction modules. Parameter counts exclude fixed spline bases and scale buffers.

Environment	Evaluated populations $N$	Scenes per $N$	Interaction interface
Canonical Weave	10, 20, 28	512, 256, 512	25 reverse steps
Highways	3, 6, 9, 12, 15, 20	10	one correction at $t=0$
Conveyor	3, 6, 9, 12, 15, 20	10	one correction at $t=0$
SMD Basic / Dense / Shelf / Room	3, 6, 9, 12, 15, 18	25 per environment	25 reverse steps
ScaledWeave	40, 64, 100, 128, 256	10	separate scaled geometry and physical clock

Appendix

Table 7. Evaluation populations and proposal interfaces. Scene counts are per population, except the three explicitly listed Weave counts. The 39-condition intervention study comprises the first seven environments (2,000 paired scenes). ScaledWeave is a separate ten-scene-per-population family. Source: frozen scene and runtime manifests.

Environment	$N$	Scenes	Unary	Akule	$\Delta$	F/E/M
Weave	28	512	115.613	32.133	72.2%	512/0/0
Highways	20	10	311.600	85.700	72.5%	10/0/0
Conveyor	20	10	285.300	122.900	56.9%	10/0/0
SMD Basic	18	25	129.960	28.120	78.4%	25/0/0
SMD Dense	18	25	138.240	31.160	77.5%	25/0/0
SMD Shelf	18	25	152.800	24.800	83.8%	25/0/0

Appendix

Table 8. Largest-population unary intervention results. Mean physical collision pair-times before postprocessing; reduction and F/E/M follow Table 9 .

Environment	$N$	Pairs	Unary	Akule	Reduction	F/E/M
Canonical Weave	10	512	8.195	6.410	21.8%	430/49/33
Canonical Weave	20	256	72.379	12.082	83.3%	256/0/0
Canonical Weave	28	512	115.613	32.133	72.2%	512/0/0
Highways	3	10	4.400	0.500	88.6%	7/3/0
Highways	6	10	16.200	2.900	82.1%	9/1/0
Highways	9	10	66.100	17.700	73.2%	10/0/0

Appendix

Table 9. All 39 evaluated population conditions; no population or paired scene is omitted. Mean unordered physical collision pair-times before smoothing, static cleanup, and hard repair. Reduction is

100(1-\bar{C}_{\mathrm{Akule}}/\bar{C}_{\mathrm{unary}})

. F/E/M counts scenes with fewer/equal/more conflicts after interaction. Provenance: frozen paired-intervention export; 64 supports, strict distance

<0.100

Map	$N$	Unary	Corrected	After static	MMD root	Roots
Highways	3	4.4	0.5	0.4	0.0	10/10
Highways	6	16.2	2.9	2.8	0.0	10/10
Highways	9	66.1	17.7	18.6	1.2	10/10
Highways	12	120.3	31.4	30.0	2.7	10/10
Highways	15	157.8	42.6	42.6	4.2	10/10
Highways	20	311.6	85.7	86.6	13.7	10/10

Appendix

Table 10. Map proposal-stage mean collision pair-times. Akule uses ten scenes per cell; the Conveyor

N=20

MMD root mean uses its six available complete roots.

Panel of Table 11 — Table 11. Ablation of selection and composition on Canonical Weave ( $N{=}28$ , 30 instances) and Shelf ( $N{=}18$ , 25 instances). Conf. is mean pre-repair collision pair-times; Repair and Plan are repair and complete-planner latency (Plan over all runs); Quality is path length / acceleration over successful plans (Weave: physical RMS; Shelf: per-step second difference); $R_{\rm ft}$ save is the fraction of pairwise corrections avoided relative to dense Akule. Source: the current manuscript’s final ablation table.

Figure 6. Frozen Weave interaction profiles over reverse steps

24\to 0

. Left: mean selected directed degree; dashed lines show dense degree

N-1

. Right: mean added and removed fractions of possible directed edges at

N=28

. Each curve uses the full corresponding panel (512/256/512 scenes). Source: saved interaction-degree and edge-transition exports.

Environment	$N$	$\beta<0$	$w<0$	Med. $\|\beta^{-}\|$	Med. $\|w^{-}\|$
Weave	10	41.57%	45.51%	0.291	0.305
Weave	20	43.05%	45.06%	0.281	0.299
Weave	28	42.96%	44.46%	0.276	0.296
Highways	20	30.88%	27.20%	0.144	0.133
Conveyor	20	41.38%	34.03%	0.139	0.124

Appendix

Table 12. Signed-composer statistics on admitted edges. Fractions count negative coefficients/weights; medians summarize their negative magnitudes.

Environment	$N$	Scenes	Unary	U	R	G	$R$ save
Weave	10	512	64.20	38.48	12.80	27.73	4.85%
Weave	20	256	65.43	39.34	20.36	27.32	19.20%
Weave	28	512	64.18	39.08	31.09	36.73	29.37%
Highways	20	10	806.03	2.06	1.38	1.82	59.39%
Conveyor	20	10	919.07	2.09	1.78	2.05	38.71%

Appendix

Table 13. Akule CUDA-event component times (ms) on RTX 5090. Weave sums 25 steps; maps use one correction after candidate generation. Savings are relative to dense

R

evaluation.

Env. / $N$	Method	Scenes	CT	Constraints	Repair (s)
Weave 10	MPD	512	5.00	10.00	3.900
Weave 10	MMD-xECBS	512	4.63	9.25	3.502
Weave 10	Akule	512	3.94	7.88	2.977
Weave 20	MPD	256	21.44	42.88	26.583
Weave 20	MMD-xECBS	256	14.16	28.31	15.588
Weave 20	Akule	256	7.20	14.40	6.936

Appendix

Table 14. Mean downstream repair workload. Weave uses full panels, Highways ten tasks, and Conveyor six matched complete-root tasks. CT counts tree expansions; constraints count generated branch constraints. Timers retain their recorded hardware.

Panel of Figure 7 — Figure 7. Canonical Weave at $N=10,20,28$ . Independent MPD proposals are shown before repair. Same task across methods at each population. Scene IDs, in population order: 510001, 510000, 105. The shared plotting conventions are defined in Section G .

Panel of Figure 8 — Figure 8. Highways at $N=3,6,9,12,15,20$ . Same task across methods at each population. Scene IDs, in population order: highways_n3_trial02, highways_n6_trial04, highways_n9_trial00, highways_n12_trial05, highways_n15_trial03, highways_n20_trial06. The shared plotting conventions are defined in Section G .

Panel of Figure 9 — Figure 9. Conveyor at $N=3,6,9,12,15,20$ . Same task across methods at each population. Scene IDs, in population order: conveyor_n3_trial00, conveyor_n6_trial02, conveyor_n9_trial06, conveyor_n12_trial07, conveyor_n15_trial05, conveyor_n20_trial05. The shared plotting conventions are defined in Section G .

Panel of Figure 10 — Figure 10. Basic at $N=3,6,9,12,15,18$ . Same task across methods at each population. Scene IDs, in population order: 81003012, 81006012, 81009012, 81012012, 81015012, 81018012. The shared plotting conventions are defined in Section G .

Panel of Figure 11 — Figure 11. Dense at $N=3,6,9,12,15,18$ . Same task across methods at each population. Scene IDs, in population order: 82003012, 82006012, 82009012, 82012012, 82015012, 82018012. The shared plotting conventions are defined in Section G .

Panel of Figure 12 — Figure 12. Shelf at $N=3,6,9,12,15,18$ . Same task across methods at each population. Scene IDs, in population order: 83003012, 83006012, 83009012, 83012012, 83015012, 83018012. The shared plotting conventions are defined in Section G .

Panel of Figure 13 — Figure 13. Room at $N=3,6,9,12,15,18$ . Same task across methods at each population. Scene IDs, in population order: 84003012, 84006012, 84009012, 84012012, 84015012, 84018012. The shared plotting conventions are defined in Section G .

$N$	Accepted	Success	Plan (s)	Length	Accel.	Jerk
10	118/512	512/512	3.128/3.131	1.811/1.808	1.593/1.525	33.54/31.79
20	103/256	256/256	7.106/7.113	1.910/1.887	2.447/2.112	54.19/45.74
28	200/512	512/512	29.944/29.957	1.949/1.933	2.813/2.573	62.50/56.44

Appendix

Table 15. Saved-path smoothing on canonical Weave. Cells show before/after values. Native success is unchanged; rejected smoothing candidates retain the original trajectory. Plan includes the recorded smoothing overhead after processing.

Backend	Proposal	Cohort	Success	Timeouts	Latency (s)	Root conflicts	CT	Length	Accel.
CBS	MMD	H	0/20	20	240.00	124.40	68.20	–	–
CBS	Akule	H	0/20	20	240.00	31.60	90.05	–	–
ECBS	MMD	H	19/20	1	167.96	80.30	51.35	1.920	2.164
ECBS	Akule	N	20/20	0	77.45	31.60	28.75	1.977	2.897
xECBS	MMD	H	20/20	0	84.73	80.30	41.75	1.890	2.215
xECBS	Akule	H	20/20	0	28.90	31.60	23.45	1.954	2.873

Appendix

Table 16. Alternative repair backends on the first 20 frozen Weave

N=28

test conditions. H denotes existing frozen records and N a new RTX 5090 run; cohort timings are not a matched-hardware speed comparison. Latency includes all attempts (240 s for a timeout); root conflicts count physical pair-times. CT is mean constraint-tree expansions. Path length (m) and acceleration RMS (m/s 2 ) average successful cases only; dashes denote no successful cases. Source: compact per-attempt backend records and their source hashes.

Explore similar work

Sep 28, 2026

Denoising Multi-Robot Trajectories

Multi-robot trajectory planning is a fundamental problem in multi-robot coordination but remains computationally challenging due to its nonconvex, multimodal, and high-dimensional nature. This work builds upon D4orm, a dynamics-aware diffusion-denoising framework, and develops a family of planning architectures for diverse operational requirements. Unlike conventional numerical optimization methods, D4orm employs sampling-based optimization to generate solution trajectories through massively parallel sampling, leveraging modern computing architectures such as GPUs. Its diffusion-denoising structure iteratively optimizes deformations to candidate control trajectories, providing an efficient and versatile paradigm for generating kinodynamically feasible and conflict-free trajectories. Using D4orm as the building block for advanced planners, we present a decoupled planner for improved scalability, an online receding-horizon planner with feedback control, and a distributed planner for resource-constrained settings. Evaluations with differential-drive and holonomic robots in 2D and 3D environments demonstrate that D4orm-based approaches find high-quality solutions faster and more reliably than other sampling-based optimization methods, such as MPPI, as well as a learned diffusion-model-based method. We further demonstrate zero-shot deployment on ten real quadrotors with obstacles, large-scale deconfliction with 100 simulated robots, and fully onboard distributed `lifelong' operation with six ground robots. Overall, these results establish diffusion denoising as a scalable and reliable framework for multi-robot coordination. Code and video: https://github.com/proroklab/d4orm

Yuhao Zhang, Keisuke Okumura, Ajay Shankar +1

Department of Computer Science and Technology, University of Cambridge, U.K. · National Institute of Advanced Industrial Science and Technology (AIST), Japan

Multi-Robot Motion Planning Kinodynamic Motion Planning Trajectory Generation Diffusion-Based Planning Multi-Robot Coordination

Ask PDF

Apr 8, 2026

Train-Small Deploy-Large: Leveraging Diffusion-Based Multi-Robot Planning

Learning based multi-robot path planning methods struggle to scale or generalize to changes, particularly variations in the number of robots during deployment. Most existing methods are trained on a fixed number of robots and may tolerate a reduced number during testing, but typically fail when the number increases. Additionally, training such methods for a larger number of agents can be both time consuming and computationally expensive. However, analytical methods can struggle to scale computationally or handle dynamic changes in the environment. In this work, we propose to leverage a diffusion model based planner capable of handling dynamically varying number of agents. Our approach is trained on a limited number of agents and generalizes effectively to larger numbers of agents during deployment. Results show that integrating a single shared diffusion model based planner with dedicated inter-agent attention computation and temporal convolution enables a train small deploy-large paradigm with good accuracy. We validate our method across multiple scenarios and compare the performance with existing multi-agent reinforcement learning techniques and heuristic control based methods.

Siddharth Singh, Soumee Guha, Qing Chang +1

Department of Mechanical & Aerospace Engineering, University of Virginia · Department of Electrical & Computer Engineering, University of Virginia

Multi-Robot Motion Planning Multi-Agent Path Finding Diffusion-Based Planning

Ask PDF

Sep 25, 2026

MR. POP: Multi-Robot Parallel Optimizing Planner for Almost-Surely Asymptotically Optimal Planning

Finding globally optimal paths remains a fundamental challenge in multi-robot motion planning. Despite acceleration of almost-surely asymptotically optimal (a.s.a.o.) planners via CPU-based parallelism, achieving both probabilistic convergence guarantees and strong computational performance, these algorithms still struggle to scale to multi-robot settings. As such, we introduce MR. POP, a GPU-based a.s.a.o. multi-robot planner based on dRRT and the AO-x meta-algorithm. MR. POP uses large-scale GPU-based SIMT-parallelism to simultaneously run hundreds of roadmap construction and tree search iterations with underlying parallel nearest neighbor search and collision checking operations. We show that this enables MR. POP to become the only planner achieving a 100% solve rate while being faster than state-of-the-art a.s.a.o. planners in multi-robot systems up to 35-DOF. MR. POP also raises the success rate of downstream motion optimizers (e.g., from 4% to 72%), by creating high-quality, diverse seeds that help avoid local minima.

Chih H. Huang, Roy Xing, Brian Plancher +1

Columbia College, Columbia University · Department of Computer Science, Dartmouth College · Department of Computer Science, Purdue University

Multi-Robot Motion Planning Motion Planning Roadmap-Based Motion Planning

Ask PDF