Multi-Robot Motion Planning with Diffusion Models

Response to reviewer WAyg

Dear Reviewer WAyg, Thank you for your insightful and thorough comments. We are very happy to hear that you found the ideas explored in our paper to be interesting, our presentation to be clear, and our experimental analysis to be thorough. Thank you for bringing the connection between GBP and MMD to our attention. We agree that there is exciting potential for integrating these algorithms, enabling new possibilities for data-driven multi-robot planning in windowed, real-time, and decentralized settings. Such integration could enable data-driven planning in environments with a priori unknown moving obstacles and decentralized online execution–areas we find particularly exciting to explore further. However, we note that the focus of our work is on centralized long-horizon data-driven planning and hence we do not compare it with bounded horizon decentralized planners like GBP and ORCA that do not learn from data. 1. *Discussion of GBP.* We agree that discussing GBP in our paper would enrich it, and we appreciate your suggestion. Specifically, we have included a discussion in our Conclusion section highlighting the connection between GBP and MMD along with the associated advantages and challenges of combining them. Additionally, we have added a standalone appendix section (A1.1) on the prospects of using MMD in online windowed settings, including an outline of the promise that integrating it with GBP holds. Reviewer frGK has also shown interest in MMD’s ability to operate in dynamic settings–we hope that this discussion will be interesting and informative for them as well. 2. *Experimental comparison with GBP.* To facilitate a discussion of the advantages and disadvantages of integrating GBP with MMD, we have run new experiments evaluating GBP in our Circle, Weave, Conveyor, Highways, and 2x2 setups. Our experimental results certainly show promise in integrating MMD with GBP. When operating in obstacle-free maps (i.e., the Empty map in the Circle and Weave setups), GBP produced slightly shorter trajectories than MMD, with the added benefit of not having to plan the full horizon. On the other hand, GBP struggled to produce trajectories in our Conveyor and Highways maps. There, robots that attempted to move from one side of the map to the other, a motion that requires moving around a large obstacle, got stuck, were repelled off the map, or collided with obstacles (depending on the choice of hyperparameters). MMD’s access to global information (in the form of training data) could help GBP-like algorithms intelligently resolve such situations by breaking the symmetry with data-driven predictions. In our 2x2 map, where trajectories are longer, GBP performed superbly–finding collision-free trajectories for up to 40 robots. This suggests that MMD could benefit from using GBP as its coordination mechanism as it will remove the combinatorial planning phase that MMD inherits from MAPF algorithms. And GBP could benefit from having diffusion models as single-robot windowed planners (potentially imposing collision avoidance soft-constraints in the same way MMD does) since those could be better globally informed and steer windowed, data-driven, movements towards their goal even in the presence of significant clutter. Given the potential that lies within incorporating GBP with MMD, and the depth of analysis that such an algorithm could benefit from, we believe that reporting metrics on a comparison between MMD and GBP in our paper would do this direction injustice as it would only provide a superficial comparison between the trajectory length and success rates of learning-based, centralized, methods and a windowed, decentralized, algorithm. Therefore, in our paper we prefer to include a discussion similar to the one written above, and leave a deeper quantitative comparison between GBP, MAPF algorithms, GBP with data-driven single-robot planners, and MMD to future work. Best regards, The Authors

Response to reviewer frGK

Dear Reviewer frGK, We sincerely thank you for your thoughtful and constructive feedback. We are encouraged by your recognition of the novelty and strengths of our paper, including the ability to scale to large environments with numerous robots without retraining, thorough comparison of different MAPF-based constraining strategies, and strong empirical performance of our method. We address your questions below. 1. *Cooperative multi-robot motion planning.* We have shown in our paper that single-robot diffusion models, when combined with MAPF-inspired constraining strategies, are sufficient to plan collision-free multi-robot trajectories in complex environments with dozens of robots. We agree that this reliance on only single-robot data may not be sufficient for cooperative multi-robot motion planning, e.g., two robots moving an object collaboratively. However, this is a much harder planning problem that is beyond the scope of this paper. Nevertheless, we believe this is an exciting direction for future research. We are interested in understanding how our method can be extended to collaborative motion planning with the minimum amount of multi-robot interaction data since it is usually much harder to collect than single-robot data. We discuss this point in the conclusion section of our paper. 2. *This paper could benefit from a more detailed discussion of the computational overhead, especially regarding the MAPF constraint strategies and the diffusion model’s denoising process.* We have added a brief discussion about the computational complexity in Section 4.2 with a reference to our detailed timing results in the appendix (A.2.1). The relationship between planning time and solution quality is intrinsically linked in our context. Our experimental results show that when A\*Data-ECBS achieves similar data adherence to MMD, the planning times are comparable. However, when A\*Data-ECBS produces solutions with lower solution quality (i.e., lower data adherence), it tends to have faster planning times. It's worth noting that there is significant potential for improving the computational efficiency of our approach through parallelization, particularly in the low-level planning phase, where each agent's path can be computed independently. However, we have left such optimizations for future work. 3. *Computational tradeoff among MMD variants.* We appreciate the suggestion to clarify trade-offs among the five MMD variants. We have added an appendix section (A.8 - Recommendations for Practitioners) that explicitly details which MMD variants are best for which scenarios (environment types and robot counts). Overall, we found MMD-xECBS to be the strongest MMD variant. It efficiently returns collision-free trajectories and scales better than other methods in cluttered maps. On the other hand, MMD-PP performs and scales better in relatively open maps with low obstacle density. However, it struggles in congested environments and does not guarantee collision-free trajectories. 4. *Generalization beyond warehouse-like environments to less structured and dynamic settings.* We picked the warehouse domain for experimental evaluation due to its significant real-world importance. However, MMD is not limited to such environments and should perform well in other scenarios too. For example, we are very interested in applying MMD to multi-robot-arm motion planning in our future work. While the focus of this paper is on motion planning in the presence of static obstacles, we believe that extending MMD to more dynamic settings (e.g., robots sharing space with humans) is possible and an exciting direction for future work. One possibility is to incorporate MMD into an MPC-style execution mechanism, wherein the robots frequently replan and execute the initial part of the plan. However, it may be too slow to plan all the way to the goal using this strategy. Hence, the robots may have to plan over a bounded time window, for example, by integrating MMD with GBP as suggested by reviewer WAyg. We have added an appendix section (A1.1) on the prospects of using MMD in online windowed settings (suitable for dynamic environments), including an outline of the promise that integrating it with GBP holds. Best regards, The Authors

Response to reviewer wKu8 (part 1/2)

Dear Reviewer wKu8, Thank you for your valuable feedback and questions. We are glad that you appreciate the real-world importance of multi-robot motion planning, the significant improvement provided by our method in a variety of scenarios, and our thorough ablation studies. We address your questions below. 1. *The novelty of the method seems limited.* To the best of our knowledge, our algorithm is the first to scale diffusion planning to dozens of robots while only using readily available single-robot data. We make two central novel contributions: First, we show through extensive experimental evaluation that conditional generative models (e.g., diffusion models) struggle in directly learning to generate multi-robot trajectories due to the exponential blow-up in the configuration space with an increasing number of robots. Second, we show that it is possible to circumvent this curse of dimensionality by using diffusion models as low-level planners in coordination algorithms inspired by many classical MAPF algorithms. As far as we know, this connection has not been established before and opens the door for future work on this intersection. In fact, reviewer WAyg has already suggested that another state-of-the-art algorithm, Gaussian Belief Propagation (GBP), could potentially be integrated with our framework. This underscores the applicability of our method to endow a wide range of multi-robot coordination algorithms with data-driven trajectory generation capabilities. 2. *In the method section (3.2), It's hard to judge which parts are from classifical MAPF algorithms, which parts are contributed by the paper to adapt MAPF algorithms into diffusion planning methods.* Thank you for drawing our attention to this. We agree that Section 3.2 could be clearer in distinguishing between the components in MMD that are derived from established MAPF algorithms and our own contributions in adapting these algorithms to diffusion planning. To address this, we have clarified Section 3.2 to include that the only aspect directly inherited from MAPF algorithms is the logic for determining the placement of strong constraints, whether through search or prioritization. In more detail, other elements such as imposing MAPF constraints on diffusion models via guidance functions, translating the focal-list mechanism to sets of weak and strong constraints (as seen in MMD-ECBS and MMD-xECBS), and reusing previous computational efforts in CBS via short noising-denoising processes (in MMD-xCBS and MMD-xECBS), are novel contributions to multi-robot planning. We additionally demonstrate in our experimental analysis and Table 2 (Appendix) that applying Conflict-Based Search (CBS)—arguably the most widely used MAPF algorithm—to coordinate diffusion-based planners often fails to solve many planning problems within practical runtimes. Therefore, our work dives deeper and contributes more advanced coordination algorithms for diffusion models, going beyond a combination of MAPF and diffusion planning techniques. 3. *The methods are not very efficient when the number of agents increases.* Scaling algorithms to large numbers of robots is a central challenge in multi-robot motion planning, mostly due to the exponential growth of the size of the search space with increasing numbers of robots. Compared with MPD, which is unable to plan for more than 6 robots, our approach can effectively plan for dozens of robots and establishes a new state-of-the-art. Our paper is only a first step towards scalable and efficient multi-robot diffusion planning and hence focuses on presenting and thoroughly analyzing our novel algorithmic framework. MMD is by no means bounded by its current runtimes and improvements in diffusion planning will directly translate to improvements in MMD. We agree with you that there is also significant room for further algorithmic optimization and we leave that for future work. 4. *How is the single-robot diffusion models training? Which dataset? Is it a single-robot dataset or a multi-robot dataset?* We agree that adding details on our training and dataset creation processes would help make our work more accessible. To this end, we outline these here and added a section to our paper (A.7) with appropriate details. Our code will also be shared along with the final paper and include our training, dataset creation, and inference scripts together with other relevant code. **Dataset creation:** All of our datasets are single-robot datasets showcasing trajectories that follow map-specific motion patterns. For example, the Empty map has straight-line trajectories, and the Conveyor map has trajectories that pass through either of the conveyor passages. Each data point is a single trajectory. We create our datasets by connecting random start and goal configurations to map-specific sub-paths with RRT-Connect and then smooth them with an optimizer. (continued)

Response to reviewer AAKU (part 1/2)

Dear Reviewer AAKU Thank you for your constructive feedback. We are glad that you found the paper easy to understand and our experiments thorough. We are grateful for your questions and comments. We have revised the paper to incorporate your feedback and respond to your questions below. 1. *Can you explain more about what the motion pattern is? Also how this task-relevent local diffusion works and how data adherence works based on this.* We agree that better defining motion patterns and local diffusion models would strengthen our paper. We clarify this both here and also in the paper. A motion pattern represents a trajectory distribution optimizing a hidden cost function defined by a specific task dataset. For example, near a conveyor belt, we can define a motion pattern requiring robots to pass through either the top corridor right-to-left or the bottom corridor left-to-right. Regarding the local diffusion models, our local diffusion approach involves decomposing a large environment into smaller regions. The main idea is to learn local diffusion models for each region and compose them during planning. This makes learning more sample efficient and leads to better generalization via composition. We have added those explanations in section 3.3 and have provided more detailed explanations in Appendix A.5.1, including expanded details on data adherence score computation and extended examples in our Conveyor, Empty, Highways, and Drop-Region maps, as well as our 2x2 and 3x3 configurations. Readers could find visualizations there demonstrating these motion patterns and their adherence across different map configurations. 2. *In Figure 3, do you have an intuition as that why A\* methods maintain a good success rate for (b) and (c) even though the agent number keeps increasing? Is there any tradeoff with the computational efficiency compared to MMD?* Thank you for that question – it probes core differences between our proposed MMD method and the A\*-ECBS and A\*Data-ECBS baselines. MMD aims to generate trajectories that maintain high data adherence, while A\*-ECBS and A*Data-ECBS show a different planning strategy that impacts data adherence. Namely, A\*-ECBS does not take into account the underlying cost of following motion patterns and, as such, opts for just finding a collision-free solution. Thus, its success rate in finding a solution is higher since it easily avoids congested regions that are important for data-adherence. In high-congestion regions like the conveyor (b) and drop-region (c), we also observe a different behavior between MMD and A\*Data-ECBS. While MMD maintains precise motion patterns (quantified by high data-adherence scores), A\*Data-ECBS redistributes robots to less congested areas– allowing it to maintain a relatively consistent success rate as agent numbers increase at the cost of poor data-adherence scores. The key difference between MMD and A\*Data-ECBS baseline is that MMD prioritizes data adherence, whereas A\*Data-ECBS balances trajectory length, fast conflict resolution, and data adherence in a way that our experimental results suggested was effective for finding valid solutions but less so for finding data-adhering ones. 3. *In Sec. 4.2, it would be good to discuss the computational complexity between A\* and MMD.* We have added a brief discussion about the computational complexity in Section 4.2 with a reference to our detailed timing results in the appendix (A.2.1). The relationship between planning time and solution quality is intrinsically linked in our context. Our experimental results show that when A\*Data-ECBS achieves similar data adherence to MMD, the planning times are comparable. However, when A\*Data-ECBS produces solutions with lower solution quality (i.e., lower data adherence), it tends to have faster planning times. It's worth noting that there is significant potential for improving the computational efficiency of our approach through parallelization, particularly in the low-level planning phase, where each agent's path can be computed independently. However, we have left such optimizations for future work.