Simultaneous Multi-Robot Motion Planning with Projected Diffusion Models
Authors: Jinhao Liang
Jacob K Christopher
Sven Koenig
Ferdinando Fioretto
Venue: ICML 2025 poster (2025)
Keywords: Multi-Agent Path Planning
Diffusion Models
Primary area: deep_learning->generative_models_and_autoencoders
TL;DR: This paper presents a method combining diffusion models with constrained optimization techniques to generate feasible multi-robot trajectories in complex and highly constrained environments.

Abstract: Recent advances in diffusion models hold significant potential in robotics, enabling the generation of diverse and smooth trajectories directly from raw representations of the environment. Despite this promise, applying diffusion models to motion planning remains challenging due to their difficulty in enforcing critical constraints, such as collision avoidance and kinematic feasibility. These limitations become even more pronounced in Multi-Robot Motion Planning (MRMP), where multiple robots must coordinate in shared spaces. To address these challenges, this work proposes **S**imultaneous **M**RMP **D**iffusion (SMD), a novel approach integrating constrained optimization into the diffusion sampling process to produce collision-free, kinematically feasible trajectories. Additionally, the paper introduces a comprehensive MRMP benchmark to evaluate trajectory planning algorithms across scenarios with varying robot densities, obstacle complexities, and motion constraints. Experimental results show SMD consistently outperforms classical and other learning-based motion planners, achieving higher success rates and efficiency in complex multi-robot environments. The code and implementation are available at https://github.com/RAISELab-atUVA/Diffusion-MRMP.

Simultaneous Multi-Robot Motion Planning with Projected Diffusion Models
Jinhao Liang' Jacob K. Christopher'
Sven Koenig? Ferdinando Fioretto
Abstract
rescue, where robots must operate reliably in complex and highly constrained settings. Despite its importance, solving MRMP in real-world scenarios remains challenging due to the need to plan trajectories in continuous spaces and the un- structured nature of their inputs. These inputs often lack the structured representations needed by classical algorithms, which require implicit representation of both robot state spaces and obstacles in configuration spaces (La Valle, 2006; Ichter et al., 2018; Luo al., 2024). Consequently, classical approaches struggle to operate effectively in these high- dimensional environments ( (Wang et al., 2021; Teng et al., 2023). Specifically, sampling-ban -haeed planners often yield non-smooth paths due to their reliance on discrete connectiv- ity between sampled configurations (Carvalho et al., 2024). Optimization- methods suffer from similar issues, as they require computationally expensive trajectory refine- ments to enforce smoothness and feasibility (Ichnowski et al., 2020).
Recent advances in diffusion models hold signifi- cant potential in robotics, enabling the generation of diverse and smooth trajectories directly from raw representations of the environment. Despite this promise, applying diffusion models to mo- tion planning remains challenging due to their difficulty in enforcing critical constraints, such as collision avoidance and kinematic feasibility. These limitations become even more pronounced in Multi-Robot Motion Planning (MRMP), where multiple robots must coordinate in shared spaces. To address these challenges, this work proposes Simultaneous MRMP Diffusion (SMD), a novel approach integrating constrained optimization into the diffusion sampling process to produce collision-free, kinematically feasible trajectories. Additionally, the paper introduces a comprehen- sive MRMP benchmark to evaluate trajectory planning algorithms across scenarios with vary- ing robot densities, obstacle complexities, and motion constraints. Experimental results show SMD consistently outperforms classical and other learning- based motion planners, achieving higher success rates and efficiency in complex multi- robot environments. The code and implementa- tion are available at https: com/ AALIELaa-attWAADiifffuuic
To address these challenges, learning-basee methods offer a promising alternative by leveraging data-driven priors to handle unstructured environments. Recently, diffusion mod- els, a class of generative models originally developed for image and signal processing tasks (Song & Ermon, 2019; Ho et al., 2020), have shown promise for single-robot motion planning (Carvalho et al., 2023; Christopher et al., 2024). However, extending diffusion models to MRMP presents new challenges: while these models effectively produce di- verse trajectories, they fail to enforce hard constraints such as collision avoidance and kinematic feasibility, limitation that becomes increasingly significant in MRMP
1. Introduction
Existing diffusion-based approaches attempt to address these constraints through gradient- based guidance or re- jection sampling (Okumura et al., 2022b; Carvalho et al., 2023). However, gradicnt- based methods are prone to fail in such scenarios due the non-convex nature of collision avoidance constraints, complicating trajectory correction. Rejection sampling methods, conversely, suffer from ineffi- ciencies, discarding large portions of generated trajectories and struggling to generate feasible solutions in cluttered en- vironments (Carvalho et al., 2024; Christopher et al., 2024).
Multi-Robor Motion Planning (MRMP) is a fundamental problem in robotics and autonomous systems, where the goal is to compute collision-free paths for multiple robots navigating shared environments (Luo et al., 2024; Shaoul et al., 2025). MRMP has widespread applications, from autonomous vehicles to warehouse logistics and search-and-
'Department of Computer Science, University of Virginia. Char- lottesville, VA 22903, USA 'Department of Computer Science, University Californi, Irvine, CA 92697, USA. Correspondence to: Ferdinando Fioretto <fforetto@ <fioretto@virginia..du virginia.edu>>.
To address these limitations, this paper introduces Simulta- neous MRMP Diffiusion (SMD), novel approach that inte- grates constrained optimization directly into the diffusion
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Simultancous Multi-Robnn Robot Motion Planning with Projected Diffusion Models
Sampling diffusion steps
TT
0
project (a(
project
Ps
(induced trajectories)
Random trajectories
Collision-free trajectories
Figure 1. SMD incorporates projection operator enforce constraints within the diffuusin process. During sampling, the projection operator iteratively corrects trajectories by mapping them to the nearest feasible points, resulting in final collision-free freee paths. The infeasible paths marked with red circles and only occur in the initial random trajectory. In the experiments, the red objects appear at sampling time only, and the robots move from their start to their goal positions x.
sampling process to generate feasible multi-robot trajecto- ries. This work reformulates MRMP within a constrained diffusion framework, where diffusion-based trajectory gen- cration is guided by an Lagrangian-dual based method. This approach enables diffusion models to satisfy collision avoid- and kinematic constraints without post-hoc filtering, making them applicable even in high-density, unstructured environments. Unlike prior methods, which degrade sig- nificantly in cluttered scenarios, our framework maintains feasibility even as the number of robots and obstacles in- creases. The overall scheme illustrated in Figure 1.
2. Related Work
Motion Planning. Motion planning computes feasible path for robot move from its start to its goal state while avoiding obstacle collisions. Sampling-baser algorithms, such as Probabilistic Roadmaps (Kavraki et al., 1996) and Rapidly-Exploring Random Trees (RRTs) Valle, 1 1998) have been widely studied for this task. These methods guarantee probabilistic completeness but face significant scalability issues, especifically in multi-robot motion plan- ning (MRMP) the configuration space of MRMP scales significantly. Alternatively, MRMP can be formulated as constrained optimization problem, solving by optimization methods such as gradient optimization techniques (Ratliff et al., 2009) and sequential convex programming (Au- gugliaro et al., 2012; Chen et al., 2015). However, these approaches encounter difficulties when taking into account changes in acceleration (Ichnowski al., 2020) and usually too conservative to find any solution, even if one exists (Chen et al., 2015). Other lines of research focus on a discretized version of this problem, known as multi- agent path finding. Specifically, multi-agent path finding re- duces the configuration space by discretizing both time and space into steps and grids, respectively (Stern et al., 2019). This simplification has enabled the development of efficient search-based algorithms (Li et al., 2019; 2021; Okumura et al., 2022a). However, these assumptions create dis- connect from real-world applications due to their oversim- plification (Shaoul et al., 2025). Unlike these approaches, this paper develops SMD, a diffusion-based MRMP frame-
Contributions. The paper makes the following contribu- tions: (1) It introduces Simultaneous MRMP Diffusion (SMD), which formulates multi-robot trajectory generation as constrained diffusion process, ensuring collision-free and kinematically feasible motion plans. (2) It integrates constrained optimization directly into the sampling process of diffusion models, enabling the direct embedding of con- straints within the trajectory generation pipeline. (3) It develops Lagrangian-dual based method reformulate the MRMP problem, dramatically improving the efficiency with these critical constraints can be satisfied during dif- fusion sampling, both theoretically and empirically. (4) Finally, it introduces the first benchmark for MRMP evalu- ation, featuring complex input maps and diverse scenarios. Our approach demonstrates significant improvements over competing methods, particularly in environments with dense obstacles and unstructured configurations.
2

---

Simultancous Multi-Robor Robii- Motion Planning with Projected Diffusion Models
work that directly learns the distribution of collision-free paths and generates feasible solutions for multiple robots simultaneously in complex environments.
This score function is trained minimize
min (. g(m:|=00)
E
(1-0+)
|150 () - Var, log ( ( )
Motion Planning with Generative Models. Recent ad- vancements in generative models have opened new avenues for solving motion planning problems by learning complex, nigh-dimensional distributions of feasible paths. For exam- ple, Okumura al. (2022b) employed a conditional varia- tional autoencoder to predict cooperative timed roadmaps. Following the introduction of diffusion models into mo- tion planning by Janner et al. (2022), subsequent research has largely focused on using gradient- based methods to guide the outputs of diffusion models toward feasible solu- tions (Carvalho et al., 2023; Luo et al., 2024; Saha et al., 2024; Ubukata et al., 2024; Carvalho et al., 2024; Naderi- parizi et al., 2025). These works design tailored cost func- tions to guide the generation of diffusion models during the sampling process. Although these approaches leverage the ability of diffusion models to generate diverse trajec- tories, they are unable to ensure constraint satisfaction in scenarios with complex environments and multiple robots. In fact, most existing work has primarily addressed single- robot motion planning. leaving multi-robot motion planning underexplored. Recently, Shaoul et al. (2025) combined diffusion models with search- multi-agent path finding algorithms, where the diffusion models generate trajectories for a single robot, and a search-based algorithm determines the final trajectories for multiple robots. While this is a substantial contribution towards MRMP, it does not ensure the feasibility of the trajectories generated by diffusion mod- els, particularly in environments with dense obstacles or complex robot interactions. In contrast, our proposed SMD directly integrates optimization techniques into the diffusion process, enabling the generation of feasible MRMP trajec- tories even in scenarios with a significant number of robots and obstacles.
and is then used to iteratively "denoise" random noise sam- ples back into data-like samples. This also known as the sampling phase.
Multi- Motion Planning. Hulti-Robot Motion Plan- ning (MRMP) involves computing collision-free trajecto- ries for multiple robots navigating a shared environment from designated start positions to goal states. Consider a set of N₂ robots AA = {a1, ag...., ON.) operating in continuous workspace. Each robot o; modeled as sphere with radius r; > 0 and has a trajectory over H time steps denoted by л,, = x?? T²",, where Th = (r..."" E R represents the robot's states at time h. For each robot, their start and target states are defined, respectively by sets B = [bi, ba,.b,,bbyy and eN.l- The robots must navigate around
E = No obstacles O for..... oN.} while adhering to kine- matic constraints such as velocity and acceleration limits.
The objective is to compute feasible set of trajectories II = { 1, 2...... π N. }, that minimizes predefined cost function while ensuring feasibility to environmental con- straints and inter-robot collision avoidance. Formally,
min II
III]
(1a)
s.t.
I lobs:
(1b)
Vi E [Na], : = b,,
(1c)
H Eis
Vi e [Na],
(Id)
Kinematic constraints on II,
(1e)
Collision avoidance between robots in II,
(1f)
3. Preliminaries
where J Na + R+ represents the cost function,
which may include objectives such as total travel time or en- ergy consumption, and Robs is the feasible region, excluding obstacle-occupied space. Constraints (1b) ensure that robots avoid obstacles, (Ic) and (1d) ensure that each robot starts at its initial position and reaches its target position. (Ic) enforce kinematic limits, defined by a maximum reachable velocity, and (1f) ensures collision avoidance, maintaining a minimum Euclidean separation between robots at all time steps. Subsequently, we denote constraint set (Ib)-(1f) with Ω.
Score-based Diffusion Models. Generative diffusion models (Sohl-Dickstein et al., 2015; Ho et al., 2020) pro- duce high-fidelity complex data operating in two phases: A forward step, that gradually introduce noise to clean data samples, followed by a reverse denoising step, in which deep neural network is trained to iteratively remove noise. This forward process defines a Markov chain {z with initial sample 4.p ~ p(æ0) and each transition (( (2;-1) realized by adding Gaussian noise according to a variance schedule at In score-bore based diffusion (Song& & Ermon, 2019; Song et al., 2020), the reverse process relies on a learned score function so (x., t) Vz, log p(æ:)) that approximates the gradient of the log probability density of the noisy data.
The MRMP problem poses significant challenges due to the difficulty of representing and navigating unstructured, high-dimensional configuration spaces and coordinating dy- namic interactions among multiple robots in continuous environments (Stern et al., 2019; Shaoul et al., 2025).
3

---

Simultancous Multi-Robol Motion Planning with Projected Diffusion Models
4. Simultaneous MRMP Diffusion
A key theoretical advantage of this approach is that retains the convergence guarantees of langevin-based sampling. Specifically, this constrained diffusion process converges to an "almost-minimizz" of the objective function (2a), where the approximation quality is bounded by the noise term z and the Langevin step size 7/2 (Xu et al., 2018).
To address these challenges, this section introduces Simulta- neous MRMP Diffusion (SMD), a diffusion method for MRMP. We start by introducing the concept of repeated projections, which constitutes core building block of SMD. Then, the section discusses how to integrate the multi-robot motion planning constraints into the diffusion framework and, finally, how to enable effective sampling in complex, high-dimensional MRMP tasks. A theoretical analysis is also provided establish the feasibility guarantees of SMD.
Importantly, as shown in (Christopher et al., 2024), this pro- cess guarantees that the generated outputs satisfy constraints from convex sets under mild conditions.
4.2. Collision-free Projection Mechanism
4.1. Repeated Projections.
While the application of repeated projections provides use- ful primitive steer samples generated by diffusion models to satisfy relevant constraints, projecting onto the space of collision-free and kinematically viable trajectories presents a critical challenge due to the nonconvex nature of these con- straints and the high dimensionality of the problem. These issues make the standard application of repeated projections ineffective in solving even simple MRMP instances. The following first presents the projection mechanism for SMD, which aims to generate feasible trajectories for all robots in the problem.
Incorporating constrained optimization techniques into gen- erative models has been an important direction in ensur- ing feasibility in structured domains. Diffusion models inherently use a variant of Langevin Monte Carlo sampling, known as Stochastic Grudient Langevin Dynamics (SGLD), for their denoising sampling process. SGLD introduces additional stochastic perturbation to pradient-based updates, resulting in a non-eeterministic version of natural gradient descent. This allows to from getting trapped local min- ima and enables diverse sampling trajectories (Welling & Teh, 2011). Given this perspective, the diffusion sampling process can be viewed as iterative unconstrained opti- mization problem aimed at maximizing the liglliiel of the true data distribution.
Note that the feasible region Ω for the MRMP problem can be represented by distinguishing between convex and nonconvex constraints. This distinction will be useful later to provide an accelerated version of the projection operator introduced above.
Building upon this understanding from Christopher et al. (2024), we can extend the standard diffusion process by incorporating feasible region f2:
Convex Constraints. First, note that each robot's trajec- tory must begin and end at its designated start and goal locations, as enforced by Constraints (Ic) and (Id). Ad- (2a) ditionally, robots must respect maximum velocity limits between consecutive time steps:
min X
Σ
log (x)
s.t.
XT,
Xu E S
(2b)
(Tt² -ー² < (u.nax At)², ViE
H). (5)
To enforce these constraints during the generative process, it is possible to modify the standard Stochastic Gradient Langevin Dynamics (SGLD) update rule by introducing projection step after each iteration:
where eguax represents the maximum allowable velocity for robot a,, and At is the time interval between steps. Together, these constraints define convex set:
Ωe II E R xxx Constr. (Ic), (Id), and (5) hold]
Pa x To V ((x, + 22
(3)
Nonconvex Constraints. To ensure collision-avoidame the following nonconvex constraints must also be imposed:
classic reverse process
where z is standard normal, "t 0 is the step size, Ux; log ((x]/xx)) xx) is approximated by the learned score func- tion So (x,, t), Ω is the set of constraints, and Prt(-) is projection onto Ω2:
(T --'-- 2 (R*)?, Vi, i # j [Na], h (H], (6)
where R2 denotes the minimum distance between robots at any time. The above states that any two robots should be far enough from each other at any point in the trajectory.
(x( arg min ||x x' x21
(4)
x' ES?
Similarly, the following constraints are imposed to avoid collisions between each robot and static obstacles:
At each time step t, starting from xf. the process performs M iterations of SGLD.
(T - -,,= (2 Vi E [Na], Vj. [No], [M], (7)
4

---

Simultancous Multi-Robol Motion Planning with Projected Diffusion Models
Algorithm 1 Diffusion Sampling Process in SMD
enforeing inter-robot collision avoidance and obstacle avoid- ance, respectively. While the standard Lagrangian formu- lation provides means of incorporating constraints into the optimization process, it suffers from slow convergence due to the instability of dual variable updates, particularly in nonconvex settings. To mitigate these issues, we adopt the augmented Lagrangian method (Boyd et al., 2011; Ko- tary et al., 2022) to improve the convergence performance. which introduces additional penalty terms on the constraint residuals:
1: Input: Gaussian Noise x
2: for = T+++ do
3: Initialize 7/e
4: for: = M do
5: Sample N/
6: Compute g s0(x; 1xxxx1111 .))
7: Update xi < Px ng + 22722)
8: end for
9: xf_11 < x
10: end for
Va, J (II
11:
Output: X
V. Ha (II) + Ho (II) + Pa H. (II) + Pol H. (II)1
+ v.
where oj is the position of obstacle j and R denotes the minimum distance at which robot must be to avoid obstacle. Together, these constraints define nonconvex ser:
where Pa and Po are penalty parameters that control the strength of the constraint enforcement. These penalties improve numerical stability by discouraging constraint vio- lations in early iterations, accelerating convergence.
2n II IR X Constr. (6), (7), hold):
and the complete feasible set is given by: Ω = Qe nnn
The corresponding Lagrangian dual function can thus be defined by:
The detailed algorithm is shown in Algorithm 1. Notably, the SMD framework allows straightforward incorporation of additional constraints, such as acceleration bounds or trajectory smoothness, by introducing these to the feasible set f2.
d(va: vo) = min C(II, Va; vo).
II
and associated Lagrangian Dual Problem is defined as max- imizing the dual function:
4.3. Lagrangian Relaxation for Efficient Projections
arg max ((Vayoo) V.
S.t. II Sg.
(10)
Although solving Pa(x)) can generate feasible trajectories, the nonconvex nature of the constraint set above results in high computational costs. To address this issue, we propose relaxation of the nonconvex constraints in MRMP (Boyd et al., 201 1) to vastly enhance the tractability of projections onto a MRMP feasible set. Following standard practices in constrained optimization, we transform inequality con- straints into equality constraints using non-negative auxil- iary variables (Kotary& & Fioretto, 2024). This simplifies multiplier updates and improves convergence:
Through weak duality, maximizing (10) provides lower bound on the optimal objective value of the primal MRMP problem. Even in cases where strong duality does not hold (e.g., as in the application context studied in this work), minimizing the duality gap allows for near-optimal feasible solutions to be obtained. Given the optimal dual variables (v", a. 1y),, a primal solution I' can be obtained by solving:
A = arg min NeR.
C(IL.V",
Ha : - -2 di (R²)² = 0, Vi,j, i Ah, Ho :(x! - 00 d. (Ro)2 0, Vi Yh.
This follows from the stationarity condition, where optimiz- ing the augmented Lagrangian function with fixed multipli- ers yields the best feasible solution.
where di and di,,.. (with vector form d' and do re- spectively) are positive auxiliary variables. Specifically, H. corresponds to the robot collision avoidance constraints and Ho to the obstacle collision avoidance constraints.
Crucially, the dual problem (10) can be solved iteratively, by employing an adaptation of a Dual Ascent method (Boyd et al., 201 1):
The Lagrangian function of the MRMP problem thus defined as:
II = arg min NeR.
C(II, & (.)
(12a)
C(II, vo, = [II] + + T. (II) +2 H. + (II), (9) where (III represents the objective function, which typi- cally finds the nearest feasible point to the input in the pro- jection, as shown in Eq. 4. Va and vo are Lagrangian mul- tipliers, and H. and H. represent the equality constraints
w k+1 = 4º + p Ha (II*).
(12b)
A+1 2 P k H.ll (II)).
(12c)
At each iteration, the primal variable II is updated by min- imizing the augmented Lagrangian, and the dual variables
5

---

Simultancous Multi-Robot Motion Planning with Projected Diffusion Models
Algorithm 2 Efficient Projection Operator for SMD
output of the projection operator II:
1: Input: Tolerance da and 6G, Weight p. Initial Trajectory
HH (T)) S da, |[Ho(TT)| S &o.
II, scaling factor Ç
2: while Vv. < 5g and Vv. < <ōo do
for some tolerances 8,: 6, > 0.
3: Da < Ha (TI, i0 < -IT
4:
II + arg minnee. V(.
5. Experimental Settings
5: Vv. + Ha (II), Vv. + (II
6: P pxp
This section describes the evaluation methodology for Multi- Robot Motion Planning algorithms,, detailing the benchmark maps, task assignment process, and performance metrics. To ensure a comprehensive evaluation, this paper also intro- duces new benchmark instances set that captures variety of real-world MRMP challenges (released as supplemental material).
7:
end while
8: Output: II
Va: V, are updated via a gradient ascent step on the con- straint residuals. This approach enables the generation of collision-free and kinematic viable trajectories for multi- ple robots, especially in complex scenarios. The efficient projection process is described in Algorithm 2.
Maps. We evaluate MRMP algorithms on both randomly generated and real-world-inspired maps.
Random maps include environments with increasing lev- els of complexity: empty maps test inter-robot collision avoidance in open spaces; basic maps introduce 10 obsta- cles, requiring navigation within the feasible region that excludes obstacle obstacles, significantly restricting movement and increasing planning difficulty. The progression from empty to dense maps allows us to systematically assess the algorithms on spatial constraints and coordination.
4.4. Theoretical Analysis for SMD
Building on our earlier discussion of how the repeated pro- jection mechanism ensures convex constraint satisfaction, we now present a more detailed theoretical justification of our proposed SMD for MRMP. The key insight is SMD can provide feasible trajectories for MRMP by introducing the Lagrangian relaxation method. Although the full MRMP problem is nonconvex, we leverage the constraint structure to control violations during each projection step.
areas: dense maps contain 20
Practical maps simulate real-world environments such as warehouses and buildings, where constrained pathways and structured layouts impose additional planning challenges. Corridor maps replicate narrow passages where robots must coordinate movements to pass each other without dead- locks. Shelf maps mirror warehouse storage layouts with tight aisles, requiring precise navigation. Room maps in- troduce multiple rooms connected by doors, restricting the number of robots that can enter at the same time and requir- ing careful scheduling to prevent congestion. Compared to random maps, practical maps emphasize not only collision avoidance but also global coordination, as robots must find feasible routes through constrained spaces.
For simplicity, we conduct our analysis on the standard Lagrangian formulation in Eq. (9), as the augmented La- grangian method mainly enhances the convergence of the original Lagrangian relaxation. Before proceeding, we make the following assumptions commonly satisfied in MRMP formulations.
Assumption 4.1. The cost function of relaxed MRMP CIII, Va: vo) is continuously differentiable and convex over the convex set Ωo-
Proposition 4.2 (Convex Feasibility Guarantee). Let II be the trajectory output by the projection operator (II within the diffusion step of SMD. Suppose that Assump- tion 4.1 holds. Then, the generated trajectory II satisfies
Each scenario includes 25 maps with different obstacle con- figurations.
dist(II, 2te) SE
Task assignment. Start and goal states are assigned dif- ferently for random and practical maps. In random maps, they are placed at feasible positions without collisions (see Figure 2), while in practical maps, they are constrained to predefined zones that reflect real-world constraints, such as pickup and drop-off locations in warehouses (see Figure 3). We conduct experiments with 3, 6, and 9 robots, generat- ing 10 test cases for each configuration, except for corridor maps, where we use 2 robots.
where dist(-) denotes the distance between the trajectory II and the feasible region Qo and E 2 O can be made arbitrarily small.
Remark 4.3. This proposition provides theoretical guar- antee that our SMD can ensure the feasibility for convex feasible set Ω. by introducing Lagrangian relaxation meth- ods. In addition to the convex constraints, SMD handles nonconvex constraints defined by functions H. (II) and Ho. (II) via a dual ascent method with the user-defined stop- ping criterion 5, and 5.- Specifically, SMD ensures the
Evaluation metries. MRMP algorithms are assessed based on their ability to generate collision-free free, efficient, and
6

---

Simultancous Multi-Robun Motion Planning with Projected Diffusion Models
Robots
6 Robots
Robocs
Empty
1.0-
N/A
1-12
Success Rate
0.5-
(a) Empty Maps.
(b) Basic Maps.
(c) Dense Maps.
Basic
Figure 2. Examples of random maps used for MRMP experiments, with increasing complexity. Colorful spheres and plates denote the start and goals of robots. White objects indicate obstacles.
Success
0.55
0.0
Dense
NiA NDA NIA
1.00 NIA
3,01
0.0
DM
MPD
MMD
SMD
(a) Corridor Maps.
(b) Shelf Maps.
(c) Room Maps.
Figure 4. Results for each method random maps with three different numbers of robots. Gray bars represents the failure rate, and values on top the bars indicate average path length per robot.
Figure 3. Examples of practical maps used for MRMP experiments
show different practical challenges in MRMP.
6. Experiments
smooth trajectories. Success rate measures the percentage of test cases solved without collisions. Path length evaluates the average travel distance per robot, reflecting efficiency. Acceleration quantifies trajectory smoothness, with lower values indicating reduced energy consumption and smoother motion. Collision ratio measures the proportion of robots that experience collisions, providing insight into the robust- ness of the planning method. These metrics collectively assess feasibility, efficiency, and safety in MRMP.
In this section, evaluate the performance of various MRMP algorithms using proposed benchmark. In most cases, regular projection methods cannot be applied to ob- tain solutions in MRMP due to the huge computational burden (hence, our omission Christopher et al. (2024) as baseline). Thus, for our implementation of SMD, we use the projection with the Lagrangian relaxation method for our experiments, except for the narrow-corride map. The imple- mentation details can be found in Appendix A. Additional experimental results are presented in Appendix C, including the performance of classical algorithms, additional evalua- tion metrics, runtime comparisons, sensitivity analysis of projection parameters, and results on other map types.
Competing Methods. We compare our proposed SMD against the following learning-basee baseline methods:
1. Diffusion Models (DM): We adopt standard diffusion models trained over the feasible trajectories to address MRMP directly (Nichol & Dhariwal, 2021).
6.1. Performance on Random Maps
2. Motion Planning Diffusion (MPD): The state-of-Ne sate-off-he--rr tttthh-art art motion planning diffusion model for single robots (Car- valho et al., 2023), which we extend to handle MRMP for comparison.
We first showcase the methods' performance on random maps. Figures 4 compares the success rate and path length for all methods for settings of increasing complexity and three configurations (3, 6. and 9 robots).
Multi-robot Motion Planning Diffusion (MMD): A re- cently introduced solution that combines diffusion mod- els with classical search-based techniques- eechniqes--generaaing MRMP solutions under collision constraints (Shaoul et al., 2025).
First, notice that the Standard Diffusion Model (DM) is un- viable for MRMP tasks. Despite reporting reasonable success rate (78%) for robots in empty maps, when simple obstacles are introduced, the success rate falls dramatically (5%). Additionally, DM fails to produce any feasible tra- jectory when scaling six or nine robots, even in empty
We also compare our proposed approaches with classical algorithms in Appendix C.
7

---

Simultancous Multi-Robbe Motion Planning with Projected Diffusion Models
Robots
N/A
N/A
NíA
1.66
Success Rate
1.0
0.5
0.0
VDM
MPD
MMD
SMD
(a) Basic Maps.
(b) Dense Maps.
(a) Results.
(b) Trajectories.
Figure 5. Trajectories generated by SMD random maps.
Figure 6. Results for each method on corridor maps. Gray bars represents failure rate, values on top of the bars indicate average path length per robot.
maps.
Next, we focus on Motion Planning Diffusiin (MPD). While it reports near-perfect success rates for the 3-robots setting (the smallest in our benchmark), this approach highly ineffecttve when scaled to additional robots. In empty envi- ronments, MPD reports 35% success rates with six robots and it fails to synthesize any feasible trajectory when ob- stacles are introduced to the map when scaling to nine robots.
ing yet commonly occurring real-world scenarios.
In corridor maps, Figure 6(a) shows that our SMD achieves perfect success rate, whereas all other methods fail to report even single feasible trajectory. In restrictive envi- ronments like this, robots need to swap their positions in a specific area to achieve their goals, as their initial relative po- sitions are opposite to their goals positions, and the narrow corridors do not allow direct position exchange. In this case, the gradient-basee guidance used by MPD in the diffusion sampling process prone failure, as cannot globally coordinate different robots to reach their respective goals. Although MMD uses multi-agent path-finding algorithms to account for goal-reasoning, it still relies on gradient-based guidance to generate trajectories. The penalty term em- ployed by this method during gradient computation is thus insufficient to produce feasible solutions in such regions. In contrast, our reformulation of the diffusion sampling process constrained optimization problem confers the ability to ensure feasibility in the generated trajectories. As shown in Figure 6(b), the trajectories generated by our SMD allow the two robots to use the only slightly wider area to swap their positions.
Multi-robot Motion Planning Diffussion (MMD) represents the current state-of-the-ar method for MRMP. This method outperforms other baselines its ability to handle an in- creased number of robots. For instance, it reports non-zero success rates for up nine robots. However, there remains steep performance drop with the increasing number of robots. For instance, it reports success rate of 27% in dense maps for 9 agents. A similar decrease in constraint satisfaction occurs for in other scenarios besides the empty maps.
In contrast, Sinultaneous MRMP Diffusion (SMD) provides new state-of-the-art results for both constraint satisfaction and path length. Unlike other methods whose success rates rapidly decline as robot and obstacle numbers grow, SMD maintains feasibility in scenarios with increased robot and obstacle counts (e.g., dense maps with 9 robots and 20 obstacles). Specifically, SMD the only known method that provides feasible solutions for the largest number of robots in complex environments. SMD reports perfect success rates and collision ratios for all tasks except the most complex maps (dense environments) and 9 robots. Even in the most challenging dense maps, where it still provides near-perfect results (96% successful). This is a 3.6x improvement over the previous state-of-the tfthear-t---rr. Sample trajectories generated by SMD are visualized in Figure
We also evaluate on shelf maps and room maps, both of which contain narrow passages that must be traversed to reach the goals. Figure 7 shows that MPD and MMD achieve similar success rate (60%) when there are only three robots in shelf maps, and MPD even provides shorter paths. However, it quickly fails to provide feasible solu- tions as the number of robots increases, even slightly. SMD again achieves perfect success rate for three robots, and it only experiences slight decline as the number of robots increases (90%). SMD also reports the shortest paths among all methods. Similarly, room maps report SMD achieving perfect success rate for 3 and 6 robots and above 90% when scaling up to 9 robots. In contrast, MPD and MMD fail to produce feasible trajectories as the number of robots increases. these maps, SMD advantage over the baselines
6.2. Performance on Practical Maps
Practical maps are designed to evaluate the ability of the methods to generate feasible trajectories for more challeng-
8

---

Simultancous Multi-Robol Motion Planning with Projected Diffusion Models
Robots
Rohots
Robots
rigid methods. For instance, such architectures are ideal for handling unstructured environments with dense obstacles, dynamic changes, and uncertain sensor inputs, where tradi- tional methods struggle to adapt but may be unnecessary in structured or open spaces.
Shelf
1.0
0.70 N/A NIA
NIA
0.94 0.95 0:33
0.50 L
Suceess Rato
0.0
8. Conclusion
Room
1.0
NIA NIA NIA
1.14 NIA NIA
1.27 1:27 N/A
1.19 1.30 13
This work introduced Simultaneous MRMP Diffusion (SMD), method that integrates constrained optimization with generative diffusion models to generate collision-free, kinematically feasible trajectories for multi-robot systems. By alternating diffusion sampling with projections onto the feasibility set, SMD eliminates the need for rejection sam- pling or post-pree post-processing. To handle complex nonconvex con- straints, the paper incorporates an Augmented Lagrangian Method enabling scalability to challenging multi-robot narios where other methods fail. To support rigorous evalu- ation, benchmark was also introduced, covering environ- ments that reflect real-world motion planning challenges. Extensive experiments across varying obstacle densities and increasing robot counts demonstrated that SMD achieves significantly higher success rates and better objective values than competing methods. The results highlight its robustness in handling both static obstacles and dynamic interactions, making it promising approach for real-world applications.
Sueces Rate
0.0
DM
MPD
MMD
SMD
Figure 7. Results for each method practical maps with three different numbers of robots. Gray bars represents the failure rate, and values top of the bars indicate average path length per robot.
There are several promising directions for future work. Ex- tending SMD to more complex scenarios, such as 3D en- viromments and humanoid locomotion is very promising. Furthermore, the extension of SMD to decentralized set- tings still remain be explored.
(a) Shelf Maps.
(b) Room Maps.
Figure 8. Trajectories generated by SMD on practical maps.
A Acknowledgments
even noticeable. These results shows the adaptabil- ity of the proposed algorithm to multiple environments and challenging scenarios (such as the narrow passages).
This research is partially supported by NSF grants 2334936, 2334448, and NSF CAREER Award 2401285. The research at the University of California, Irvine was supported by the NSF grants 2434916, 2346058, 2321786, 2121028, and 1935712, as well as gifts from Amazon Robotics. The au- thors acknowledge Research Computing at the University of Virginia for providing computational resources that have contributed to the results reported within this paper. The views and conclusions contained this document are those of the authors and should not interpreted as represent- ing the official policies, either expressed implied, of the sponsoring organizations, agencies, or the U.S. govermment.
Finally, Figure 8 provides two illustrative cases for shelf maps (a) and room maps (b) where SMD is the only method across those tested able to generate feasible solutions. A common characteristic of these two instances is that multiple robots need to pass through the same narrow passage, scenario frequently encountered in real-world applications.
7. Discussion and Limitations
While SMD provides Kate-of-the-art results for MRMP tasks, consideration should be given to the appropriate ap- plications of this approach. First, generative models incur inference-time costs that should be considered when ap- plying these models to motion planning. Diffusion models are most advantageous in scenarios where the complex- ity of the environment and the need for multimodal trajec- tory generation outweigh the benefits of faster but more
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.

---

Simultancous Multi-Robol Motion Planning with Projected Diffusion Models
References
Kotary, J. and Fioretto, F. Learning constrained optimization with deep augmented lagrangian methods. arXiv preprint arXiv: S.Kiv:24033034333 2024.
Augugliaro, F., Schoellig, A. P., and D' D'Andrea, R. Gen- eration of collision-free trajectories for a quadrocopter fleet: A sequential convex programming approach. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 1917-1922, 2012. doi: 10.1109/ IROS 2012.6683.....
Kotary, J., Fioretto, F., and Van Hentenryck, P. Fast approxi- mations for job shop scheduling: A lagrangian dual deep learning method. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pp. 7239-7246, 2022.
Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J., et al. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends@ in Machine learning. 3(1):1-122, 2011.
LaValle, Rapidly-exploring random trees: A new tool for path planning. Research Report 9811, 1998.
LaValee, M. Planning algorithms. Cambridge university press, 2006.
Carvalho, J., Le, A. T., Baierl, M., Koert, D., and Peters, J. Motion planning diffusion: Learning and planning of robot motions with diffusion models. In 2023 IEEE/RSJ International Conference on Intelligent Robots and Sys- tems (IROS), pp. 1916-1923. IEEE, 2023.
Li, J., Felner, A., Boyarski, E., Ma. H., and Koenig, S. Improved heuristics for multi-agent path finding with seflict-based search. In ICCAI, volume 2019, pp. 442- 449, 2019.
Carvalho, J., Le. A., Kicki, P., Koert, D., and Peters, J. Motion planning diffusion: Learning and adapting robot motion planning with diffusion models. arXiv preprint arXiv:2412.19945 2024.
Li, J., Ruml, W., and Koenig, S. Eecbs: A bounded- suboptimal search for multi-agent path finding. In Pro- ceedings of the AAA/ conference on artificial intelligence, volume 35, pp. 12353-12362, 2021.
Chen, Y., Cutler, M., and How, J. Decoupled multi- agent path planning via incremental sequential convex programming. In 2015 IEEE International Conference on Robotics and Automation (ICRA), pp. 5954-59551 2015. doi: 10.1 019//CRA.201..714000
Luo, Y., Sun, C., Tenenbaum, J. B., and Du Y. Po- tential based diffusion motion planning. In Forty- first International Conference on Machine Learning. 2024. URL https:: wttp//ppeevveeeeeee/ee wtt.eeww.eee/.rrreeeeeeeeee id=Qb68Rs0p9f.
Christopher, J. K., Back, S., and Fioretto, F. Constrained synthesis with projected diffusion models. In The Thirty- eighth Annual Conference on Neural Information Pro- cessing Systems, 2024.
Naderiparizi, S., Liang, X., Zwartsenberg, B., and Wood, F. Constrained generative modeling with manually bridged diffusion models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pp. 19607-19615, 2025.
Ho. J., Jain, A., and Abbeel, P. Denoising diffusion proba- bilistic models. Advances in neural information process- ing systems, 33:6840-668 68510 2020.
Nichol, A. Q. and Dhariwal, P. Improved denoising diffu- sion probabilistic models. In International conference on machine learning, pp. 1162-8171. PMLR, 2021.
Ichnowski, J., Avigal, Y., Satish, V., and Goldberg, K. Deep learning can accelerate grasp-optimized motion planning. Science Robotics, 5(48) 2020.
Okumura, K., Machida. M., Défago, X., and Tamura, Y. Priority inheritance with backtracking for iterative multi- agent path finding. Artificial Intelligence, 310:103752, 2022a.
Ichter, B., Harrison, J., and Pavone, M. Learning sampling distributions for robot motion planning. In 2018 IEEE International Conference on Robotics and Automation (ICRA), pp- 7087-7094, 2018. doi: 10.1109//CR.22018 8460730.
Okumura, K., Yonetani, R., Nishimura, M., and Kanezaki, A. Ctrms: Learning to construct cooperative timed roadmaps for multi-agent path planning in continuous spaces. In Proceedings of the 21st International Con- ference on Autonomous Agents and Multiagent Systems, 2022b.
Janner, M., Du, Y., Tenenbaum, J. B., and Levine, S. Plan- ning with diffusion for flexible behavior synthesis. In International Conference on Machine Learning, 2022.
Kavraki, L.,, Svestka, P., Latombe, J.-C., and Overmars, M. Probabilistic roadmaps for path planning in high- dimensional configuration spaces. IEEE Transactions on Robotics and Automation, 12(4):5665580 1996. doi:
Ratliff, N., Zucker, M., Bagnell, J. A., and Srinivasa, S. Chomp: Gradient optimization techniques for efficient motion planning. In 2009 IEEE international conference on robotics and automation, pp. 489-494, IEFF, 2009.
10. 109/9.5008439
10

---

Simultancous Multi-Robnn Robttt Motion Planning with Projected Diffusion Models
Saha, K., Mandadi, V., Reddy, J., Srikanth, A., Agar- wal, A., Sen, B., Singh, A., and Krishna, M. Edmp: Ensembleeof-coost--uuded diffusion for motion planning. In 2024 IEEE International Conference on Robotics and Automation (ICRA), pp. 10351-10358, 2024. doi:
1 1061059....
Shaoul, Y., Mishani, I,, Vats, S., Li, J., and Likhachev, M. Multi-robot motion planning with diffusion models. In The Thirleenth International Conference on Learning Representations, 2025.
Sohl-Dickstein, J.. Weiss, E., Maheswaranathan, N., and Ganguli, S. Deep unsupervised learning using nonequi- librium thermodynamics. In International conference on machine learning, pp. 2256-2265. PMLR, 2015.
Song, Y. and Ermon, S. Generative modeling by estimating gradients of the data distribution. Advances in neural information processing systems, 32, 2019.
Song, Y., Sohl-Dickstein, J., Kingma, D. P., Kumar, A., Er- mon, S., and Poole, B. score-based generative modeling through stochastic differential equations. arXiv preprinl arXiv:2011.13455 2020.
Stern, R., Sturtevant, N., Felner, A., Koenig, S., Ma, H., Walker, T., J., Atzmon, D., Cohen, L., Kumar, T., al. Multi-agent pathfinding: Definitions, variants, and bench- marks. In Proceedings of the International Symposium on Combinatorial Search, volume 10, pp. 151-158, 2019.
Teng, S., Hu, X., Deng, P., Li, B., Li, Y., Ai, Y., Yang, D., Li, L., Xuanyuan, Z., Zhu, F., and Chen, L. Motion planning for autonomous driving: The state of the art and future perspectives. IEEE Transactions on Intelligent Vehicles, 8(6))3692-3711, 2023. doi: 10. (0.1109/TT/220233377455
Ubukata, T., Li, J., and Tei, K. Diffusson model for plan- ning: A systematic literature review. arXiv preprint arXiv:2408. 10266, 2024.
Wang, J., Zhang, T., Ma. N., Li, Z., Ma, H., Meng, F. and Meng, M. Q.-.. A survey of learning-basee based robot motion planning. IET Cyber-Systems and Robotics, 3(4): 302-314, 2021.
Welling, M. and Teh, Y. W. Bayesian learning via stochastic gradient langevin dynamics. In Proceedings the 28th international conference on machine learning (ICML-I1),
pp. 681-688. Citeseer, 2011.
Xu, P., Chen, J., Zou, D., and Gu, Q. Global convergence of langevin dynamics based algorithms for nonconvex optimization. Advances in Neural Information Processing Systems, 31, 2018

---

Simultancous Multi-RRbot Motion Planning with Projected Diffusion Models
A. Implementation Details
Software:
The software used for experiments is Rocky Linux release 8.9, Python 3.8, Cuda 11.8, and PyTorch 2.0.0. Hardware: For each of our experiments, we used 1 AMD EPYC 7352 24-Core Processor and 1 NVIDIA RTX A6000 GPU.
A.1. MRMP Details
In our experiments, the size of each local map was 2 x units. The robot radius was set to 0.05 units all cases, except for the corridor map, where it was 0.1 units. The obstacle sizes in random maps varied between 0.05 and 0.1 units.
To adopt the EECBS algorithm, discretized the map into grid with cell size of 0.1 units, which corresponds the robot's ' diameter. If an obstacle present within grid cell, the cell was marked as an obstacle. The robot's 'ss starting position was determined by the grid cell in which its center was located.
A.2. Training Details
Our implementation builds upon the official code of Carvalho et al. (2023) and Shaoul et al. (2025), with modifications to accommodate our specific requirements. Since MMD can be trained with single-robot motion planning data, we first trained it accordingly. Then, by running MMD, we obtained the feasible solutions of MRMP it generated and used them as training data. Table shows the hyperparameters used for training the score-based diffusion models in our experiments.
Table 1. Hyperparameters for Training in Experiments.
HyperParameters
Value
Diffusion Sampling Step
25
Learning Rate
le-4
Batch Size
64
Optimizer
Adam
A.3. Evaluation Details
We conducted experiments on six types of maps, each with 25 different parameters, such as obstacle size and positions. For all map types except corridor maps, we evaluate three different numbers of robots (3, 6, and 9). corridor maps, only two robots are tested. For each number of robots, we generate 10 test cases, resulting in 4,000 test instances for each method.
Table Summary MRMP Benchmark Instances
Obstacle
Number of Robots
Start & Goal
Number of Instances
Map Type
Variations
Variations
Variations
Empty Maps
25
3
10
750
Basic Maps
25
3
10
750
Dense Maps
25
10
750
Corridor Maps
25
10
250
Shelf Maps
25
10
750
Room Maps
25
10
750
Total
4000
For each generated path, we first check for collisions and compute the success rate each method. For collision- freee cases, we analyze path length and acceleration. For cases with collisions, we report the collision ratio. If method fails to generate a feasible solution, its path length and acceleration are excluded from the statistical analysis.
12

---

Simultancous Multi- Robott Motion Planning with Projected Diffusion Models
B. Missing Proofs
B.1. Proof Proposition 4.2
Proof. By Assumption 4.1, the projection operator Pa(x) performs the following optimization problem at each iteration:
arg min L(II, Va, Vo). NtA.
(13)
Since S2e is convex and C[II, v v²)) is convex and continuously differentiable over Ωe. the optimization problem has a unique global minimum.
We define single update step for the diffusion sampling process as:
U = II + 7I + 22nz.
(14)
For each time step i, there exists a minimum iteration index I such that:
ei s.t.
| + 76 VoV log (II, (H,)))))) s FFlll
(15)
where Ft is the closest point to the global optimum that can be reached via a single gradient step from any point Q2.
Let Error be the distance between IT; and its nearest feasible point. Using Theorem 5.2 in (Christopher et al., 2024), for any 2 I, we have:
E Error[U (I.)), s < E [E)
(16)
where ę 2 0 is arbitrarily small.
Therefore, the expected distance between the final generated trajectory and the feasible set Q2 is bounded above by &, which means our SMD method yields strictly smaller expected constraint violation and provides feasibility guarantee for the convex constraint set 2
C. Additional Experimental Results
Our manuscript primarily evaluates learning-based algorithms based on their performance in terms of success rate and path length (Figure Figure 6(a), and Figure 7). While these metrics are sufficient to demonstrate SMD's ability consistently outperform its competitors, two additional aspects warrant further investigation: (1) comparison with traditional methods and (2) solution time and collision ratio, which quantifies the proportion of robots that collide when no feasible solution is found. Specifically, we discretize the environment to adopt a powerful near-optimal multi-agent path finding algorithm, Explicit Estimation Conflict-Basse Search (EECBS) (Li et al., 2021).
mecsuurd by acceleration (computed as the absolute difference in velocity between consecutive
As shown in Table 3 and Table 4, our proposed SMD consistently achieves an impressive success rate across all tested scenarios. In contrast, traditional approaches such EECBS also maintain a high success rate but struggle with path length, which is approximately 20% longer than that of our method. This is caused by they operate within a predefined grid structure. Notably, our SMD achieves near-zero collision rates, outperforming other carning-based approaches, which frequently fail to avoid collisions in complex scenarios. The computational costs are reported in Table 5. Notably, more challenging tasks typically take longer to solve, thus increasing the average running time.
In addition, Table 6 shows evaluation results on practical maps introduced by (Shaoul et al., 2025). SMD still maintains a zero collision rate. These results further confirm the practical applicability and reliability of our approach.
In Figures 9 and 10, we present sensitivity analysis of the scaling factor used in ALM-based projection. The results suggest that careful tuning of Ç is not necessary; using moderate value such as I. 1.05 already achieves good convergence performance.
13

---

Simultancous Multi-Robbe Motion Planning with Projected Diffusion Models
Table Additional results for classical algorithms and learning based algorithms in random maps. is the success rate, denotes the average path length per robot, A is the average acceleration, and C is the collision ratio (see Section 5). We omit acceleration and collision
information for multi-agent path finding methods, as they assume constant velocities and typically do not return infeasible solutions.
Map
Robots
Metrie
EECBS
DM
MPD
MMD
Ours
S L J
1
0.7840
1,2591
0.9997
1.0180
1.1109
1.0125
3
A
0.0030
0.0022
0.0028
0.0010
C
0.1493
0
St
1 1.2607
0.3520
Empty Maps
L4
2.5886
1.1139
1.1764
6
A
0.0062
0.0029
0.0034
C1
0.4167
0
St
1
0
0
L
1.2684
1.1168
1.1945
A
0.0031
0.0046
C
0.9929
St
0.0520
0.9960
0.9280
L4
1.3236
0.9910
1.0310
1.1315
1.0091
3
A C4
0.0031
0.0012
0.0032
0.0040
0.6133
0.0013
0.0467
St
0
0
0.8320
Basic Maps
I.
1.3228
1.1319
1.1560
A
0.0033
0.0120
C
0.9847
0.0813
St L4 A
1 1.3244
0
0.7280
1.1375
1.2212
0,0035
0.0048
C
0.1093
St
0.968
0
0.9920
0.6600
L1
1.4945
1.0568
1.1638
1.0337
3
AL
0.0014
0.0037
0.0025
C
0.9093
0.0040
0.1813
ST
0.944
0
0.4360
Dense Maps
L
1.5135
1.1693
1.1841
6
A
0.0038
0.0064
C
0.2687 1
S
0.932
0
O
0.2720
0.9600
L
1.5349
1.1793
1.3556
9
A
0.0041
0.0052
C
0.3707
0.0044
14

---

Simultancous Multi-Robbe Motion Planning with Projected Diffusion Models
Table 4. Additional results for classical algorithms and learning-based algorithms in practical maps
Map
Robots
Metric
EECBS
DM
MPD
MMD
Ours
S
0
L L
1.4208
1.6619
Corridor Maps
2
A C
4
0.0012
1
0
S LJ A L C4
0.1200
0.5960
0.5960
1.1697
0.7884
0.8825
0.9371
0.9017
3
0,0030
0.0081
0.0030
0.0060
0.5027
0.2493
0.3133
0
St L4
0
0.5000
0.9560
Shelf Maps
1.1493
0.9317
1.0632
A C
0.0030
0.0018
0.9960
0.3740
0.01
S L4
0.4480
0.9320
1.1427
0.9331
1.0838
C4
0.0032
0.0068
A 1
0,4218
0.0111
St
0.0840
0.1360
LJ
1.6956
1.1771
1.2697
1.1917
3
A C4
0
0.0066
0.0043
0.0030
0.6520
0.6867
O
St L1 AL C4
0.9960
0.0240
Room Maps
1.6778
1.2660
1.3019
0.0032
0.0014
0.8033
ST L A C1
0.9920
0
0,9600
1.6620
1.3374
0,0033
0.8849
0.0044
15

---

Simultancous Multi-Robbe Motion Planning with Projected Diffusion Models
Table 5. Running time in seconds with success rates (shown in parentheses and expressed as percentages) for all learning based methods across maps. consider only the time consumed generate feasible trajectories for MMD, as the running time failed trajectories in MMD is determined by predefined time limit, which could be meaningless if we calculate the running time using time limit (e.g.. 3000s).
Map
Robots
DM
MPD
MMD
Ours
3
4.2(78.4)
14.1(100)
37.6(100)
29.5(100)
Empty Maps
3.7(0)
11.7(35.2)
72.1(100)
103.8(100)
3.9(0)
9.9(0)
108.5(100)
204.7(100)
3
4.1(5.2)
14.3(99.6)
39.6(92.8)
75.1(100)
Basic Maps
4.1(0)
9.9(0)
81.9(83.2)
235.2(100)
9
4.1(0)
10.2(0)
123.1
481.6(100)
3
3.8())
14.5(99.2)
46.3(66.0)
73.7(100)
Dense Maps
4.3(0)
10.1(0)
105.3(43.6)
255. 1(1.0
9
4.1(0)
10.3(0)
192.4(27.2)
551.1(96.0)
3
4.1(12.0)
9.3(59.6)
59.2(59.6)
91.3(100)
Shelf Maps
4.1(0)
7.600)
128.4(50.0)
283.2 283.2(95.6)
9
4.1(0)
8.2(0)
200.2(44.8)
585.9(93.2)
3
4.1(0)
7.9(8.4)
20.5(13.6)
74.6(100)
Room Maps
4.1(0)
8.8(0)
41.2(2.4)
158.7(100)
4.1(0)
8.5(0)
N/A(0)
255.7(96.0)
16

---

Simultancous Multi-Robun Motion Planning with Projected Diffusion Models
Table 6, Additional results for MMD and SMD in maps used in (Shaoul et al., 2025).
Map
Robots
Metric
MMD
Ours
1
L4
1.1638
1.1391
3
A
0.0026
0.0030
C4
0
0
S
1 1.1775
Highways Maps
L 4
1.1669
6
A 0.0028
0.0022
C+
0
S
1 1.1802
L4
1.1792
9
A
0.0028
0.0031
C1
0
0
S1
1 1,1499
L
1.1529
3
A 0.0030
0.0029
C1
0
S
1 1.1806
Conveyor Maps
L1
1.1726
6
A 0.0027
0.0044
C1
0
0
S1
L1
1.1916
1.2003
A 0.0031
0.0067
C1
0
S
1 1.0337
L4
1.1417
3
A
0.0024
0.0051
C4
0
0
ST
1 1.1841
Drop-Region Maps
L4
1.1604
6
A 0.0028
0.0039 0
C1
S
L
1.1719
1.3556
9
0.0027
0.0075
C4
0
0
17

---

Simultancous Multi- Robot Motion Planning with Projected Diffusion Models
10"
10'
10a
Gradient
Gradient
Gradient
10
10
10
10"
100 Iterations
200
100 Iterations
200
100
200
Iterations
(a) Empty Maps with 3 Robots.
(b) Empty Maps with 6 Robots.
(c) Empty Maps with 9 Robots.
10
10
Gradieet
Gradient
Gradieet
10
10
10
100
200
100
200
100
200
Iterations
Iterations
Iterations
(d) Basic Maps with Robots.
(c) Basic Maps with Robots.
(f) Basic Maps with 9 Robots.
10
10'
Gradient
10
Gradient
Gradient
10
10a
10"
10aa
100
200
100
200
100
200
Iterations
Iterations
Iterations
(g) Dense Maps with 3 Robots.
(h) Dense Maps with 6 Robots.
(i) Dense Maps with Robots.
10"
10'
10
Gradient
10
Gradient
10
Gradient
10
10T4
10"
100
100
100
100
Iserations
Iterationns
Iterations
(i) Shelf Maps with 3 Robots.
(k) Shelf Maps with 6 Robots.
(I) Shelf Maps with 9 Robots.
10
10"1
10
Gradivat
Gradient
Grodoent
-0
10
10 6
100
100 Tterations
200
100
Iterations
Iterations
(m) Room Maps with 3 Robots.
(n) Room Maps with 6 Robots.
(o) Room Maps with 9 Robots.
1.000
1.010
1.030
1.050
1.070
1.090
Figure 9. Sensitivity analysis of the scaling factor ( on gradient convergence for inter-agent collision avoidance constraints in ALM-based projection, evaluated for each map with different numbers of robots. The scaling factor Ç determines how the coefficient of the augmented term is multiplied at each iteration. We test five increasing values Ç from 1.01 1.09, as well as a constant value 1.00 as the ablation study.
18

---

Simultancous Multi-Robol Motion Planning with Projected Diffusion Models
Grodient
10
Gradient
Gradient
100
10
10
10"
10
100
200
100 Iterations
200
100
200
Iterations
Iterations
(a) Basic Maps with 3 Robots.
(b) Basic Maps with 6 Robots.
(c) Basic Maps with 9 Robots.
Gradivat
10"
Gradieat
10
Gradieat
10
1
10
10
100
200
100
200
100
200
Iterations
Iterations
Iterations
(d) Dense Maps with 3 Robots.
(c) Dense Maps with 6 Robots.
Dense Maps with Robots.
Gradient
10"
Gradient
10
Grudient
10
-
10
100
200
100 Iterations
200
100
200
Ineraionn
Iterations
(g) Shelf Maps with 3 Robots.
(h) Shelf Maps with Robots.
(i) Shelf Maps with 9 Robots.
Gradient
10"
Gradient
10
Cradient
10
10
10
10
100
200
100 Iterations
200
100
200
Iterations
Iterations
Room Maps with Rohots.
(k) Room Maps with 6 Robots.
Room Maps with Robots.
1.000
1.010
1.030
1.050
1.070
1.090
Figure 10. Sensitivity analysis of the scaling factor gradient convergence for obstacle collision avoidance constraints in ALM-based projection, which leads to similar conclusions with inter-agent collision avoidance constraints.
19


Reviews:
[{"review_id": "VGNKSvHlUg", "reviewer": "Reviewer_7Hco", "summary": "This paper introduces Simultaneous MRMP Diffusion (SMD), a novel method for enforcing critical constraints, such as collision avoidance and kinematic feasibility, in Multi-Robot Motion Planning (MRMP). SMD integrates constrained optimization into the diffusion process to generate collision-free, kinematically feasible trajectories, thereby embedding these constraints directly within the trajectory generation pipeline. A Lagrangian-dual based approach is employed to achieve this integration. Additionally, this work presents the first benchmark for MRMP evaluation, featuring complex input maps and diverse scenarios. Experimental results demonstrate that SMD outperforms both classical and learning-based motion planners, achieving higher success rates and greater efficiency in complex multi-robot environments.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the helpful comments, in particular the acknowledgement of the **strong empirical performance** of our proposed SMD and **a novel benchmark** for MRMP. We provide below our answers to your constructive questions.\n\n- **Q1: Does projection actually help guarantee collision avoidance and kinematic feasibility?**\n\nFrom the **theoretical perspective**: \n\nFirstly, In lines 208–219, we demonstrate that the derived projeciton operator satisfies both the **convergence and convex constraint feasibility guarantees**. Although MRMP is inherently nonconvex, our Augmented Lagrangian-based projection reformulates it into a convex problem, allowing generated trajectories from our SMD to **satisfy relaxed MRMP constraints theoretically**. We address remaining nonconvex constraints via a dual ascent method, providing a clear stopping criterion and ensuring **constraint violations less than a predetermined threshold**. To the best of our knowledge, this is the first work offering these guarantees in diffusion-based trajectory planning. \n\nNext, if you ask *why project throughout the diffusion process?* The shortcomings of post-processing methods are well documented within the literature: It is shown to substantially degrade sample quality ([1] highlighs that samples are often too \"implausible to be corrected... [and] may be pushed away from the data distribution.\"). \n\nFrom the **empirical perspective**: \n\nWe do provide this analysis in our experiments. Performance is measured by success rate: **the percentage of collision-free, kinematically feasible trajectories in test cases**. SMD consistently achieves the highest success rate, significantly outperforming other diffusion-based approaches. Specifically, the **key difference between SMD and MPD (a baseline method in our experiments) is integrating constrained optimization into the diffusion process**. We will further clarify this aspect in the revised version providing a numerical summary in the introduction.\n\nWe will be happy to include a more formal statement of theoretical analysis in the final version.\n\n- **Q2: How does Simultaneous MRMP Diffusion perform on more complex plans where the trajectories are more complex?**\n\nWe have evaluated our method in scenarios **significantly more challenging than those explored in previous studies**. Compared to  MPD, we extend our experiments to multi-robot systems; compared to MMD (the previous SOTA appraoch, which was deposited on ArXiv only 3 months before this submission), we increase both the number and density of obstacles. **In fact, our paper even proposes a new benchmark that provides the highest degree of scaling within Multi-Robot Motion Planning to date.** Our method consistently achieves superior performance under these complex conditions. We agree that further investigation into more complicated scenarios, such as 3D environments, would be valuable; This is an important direction for future work.\n\n**Reviewer’s Additional Points**:\n\n> **A1**: Feasibility analysis in experiments section & Theoretical justifications for projecting the diffusion process\n\nPlease refer to our response to Q1 for details.\n\n> **A2**: The process and effectiveness of reformulating inequality constraints into equality ones\n\nWe take a general inequality constraints as an example:\n$$\nh(x)\\geq b,\n$$\nwhere $x$ is the decision variable and $b$ is a parameter. Directly handling Eq (1) with Augmented Lagrangian methods are complicated because multipliers for inequality constraints should be larger than 0, which introduces extra decision logic.\n\nInstead, equality constraints can lead better convergence properties and simplify multiplier updates:\n$$\n\\boldsymbol{\\nu}^{k+1}=\\boldsymbol{\\nu}^{k}+\\alpha^k\\boldsymbol{h}(x^k)\n$$\nwhere $\\boldsymbol{\\nu}$ represents the multiplier and $\\alpha$ is the step size. \nTo transform inequalities into equalities, we introduce non-negative auxiliary variables $s$:\n$$\nh(x)-b-s=0.\n$$\nThe presence of non-negative variable $s$ can ensure Eq. (3) is equivalent to Eq. (1):\n\n- If $h(x)\\geq b$ , then $s=h(x)-b\\geq0$ makes the equality hold.\n- If $h(x)-b-s=0$ and $s\\geq0$, then $h(x)-b=s\\geq0$.\n\nWe will provide a more detailed description in the revised paper.\n\n> **A3**: Visualizations for the Benchmark\n\nWe will include linked a GitHub page with visualizations in the final version:  https://drive.google.com/drive/folders/1ZdfNmA9BfIdshIbRN3AmAcyvXakhrhkr?usp=drive_link\n\n> **A4**: Figure 1’s overview\n\nA new figure is here: https://drive.google.com/file/d/1W8tuHwVLBV-2zZ9It0pLIdny1ZHchoxF/view?usp=drive_link \n\nCould you let us know if you have further suggestions?\n\n---\n\nWe want to thank the reviewer again for their valuable feedback. We believe that our response has addressed each of your comments but are happy to provide additional details if requested. We would be grateful if you could consider increasing your score to reflect this. Many thanks!\n\n\n\n[1] Yuan et al. \"Physdiff: Physics-guided human motion diffusion model.\"", "claims_and_evidence": "- This paper claims that diffusion processes integrated with constrained optimization helps produce collision-free, kinematically feasible trajectories but analysis on these aspects are missing from the experiments section.\n- Theoretical justifications for projecting the diffusion process is unclear which leads to confusion and weakens the argument for using this particular method.", "methods_and_evaluation_criteria": "- Comparison candidates seems to be well chosen including state-of-the art methods which helps validate the results of the paper\n- The random maps designed for MRMP experiments are well chosen which covers many scenarios and tests the ability of each planner to a high degree.", "theoretical_claims": "- How the equations constrains each robot's trajectory is rather unclear and requires further explanation.\n- In section 4.2 the process of the inequality being rewritten as equalities are missing which makes it harder to understand and appreciate.", "experimental_designs_or_analyses": "- The experiments cover various scenarios including randomly generated and structured real-world-inspired maps. \n- Random maps include environments with increasing difficulty. Basic maps introduce multiple obstacles which requires navigating through narrow corridors. Dense maps contain many obstacles significantly restricting movement. The various difficulties help test the planning algorithms to their limit.\n- Practical maps include corridors, warehouse storage layouts with tight aisles, rooms connected with doors. These maps are well designed to test global coordination.", "relation_to_broader_scientific_literature": "- This paper proposes to constrain the diffusion process to avoid collisions and satisfy kinematic feasibility. Compared to previous works, a novel constrained optimization process is integrated into the diffusion process.\n- Furthermore, this paper proposes a method for evaluating Multi-Robot Motion planning (MRMP) which can be used for future works.", "essential_references_not_discussed": "All necessary references are included in the paper. No further recommendations required.", "other_strengths_and_weaknesses": "- The proposed method achieves state-of-the-art results for MRMP.\n- Rejection sampling or post-processing is not required for the proposed method.\n- Proposing a new evaluation method is a meaningful contribution to the research community.\n- Theoretical justifications lacks clarity and would benefit from further explanations.\n- Figure 1's overview could be improved to clarify the projection operation.", "other_comments_or_suggestions": "- On the last sentence in page 3, there is a typo: This allows it to from ~.", "questions_for_authors": "- Does projection actually help guarantee collision avoidance and kinematic feasibility?\n- How does Simultaneous MRMP Diffusion perform on more complex plans where the trajectories are more complex?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Y87YgVAt7g", "reviewer": "Reviewer_9rTn", "summary": "This paper proposes a new method for tackling the constraint satisfaction challenge in Multi-Robot Motion Planning (MRMP). The paper highlights challenges in existing methods, such as learning-based approaches, that struggle with obeying hard constraints. The proposed method, SMD, addresses these issues by incorporating constrained optimization into diffusion models. To handle nonconvex constraints efficiently, SMD employs an augmented Lagrangian method. This paper also proposes a MRMP benchmark with varied scenarios. SMD outperforms state-of-the-art MRMP methods in complex multi-robot settings.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer 9rTn for the insightful feedback including acknowledging the **effectiveness** of our proposed SMD and **comprehensive benchmark** for evaluating MRMP. We provide below our answers to your valuable questions:\n\n- **Differentiation from Christopher et al. (2024)**\n\nIndeed, our work draws inspiration from Christopher et al. (2024), but our contribution is far from being an application of the such framework. It is a significant extension specifically tailored to MRMP. \nOur first key contribution is a diffusion-based method explicitly designed to overcome the challenge of ensuring trajectory feasibility in MRMP. Our SMD can consistently **generate feasible trajectories in complex MRMP scenarios where existing state-of-the-art methods fail**. \n\nFurthermore, our approach extends projected diffusion models to MRMP by introducing **two key innovations beyond Christopher et al. (2024)**:\n\n   1. We propose a relaxation of the MRMP nonconvex constraints using an Augmented Lagrangian method, transforming the problem into a convex formulation. This significantly enhances projection efficiency. In contrast, Christopher et al. (2024)'s method **faces substantial difficulties** when solving even relatively simple MRMP instances even with 3 robots due to the complexity of nonconvex projections, and thus it cannot be applicable in practice. \n\n   2. As we shown in lines 208–219 in our paper, SMD ensures the outputs generated by diffusion models can satisfy convex constraints. For a more detailed theoretical analysis, we also refer the reviewer to our response to Comment 2 from Reviewer 7Hco.\n\nAdditionally, we contribute a **new benchmark** for evaluating MRMP methods, which has been valued by other reviewers and which we believe, will benefit this community. We will be more explicit about our contribution in the final version of the paper.\n\n\n**Reviewer’s Additional Points**:\n\n> The submission claims that SMD maintains feasibility as robot/obstacle density increases, however, MRMP complexity grows combinatorially with robot count\n\nWe agree that MRMP is highly challenging, especially in complex environments. Recent advances in MRMP exploit diffusion models to generate diverse solutions, but existing methods fail to satisfy non-collision, which is key, in complex environments. Such issues become more pronounced as robot/obstacle density increases. As shown in our experiments, the previous state-of-the-art methods **succeeds only in empty environments with 3 robots**, yet performance **significantly degrades to a 27.2% success rate with 9 robots and 20 obstacles**.\n\nUnlike other methods whose success rates rapidly decline as robot and obstacle numbers grow, **SMD maintains feasibility in scenarios with increased robot and obstacle counts **(e.g., dense maps with 9 robots and 20 obstacles). Specifically, SMD is the only known method that **provides feasible solutions for the largest number of robots** in complex environments. Even in the most challenging dense maps, where it still maintains a near-perfect success rate. \n\nAs briefly mentioned above, to mitigate the computational complexity brought by the large number of obstacles and robots, we develop an Augmented Lagrangian-based projection, which **reformulates nonconvex MRMP into a convex problem**. This significantly enhances projection efficiency and make using projection-based methods in MRMP possible, without affecting its success rate.\n\nThank you for your points. We will further emphasize the significance of our results in the revised manuscript to help readers more directly appreciate our results.\n\n---\n\nWe would like to sincerely thank you for your insightful feedback, which is valuable to improve our manuscript. We hope our responses have addressed your concerns and we would be grateful if you could consider increasing your score to reflect this. Many thanks!", "claims_and_evidence": "1. The submission claims that SMD maintains feasibility as robot/obstacle density increases, however, MRMP complexity grows combinatorially with robot count.\n2. The main contribution—integrating constrained optimization into diffusion via projections—appears closely aligned with Christopher et al. (2024). The primary adaptation here is applying this framework to MRMP and replacing the solver with an augmented Lagrangian method.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "No proofs.", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "Generative diffusion models, Multi-Robot Motion Planning", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strengths:\n1. The paper demonstrates the effectiveness of the proposed method.\n2. The paper introduces a comprehensive benchmark tailored to MRMP.\n\nWeaknesses:\nThe main contributions closely follow Christopher et al. (2024), with the main adaptations being its application to MRMP and the use of an augmented Lagrangian solver.", "other_comments_or_suggestions": "It would be helpful if the authors could clarify any additional novelty/contributions.", "questions_for_authors": "Differentiation from Christopher et al. (2024)", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MCYnPeY7fI", "reviewer": "Reviewer_ZshS", "summary": "The paper tackles constraint enforcement for trajectory generation with diffusion models in the context of multi-agent motion planning. Instead of encoding constraints as auxiliary energy terms, the paper proposes to project intermediate generations on to the collision-free manifold. The projection operator is tackled by dual ascent method so the formulation can be more tractable than solving the original constrained optimization problem. The method is shown to outperform standard diffusion model and variants with planning in-the-loop, in particular in complex problems with more agents and map layout entailing coordination.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback including acknowledging the **superior performance of our SMD in complex scenarios**. We provide below our answers to your valuable questions:\n\n**Questions For Authors:**\n\n- **Q1: How can the framework be used to handle general multi-agent planning constraints beyond collision avoidance?**\n\nWe agree that quadratic form of constraints used in our work usually captures inter-distance between sphere-shaped robots. Such a formulation is also **widely adopted by existing methods** (e.g., the previous SOTA, MPD and MMD used in our experiments) and can be found in practical environments [1]. If extended to other robot shapes like rectangles, our framework still works but with more complex constraints. A simple alternative is to use the minimum bounding sphere, or multiple spheres to approximate the irregular shapes.\n\nWe would like to clarify we do not *only* consider inter-distance constraints, but also **ensure the kinematical constraints (e.g., velocity limits)** in our paper. Additionally, SMD can handle other constraints such as acceleration and smoothness constraints easily by adding these to the constraint set. This could be a meaningful future direction. We will further elaborate in the final version of the paper.\n\n- **Q2: The problem seems not to cover anonymous agent planning. Can it be used on this category of problems?**\n\nProvided that anonymous agent planning is, in fact, a less constrained problem than MRMP, our method can be employed without changes if we preassign goals to agents. For better performance, we can modify the constraints governing the initial and final states of the agents.\n\n- **Q3: What is the computational cost for the inference of diffusion model with embedded projection. Can it afford some replanning to close the loop?**\n\nWith a tolerable increase in runtime, our method achieved significant performance improvement over the previously SOTA methods! The detailed comparison is available at this link: https://drive.google.com/file/d/10AnaJkw5Sva8qdNtXbexmNst80pKKjnF/view?usp=drive_link. Our running time can be further optimized using multiple techniques, such as parallelism and learning to optimize methods.\n\nOur method can be easily adapted to support replanning. In fact, this is our current focus. To do so, we adjust the input to incorporate the existing trajectories and perform local updates according to the changed conditions. This approach also significantly reduces computational overhead!\n\n**Reviewer’s Additional Points**:\n\n> **A1**: The reasoning behind the effectiveness of our method, and whether it generalizes beyond quadratic inter-distance constraints\n\nFor general constraints, please refer to our response to Q1 for details.\n\nFor theoretical and empirical analysis for the effectiveness of our SMD, please refer to our response to Q1 from Reviewer 7Hco.\n\n> **A2**: Clarifying our sampling process\n\nWe're happy to clarify this, as it seems there are a few key misunderstandings of our work. First, there seems to be a misunderstanding regarding our approach, which is not merely a \"blend of sampling and gradient-based optimization\".\n\nThe gradients are computed based on the constraint residuals iteratively, which is a common practice in the *dual ascent method* in constrained optimization. Specifically, our approach leverages an optimization solver to project the infeasible trajectories — generated during the diffusion sampling process (from noise to trajectory) — onto the feasible region. This allows us to achieve SOTA performance.\n\nSecond, our paper's contribution is centered on extending the *sampling process* and is consequentially applied at *inference time only*. We defer details about training to the appendix because this is not where our work is centered. This aspect however, is important: **it is what allow us to generalize beyond training distribution and handle maps, even if they were never seen before**. \n\nWe will be happy to include the training details in the main text and provide a more detailed description of Algorithm 2 in the final version. \n\n> **A3**: Coefficients of constraint residual norms\n\nDuring rebuttal, we evaluated the convergence performance with 6 different coefficients for the constraint residual norms. The results are available at: https://drive.google.com/file/d/1jjlOs9GEYd2qE4X6OLd4wjEoR3PVkDwo/view?usp=drive_link\n\nImportantly, there is no change w.r.t. the paper's conclusions.\n\n---\n\nWe appreciate your efforts and insightful feedback! We believe our response has addressed each of your questions but would be happy to provide more details if requested. As the points covered in your review are primarily requests for clarifiying, we would be grateful if you could consider increasing your score to reflect this. Many thanks!\n\n[1] Clearpath Robotics. *TurtleBot 4*. https://clearpathrobotics.com/turtlebot-4/\n[2] Rockafellar, R. T. Augmented Lagrange multiplier functions and duality in nonconvex programming.", "claims_and_evidence": "The central claim lies in using projection to enforce collision avoidance constraints is more amenable to generate solutions for complex multi-agent planning problems. This is validated by the results on dense and real-world maps in Figure 3.", "methods_and_evaluation_criteria": "The method follows literature-based formulation and dual ascent method for the effectiveness on solving constrained optimization. The reasoning looks solid although the insights about why the idea can bring about such effectiveness could be better addressed. The main issue on the method is that it seems heavily relying on the quadratic form of constraints that can only capture inter-distance between sphere-shaped robots. It is unclear whether other types of constraints can also be handled by the framework.\n\nThe evaluation is made on collision-free motion planning problems on maps with different levels of complexity and number of agents. The criteria on success rate makes sense.", "theoretical_claims": "There is no theoretical result presented in the paper.", "experimental_designs_or_analyses": "The experiment designs look sound to verify the acclaimed challenge of applying diffusion model to multi-agent motion planning and the effectiveness of projection based constraint enforcement. The analysis focuses on success rate of solving the problem and shows clear benefits of the proposed method in handling more complex setups.", "relation_to_broader_scientific_literature": "The idea of leveraging alternating gradient descent to enforce constraints in denoising process seems applicable to broader works on embedding differential optimization in the learning loop. However, it is unclear whether the relaxation can work for non convex constraints other than a quadratic form which works for capturing the inter-agent collision avoidance but might be limited for general constraint enforcement.", "essential_references_not_discussed": "I am not aware of other essential references to be discussed.", "other_strengths_and_weaknesses": "The paper clarity can be improved as the method in beginning reads like a blend of sampling and gradient-based optimization. The details on training implementation is placed in the appendix so it was only clear to me at the end that the paper is about regressing solver's results. The clarity is also very demanding for the implementation of training. Algorithm 2 seems requires to differentiate though an optimization process and it is not clear from the paper whether the gradients are attained through unrolling the optimization process or adjoint methods. \n\nThe method seems to have some design space to explore, e.g. coefficients of constraint residual norms. An ablation study can better demonstrate the robustness of the method on the parameter choice.", "other_comments_or_suggestions": "Line 164: \"this allows it to from\" missing a verb here?", "questions_for_authors": "1. How can the framework be used to handle general multi-agent planning constraints beyond collision avoidance?\n\n2. The problem seems not to cover anonymous agent planning. Can it be used on this category of problems?\n\n3. What is the computational cost for the inference of diffusion model with embedded projection. Can it afford some replanning to close the loop?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nLOyxhQPyE", "reviewer": "Reviewer_LLNt", "summary": "The paper proposes Simultaneous Multi-Robot Motion Planning with Projected Diffusion Models (SMD), a novel method for multi-robot motion planning (MRMP) that integrates constrained optimization into the sampling process of diffusion models. Although diffusion models have demonstrated promising capabilities in generating diverse and smooth robot trajectories, they often fail to satisfy essential constraints, including collision avoidance and kinematic feasibility. To address this, the authors introduce a constrained optimization approach embedded within the diffusion model's sampling process using an augmented Lagrangian method. This formulation efficiently projects generated trajectories into feasible spaces, ensuring compliance with both collision avoidance and kinematic constraints. Additionally, the authors provide a comprehensive new benchmark dataset to evaluate multi-robot motion planners across scenarios with varying obstacle densities and spatial complexities. Empirical results show that SMD significantly outperforms other baselines.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the helpful review, in particular the acknowledgement of the **strong empirical performance** of our proposed SMD and the contribution of **a comprehensive benchmark** for MRMP. We provide below our answers to your insightful questions.\n\n- **Q1: SMD’s inference time with more robots (e.g., up to 100) & experiments with large-scale scenarios?**\n\nIt would be amazing to succeed in such scenarios. However, these usually require much-simplified problems, including using a discretization of the underlying map in which multi-agent path finding (MAPF) formulation arises, and assumptions on fixed velocity and discretized environment\n\nPlease note that our proposed method scales to the **largest number of robots** in complex scenarios tested so far in this realistic setting, thus setting a new SOTA standard. Additionally, our newely proposed benchmark provides the most comprehensive robot scaling of any existing baselines. We are hopeful that our benchmark will be a useful contribution to the community. \n\nWe have also included additional inference times. Please refer to our response to Q3 from reviewer ZshS. Many thanks!\n\n\n- **Q2: Senstivity analysis and tuning for the additional hyperparameters introduced**\n\nThank you for bringing up this point. During rebuttal, we have conducted an extensive senstivity analysis. We ask you to refer to our response to A3 from reviewer ZshS for more details. \nThe empirical observations strongly suggest that our method, being able to integrate constraints directly in the sampling phase of diffusion models, is very robust across a range of hyperparameters, thus reducing the need for meticulous tuning. This is a strength that we plan to discuss in the final version of the paper. \n\n- **Q3: Concerns on generating unrealistic trajectories**\n\nWhile the reviewer suggests that projecting early on in the diffusion process may \"lead to convergence towards unrealistic trajectories,\" in fact, the opposite is consistently observed. First, consider a case where a single post-processing projection is used to correct the final sample $x_0$. If $x_0$ is far from the constraint set, the projection will alter the trajectories significantly, leading to a lower degree of realism. This is well documented by prior literature [1,2] and has motivated constraint imposition earlier on in the sampling process. By projecting earlier in the diffusion process, the following denoising steps will restore any reaslism that is lost by projecting. Instead, we converge to a feasible subdistribution of the training data.\n\nPractically, the projection starting point could be tuned to balance the tradeoff between computational overhead and generation realism [2], but we defer this type of analysis to future research.\n\n- **Q4: Performance evaluation on SMD's Benchmark & complex robotic systems**\n\nIndeed, maps used in SMD's benchmarks contain fewer obstacles, under which both methods (ours and prior baselines) easily succeed. On more challenging maps, such as dense maps, our method demonstrates clear advantages. \nThe results on the original MMD benchmark can be found here: \nhttps://drive.google.com/file/d/1fOCDaNoU6AP9-f5AvMuurvYSHsogwuNR/view?usp=drive_link\nWe would be happy to include them in the final version of the paper if the reviewer suggests so. \n\nRegarding more complex scenarios, while this paper focuses on motion planning in environments with static obstacles, we agree that extending SMD to handle more complex systems (e.g., humanoid locomotion) is an exciting direction for future work. Indeed, our group is active in these directions. One possible extension is to incorporate human trajectory prediction into the projection mechanism, or to adopt a MPC framework to adapt to dynamic agents.\n\n**Reviewer’s Additional Points**:\n\n> **A1**:Reproducibility and practical integration\n\nWe agree and intend to release our code following the review cycle. It had previously been our intent to provide an anonymized repository with code examples for the rebuttal, but due to ICML's updated policy, we are only allowed to include figures, tables and explanations related to them in linked material. Our lab has a long tradition of sharing codes and associated github pages with execution instructions and tutorials. \n\nAs far as practical integration, our method is training-free and thus can be directly embedded into existing methods to improve performance. **This is also what allows us to generalize to unseen maps!**. The method is easy to use and requires minimal modification to existing pipelines.\n\n\n---\n\nThank you for your time assessing our work! We appreciate your suggestions and will add the additional results that your review motivated to our subsequent draft. We would be grateful if you could consider increasing your score to reflect this. Many thanks!\n\n[1] Christopher, Jacob K., et al. \"Constrained synthesis with projected diffusion models.\"\n\n[2] Yuan, Ye, et al. \"Physdiff: Physics-guided human motion diffusion model.\"", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "No theoretical section is presented in the paper.", "experimental_designs_or_analyses": "I find the experimental designs reasonable and sufficiently aligned with the paper’s objectives.", "relation_to_broader_scientific_literature": "This paper builds on prior score-based diffusion approaches and extends them by incorporating an augmented Lagrangian framework to handle multi-robot constraints, bridging a gap in the literature where most methods either rely on gradient-based cost penalties or post-hoc filtering for feasibility.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strengths:\n\nThe paper is well-written, and the proposed method is described clearly.\n\nThe combination of diffusion models with constrained optimization to ensure feasibility seems both novel and promising.\n\nThe comparisons against a strong baselines (including MMD) in the multi-robot motion planning setting help validate the method’s effectiveness.\n\nWeaknesses:\n\nIt remains unclear how sensitive the method’s performance is to certain hyperparameters introduced by constrained optimization, and how difficult they are to tune in practice.\n\nThe paper lacks discussions about reproducibility and practical integration.", "other_comments_or_suggestions": "While the core contribution is solid, additional details about computational overhead—particularly in comparison to MMD—would strengthen the paper.\n\nProviding at least one reproducible example or making the code available would greatly help readers verify the claims and understand how easily the proposed SMD method can be integrated into existing robot planning systems or simulation environments.", "questions_for_authors": "How does SMD’s inference time scale with the number of robots (e.g., up to 100)? Do you have experimental evidence indicating whether it remains tractable for large-scale multi-robot scenarios?\n\nCould you provide some results / explaintions on how senstive the performance of the proposed approach is to the additional hyperparameters introduced and how hard it is tune them?\n\nIn the early diffusion steps, when the trajectory is still highly noisy, wouldn't strongly enforcing constraints potentially lead to convergence towards unrealistic trajectories?\n\nWhile the proposed benchmark is a valuable contribution, I have some concern that it might be biased toward your method’s strengths. Have you tested SMD on other existing benchmarks (e.g., those used in MMD) to confirm consistent performance improvements? Additionally, do you expect that SMD can handle more complex robotic systems (e.g., humanoid locomotion or higher-dimensional configuration spaces), rather than just 2D disk navigation?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This work proposes Simultaneous Multi-robot motion planning Diffusion (SMD) for the problem of finding conflict-free trajectories under kinematic constraints.

The reviewers agree that the proposed approach is an interesting and promising application of diffusion models in the multi-robot navigation context. There are some shared concerns about a straightforward centralised architecture that does not enable scaling to larger teams of robots; and some points regarding clarity of presentation that should be addressed.

However, all-in-all there is an agreement that presenting this paper is worthy of being presented at ICML.
Decision: Accept (poster)