Simultaneous Multi-Robot Motion Planning with Projected Diffusion Models

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.

• Q1: SMD’s inference time with more robots (e.g., up to 100) & experiments with large-scale scenarios?

It 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

Please 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.

We have also included additional inference times. Please refer to our response to Q3 from reviewer ZshS. Many thanks!

• Q2: Senstivity analysis and tuning for the additional hyperparameters introduced

Thank 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. The 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.

• Q3: Concerns on generating unrealistic trajectories

While 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.

Practically, 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.

• Q4: Performance evaluation on SMD's Benchmark & complex robotic systems

Indeed, 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. The results on the original MMD benchmark can be found here: https://drive.google.com/file/d/1fOCDaNoU6AP9-f5AvMuurvYSHsogwuNR/view?usp=drive_link We would be happy to include them in the final version of the paper if the reviewer suggests so.

Regarding 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.

Reviewer’s Additional Points:

A1:Reproducibility and practical integration

We 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.

As 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.

---

Thank 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!

[1] Christopher, Jacob K., et al. "Constrained synthesis with projected diffusion models."

[2] Yuan, Ye, et al. "Physdiff: Physics-guided human motion diffusion model."

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:

Questions For Authors:

• Q1: How can the framework be used to handle general multi-agent planning constraints beyond collision avoidance?

We 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.

We 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.

• Q2: The problem seems not to cover anonymous agent planning. Can it be used on this category of problems?

Provided 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.

• Q3: What is the computational cost for the inference of diffusion model with embedded projection. Can it afford some replanning to close the loop?

With 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.

Our 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!

Reviewer’s Additional Points:

A1: The reasoning behind the effectiveness of our method, and whether it generalizes beyond quadratic inter-distance constraints

For general constraints, please refer to our response to Q1 for details.

For theoretical and empirical analysis for the effectiveness of our SMD, please refer to our response to Q1 from Reviewer 7Hco.

A2: Clarifying our sampling process

We'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".

The 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.

Second, 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.

We 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.

A3: Coefficients of constraint residual norms

During 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

Importantly, there is no change w.r.t. the paper's conclusions.

---

We 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!

[1] Clearpath Robotics. TurtleBot 4. https://clearpathrobotics.com/turtlebot-4/ [2] Rockafellar, R. T. Augmented Lagrange multiplier functions and duality in nonconvex programming.

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:

• Differentiation from Christopher et al. (2024)

Indeed, 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. Our 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.

Furthermore, our approach extends projected diffusion models to MRMP by introducing two key innovations beyond Christopher et al. (2024):

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.

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.

Additionally, 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.

Reviewer’s Additional Points:

The submission claims that SMD maintains feasibility as robot/obstacle density increases, however, MRMP complexity grows combinatorially with robot count

We 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.

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 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.

As 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.

Thank 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.

---

We 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!

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.

• Q1: Does projection actually help guarantee collision avoidance and kinematic feasibility?

From the theoretical perspective:

Firstly, 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.

Next, 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.").

From the empirical perspective:

We 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.

We will be happy to include a more formal statement of theoretical analysis in the final version.

• Q2: How does Simultaneous MRMP Diffusion perform on more complex plans where the trajectories are more complex?

We 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.

Reviewer’s Additional Points:

A1: Feasibility analysis in experiments section & Theoretical justifications for projecting the diffusion process

Please refer to our response to Q1 for details.

A2: The process and effectiveness of reformulating inequality constraints into equality ones

We take a general inequality constraints as an example:

$$h(x)\geq b,$$

where $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.

Instead, equality constraints can lead better convergence properties and simplify multiplier updates:

$$\boldsymbol{\nu}^{k+1}=\boldsymbol{\nu}^{k}+\alpha^k\boldsymbol{h}(x^k)$$

where $\boldsymbol{\nu}$ represents the multiplier and $\alpha$ is the step size. To transform inequalities into equalities, we introduce non-negative auxiliary variables $s$:

$$h(x)-b-s=0.$$

The presence of non-negative variable $s$ can ensure Eq. (3) is equivalent to Eq. (1):

• If $h(x)\geq b$ , then $s=h(x)-b\geq0$ makes the equality hold.
• If $h(x)-b-s=0$ and $s\geq0$, then $h(x)-b=s\geq0$.

We will provide a more detailed description in the revised paper.

A3: Visualizations for the Benchmark

We will include linked a GitHub page with visualizations in the final version: https://drive.google.com/drive/folders/1ZdfNmA9BfIdshIbRN3AmAcyvXakhrhkr?usp=drive_link

A4: Figure 1’s overview

A new figure is here: https://drive.google.com/file/d/1W8tuHwVLBV-2zZ9It0pLIdny1ZHchoxF/view?usp=drive_link

Could you let us know if you have further suggestions?

---

We 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!

[1] Yuan et al. "Physdiff: Physics-guided human motion diffusion model."