Dispersive Tree Agreements for Multi-Robot Coordination

Shashank A. Deshpande; Blake T. Edwards; Jonathan P. How

cs.ROOct 22, 2026

Dispersive Tree Agreements for Multi-Robot Coordination

Authors: Shashank A. Deshpande, Blake T. Edwards, Jonathan P. How

Organizations: Department of Aeronautics and Astronautics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA

Abstract

Multi-robot coordination of nonlinear systems is naturally formulated as joint-space optimal control subject to constraints over groups of robots. Existing methods that approach joint optimality remain largely centralized, offline, and confined to collision-free motion planning, while decentralized, real-time counterparts target safe navigation without pursuing the joint optimum. This paper develops a decentralized, real-time planner that approaches the joint optimum as an anytime process. We extend a recent single-robot framework that searches dispersive trees of forward-propagated commands for differentially flat systems to coordinate a multi-robot team near-optimally. We first show that the inter-robot coupling can be effectively replaced by some local constraints, under which locally grown dispersive trees contain a near-optimal agreement. It is this structure that the robots pursue by decentralized column generation, negotiating rents on the shared space that guide the search of each robot's tree. The negotiation settles on an agreement whose near-optimality is certified at quiescence. Our protocol, WarpWeaver, implements this negotiation as an asynchronous real-time loop over a receding horizon, and demonstrates effective closure to quiesced agreements even when real-time deadlines cut the negotiation short. In simulation, WarpWeaver reduces total travel time by up to 22% against centralized offline planners on the Dynobench suite and by up to 37% against a decentralized real-time baseline, and nearly doubles the success rate of a task-specific planner on graph connectivity. Hardware experiments on six robots planning onboard demonstrate real-world implementability.

Figures & tables

Fig. 1: (a) Iterated Best Response, $F={\color[rgb]{0.168,0.4297,0.5508}7.5}\;{+}\;{\color[rgb]{0.707,0.3125,0.1719}10.0}=17.5$ s, vs. (b) Dispersive Tree Agreement, $F={\color[rgb]{0.168,0.4297,0.5508}8.0}\;{+}\;{\color[rgb]{0.707,0.3125,0.1719}5.5}=13.5$ s, where the total travel time $F$ sums the arrival times of the blue and red robots.

Fig. 2: Decentralized column generation. The dual of the restricted master over the pool

Q

sets common prices, under which each agent searches its own dispersive tree. Sequences that improve the pool return as new columns until the agreement is certified at quiescence.

Fig. 3: The WarpWeaver protocol ( Algorithm 1 ), visualized as a flowchart at the onboard computer of agent

i

. Each agent asynchronously runs an identical loop onboard.

Panel of Figure 4 — Algorithm 1 WarpWeaver at agent $i$

Platform	$f_{i}$ , $U_{i}$	$E_{i}$	$R_{i}$	$B_{i}$ (m)	$\mathcal{A}$	Search Parameters
Unicycle	$\dot{p}=ve_{\theta}$ , $\dot{\theta}=\omega$ , $\|v\|,\|\omega\|\leq 0.5$	–	–	Box $0.5\times 0.25$	Constant $(v,\omega)$ on a lattice $(v,\omega)\in G_{8}\bigl[-\tfrac{1}{2},\tfrac{1}{2}\bigr]^{2}$	$\Delta=0.5,\ T=10$ , $\Delta_{s}=0.5,\ s_{i}=0.08$ , $\varepsilon_{g}=0.5$ , $S=0.6,\ n_{s}=5$
Double Int. (3D)	$\ddot{p}=a$ , $\\|a\\|_{\infty}\leq 2$	$\\|v\\|_{\infty}\leq 0.5$	$\\|v\\|_{\infty}\leq 0.17$	Ball $0.1$	Constant $a$ on a lattice of the admissible box $a\in G_{4}\bigl(J(x)\bigr)$ , with $J(x)=[-2,2]^{3}\cap\bigl([-\tfrac{1}{2},\tfrac{1}{2}]^{3}-v\bigr)/\Delta$	$\Delta=0.5,\ T=10$ , $\Delta_{s}=0.5,\ s_{i}=0.25$ , $\varepsilon_{g}=0.5$ , $S=0.25,\ n_{s}=5$
Triple Int. (3D)	$\dddot{p}=j$ , $\\|j\\|\leq 25$	$\\|v\\|\leq 4$ , $\\|a\\|\leq 8$	$\\|v\\|_{\infty}\leq 0.3$ , $\\|a\\|_{\infty}\leq 0.6$	Ball $0.15$	Admissible jerk profiles to diverse reference velocities $j\in\bigl\{j^{1}_{\bar{v}},\,j^{2}_{\bar{v}}:\bar{v}\in V(x)\bigr\}$	$\Delta=0.5,\ T=8$ , $\Delta_{s}=0.5,\ s_{i}=2$ , $\varepsilon_{g}=0.75$ , $S=0.35,\ n_{s}=10$
X500	$\dot{p}=v$ , $m\dot{v}=c\,b_{3}(q)-mge_{3}$ , $\dot{q}=\tfrac{1}{2}q\otimes\omega$ , $J\dot{\omega}=M-\omega\times J\omega$ , $(c,M)=B\eta$ , $t_{m}\dot{\eta}=u-\eta$ , $u\in[0.19,8.55]^{4}$	$\\|v\\|\leq 4$ , $\|\omega_{1,2}\|\leq 3.84$ , $\|\omega_{3}\|\leq 3.49$ , $\angle(b_{3},e_{3})\leq 45^{\circ}$	$\\|v\\|_{\infty}\leq 0.5$ , $\\|\omega\\|_{\infty}\leq 0.5$	Ball $0.1$	Smooth acceleration references on a lattice, tracked by the geometric controller of [ 17 ] $a\in G_{5}[-8,8]^{2}\times\{-8,-4,0,1.85,3.7\}$ , $c_{-}\leq\\|a+ge_{3}\\|\leq c_{+}$	$\Delta=0.25,\ T=6$ , $\Delta_{s}=0.5,\ s_{i}=2$ , $\varepsilon_{g}=0.75$ , $S=0.6,\ n_{s}=25$
Single Int. (2D)	$\dot{p}=u$ , $\\|u\\|\leq 1.5$	–	–	Disk $0.36$	Constant $u$ on a polar lattice $u\in\{\sigma e_{2\pi k/16}:\sigma\in\{0.5,1,1.5\},$ $k<16\}$	$\Delta=1,\ T=10$ , $\Delta_{s}=1,\ s_{i}=0.1$ , $\varepsilon_{g}=1.5$ , $S=0.75,\ n_{s}=10$

TABLE I: Platforms, command sets, and search parameters. Commands are held over windows of length

\Delta

(s) [ 17 ] , and each set also contains a hold and, for the integrators, a brake toward rest.

G_{n}[l,u]

: the

n

-level grid on

[l,u]

;

e_{\theta}=(\cos\theta,\sin\theta)

. Triple integrator at

x=(p,v,a)

j^{1}_{\bar{v}}=-a/\Delta\pm 4\lambda_{1}(\bar{v}-v-\Delta a/2)/\Delta^{2}

, with

+

on the first half window, and

j^{2}_{\bar{v}}=2\lambda_{2}(\bar{v}-v-\Delta a)/\Delta^{2}

, with

\lambda_{1},\lambda_{2}\leq 1

maximal within the bounds;

V(x)=\{\sigma(\cos\phi\,e_{\psi+\theta},\sin\phi)\}

\sigma\in\{\frac{4}{3},\frac{8}{3},4\}

\theta\in\{0,\pm 5^{\circ},\pm 10^{\circ},\pm 20^{\circ}\}

\phi\in\{0,\pm 20^{\circ}\}

\psi

the heading of

v

. X500: attitude

q

, body axis

b_{3}

, body rate

\omega

, rotor thrusts

\eta

(N), mixer

B

, motor time constant

t_{m}

T

: horizon in windows;

\Delta_{s}

(s): stride;

s_{i}

: pruning radius;

\varepsilon_{g}

: goal tolerance;

S

(m): cell diameter;

n_{s}

: substeps per window.

Panel of Figure 6 — Fig. 4: WarpWeaver in simulation. (a) Circle-10, unicycles. (b) Forest-10, 3D double integrators. (c) Ten triple integrators on a forest map of EGO-Swarm. (d) Connectivity maintenance in the forest world of Realm, with the live links at three instants. In (a) and (d), each robot has its own colour and is drawn at three instants, later ones more opaque. In (b) and (c), trajectories and bodies are coloured by time from start (circle) to goal (star).

	Instance	$N$	Warp- Weaver	Quie- sced	db-CBS	db-ECBS	db-PIBT	db-LaCAM @60 s
Unicycle	swap2	$2$	$\mathbf{11.0}$	$11.0$	$12.0$	$14.4$	$16.8$	$15.6$
	swap4	$4$	$\mathbf{24.0}$	$22.5$	$27.6$	$27.1$	–	$72.0$
	atgoal	$2$	$\mathbf{6.5}$	$7.0$	$8.4$	$8.3$	$25.2$	$16.8$
	circle6	$6$	$84.5$	$83.5$	$90.0$	$\mathbf{82.9}$	$97.2$	$96.0$
	circle8	$8$	$\mathbf{113.0}$	$113.0$	$121.2$	$117.8$	$141.6$	$136.8$
	circle10	$10$	$\mathbf{140.5}$	$139.5$	$150.0$	$156.3$	$182.4$	$196.8$

TABLE II: Multi-robot Dynobench: total travel time (s) summed over agents, median. Quiesced: WarpWeaver with the world paused until

\varepsilon_{q}

-quiescence or for at most

5

s ( Section VI-C ),

\varepsilon_{q}

-quiescent at more than

84\%

of the iterations of every run, median over five trials.

Map	Planner	Success	$F$ (min–max)
Forest 1	WarpWeaver, triple int.	$\mathbf{5/5}$	$\mathbf{91.5}$ (91.0–94.5)
	WarpWeaver, X500	$\mathbf{5/5}$	$97.5$ (97.5–101.0)
	EGO-Swarm	$4/5$	$145.7$ (142.4–148.5)
Forest 2	WarpWeaver, triple int.	$\mathbf{5/5}$	$\mathbf{92.5}$ (91.0–93.0)
	WarpWeaver, X500	$\mathbf{5/5}$	$99.0$ (98.0–102.0)
	EGO-Swarm	$\mathbf{5/5}$	$145.9$ (136.0–154.0)

TABLE III: Ten drones on the EGO-Swarm forest maps.

F

: total travel time (s) summed over agents, median (min–max) over successful trials.

	WarpWeaver		db-LaCAM
$N$	Total	per robot	Total	per robot
$10$	$167.5$ ( $167.0$ – $168.5$ )	$16.8$	$217.2$	$21.7$
$20$	$435.5$ ( $432.5$ – $438.0$ )	$21.8$	$522.0$	$26.1$
$30$	$649.5$ ( $645.0$ – $654.0$ )	$21.7$	$884.4$	$29.5$
$40$	$910.5$ ( $904.0$ – $913.0$ )	$22.8$	$1400.4$	$35.0$
$50$	$1126.5$ ( $1107.5$ – $1165.5$ )	$22.5$	$1470.0$	$29.4$

TABLE IV: Scaling tests, unicycles in a

20\times 20

m arena, five trials per

N

, WarpWeaver in real time (emulated). Total travel time summed over agents and per robot (s), median (min–max) for WarpWeaver and the median best solution of db-LaCAM within

300

World	Planner	Success	Time (s)	Conn.	Path
Clutter	WarpWeaver	$\mathbf{5/5}$	$\mathbf{23.9}$ (19.7–39.1)	$1.00$	$122$
Clutter	Realm	$\mathbf{5/5}$	$58.3$ (31.0–109.2)	$1.00$	$193$
Garage	WarpWeaver	$\mathbf{5/5}$	$\mathbf{43.8}$ (25.8–54.0)	$1.00$	$234$
Garage	Realm	$3/5$	$61.9$ (55.3–85.5)	$1.00$	$226$
Forest	WarpWeaver	$\mathbf{5/5}$	$\mathbf{54.6}$ (45.3–73.8)	$1.00$	$273$
Forest	Realm	$0/5$	–	$1.00$	–

TABLE V: Connectivity maintenance against Realm, four robots. Time: arrival of the last robot (s), median (min–max); Conn.: fraction of time connected, worst task; Path: summed path length (m), median.

	Quiesc.			$t_{q}$ , $\varepsilon_{q}=1$			$F$
$N$	RT	$\varepsilon_{q}=0$	$\varepsilon_{q}=1$	p50	p90	p99	RT	$\varepsilon_{q}=0$	$\varepsilon_{q}=1$
$10$	$70\%$	$98\%$	$100\%$	$0.11$	$0.31$	$1.26$	$167.5$	$167.5$	$167.0$
$20$	$16\%$	$58\%$	$99\%$	$1.32$	$2.41$	$>5$	$435.5$	$431.5$	$435.0$
$30$	$6\%$	$33\%$	$93\%$	$1.48$	$4.63$	$>5$	$649.5$	$643.0$	$658.0$
$40$	$1\%$	$7\%$	$60\%$	$3.56$	$>5$	$>5$	$910.5$	$899.5$	$898.5$
$50$	$0\%$	$2\%$	$7\%$	$>5$	$>5$	$>5$	$1126.5$	$1072.0$	$1065.5$

TABLE VI: Quiescence in real time and with the world paused (cap

5

s, one trial per

N

). Quiesc.: iterations that end quiescent, in real time (median over the trials of Table IV ) and within the cap at

\varepsilon_{q}=0

and

\varepsilon_{q}=1

;

t_{q}

: time to quiescence at

\varepsilon_{q}=1

(s), capped iterations counted as

>5

;

F

: total travel time (s) in real time (median, Table IV ) and with up to

5

s of negotiation per iteration.

Panel of Figure 12 — Fig. 5: Six robots, one take per task. Left: executed trajectories from motion capture, each robot in its own colour, with the robots at the start, midway, and at the last arrival, later instants more opaque. Right: the camera frames overlaid, later ones more opaque. (a) Swap around four pillars. (b) Tethered swap, with the tied pairs joined by dashed lines. (c) Doorway swap.

Task	Success	Last arrival	Total	Sep.	Tether
Swap	$3/3$	$20.2$ ( $20.0$ – $20.8$ )	$108.1$	$0.28$	–
Tethered swap	$3/3$	$30.4$ ( $24.5$ – $31.9$ )	$125.4$	$0.28$	$2.37$
Doorway swap	$3/3$	$33.6$ ( $25.3$ – $35.6$ )	$162.1$	$0.12$	–

TABLE VII: Real-robot experiments, six robots, three consecutive takes per task. Time: arrival of the last robot (s) and total travel time summed over robots (s), median (min–max); Sep.: smallest distance between two robots minus both clearance radii (m); Tether: largest distance within a tied pair (m), against

L=2.4

Multi-Robot Coordination

Multi-robot coordination studies how teams of robots plan, communicate, allocate tasks, and act together safely and efficiently.

See all 322 papers

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 Robotic Optimization

Ask PDF

May 19, 2026

Scalable Multi-robot Motion Planning via Hierarchical Subproblem Expansion and Workspace Decomposition Refinement

A fundamental challenge in multi-robot motion planning is achieving sufficient coordination to avoid inter-robot conflicts without incurring the large computational expense of searching the joint configuration space of the robot group. In this work, we present a method for multiple mobile robot motion planning that achieves an improvement in planning time up to an order of magnitude by leveraging the insight that we can use discrete search over a workspace decomposition to provide coordination between robots during planning. While prior work uses workspace topology to inform when coordination between robots is needed and then composes robots into their joint configuration space, we take a step further by iteratively refining our workspace representation to allow our planner to search smaller, decoupled configuration spaces.

Isaac Ngui, Courtney McBeth, James D. Motes +2

University of Illinois Urbana-Champaign, Urbana IL 61801, USA · Instituto Tecnológico Autónomo de México, Mexico City, Mexico

Multi-Robot Motion Planning Hierarchical Planning Multi-Robot Coordination

Ask PDF

May 26, 2026

Simulation-Informed Diffusion for Decentralized Multi-robot Motion Planning

Decentralized multi-robot motion planning requires each robot to generate collision-free trajectories from local observations, without global sensing or reliable communication. However, most existing planners, whether classical or learning-based, generate trajectories from a static snapshot of the local observation, which limits their ability to anticipate the future behavior of neighboring robots. This limitation is critical as the number of robots increases and the environment becomes more cluttered. To overcome this challenge, this paper introduces Simulation-Informed Diffusion (SID), a decentralized framework built on constraint-aware diffusion models (CADM). SID first uses CADM to simulate the future trajectories of neighboring robots from their currently observed states, and then uses the same CADM to plan each robot's own trajectory under safety constraints informed by these simulations. Crucially, the accurate simulation of neighbors enables a minimal communication scheme that triggers coordination only when necessary in highly congested scenarios. Experiments across diverse environments show that SID consistently outperforms baseline methods in terms of planning effectiveness and constraint satisfaction, and scales to scenarios with 108 robots and 160 obstacles.

Jinhao Liang, Sven Koenig, Ferdinando Fioretto

University of Virginia · University of California, Irvine

Multi-Robot Motion Planning Constrained Motion Planning Diffusion-Based Planning Safe Motion Planning Decentralized Multi-Agent Motion Planning

Ask PDF

Abstract

Multi-Robot Coordination

Explore similar work

Denoising Multi-Robot Trajectories

Scalable Multi-robot Motion Planning via Hierarchical Subproblem Expansion and Workspace Decomposition Refinement

Simulation-Informed Diffusion for Decentralized Multi-robot Motion Planning