Distributed Motion Planning for Multi-Robot Systems under Topological Constraints

Gianpietro Battocletti; Dimitris Boskos; Dimos V. Dimarogonas; Bart De Schutter

cs.ROOct 7, 2026

Distributed Motion Planning for Multi-Robot Systems under Topological Constraints

Authors: Gianpietro Battocletti, Dimitris Boskos, Dimos V. Dimarogonas, Bart De Schutter

Organizations: Delft Center for Systems and Control, Delft University of Technology, Delft, The Netherlands. · Division of Decision And Control Systems, KTH Royal Institute of Technology, Stockholm, Sweden.

Abstract

Efficient and distributed coordination of mobile robots is one of the main challenges in multi-robot systems. Topological constraints, often expressed as topological braids, are a popular tool to encode complex coordination patterns between multiple mobile robots, as they offer a compact and abstract representation of the desired qualitative relation between the space-time trajectories of the robots. However, execution of joint motion plans encoded as braid-based topological constraints via distributed controllers is challenging, with existing approaches, generally based on the execution of one braid generator at a time, producing slow and suboptimal trajectories. We propose a distributed controller based on Model Predictive Control (MPC) to efficiently execute braid-based topological specifications. Rather than directly tracking the braid specification, we propose to use winding numbers, which are topological invariants for braids, as a proxy. This has the twofold benefit of converting braids into a continuous function, which can be easily tracked by an MPC controller through an appropriate term in the cost function, and of decoupling the global braid specification into a set of pairwise specifications, which can be tracked distributedly through the solution of only local MPC problems. To maintain global coordination, we propose a consensus-based progress estimation approach, which allows the robots to synchronize their motion toward the desired specification. We validate the proposed approach in simulation and in real-world experiments, where we demonstrate the effectiveness of the proposed approach and the improvement over existing approaches in terms of execution speed and control effort.

Figures & tables

Figure 1: (a) Example of a geometric braid composed of 3 strands. A corresponding braid word is

\omega=\sigma_{1}\sigma_{1}^{-1}\sigma_{2}\sigma_{1}^{-1}

. (b) Two braid generators

\sigma_{1}

\sigma_{1}^{-1}

, and the identity braid

e

. (c) Example of product operation between two braid generators, corresponding to their concatenation.

Figure 2: (a) a set of three space-time curves

\lambda_{1}

\lambda_{2}

\lambda_{3}

generated by the motion of 3 points

x_{1},x_{2},x_{3}

\mathcal{X}

over time. The curves are projected on the plane

\Pi

to generate the braid diagram shown in (b). The braid diagram corresponds to the braid word

\omega=\sigma_{1}^{-1}\sigma_{2}^{-1}\sigma_{2}^{-1}\sigma_{1}^{-1}\sigma_{1}^{-1}\sigma_{1}^{-1}

Figure 3: On the left-hand side, an example of the relative angle

\theta_{i,j}

for a pair of strands. On the right-hand side, the winding number corresponding to a pairwise swap between two strands, the sign of which depends on the rotation direction.

Figure 4: (a) Example of a geometric braid composed by 4 strands. A corresponding braid word is

\omega=\sigma_{3}\sigma_{1}^{-1}\sigma_{2}\sigma_{1}\sigma_{1}\sigma_{3}^{-1}

. (b) Winding numbers between each pair of strands in the given braid computed using the preprocessing strategy from Section 4.1.1 . (c) Winding numbers computed from Algorithm 1 . In (b) we have

B=6

, in (c)

B^{\prime}=4

	$\displaystyle\quad\qquad w^{\prime}_{i,j}(B^{\prime})$	$\displaystyle\leftarrow w^{\prime}_{i,j}(B^{\prime}-1)$
		$\displaystyle+\begin{cases}s_{b^{\prime\prime}}\frac{1}{2}&\text{if }\|p_{B^{\prime}}(i)-p_{B^{\prime}}(j)\|=1\\ &\;\text{and }p_{B^{\prime}}\left(\min\{i,j\}\right)\in\Omega,\\ 0&\text{otherwise}\end{cases}$

Algorithm 1 Preprocessing routine to compute

\mathcal{W}

Figure 5: (a) Example of a sequence of four permutation grids, describing three swaps in the relative positions for a set of

m=3

robots. (b) Example of a set of representative paths describing the same topological equivalence class as the sequence of permutation grids on the left.

Figure 6: (a) Projection of the initial positions of the robots on the projection plane

\Pi

. (b) Computation of the relative angles

\theta_{i,j}(0)

and

\theta_{i,j}^{\Pi}(0)

used to initialize the winding numbers set

\bar{\mathcal{W}}

Parameter	Value
$\Delta t$	0.25 s
$K$	21
$\xi_{\mathrm{u}}$	0.05
$\xi_{\mathrm{g}}$	1
$\xi_{\mathrm{w}}$	20
$s$	20

Table 1: Values of the parameters of the D-WMPC and GBC approaches used in the simulations.

Figure 7: Simulation of the D-WMPC controller for a set of $m=10$ robots. (a) The braid diagram corresponding to the input specification $\omega$ . (b) The target winding numbers $w_{i}j$ (top plot) and the realized winding numbers $\bar{w}_{i}j$ corresponding to the trajectories of the robots (bottom plot). (c) The local (colored lines) and global (black dashed line) estimation of the progress variable $\tau$ over time. (d) The trajectories of the 10 robots over time.

#	$m$		$T$ [s]	$t_{\mathrm{sol,avg}}$ [s]	$t_{\mathrm{sol,max}}$ [s]	$l_{\mathrm{avg}}$	$l_{\mathrm{min}}$	$l_{\mathrm{max}}$	$u_{\mathrm{avg}}$	$\Sigma u$
1	3	D-WMPC	32.50	0.0348 $\pm$ 0.0060	0.0539	11.33 $\pm$ 1.22	9.77	12.75	0.0007 $\pm$ 0.0044	8.52
1	3	GBC	115.50	0.0268 $\pm$ 0.0141	0.0785	32.18 $\pm$ 6.99	23.10	40.13	0.0020 $\pm$ 0.0071	24.18
2	5	D-WMPC	29.50	0.0354 $\pm$ 0.0083	0.0583	7.94 $\pm$ 2.71	4.40	12.69	0.0005 $\pm$ 0.0035	9.96
2	5	GBC	94.75	0.0278 $\pm$ 0.0152	0.0980	26.71 $\pm$ 3.78	22.66	33.26	0.0017 $\pm$ 0.0064	33.43
3	5	D-WMPC	44.75	0.0352 $\pm$ 0.0089	0.0584	9.47 $\pm$ 2.84	5.04	13.61	0.0006 $\pm$ 0.0035	11.89
3	5	GBC	145.25	0.0223 $\pm$ 0.0146	0.0983	27.64 $\pm$ 3.87	23.10	34.21	0.0017 $\pm$ 0.0064	34.59

Table 2: Comparison of the GBC and D-WMPC approaches in simulation.

Figure 8: Control architecture for the real-world experiments in the ATMOS platform. The red box represents the ROS 2 node with the proposed controller, the orange ones the ROS 2 nodes running the px4-mpc controllers, and the yellow ones the PX4 flight controllers running on board of the robots.

	Robot 1	Robot 2	Robot 3
D-WMPC	10.59	9.44	9.66
GBC	13.24	13.48	15.01

Table 3: Length of the trajectories of the ATMOS robots in the experiment depicted in Figure 9 , expressed in meters.

Figure 9: Experiment with the ATMOS robots. The robots are tasked with tracking the specification ( 40 ). Both the sets of trajectories yield a topological braid corresponding to the specification.

Figure 10: Input forces $F_{x}$ and $F_{y}$ , expressed in N, generated by the D-WMPC (left) and GBC (right) approaches to execute the trajectories of the experiment depicted in Figure 9 .

Panel of Figure 11 — Figure 11: Experiment with tethered ATMOS robots. (a) A close-up of the initial knot between the tethers. (b) The robots in the initial configuration, with the tethers entangled by the knot. (c) The robots in their final configuration with the tethers free from entanglement. (d) The paths followed by the robots to disentangle the tethers, corresponding to the specification $\omega=\sigma_{2}\sigma_{1}^{-1}\sigma_{2}\sigma_{1}^{-1}$ . The top plot shows the trajectories under the D-WMPC controller, the bottom one those generated by the GBC controller.

Figure 12: Input forces $F_{x}$ and $F_{y}$ , expressed in N, generated by the D-WMPC (left) and GBC (right) approaches to execute the trajectories of the experiment depicted in Figure 11 .

	Robot 1	Robot 2	Robot 3
D-WMPC	3.46	4.80	4.51
GBC	4.51	6.30	6.49

Table 4: Length of the trajectories of the ATMOS robots in the experiment depicted in Figure 11 , expressed in meters.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Figure 13: Maximum change in the relative heading between two robots over a time step. Two robots

i,j

are displayed, each moving of the maximum distance they can cover in one time step, i.e.,

v_{\mathrm{max}}\Delta t

Explore similar work

Denoising Multi-Robot Trajectories
Sep 28, 2026Yuhao Zhang, Keisuke Okumura, Ajay Shankar +1Multi-Robot Motion Planning Multi-Robot Systems
Department of Computer Science and Technology, University of Cambridge, U.K. · National Institute of Advanced Industrial Science and Technology (AIST), Japan
Simultaneous Arrival Control for Distributed Multi-Robot Systems with Curvature and Constant-Speed Constraints
Jul 16, 2026Zhouru Xiao, Yang Lu, Weijia Yao +2Multi-Robot Systems Queue Control
School of Artificial Intelligence and Robotics, Hunan University, China · College of Intelligence Science and Technology, National University of Defense Technology, China
Distributed Model-Based Diffusion For Scalable Multi-Robot Trajectory Optimization
Jul 23, 2026Haejoon Lee, Xinyi Wang, Taekyung Kim +1Multi-Robot Systems Multi-Robot Motion Planning
Robotics Department, University of Michigan, Ann Arbor, MI, USA

Sep 28, 2026, cs.ROJ/K move · Enter open · S save

Denoising Multi-Robot Trajectories

Yuhao Zhang, Keisuke Okumura, Ajay Shankar, Amanda Prorok

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 Multi-Robot Systems Denoising Diffusion Probabilistic Model

Open paper AskPDF arXiv

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 \textit{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

Abstract

Explore similar work

Denoising Multi-Robot Trajectories

Simultaneous Arrival Control for Distributed Multi-Robot Systems with Curvature and Constant-Speed Constraints

Distributed Model-Based Diffusion For Scalable Multi-Robot Trajectory Optimization