Multi-Robot Motion Planning with Diffusion Models
Authors: Yorai Shaoul
Itamar Mishani
Shivam Vats
Jiaoyang Li
Maxim Likhachev
Venue: ICLR 2025 Spotlight (2025)
Keywords: Multi-Agent Planning
Robotics
Generative Models
Primary area: applications to robotics, autonomy, planning
TL;DR: This paper presents a method combining diffusion models with search-based techniques to generate scalable multi-robot trajectories using only single-robot data.

Abstract: Diffusion models have recently been successfully applied to a wide range of robotics applications for learning complex multi-modal behaviors from data. However, prior works have mostly been confined to single-robot and small-scale environments due to the high sample complexity of learning multi-robot diffusion models. In this paper, we propose a method for generating collision-free multi-robot trajectories that conform to underlying data distributions while using only single-robot data. Our algorithm, Multi-robot Multi-model planning Diffusion (MMD), does so by combining learned diffusion models with classical search-based techniques---generating data-driven motions under collision constraints. Scaling further, we show how to compose multiple diffusion models to plan in large environments where a single diffusion model fails to generalize well. We demonstrate the effectiveness of our approach in planning for dozens of robots in a variety of simulated scenarios motivated by logistics environments.

Published as a conference paper at ICLR 2025
MULTI-ROBOT MOTION PLANNING WITH DIFFUSION MODELS
Yorai Shaoul Itamar Mishani Shivam Vats Jiaoyang Li & Maxim Likhachey! 'Camegie Mellon University Brrwwn University {yshaoul, mainhani, svats, jiaoyanl, maxim]er @cs. cmu. edu
'Equal contribution
ABSTRACT
Diffusion models have recently been successfully applied to wide range of robotics applications for learning complex multi-modal behaviors from data. However, prior works have mostly been confined to single-robot and small-scale enviromments due to the high sample complexity of learning multi-robot diffu- sion models. In this paper, we propose a method for generating collision-free multi-robot trajectories that conform to underlying data distributions while us- ing only single-robot data. Our algorithm, Multi-robot Multi-model planning Diffusion (MMD), does so by combining learned diffusion models with classi- cal search-based pachniques-generaatiie straints. Scaling further, we show how to compose multiple diffusion models to plan large environments where a single diffusion model fails to generalize well. We demonstrate the effectiveness of our approach in planning for dozens of robots in a variety of simulated scenarios motivated by logistics environments.
data-driven motions under collision con-
INTRODUCTION
Multi-robot motion planning (MRMP) a fundamental challenge in many real-world applications where teams of robots have to work in close proximity to each other to complete their tasks. In automated warchouses, for example, hundreds mobile robots and robotic manipulators need to coordinate with each other transport and exchange items while avoiding collisions. Learning mo- tions from demonstrations can oftentimes allow robots to complete tasks they couldn't otherwise, like navigating a region in a pattern frequently followed by human workers: however, is un- clear how to best incorporate demonstrations in MRMP. In fact, MRMP at its simplest form, where robots only concerned with finding short trajectories between start and goal configurations, is already known to be computationally intractable (Hopcroft & Wilfong 1986) (186)-significantl harder than single-agent motion planning due to the complexity of mutual interactions between robots. Attempting to simplify the problem, various approximate formulations have been proposed in the literature. For example, a popular approach is to formulate the problem multi-agent path find- ing problem (MAPF) (Stern al. 2019) by discretizing space and time. While the latest MAPF planners (Li et al. |021]0000 Okumura, 2024) can compute near-optimal plans and scale to hundreds of agents, they make strong assumptions, such constant velocities and rectilinear movements that limit their real-world application and reduce their ability to generate complex behaviors learned from demonstrations.
In single-agen motion planning. methods that learn to plan from data (Xiao et al. 2022) have been widely used circumvent similar limitations resulting from inaccurate models (Vemula et al. 2021)

---

Published as a conference paper at ICLR 2025
partial observability (Choudhury et al., 2018) and slow planning (Sohn et al. 2015 Qureshi al. 2020). More recently, diffusion models (DM) have emerged as the generative model of choice for learning visuomotor manipulation policies from demonstrations (Chi et al. 2024). motion plan- ning (Carvalho et al. 2023), and reinforcement learning (Janner et al. (022). However, there has been relatively little work extending these ideas to multi-robot motion planning. This is due to the twin challenges of generating high quality multi-agent data and the curse of dimensionality, i.e.,
significantly higher sample complexity of learning multi-robot models.
In this paper, we propose data-efficient and scalable multi-robot diffusion planning algorithm. Multi-robot Multi-model planning Diffusion (MMD), that addresses both these challenges by com- bining constraint braseeditt-baeed MAPF planners with diffusion models. Importantly, our approach calls for learning only single-rohot diffusson models, which does away with the difficulty of obtaining multi-robot interaction data and breaks the curse of dimensionality. MMD generates collision-fres freee trajectories by constraining single-robot diffusion models using our novel spatio-temporal guid- ing functions and choosing constraint placement via strategies inspired by MAPF algorithms. Our contributions in this paper are threefold: (1) We propose a novel data-efficient framework for multi- robot diffusion planning inspired by constraint-based search algorithms. (2) We provide com- parative analysis of the performance of five MMD algorithms, each based on a different MAPF algorithm, shedding light their applicability to coordinating robots leveraging diffusion mod- els for planning.
(3) We show that we can scale our approach to arbitrarily large and diverse maps by learning and composing multiple diffusion models for each robot. Our experimental re- sults from varied motion planning problems in simulated scenarios motivated by logistics environ- ments suggest that our approach scales favorably with both the number of agents and the size of the environment when compared to alternatives. Video demonstrations and code are available at httpss//mmlliirrott--dff.e htt.:/fuuiiinnittuuu.... github.
PRELIMINARY
In this section we define the MRMP problem and provide relevant background on constraint-based MAPF algorithms and on planning with diffusion models. Sec. elaborates on how we combine these concepts to coordinate numerous robots that plan with diffusion models.
2.1 MULTI-ROBOT MOTION PLANNING (MRMP)
Given n robots R, MRMP seeks of collision-free trajectories, one for each robot, that optimize a given objective function. Let St be the state space of single robot and a state be s := [q q St where q' and q' are the configuration and velocity of the robot. Each robot has an assigned start state Sum E S' and binary termination (goal) condition T S - (0. 1). An MRMP solution is a multi-robot trajectory 7 = {r1, ...7", where 7 : [o] + S' represents the trajectory of robot R, over the time interval [0, T'), with T being the terminal time. In practice, we uniformly discretize the time horizon into H time steps and optimize over a sequence of states T' = =(s}, (sf.s),.... sJ..., ). Subscripts, e.g., T/. indicate indexing into a trajectory. Each trajectory T² must avoid collisions between robots and with obstacles in the environment. In MRMP, robots share workspace W (i.e., W C R for general robots and W C R² for robots the plane) and occupy some volume or area within W, which we denote as Rx(g') C W for rohot R; in configuration q'.
The usual MRMP objective is to minimize the sum of the single-robot costs (e.g., the cumulative motion) across all robots. General cost functions can be defined on the trajectories, and the ob- jective then becomes [(T) + + D. cost(r'). When learning from data, we are interested in data adherence, i.e., the trajectories should match the underlying trajectory distribution. We define cost (T) 1 Σ costeau( (r') quantify how well, on average, trajectories in T follow their underlying data distribution. This metric is task specific; we provide some examples in Sec.
2.2 MGLTI-AGENT PATH FINDING (MAPF)
The MAPF problem, a simpler form of MRMP, seeks the shortest collision-fre free paths II = { . " for n agents graph. This graph approximates their configuration space, with vertices corresponding to configurations and edges to transitions. Each path ा' {qi.... q'p is a trajectory without velocity that need not be dynamically feasible. In MAPF studies, constraint-based
2

---

Published as a conference paper at ICLR 2025
algorithms have become popular due to their simplicity and scalability. These algorithms are effec- tive, in part, because they avoid the complexity of the multi-agent configuration space by delegating planning to single-agent planners and avoid collision via constraints. For instance, if configuration q' for R, leads to a collision at time (or interval) 1, this can be prevented by applying the constraint set C = [(R,,, q' })} to the path πτ', thereby preventing the configuration from being used that time. Several MAPF algorithms, including Prioritized Planning (PP) (Erdmann & Lozano-Peree
1987 and Conflict-Based Search (CBS) (Sharon et al.) 2015), use this mechanism to force single- agent planning queries to avoid states that would lead to collisions. We detail these methods in Sec. G and explain how, despite traditionally being used for MAPF, their principles can be applied to coordinating robots in continuous space that generate data-driven trajectories via diffusion models.
2.3 PLANNING WITH DIFFUSION MODELS
Motion planning diffusion models are generative models that learn denoising process to recover a dynamically-feasbbl trajectory from noise (Carvalho et al. 2023 Janner et al. 2022). Given a dataset of multi-modal trajectories, diffusion models aim to generate new trajectories that follow the underlying distribution of the data. Additionally, these trajectories may be conditioned objective O, for example, goal condition and collision avoidance. Specifically, given task objective O, motion planning diffusion models aim to sample from the posterior distribution of trajectories:
task
arg max log p(T)) O) arg min (J(T') log ((T)(
(1)
The first term of the objective, J(r'), ), can be interpreted (Carvalho et al. (202)), in which we try to minimize a cost function (or, equivalently, maximize reward function). The second term, p(T),, is the prior corresponding the data adherence discussed in Sec. 2.1
standard motion planning objective
Diffusion models are type of score-based model (Song et al. 2021). where the focus is learn- ing the score function (the gradient of the data distribution's 's log-probability) rather than learning the probability distribution directly. The score function is learned using denoising score matching, a technique for learning to estimate the score by gradually denoising noisy samples. The diffu- sion inference process consists of K-step denoising process that takes a noisy trajectory K r and recovers a feasible trajectory 97', which also follows the data distribution. We use the notation Pr' T',-. ..... 7' to denote the evolution of the trajectory in the diffusion process. To generate a trajectory 97" from noise trajectory K 7' ~ (O, I), we use Langevin dynamics sampling (Ho jet al., 2020), an iterative process that is a type of Markov Chain Monte Carlo method. At each denoising step k E {K, 1), trajectory-space mean 1i-1 1 is sampled from the network pao
! =
[0=)=po(">)) (*(***)
(2)
Now, with the variance prescribed by deterministic schedule {32, I k {K.... 11,, the next trajectory in the denoising sequence is sampled from the following distribution:
k-1 N + 1 1k-11)
(3)
Guidlncee
The term V (((pr) is the gradient of additional trajectory-space objectives (described in Eq. D imposed on the generation process. This term, also called guidance, can include multiple weighted cost components, each optimizing for a different objective. For instance, we can have J= -Doby + AAamoathhaammoth to penalize trajectories in collision with objects via Jabj and to encour- age the trajectory to be dynamically feasible via Jsmooth We denote the trajectory generation process queried with a start state sumn goal condition T and costraint set (Sec. 3.1 as f (s) C),
METHOD
We present Multi-robot Multi-model planning Diffusion (MMD), an algorithm for flexibly scaling diffusion planning to multiple robots and long horizons using only single-robot data. MMD im- poses constraints on diffusion models to generate collision-free trajectories, addressing three main questions: how, when, and where to impose them. First, we discuss integrating apatio-tempont constraints into the diffusion denoising process through guiding functions. Next, we introduce five MMD algorithms, each inspired by a MAPF algorithm regarding constraint placement and timing. Finally, we demonstrate how sequence multiple models for long-horizon planning.
3

---

Published as a conference paper at ICLR 2025
Algorithm 1: MMD-CBS sketch. Colored lines are only in MMD-PP, MMD-ECBS
Input: Starts, goal conditions, and single-robot
diffusion models {sian: T [
(a) Two robots aim switch positions. Blindly generated single-robot trajectories collide.
Output: Trajectories
{ |
Nuv new CT node; New.. Cr + 0 (1,
for i E (1...., . do
Camigg Oweak 0,0
If Emply constraints
Garong f- {(Ri, 7) Oweak +- {(R,, 7)
B Avoid other robots.
Penalize callisions.
Nmo. <- fa T,, Caronn U Cweak
end
return N
CT
4- (N
I| Initialize CT.
while CT + 0 do
N f arg min nunContlicts
N'ECT
Remove N from CT
(b) The diffusion denoising process for the left robot in (a), under temporally- activated constraint (in red), yields multi- modal trajectories.
if N.T conflict-free then
return N.T
Retum collision free.
end
p. 1. R,, R₂+ f- getOneten.flett (N.r)
for l E (i.j] Spli N; constrain conflicting robots. do
N' < N.copy
N² t C* U RRRE, (,)
C t- [Re, (N' .T)
Penalize collisions.
(c) Collision-frre solution.
N (SSunn T .N.CC CCCCeu))))
CT + CT CT U[N'
Figure 1: An illustration of how MMD- CBS generates collision-fie -frce trajectories with constrained diffusion models.
end
end
3.1 CONSTRAINTS DIFFUSION MODELS
An intuitive and effective constraint for multi-robot motion planning in robotics is the sphere con- straint (Li et al. 2019 Shaoul et al. 2024b). It defined by a point p E W and restricts robots from being closer to p than radius E R at certain time range := [ At, t + At). The sphere constraint can be imposed as a soft-constraint on diffusion model by incorporating it in its guiding function J.).. This can be done by adding cost term Te that repels the robots from the sphere's 's center point p. Let & be the generated trajectory for R, at step & of the diffusion denoising pro- cess, and (Ra, (p),,,, t) be sphere constraint centered at p with radius over time interval t. The guidance cost term for R, can be defined as:
Je( = Σ max (c.r (R.
0)
(4)
with d (Ra(*T(),p) the distance from point p to R, at r and 2 1 padding factor.
3.2 CONSTRAINING STRATRGIES
To determine when and where to apply constraints diffusion models, MMD draws on MAPF strategies like CBS and PP. We propose five MMD variants, each inspired by a state-of-the-art search algorithm. Alg. provides summary of these methods and we elaborate upon them here
'The sphere constraint generalizes the MAPF vertex constraint, it constrains robots from visiting the point of collision itself instead of single colliding contiguration corresponding vertex in graph. In MAPF, the point of collision and the graph vertex coincide.
'In MMD, we use the search or prioritization logic found in MAPF algorithms for placing "strong" con- straints on diffusion models, while all other aspects of MMD are more loosely inspired by MAPF algorithms.
4

---

Published as a conference paper at ICLR 2025
MMD-PP. Prioritized Planning sequentially plans paths for robots R, A [1....n) This dering of robots is treated as a priority ordering in that, on each call, robot R, must generate a path n' that avoids all R, that previously planned. Robot R, does so by respecting the constraints C == (-R, q' R,(q') n (T!) * 0 Wt). To translate this approach to trajectory gener- ation with diffusion models, MMD-PP represents robot volumes using spheres, as is common in robotics, and uses the sphere representation of higher-priority robots as sphere soft-constraints for lower-priority robots. Specifically, let a nigh-priority robot R, be modeled with M, spheres and p/n and ri. be the position and radius of the m" sphere time t. Then, lower-priority robot R, generates a trajectory under the constraint set {(R4, S, (Pi)): t) m E (1....M, MaJ.j - i], where < indicates priority precedence. In Alg. (Ra, T) means that all trajectories of Rzzt in T must be similarly avoided.
MMD-CBS. CBS is a popular MAPF solver that combines "low-level" planners for individual agents with a "high-level" constraint tree (CT) to resolve conflicts (i.e., collisions). The algorithm initiates by creating the root node Nrott in the CT, planning paths for each agent independently, and storing these paths in - CBS repeatedly extracts nodes N from the CT and inspects NI11 for confticts. If no conflicts exist, the algorithm terminates, returning ..II. Otherwise, CBS selects a conftict time i where agents R, and R, collide at positions q' के and q' = in N.II. CBS then splits node N into two new CT nodes, N, and Nj. each inheriting the (initially empty) constraint set N.C and paths N.11 from N, and incorporating new constraint for preventing the respective agent from occupying the conflict position at time t. For example, N,.C + N.C' u { (R. ()) for R,, Paths for R, and R, are then replanned using low-level planners under the updated constraints in N,.C and N, The new CT nodes, with updated paths in NII and NI.II. are added to the CT. MMD MMD-CBS follows the general CBS structure. It keeps a CT of nodes N, each with trajectories N.T, and uses motion planning diffusion models as low-level planners. The algorithm identifies a collision point p for each conflict and resolves it by imposing sphere soft-constraints centered at p on affected robots (see Fig. for an illustration and Sec.
-I.
A.4 for parameter values).
MMD-ECBS. Enhanced- CBS (ECBS) (Barer al. 2014) informs CBS low-level planners of the paths of other robots in the same CT node and steers the search towards solutions that are more likely to be collision-free. To emulate this diffusion- based trajectory generation, MMD-ECBS imposes two types of soft constraints: "weak" and "strong." For each robot R, with a trajectory in the CT node N. a weak soft-constraint that forbids R, from colliding with any other R2 with T² E N.T is imposed. This is done in a similar way MMD-PP but with lower penalty value (Sec. A.4). The strong constraints are the same as those in MMD-CBS, resolving previously observed conflicts.
Reusing Experience in CBS. Recent studies indicate that leveraging previous single-robo solutions to guide replanning enhances the efficiency of CBS (Shaoul et al. 2024a). This is primarily because the motion planning problem between CT node its successors is nearly identical, with the only difference being a single constraint, making planning from scratch wasteful. This can be utilized in MMD replanning by initially adding noise to the stored trajectory for a limited number of steps (3 in our experiments; regular inference uses 25 steps) and then denoising with the new soft-constraints. This approach, in the context of single-robot planning, was first proposed in Jaaner et al. (2022) and further refined in Zhou et al. (2024). Adding this functionality to MMD-CBS and HIMD-ECB yields our two final MMD algorithms, MMD-xCBS and MMD-XECBS, respectively. Both reuse previous solutions to inform replanning and are otherwise unchanged.
3.3 SEQUENCING DIFFUSION MODELS FOR LONG HORIZON PLANNING
Diffusion models have shown notable success learning trajectory distributions within specific con- texts. However, they face challenges in modeling complex trajectory distributions and generalizing to diverse contexts (e.g., significantly different obstacle layouts). We propose utilizing an ensemble of local diffusion models for each robot to facilitate varying-context planning. Each local model is trained to capture a particular motion pattern, i.c., a trajectory distribution generated by a hidden cost function defined by a specific task dataset. For example, near 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. By sequentially combining multiple local models, each corresponding to local map segment, we enable morgooo single-robot planning that is easier to learn, generalizes well to different contexts, and scales effectively to large maps.
5

---

Published as a conference paper at ICLR 2025
Average Data Adherence by Nechod
Averoge Data Adherence Medhod
0-0-6
Metic
(a) Empty map.
(b) Data adherence the (c) Highways map.
(d) Data adherence in the Highways map.
Empty map.
Figure 2: A comparison between MMD and "composite" diffusion models that generate trajectories for all agents at once. We observed consistent performance from MMD but sharp decrease for the baseline, unable to produce valid solutions for 9 agents (denoted as zero adherence score). Since MMD uses the same single-agent model for all robots in these experiments, it is straightforward to keep increasing the number of agents without needing any retraining or new datasets.
During online planning, given specific single-robot task Of (which includes the start state and the termination condition), we can query the task-relevant local diffusion models to generate a full- horizon motion plan. Motivated by Mishra al. (2023), this is done by sampling from the local models in parallel, while incorporating a cross-conditionngg term that constrains the local trajectories connect seamlessly. Let T be local trajectory sampled from a local probability distribution p'. The goal of the single-robot planner is to sample from the posterior distribution of trajectories:
arg max
log logp(Ti(0)= = arg max logp(T") ...., "".,, ri. .i.,
(5a)
subject to
11 = T 11
i1-1 Vi I....,L L
(5b)
Following Eq. the new objective becomes:
[ [(Ti)....,,
arg min ritl Thi
rid)
Σ log ((gp(
(6)
In practice, MMD ensures proper sequencing of the local diffusion models by introducing con- straints requiring the last state of the trajectory from model I be equal the first state from model 1+1 (see Eq. 5b and treating generation of local trajectories as inpainting (Lugmayr et al. 2022).
4 EXPERIMENTAL ANALYSIS
We tested MMD's efficacy in learning multi-robot trajectories on increasingly complex maps with varying numbers of holonomic ground robots simulated warehouse, modeling robots as disks. Our goals were to (i) compare our approach with common methods for integrating data into multi-robot trajectory generation, (ii) identify the most effective constraining strategies with MMD, and (iii) evaluate MMD's scalability. Each experiment with robots begins by randomly picking start and goal states on a map for various algorithms to compute valid trajectories T (or MAPF paths II) between. We evaluated the methods by success rate, the percentage of problems solved with no collision within time limit, and data adherence, the average alignment of T¹ E T with the dataset motion patterns. Data adherence perfect conformity and lower otherwise. Our evaluation maps, datasets, and adherence functions are summarized here with simple illustrations and more details are in the appendix.
a map-specific function costaau (7'), scoring 1 for
Another option is to add guidance term penalizing discontinuity. This approach is more flexible as it can optimize for connection points that leamned well (e.g., classifier guidance the connection itself).

---

Published as a conference paper at ICLR 2025
Drop-Region map (Fig. 3c simulates package drop-off chutes. Motion demonstra- tions are trajectories between random states that include pause at one of sixteen drop-off regions- -ext to any chute edge midpoint. Adherence is met for T', i.e., costaam (T') = 1, if includes such a pause. Otherwise, it is zero.
Conveyor map (Fig. 3b features narrow passages with directional motion require- ments. Demonstrations connect random states with trajectories that pass along the top corridor to the left, or through the bottom corridor to the right. Trajectory T' adheres data if similarly passes through either corridor before reaching its goal.
Highways map (Fig. Bay. requires counter-clockwise movement around central obstacle-a pattern shown in its associated data. This map can be seen as modu- lar building block for larger multi-robot environments with its required motion pat- tern promoting easier coordination. Adherence is met for T' if its cumulative motion within the map counter-clockwise.
Empty map (Fig. 2a) is our simplest. Robots are scored highly if they move in straight lines and gradually worse the more they deviate. Demonstrations are of straight line motions.
Larger Maps (Fig. 5 In our larger scale experiments (Sec. 4.3)
trajectories are computed within 2 x 2 and 3 x 3 maps composed of smaller, local maps. Required motions are dictated by spanned local maps, and the overall adherence is the average adherence per local map.
4.1 DECOUPLING SCALES MULTI-ROBOT DIFFUSION PLANNING
An appealing approach for learning multi-robot trajectory generation is by obtaining multi-robot trajectory datasets and training a single model to jointly generate trajectories for all robots. To test this approach, we evaluated MPD-Composile a state-of-the-art motion planning diffusion model (MPD) (Carvalho et al., 2023) that we trained on multi-robot data we collected in two maps: Empty and Highways. We created three models: for 3, 6. and robots. Each model was also given an additional guidance term that penalized collisions between robots. Across 300 tests, 50 for each map and group size, we compared MPD-Composite to MMD-xECBS (referred to as MMD). See Fig. 2 for results. The composite model achieved perfect success rates and high data adherence scores with 3 robots but struggled as the number of robots increased to 6. No valid trajectories were generated in any test with 9 agents using MPD-Composit in either map. In contrast, MMD solved all 300 problems successfully and further scaled to 40 agents in additional random tests, also producing trajectories with high data adherence scores and no collisions.
4.2 MMD OUTPERFORMS MAPF WITH LEARNED COST MAPS
From search-basee planning viewpoint, compelling way integrate motion data into multi- planning is by reducing MRMP to MAPF and forming cost maps to direct algorithms like ECBS (Cohen et al., 2016)) This sacrifices dynamic feasibility, limiting solutions fixed graph, but can still offer a desirable homotopy class and be assessed for data compliance. Our second experiment set evaluates this method's potential to produce data-compliant motions (see Fig. B}. We created 180 motion planning problems, 10 per group size across three maps, and assessed two search-based methods: A ADaataECCSS and A *EECCS. The former plans single-robot paths using A* (Nilsson) 1982) with statistical cost maps, where edge costs are lower if map dataset trajectories frequently visit those areas. The latter uses uniform costs (i.e., has no knowledge of the data) and is reported only to provide context for A Data-FFCBS's performance.
Integrating motion data into statistical cost maps shows mixed results: it improves Highways map performance by 35% over A*ECBB but reduces success rates. In other maps, it finds collision- free paths but struggles with complex motion distributions. MMD methods, by contrast, effectively generate trajectories with high data adherence and often high success rates, As shown in ... and Table 2 planning time and solution quality correlate: when A A*Data-ECBS matches MMD's data adherence. their planning times align, but faster A*Data-ECBs solutions come at the cost of lower quality. We believe there is significant potential to improve the computational efficiency of MMD through parallelization. However, have left such optimizations for future work.

---

Published as a conference paper at ICLR 2025
Success Rate by Method
Average Data Adherence by Method
Methed
MMD-ECES
O-
MMD-CIS
MMD-HCBS
ArDete-EEES
MMD-KECBS
Namber ef Aggets
Aamber Agaess
Highways map.
Success Rate by Method
Average Data Adherence by Method
Methed
ECBS
NMD-CBS
MCBS
A/Datt ECBS
A-EC35
XMCBS
215
350
315
860
(b) Conveyor map.
Success Rate by Method
Average Data Adherence by Method
Mathed
NWD-ECES
NMD-CES
MMD-CCB
MMD
Agentt
(c) Drop-Region map.
Figure 3: Analysis of success rates and data adherence scores, in randomly generated planning queries, of all MMD instantiations and MAPF method with and without learned cost map. The left column shows our maps, the middle column compares success rates across 10 trials per robot count, and the right column presents the average data adherence scores.
4.2.1 ANALYZING MMD CONSTRAINING STRATEGIES.
Further analysis reveals trend familiar from the MAPF literature. MMD-CBS struggles with scal- ability, MMD-ECBS significantly outperforms it, and accelerated versions further improve perfor- mance. MMD-PP finds efficiency in requiring only one inference pass per robot, however, because the constraints diffusion models are soft, trajectory generation queries are not guaranteed to completely avoid higher-priority robots, and as such MMD-PP may fail to produce collision-fie free solutions. This is reflected in lower success rates in congested maps. In contrast, CBS-based MMD methods only failed by exceeding our 60-second runtime limit. MMD-XECBS outperformd other MMD algorithms in success rates and matched MMD-ECBS in data adherence.
To test MMD's MRMP solving ability without regard to data adherence, we created two free-space experiments focusing robot interactions (Fig. 4p. In the circle setup, robots move between oppo- site points on a circle, likely colliding at the center. the weave setup (inspired by Tajbakhsh et al. (2024), ) robots begin opposite points of square, aiming to switch places. CBS- baseb meth- ods were challenged in circle since incrementally constraining the center region is time-consuming. MMD-PP's stronger constraints navigated around congestion and solved more problems, however, occasionally failed to produce valid solutions. In weave. where navigating around congestion is more difficult, CBS-based methods generated collision-free trajectories more effectively.
4.3 SEQUENCED DIFFUSION MODELS FOR LONG-HORIZON PLANNING
We present feasibility study on expanding MMD algorithms to larger maps using the sequencing method described in Sec. 3.3 This technique assembles smaller local maps, each associated with
8

---

Published as a conference paper at ICLR 2025
Average Trijectory Length Per Agent by Method
Average Planning Time Method
Method
MMD-FORS
MMD-PF
MMD-CBS
MMD-C885
MMD--ECUS
Narter of Agpets
Nunber et tapees
Circle setup.
Average Trajectory Length Per Agent by Method
Average Planning Time Method
Method
MMD-PP
MMD-CRS
MMDxC3S
MMD
Namber Agents
Namber of
(b) Weave setup.
Figure 4: Scalability tests in high-congestion free-space MRMP. Circle (top row) asks robots to swap positions between opposite points on the perimeter. Weave (below), asks robots to exchange positions along uniformly spaced boundary points. Length is zero for failed problems (MMD-PP failures were due to yielding invalid solutions, and other methods failed by exceeding 240 seconds).
diffusion model, to collectively generate long-horizon, data-driven trajectories. In our experiments, we tested three MMD methods MMD-PP, MMD-ECBS, and MMD-xECBS in 120 trajectory generation tests, allowing relaxed 240-second time frame. A standout feature of the sequencing method is its ability to create trajectories that follow task-skeleton passing through series of local maps within the larger global map. For this purpose, our experiments assign a random sequence of three tasks per robot (a sequence of local maps), and randomly selects start and goal states within the first and last local maps in the sequence. The results (Fig. 5 show MMD-XECBS scaling to long planning horizons without compromising data adherence. This demonstrates MMD's capability to efficiently produce multi-robot trajectories in large environments by utilizing diffusion models trained with easily gathered data from small, local maps.
RELATED WORK
Multi-Robon Motion Planning. Many MRMP algorithms (Sanchez Latombe, 2002 Solovey
et al.) 2016) approach the problem by treating it as a coupled system applying sampling-bant based planners such as PRM (Kavraki et al. 1996) and RRT (Karaman & Frazzoli (01I)) to the composite configuration space of all robots. While this approach guarantees probabilistic completeness, struggles to scale with the number of robots due to the exponential growth of the configuration space. Given the ESPACE-hardnest of MRMP (Hoperoft & Wilfong 1986). many practical algorithms introduce approximations to make the planning problem more tractable. Some of the most successful MRMP methods transform the problem into multi-agent path finding (MAPF) problem (Stern)
et al. 2019) through state and time discretization (Li et al., 2019 Honig et al. 2018).
Decoupled algorithms like prioritized planning (Erdmann
Lozano-Perez) 1987) and Leroy et al. (1999) generate robot motions one after another, fixing each plan and regarding them as dynamic obstacles in subsequent planning iterations. This allows them to quickly find solutions for large numbers of robots, but sometimes fail to find any solution even if one exists, i.e., they are often incomplete. Seeking to balance theoretical guarantees with practical efficiency, hybrid algorithms like CBS (Sharon et al. 2015) and its variants (Barer et al. 2014 Li et al. (022]) decouple the MRMP into two levels high-level, in which they resolve conflicts between robots, and low-level, in which they plan motion for each robot independently. A and its derivatives
the de facto standard for motion planning for navigation, serving as the low-level search algorithm in many of these state-of-the-art approaches, they efficient, complete, and bounded sub-optimal.

---

Published as a conference paper at ICLR 2025
Success Rate by Method
Average Data Adherence by Method
Medicd
MMD-PP
MMD-ECaS
MMD-EECB
Namber of Ageets
115
(a) x map.
Success Rate by Method
Average Data Adherence by Method
Mothod
MMD.Pp
MMD
50
3-1
Agents
(b)3 3 map.
Figure 5: Experimental setup and results for scaling MMD larger environments and longer plan- ning horizons. MMD still relics on single agent data in small, local maps and does not require training of new networks for this scale-up. We evaluate three MMD variants across two large maps made of tiled local maps to cover a significantly larger area.
Planning with Diffusion Models. Lately, there has been surge of interest in applying diffusion models (Sohl-Dickstein et al., 2015) to solve sequential decision making tasks, including planning and reinforcement learning (Ubukata al. 2024). Diffuser (Janner al., 2022) first proposed the
idea of using diffusion models for trajectory planning and showed how dassifier-guided sampling and image inpainting can be used for adaptation at test time. Recent works have used diffusion
models as priors for single-robot motion planning (Carvalho et al.] (202)) for learning visuomotor policies (Chi et al.] (204)). and for offline decision-making (Ajay et al. [202)). Most of these have been limited to angle-agent planning with two notable exceptions. Jiang al. (2023) learns a joint motion distribution for multi-agent motion prediction and concurrent work by Mishra et al. (2024) uses tempoall factor graphs to compose modular generative models for solving long-horize bimanual tasks. By contrast, we focus on generating kinodynamically feasible and collision-fi free trajectories for dozens of robots and complex environments without learning joint distribution.
6 CONCLUSION
In this paper, we present MMD, multi-robot motion planner that learns to generate smooth collision-fred trajectories for dozens of robots in complex environments. Our key contribution is showing how single robot diffusion models can be effectively combined with search algorithms to generate data-driven multi-robot trajectories. By learning only single-rohot diffusion models, MMD simplifies data requirements and breaks the curse of dimensionality plaguing approaches that learn from multi-robot data. Additionally, by learning generative models of robot trajectories, MMD over- comes many of the limitations of popular model-based MAPF algorithms, such as state discretiza- tion, known cost function, and constant velocities. We believe MMD opens up exciting avenues for future work on combining the strengths of search algorithms and diffusion planning.
Limitations. We are excited about the potential of MMD to push forward multi-robot coordination and collaboration and offer a few avenues for future work. First is combining MMD with decen- tralized and windowed multi-robot planning algorithms, like Gaussian Belief Propagation (GBP) (Patwardhan et al., 2023), whose collision avoidance signals could be incorporated into single-robot diffusion guidance functions. We discuss this research direction in Sec. A.I.I Second, we believe that the CBS- based MMD methods can be greatly accelerated, mostly through parallelization of the high-level search. Finally, we believe the frontier of MRMP lies in collaboration. Currently, MMD focuses on coordinating robots, seeking to produce collision free data-driven trajectories. Carrying out collaborative tasks is interesting next step.
10

---

Published as a conference paper at ICLR 2025
7 REPRODUCIBILITY
We aspire for MMD to be easily used and extended by researchers and practitioners. To this end, we make our source code for all MMD algorithms, scripts for data generation, training, and evaluation, and evaluation maps publicly available at htt http://gtttbbbbb com/ voraish/aa mmd This code, along with the parameter values detailed in Sec. A.4] is sufficient for reproducing the experiments and results presented in this paper. To run our code "out of the box," without dataset generation or training, we provide pre-trained models and datasets detailed Sec. | with detailed instructions. For hardware and software dependencies, we specify the exact versions of libraries and tools required in our repository and also detail our hardware setup in Sec. A.4
ACKNOWLEDGMENTS
We thank Mohit Sharma and Ilan Mitnikov for fruitful discussions. This work was supported by the National Science Foundation under grant IIS 2328671 and grant #1955361, well by the Office of Naval Research (ONR) under REPRISM MURI N00014241266 and ONR grant #N00014-22 2592. Partial funding was also provided by gift from Amazon and the Robotics and Al Institute.
REFERENCES
Anurag Ajay. Yilun Du, Abhi Gupta, Joshua B. Tenenbaum, Tommi Jaakkola, and Pulkit Agrawal. Is conditional generative modeling all you need for decision making? In The Fleventh Interna- tional Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023.
Max Barer, Guni Sharon, Roni Stern, and Ariel Felner. Suboptimal variants of the conflict-bssed search algorithm for the multi-agent pathfinding problem. In International Symposium on Com- binatorial Search, pp. 19-27,200 2014.
Joao Carvalho, An Le, Mark Baierl, Dorothea Koert, and Jan Peters. Motion planning diffusion: Learning and planning of robot motions with diffusion models. In International Conference on Intelligent Robots and Systems. IEEE, 2023.
Cheng Chi, Zhenjia Xu, Siyuan Feng, Eric Cousineau, Yilun Du, Benjamin Burchfiel, Russ Tedrake, and Shuran Song. Diffusion policy: Visuomotor policy learning via action diffusion. The Inter- national Journal of Robotics Research, 2024.
Sanjiban Choudhury, Mohak Bhardwaj, Sankalp Arora, Ashish Kapoor, Gireeja Ranade, Sehastian Scherer, and Debadeepta Dey. Data-driven planning via imitation learning. The International Journal of Robotics Research, 37(13-14):1632-1672, 2018.
Liron Cohen, Tansel Uras, TK Satish Kumar, Hong Xu, Nora Ayanian, and Sven Koenig. Improved solvers for bounded-suboptimal multi-agent path finding. In IJCAI, 2016.
Michael Erdmann and Tomas Lozano-Perez. On multiple moving objects. Algorithmica, pp. 477- 521, 1987.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. In H. Larochelle. M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neu- ral Information Processing Systems, volume 33, pp. 6840-6851. Curran Associates, Inc., www.nnuriis... wwtpccppppppp.eeeeeeeee foarr_filee files/paper//222//
2020. URL https::/proceeedd//://// Elle/Acccccecc5544100666777 htt.a/771111aa11111aaa----aaeaee .ddf
Wolfgang Hönig, James A Preiss, TK Satish Kumar, Gaurav S Sukhatme, and Nora Ayanian. Tra- jectory planning for quadrotor swarms. IEEE Transactions on Robotics, 34(4):856-869, 2018.
John E Hopcroft and Gordon T. Wilfong, Reducing multiple object motion planning to graph search- ing. SIAM Journal on Computing, 7583)776 1986.
Michael Janner, Yilun Du, Joshua Tenenbaum. and Sergey Levine Planning with diffusion for
flexible behavior synthesis. In International Conference Machine Learning. PMLR, 2022.
11

---

Published as a conference paper at ICLR 2025
Chiyu Jiang, Andre Cormman, Cheolho Park, Benjamin Sapp, Yin Zhou, Dragomir Anguelov, al. Motiondiffuser: Controllable multi-agent motion prediction using diffusion. Proceedings of the IEEE/CVF Conference Computer Viston and Pattern Recognition, pp. 9644-9653, 2023.
Sertac Karaman and Emilio Frazzoli. Sampling-based algorithms for optimal motion planning. The International Journal of Robotics Research, pp. 846-894, 201
Lydia E Kavraki, Petr Svestka, J-C Latombe, and Mark H Overmars. Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE transactions on Robotics and Au- tomation, 12(4):566-558) 1996.
J.J. Kuffner and S.M. LaValle. Rrt-connect: An efficient approach to single-query path planning. IEEE International Conference on Robotics and Automation, 2000.
Stephane Leroy, Jean-Paul Laumond, and Thierry Siméon. Multiple path coordination for mobile robots: A geometric algorithm. In IJCAI, volume 99, pp. 1118-1123, 1999.
Jiaoyang Li, Pavel Surynek, Ariel Felner, Hang Ma, TK Satish Kumar, and Sven Koenig. Multi- agent path finding for large agents. In AAAI Conference on Artificial Intelligence, pp. 7627-7634, 2019.
Jiaoyang Li, Wheeler Ruml, and Sven Koenig. Eecbs: A bounded subolpidaauubooiiaalaaa search for multi-agent path finding. In AAAI Conference Artificial Intelligence, pp. 12353-12362, 2021.
Andreas Lugmayr, Martin Danelljan, Andres Romero, Fisher Yu, Radu Timofte, and Luc Van Gool. Repaint: Inpainting using denoising diffusion probabilistic models, 2022. URL https:
7/arxiv. wwt.vvs.rrrab///// /2011.2211... 09865
Utkarsh Aashu Mishra, Shangjie Xue, Yongxin Chen, and Danfei Xu. Generative skill chaining: Long-horizon skill planning with diffusion models. In Conference on Robot Learning, 2023.
URL Btgp:tttss///eeeeeviiii netpeeeww.eeeeeeeeeeeeeeeeeeeeee fort/fformm2 HEttHJ991y5
Utkarsh Aashu Mishra, Yongxin Chen, and Danfei Xu. Generative factor chaining: Coordinated manipulation with diffuusion factor graph. In 8th Annual Conference on Robot Learning, 2024. httttp:://ppeneevieeee
p6
Nils J Nilsson. Principles of artificial intelligence. Springer Science Business Media, 1982.
Keisuke Okumura. Engineering lacam": Towards real-time, large-scale, and near- pear-optimal multi- agent pathfinding. In 23rd International Conference Autonomous Agents and Multiagent Sys- lems, 2024.
Keisuke Okumura, Manao Machida, Xavier Défago, and Yasumasa Tamura. Priority inheritance with backtracking for iterative multi-agen agent path finding. In International Joint Conference on Artificial Intelligence, pp. 335-542, 2019.
Aalok Patwardhan, Riku Murai, and Andrew J. Davison. Distributing collaborative multi-robot planning with gaussian belief propagation. IEEE Robotics and Automation Letters, 8(2):552- 559, 2023. doi: 10.1 1099099222.22222227555
Judea Pearl and Jin H. Kim. Studies in semi-admissible heuristics. IEEE Transactions Pattern Analysis and Machine Intelligence, pp. 392-399, 1982.
Ahmed Hussain Qureshi, Yinglong Miao, Anthony Simeonov, and Michael C Yip. Motion plan- ning networks: Bridging the gap between learning-based and classical motion planners. IEEE Transactions on Robotics, 37(1):48-66 2020.
Gildardo Sanchez and J-C Latombe. Using prm planner to compare centralized and decoupled planning for multi-robot systems. Proceedings 2002 IEFE international conference on robotics and automation (Cat. No. 02CH37292), volume 2, pp. 2112-2119, IEEE, 2002.
Yorai Shaoul, Itamar Mishani, Maxim Likhachev, and Jiaoyang Li. Accelerating bearch-based plan- ning for multi-robot manipulation by leveraging online- generated experiences. In International Conference Automated Planning and Scheduling, 2024a.
12

---

Published as a conference paper at ICLR 2025
Yorai Shaoul, Rishi Veerapaneni, Maxim Likhachev, and Jiaoyang Li. Unconstraining multi-robot manipulation: Enabling arbitrary constraints in ecbs with bounded sub-optimality. Interna- tional Symposium on Combinatorial Search, 2024b.
Guni Sharon, Roni Stern, Ariel Felner, and Nathan R Sturtevant. Conflict-baseed search for optimal multi-agent pathfinding. Artificial Intelligence, pp. 40-66, 2015.
Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In International conference on machine learn- ing. pp. 2256-2265, PMLR, 2015.
Kihyuk Sohn, Honglak Lee, and Xinchen Yan. Learning structured output representation using deep conditional generative models. Advances in neural information processing systems, 28, 2015.
Kiril Solovey, Oren Salzman, and Dan Halperin. Finding a needle in an exponential baystack: Dis- crete for exploration of implicit roadmaps in multi-robot motion planning. The International Journal of Robotics Research, 35(5):001-511 2016.
Yang Song, Jascha Sohl-Dickstein, Diederik P. Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. In 9th International Conference Learning Representations. ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL /ttps://openrevieww net forum?id
PXTIG1 IRRHH
Roni Stern, Nathan Sturtevant, Ariel Felner, Sven Koenig, Hang Ma, Thayne Walker, Jiaoyang Li, Dor Atzmon, Liron Cohen, TK Kumar, et al. Multi-agent pathfinding: Definitions, variants, and benchmarks. International Symposium on Combinatorial Search, pp. 151-158, 2019.
Ardalan Tajbakhsh, Lorenz Biegler, and Aaron M Johnson. Conflict-based model predictive con- trol for scalable multi-robot motion planning. In IEFE International Conference on Robotics and Automation. IEBE, 2024.
Toshihide Ubukata, Jialong Li, and Kenji Tei. Diffusion model for planning: systematic literature review. arXiv preprint arXiv:2408. 10266, 2024.
Jur Van Den Berg, Stephen J Guy, Ming Lin, and Dinesh Manocha. Reciprocal n-body collision avoidance. In Robotics Research: The 14th International Symposium ISRR, pp. 3-19. Springer, 2011.
Anirudh Vemula, Andrew Bagnell, and Maxim Likhachev. Cmax++: Leveraging experience in planning and execution using inaccurate models. In Proceedings of the AAAI Conference Artificial Intelligence, 2021.
Xuesu Xiao, Bo Liu, Garrett Warnell, and Peter Stone. Motion planning and control for mobile robot navigation using machine learning: survey. Autonomous Robots, 46(5):569-597, 2022.
Siyuan Zhou, Yilun Du, Shun Zhang, Mengdi Xu, Yikang Shen, Wei Xiao, Dit- Yan Yeung, and Chuang Gan. Adaptive online replanning with diffusion models. Advances in Neural Information Processing Systems, 2024.
13

---

Published as a conference paper at ICLR 2025
A APPENDIX
These additional materials come to add auxiliary details on our algorithms and their implementation, alongside providing further experimental evidence that we omitted from the main text. We begin with additional discussion our algorithmic framework, move on to provide additional results, and conclude with implementation and baseline details.
A.1 ADDITIONAL ALGORITHMIC DISCUSSION
In this section, we expand on few key ways in which MMD-PP and MMD-CBS improve on their classical counterparts. These were lightly touched on in the main text. We outline them in more detail here.
CT Node Ordering in CBS. Traditionally, MAPF algorithms aim to find the shortest paths from starts to goals. Therefore, in CBS, the high-level nodes N popped from the CT are the ones of least cost. our case, where the data-driven objective function scoring trajectories generally not available in practice, we instead aim to quickly find solutions that are collision-free, delegating the task of finding high-quality solutions to the diffusion models. To this end, the MMD CBS strategies choose CT nodes with the least number of conflicts explore first, they are more likely to lead to collision- free solutions quickly. This is similar to the algorithm GCBS-H outlined in Barer et al. 2014). Resembling their outcomes, also observed significant runtime improvement between prioritizing CT nodes based on their geometric quality and their collision count.
Batch Trajectory Generation. Planning with diffusion models has the added benefit of being able to generate a diverse set of solutions with a single inference pass (Carvalho et al.) 2023). MMD makes use of this property. In contrast to the original CBS, where CT nodes N store single path for each robot within N.II, MMD stores trajectory batches for each robot R2 within N.r. That is, N.r' may be a set of B E z2D trajectories, with B being a batch size. MMD-PP follows similarly, storing a batch of trajectories for each robot. When planning for R. MMD generates a batch of trajectories under the currently active constraint set N.C (see Fig. 1]. Once the batch is generated, MMD iterates over the new resulting trajectories N.r' and marks the one with the least collisions as the representative trajectory for R4. MMD-PP this trajectory is used to define the placement of soft-constraints in following iterations and will be part of the solution. In MMD-ECBS, weak soft-constraints will similarly be added. All MMD CBS-based algorithms use representative trajec- tories to compute the number of conflicts within CT nodes. When conflict-fri free CT node is found (e.g., there are no collisions between representative trajectories), MMD returns the representative trajectories of N.T as the solution.
A.1.1 BEYOND FULL--HORIZON PLANNING
In this work, we focus on scenarios where possible to carry out centralized planning. That is, single algorithm generates full-horizon trajectories for all robots, and robots later execute these trajectories. This formulation is common in robotics and the planning community more broadly, however, it has some limitations. For example, this setup requires that the motion of all moving obstacles be known a priori, that all robots be able to carry out their trajectories as prescribed, and that time for offline planning be available. In the real world, such information or resources may not always be available (e.g., when robots operate next to humans). In this section, we provide a brief introduction to another class of multi-robot planning algorihnss-decenraliin algorithms- that address some of these challenges. We also explore an exciting avenue for future work: combining these algorithms with MMD to mitigate the limitations of each approach.
and windowed
The structure of decentralized and windowed multi-robot planning algorithms differs fundamentally from full-horizon planning algorithms in that they break the "plan-then-act" paradigm (Patwardhan et al.) 2023) Van Den Berg et al. 2011; Okumura et al., 2019). While full-horizon planners first generate a set of trajectories for all robots and then robots execute them as prescribed, windowed algorithms instead ask each robot to plan short trajectory for itself, execute it, observe the new state of the world, and repeat. This setup gives up on global optimality in favor of allowing faster planning cycles and decentralized computation. In that, it removes the reliance that implicitly also assumes perfect communication between robots. Instead, planned trajectories communicated and negotiated between neighboring robots. We believe that MMD could benefit
central planner
14

---

Published as a conference paper at ICLR 2025
Empty
Map
Highways Map
70
Method
St
D1
T1
A.
71
Method
St
D7
T
Al
MMD
100%
0.999
3.4
0.002
MMD
100%
0.96
3.3
0.042
3
3
MPD-C
100%
1.000
2.1
0.010
MPD-C
100%
0.98
2.1
0.032
MMD
100%
0.995
7.0
0.002
MMD
98%
0.97
6.9
0.045
6
6
MPD-C
62%
0.331
2.2
0.142
MPD-C
0%
MMD
100%
0.991
11.1
0.002
MMD
96%
0.97
10.7
0.043
9
9
MPD-C
0%
MPD-C
0%
Table 1: Comparison of methods by number of agents in the Empty enviromment (left) and the Highways environment (right). S is the success rate (%). D the data adherence score (see Sec. [). T the average planning time (seconds), and A is average acceleration (length units/s²), proxy for smoothness. Despite being computationally efficient, the composite baseline struggles to maintain high data adherence scores. Here, MMD MMD-xECBS.
from this structure, as it enables adaptation dynamic environments and reduces the combinatorial complexity of MAPF algorithms by which our proposed MMD algorithms are inspired. However, the best approach for adapting MMD decentralized and windowed settings remains unclear.
One algorithm that could shed light on how to step towards decentralized and windowed data-driven trajectory generation with MMD is Gaussian Belief Propagation Planner (GBP) (Patwardhan al. 2023]. This planner is recently proposed decentralized and windowed algorithm for multi-robot planning that frames short-horizon planning as inference. A particular similarity between GBP and MMD is the way single-robot plans influence each other to achieve collision-free multi-robot plans. In both MMD and GBP, soft constraints are imposed on single-robot time-discretized trajectories (either full-horizon or short-horizon window) to guide their trajectory generation processes towards favorable regions in trajectory space (e.g., collision-free, respecting dynamics, etc.). Given this similarity, it is reasonable to believe that by incorporating signals from GBP's factor graph into MMD's s guidance functions, MMD could be adapted to the decentralized and windowed setting.
A.2 EXPERIMENTAL EVALUATION: ADDITIONAL RESULTS
We provide additional quantitative and qualitative results for our first two experiment sets, outlined in Table I Table and Fig. 6 Discussions of these experimental results are included.
A.2.1 ADDITIONAL QUANTITATIVE RESUTLS
Our manuscript mainly evaluated algorithms based on their performance in terms of success rate and data adherence (Fig. Fig. and Fig. PD. While these metrics are sufficient to capture MMD's ability to consistently produce trajectories that follow an underlying motion data distribution, one may also be interested in solutions' smoothness and the wall-clock time takes to generate those. To this end, we include results for the average acceleration per robot (column A in Table I and Table 2), as a proxy for smoothness, and the runtime for trajectory generation (column T).
Average Acceleration Per Robot. Despite showing little information, since the composite base- line quickly failed produce valid trajectories, Table offers valuable insights nonetheless. The A column provides a glance into the reason for composice-model' failure. Consistent with our ob- servations, we notice that the average acceleration per robot the G-robot case is drastically higher for the composite model than for MMD. This behavior, visually, translates to trajectories including small loops and sharp turns. See Fig. for an example. We have trained MPD-Com Composite to conver- gence using our datasets (Sec. A.6) and performed additional tuning, however, its generated motions struggled capture the smooth, dynamically feasible transitions as the number of robots grew to 9. MMD, however, produced better and larger-scale trajectories. Table shows MMD keeping low erage accelerations per robot. In larger teams of robots, we notice the acceleration remaining mostly constant within each map when the number of robots grows. This shows that robots produce similar motions within each map regardless of congestion levels sign of consistency that we seek as the number of robots scales.
Trajectory Generation Runtime. While the composite models enjoy an invariance to the number of robots, those only require single inference pass for multi-robot trajectory generation, this is not
15

---

Published as a conference paper at ICLR 2025
Highways Map
Conveyor Map
Drop-Region Map
11
Method
ST
DT
T.
A,
ST
DT
T1
A1
ST
DT
TL
A
MMD-ECBS
100%
0.93
3.5
0.04
100%
0.87
4.5
0.09
100%
1.00
3.8
0.05
MMD-PP
1005
0.93
0.04
100%
0.80
4.2
0.09
100%
0.97
4.2
0.05
MMD-CBS
1003
0.93
4.0
0.04
100%
0.93
5.7
0.10
100%
1.00
6.7
0.06
MMD-XCBS
100%
0.93
3.6
0.04
100%
0.93
4.3
0.11
100%
1.00
4.5
0.07
A BCBB
NCBB
100%
0.57
0.1
100%
0.00
0.5
100%
0.27
0.2
MMD-<ECBS
107%
1.00
7.0
0,05
100%
0.95
9.3
0.11
100%
0.90
7.7
0.06
MMD ECBS
100%
1.00
7.3
0.05
100%
0.92
13.2
0.09
100%
0.95
8.4
0.05
MMD-PP
100%
0.98
8.9
0.04
70%
0.90
8.7
0.09
100%
0.93
8.4
0.05
MMD-CBS
100%
1.00
100%
0.93
18.9
0.10
100%
16.7
0.06
MMD xCBS
100%
1.00
10.2
0.05
100%
0.95
11.0
0.14
100%
0.97
12.1
0.08
AaData-ECBS
100%
0.17
1.1
100%
A*-ECBS
100%
0.55
0.7
100%
0.05
2.4
100%
0.12
1.1
MMD-xECBS
100%
0.97
12.7
0.05
100%
0.93
14.6
6.11
100%
0.94
12.9
0.06
MMD-ECBS
100%
100%
0.92
19.6
0.09
100%
0.06
MMD-PP
90%
0.96
13.5
0.05
30%
1.00
12.4
0.10
60%
0.93
12.3
0.06
MMD-CBS
100%
60%
0.94
46.6
0.11
50%
0.93
47.5
0.08
MMD-xCBS
100%
0.96
29.8
0.05
100%
0,94
32.8
0.20
70%
0.92
39.1
0.11
A ECBS
100%
0.88
14.0
100%
0.10
2.7
100%
0.22
1.3
A*FECBS
100%
0.51
100%
0.06
3.4
100%
0.19
0.8
MMD-AECBB
107%
0.99
15.8
0.04
100%
0,94
23.1
0.13
100%
0.87
22.9
0.07
MMD-PP
80%
0.99
18.4
0.05
30%
0.86
16.9
0.10
0%
12
MMD CBS
0%
0%
MVDDxxCSS
30%
54.6
0.05
10%
1.00
53.5
0.19
A DatataECSS
80%
0.83
19.7
100%
0.14
3.8
100%
0.22
4.0
MMD-1ECBS
100%
0.97
24.3
0.05
90%
0.96
38.3
0.14
100%
0.80
35.7
0.07
MMD-EEBS
100%
0.97
29.3
0.05
80%
0.97
43.7
0.10
60%
0.86
43.0
0.06
MMD-PP
60%
0.99
23.2
0.05
0%
15
MMD-CBS
0%
0%
0%
Daai ECBS
50%
0.85
32.0
100%
0.11
14.4
100%
0.24
7.7
A*-ECBS
100%
0.04
13.4
100%
MMD AECBS
100%
0.96
46.1
0.05
0%
MMD-ECBS
60%
0.97
$1.8
0.05
0%
0%
20
MMD-CRS
0%
0%
0%
MMD-xCBS
0%
A 'DaaaECBS
22%
0.82
43.5
100%
0.11
15.6
100%
0.23
15.7
A-ECBS
80%
0.46
21.6
100%
0.05
21.0
100%
0.22
16.5
Table 2: Additional results for a subset of our MMD and MAPF evaluation. Table columns are
similar to Table We omit acceleration information from the MAPF methods as those plan on grid graph and assume constant velocities.
the case for MMD. For once, all MMD algorithms begin with the sequential process of generating trajectories for all robots one at a time. The time for this operation, of course, scales linearly with the number of robots. As mentioned in our conclusion, the MMD CBS-based methods are naturally parallelized. Since the runtime of these methods tightly related to the number CT nodes created, which could be evaluated in parallel, doing so may drastically reduce runtimes. We leave this to future work.
MAPF Baseline Runtime. The trends of our timing results for the MAPF baselines shown in Table are inconsistent across maps. Interestingly, the planning time for A*Data-ECBS the Highways map was significantly higher than that of *CCCCS This comes with the added benefit of the pro- duced paths better adhering to data. In the other two maps, which have more challenging underlying motion data distributions, the difference between **Dat-ECBB and A*-ECBS was insignificant, though so were the data adherence scores. It is unclear to us how to effectively incorporate demon- strations from data into MAPF solvers without compromising their ability scale.
A.3 ADDITIONAL QUALITATIVE RESULTS
To better capture the behavior of the various trajectory generators discussed in this paper, Fig. shows a series of images of generated trajectories in two problems. We keep the number of robots low for clarity. Videos are available in supplementary materials well.
16

---

Published as a conference paper at ICLR 2025
MMD-XECBS
MMD-PP
MPDDComposite
A*Data-ECBS
Empty
Highways
Empty
Highways 6
Fail
Figure 6: Visual examples of trajectories generated by MMD-XECBS, MMD-PP -P. MPD MPD-Composite, and A*Data-ECBS in tests within the Empty and Highways maps. The top two rows show test cases with 3 robots, and the bottom two with 6. All planning problems follow the circle setup (Sec. 4.2 with radius 0.6 for the Highways map and 0.8 for the Empty map.
A.4 IMPLEMENTATION DETAILS
We implemented all of our algorithms in Python and ran our experiments a laptop with an In- tel Core 19-10H CPU, 32GB RAM (5.2GHz), and Nvidia GeForee RTX 3080Ti Laptop GPU (16 GB). We based our diffusion planning implementation on the official code of Caarvalho et al. 2023) and used exponential variance schedule. The guidance function cost components we used were Jsmoath to encourage dynamically feasible trajectory generation with GPMP, Jatj for obstacle avoidance (both from Carvalho al. (2023)), and J. for constraint satisfaction. We set the weights Asmooth 8e-2, Aabj = 2e-2, and A 2e-1 1 for strong soft-constraints and X = 2e-2 2 for weak soft-constraints.
In our experiments, the size each local map was x 2 units, and the diameter each disk robot was 0.1 units. The radius for CBS sphere constraints was the disk robot radius multiplied by margin, resulting in a radius value of 0.12 units, and the time interval At was 0.08 seconds (2 time steps).
17

---

Published as a conference paper at ICLR 2025
A.5 EXPERIMENTAL EVALUATION: ADDITIONAL DETAILS
This section provides details about our experimental setup, namely the data adherence scoring func- tion costaa (T) that we used to evaluate trajectories T' each map. We also include details on our baseline implementations.
A.5.1 DATA ADHERENCE FUNCTIONS
As discussed in Sec. 4 each of our local maps has associated motion pattern for robots to follow when those move within it. This motion pattern is reflected in the trajectory dataset associated with each map. Sec. A briefly outlined the data adherence score functions for each map, and we provide more specific definitions here. We also include more details on our larger maps. including the structure of their local maps. illustrations (Fig. 7. and their adherence scores are computation method.
Drop-Region map (Fig. 3c simulates package drop-off chutes. Adherence is met for T', i.e., costama (os)) 1, if the trajectory spends at least 25% of its duration, consecutively, in a region of radius 0.15 centered 0.15 units off the midpoint of each of the 16 chutes.
Conveyor map (Fig. 3b) features narrow passages with directional motion requirements. Trajectory T' adheres to data if it includes section that enters the top corridor from the right and leaves from the left, vice versa for the bottom corridor. There is no restriction on robots transitioning through the corridors in reverse, and no restriction on start or goal states being within the corridors. This requires robots to reason about traversal ordering.
Highways map (Fig. 3a requires counter-clockwise movement around a central obstacle. The origin of the map is the middle of the centeral obstacle. For each state transition of trajectory T', from t to T the angle between the vectors pointing from the origin to 4:41 and to qi is computed. q is the associated configuration at T!- We define adherence to be met for T its cumulative angle is positive, i.e., counter-clockwise.
Empty map (Fig. 2a is our simplest. Trajectories 7', which have H time steps, are scored based on the fraction of their steps that lie within margin of straight-line interpolation between initial and final configurations qi. 4' in T'. Specifically, let be the distance between the first and last configurations in r', and let m be the number of trajectory configurations whose distance to the line qi - qi is less than 1. We define costaau := m H
10
2 x 2 map (Fig. 5ahe is first instance of larger map, composed by four local maps (from top left going clockwise): Empty, Conveyor, Highways, and Highways. In these larger maps, each robot is given start and goal configuration, well a sequence of local maps traverse. We can see this sequence as a form of a task-level plan. The trajectory for a robot R2 is generated with a single forward pass by sequencing local diffusion models, described Sec. B.3 The resulting trajectory T' can be seen as a concatenation of L local trajectories -i.1 ..... ThE one for each local map. Since robots must adhere the motion pattern prescribed by each local map they move through, we compute the total data-adherence score for a trajectory to be the average adherence
across all its traversed local maps, i.e., costaata (T') El= costdata (T..).
3 x 3 map (Fig. 5b) is our second instance of larger map, composed by the local maps (in row- major): Empty, Conveyor, Prop-Region, Highways, Highways, Highways, Conveyor, Drop-Region, Empty. Data adherence in all larger maps is computed similarly to the 2 x 2 map described above.
To mimic real-world scenarios, we have staggered the start times of robots in our large scale experi- ments in Sec. 4.3 There, robots began moving 10 time steps apart. Robots in motion were required avoid static robots. Those may be stopped in high-density regions, potentially causing congestion.
A.6 BASELINE DETAILS
Our experiments include two families of baselines: composite models and MAPF methods. Both baselines attempt produce trajectories (or paths) that distribute according to underlying motion pattern that is reflected in dataset. This section comes to provide additional details regarding these baseline methods.
18

---

Published as a conference paper at ICLR 2025
(a) Empty map.
(b) Conveyor map.
(c) Highways map.
(d) Drop-Region map.
S
( x map.
(1) 3 x 3 map.
Figure 7: Illustrations of our different maps. In the top row, we show an example trajectory that follows the data distribution prescribed by maps' underlying motion patterns. Below, we include illustrations of our x and 3 x 3 maps and outline the boundary between their local maps for better clarity. The larger maps include visualizations of single-robot trajectories generated by MMD with a perfect data-adherence score.
Composite Models. Training composite models requires two components. The first is dataset of multi-robot motions, and the second is model that can be trained to generate trajectories that resemble those the data. Given that obtaining multi-robot motion datasets is generally intractable as it requires solving MRMP problem for each datapoint, in this paper we focus single-robot data and construct our multi-robot datasets from collision-free subsets our single-robot datasets. It is worth noting that given that our multi-robot datasets were composed of single-robot data, the conclusions from our results that it is difficult to learn multi-robot trajectory generation from composed single-robot data, and not that it uniquely challenging task in the general case. See Sec. 4.1 for a description of our composite models.
MAPF Baselines. Our MAPF baselines, termed A 4*Data-ECHS and A A*-ECBS, both similar algorithmically and only differ in the edge costs they use for single-robot graphs. We will start with describing the algorithms and then give additional details for cost map creation. The low-level planners used in these baselines are A* with a focal list mechanism, also known as A (Pearl & Kim 1982p. We the focal list bound 1.5 and did not allow for re-expansions in our implementation. On the high-level search, we prioritized CT nodes strictly based on their conflict count to match the strategy MMD. All robots our experiments travelled on 4-connected regular grid graph with step size of 0.1, and were allowed to move up, down, left, right, or wait on each time step, with each action incurring a unit cost in A ECBS. is worth noting that the robots in our experiments are not point-robots, and so robot-robot collision checking is needed to find conflicts (e.g., two robots traversing different edges between and t' may still cause an edge conflict). This affected runtime. To encode dataset demonstrations in A Daaat-ECBSS as discussed Sec. 4.2 To do so in given map, we iterate over all its dataset entries, and follow each trajectory, keeping track of which discretized cells (centered at states it visited. For each
created cost maps for each evaluation map
19

---

Published as a conference paper at ICLR 2025
cell that the trajectory visited, we find the first trajectory state outside of its center s, call it s', and increment a count for the outgoing graph (directed) edge from s that aligns best with the line between and s'. Eventually, we assign directed edge costs of 1 + with being the number of trajectories that incremented this edge or none have. Our A Data-FBCBS and A A*EECBS implementation was done in Python.
A.7 TRAINING AND DATASET GENERATION DETAILS
In this section, we give brief overview of our data generation and network training processes. We note that our code for generating data, training models, and multi-robot motion planning with MMD publicly available, and we encourage readers to consult it for exact implementation details.
Dataset Generation: In this work, each (local) map is associated with a dataset of trajectories. There, each data point one, single-robot, trajectory from a random collision-free start configura- tion to a random collision-free goal configuration. The trajectory connecting the start and goal is discretized uniformly to 64 points such that the time between consecutive trajectory configurations is constant. Each configuration on trajectory is complemented with velocity information too. Im- portantly, each dataset trajectory respects the motion pattern dictated by the map within which is embedded. For example, trajectories in the Empty map will be straight lines, and in the Conveyor map trajectories will all pass through either of the conveyor passages. See Fig. 7 for illustrations of similar trajectories to those found in our datasets. To create the datasets, motion pattern function that, given start and goal configurations, generates the critical motions that associated with adhering to a map's underlying motion pattern. We call these motions skill sub- paths. For instance, in the Conveyor map, a skill sub-path will be a short sequence of confi configurations moving a robot throughout one of the corridors in the map. Given skill sub-path, we create the final dataset trajectory by connecting the start configuration to the beginning of the skill sub-path. the end of the skill sub-path to the goal configurations (both with RRT-Connech (Kuffner & La Valle, 2000), and finally smooth the resulting trajectory with B B-spline and an optimizer. This process is heavily inspired by the methodology used by [Carvalho et al. (2023).
endow each map with
The motion planning diffusion models that we use in this work generate single-robot trajectories. Therefore, during training time, they are not required to reason about other robots. This allows us to use previously established training methodologies for motion planning diffusion models directly. In our work, we follow the same training procedure outlined Carvalho ct al. (002)) though other options can be used as well.
Training procedure:
A.8 RECOMMENDATIONS FOR PRACTITIONERS
We have presented five MMD variants in this paper alongside other approaches to multi-robot mo- tion planning under learned motion distributions. Our experience with these algorithms has shed light some of their practical strengths and weaknesses, which could be of interest practitioners who wish to deploy or extend MMD. To this end, we offer a short set of recommendations regarding which MMD algorithms perform best in different scenarios. First, in situations with relatively small number of robots, the differences between the MMD variants are less pronounced, as all of them solve problems relatively well. This is mostly owed to the capabilities of diffusion planning models since, in those cases, coordination is relatively easy. In such cases, we recommend using one of the CBS-based MMD algorithms since those will guarantee that solution will be collision-free (and will normally find solution within short time). Among the CBS-based MMD algorithms, MMD-XECBS proved to be the best choice, as more efficient than the other CBS -Bseb MMD variants and can find solutions with similar quality.
When the number of robots increases, we can distinguish between two types of scenarios: those that are relatively free and those that are cluttered. Free scenarios are those in which the robots can easily move around each other. The reason for this could be because there are not many obstacles in the environment (e.g., our Empty map) or because the underlying learned motion patterns help avoid congestion (e.g., our Highways map). Cluttered scenarios are the opposite, where the robots are forced to move close each other, either by the environment or by the learned motion patterns. In free scenarios, we recommend considering MMD-PP, as is the fastest algorithm and can effectively find collision-free solutions. However, in cluttered scenarios, we recommend using MMD-XECBS
20

---

Published as a conference paper at ICLR 2025
since its search over consttaint-cooiiguuattons showed promise in handling congestion, performing better than MMD-PP.
21


Reviews:
[{"review_id": "LS6sJHkRSN", "reviewer": "Reviewer_AAKU", "summary": "This paper presents a multi-robot motion planning algorithm leveraging diffusion models and MAPF algorithms. In the proposed MMD algorithm, a conditional diffusion model is used to generate collision-free trajectories for the robot, and MAPF provides the logic to impose constraints on robots such that it scales in a multi-agent setting. The paper benchmarks with A* search and tests it on multiple multiagent tasks with varying complexity. The results show good success rate and data adherence for the proposed methods.", "questions": "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.\n2. 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?\n3. Is there any other search algorithm other than A* that should we consider? Can have a closer connection between the related work and the baseline methods.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. This paper provides a very thorough discussion of how to combine MAPF algorithms with diffusion models and demonstrate its ability to scale to multi-agent settings.\n2. The experiment setting is diverse with varying levels of difficulties.\n3. The writing is clear and structured and the paper is easy to read.", "weaknesses": "1. It would be good to discuss other search algorithms in multi-agent motion planning or at least discuss why only A* is chosen\n2. In Sec. 4.2, it would be good to discuss the computational complexity between A* and MMD.\n3. The explanation of the motion pattern is insufficient. Then it becomes a bit confusing in Sec 3.3 how this task-relevant local diffusion model works and also in Sec. 4 what the data adherence means.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "LPwE1eCwj1", "reviewer": "Reviewer_wKu8", "summary": "This paper focuses on the collision-free multi-robot planning problem. They combine single-robot diffusion planning models with multi-agent path finding (MAPF) algorithms. They leverage different MAPF algorithms to generate spatio-temporal constraint functions and use these functions to guide diffusion planning models to generate soft-constraint multi-robot trajectories.", "questions": "* How is the single-robot diffusion models training? Which dataset? Is it a single-robot dataset or a multi-robot dataset?\n* Search-based algorithms (A*) achieve a higher success rate compared to MMD. Is it fair to compare search-based algorithms at data adherence scores since search-based algorithms are not learned from dataset?\n* The performances of MPD are very low even if the number of agents is less than 5. Is it normal?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* The questions of multi-robot motion planning that the paper aims to solve is meaningful and it has many real-world applications like automated warehouses.\n* The method proposed by the paper is diretly and simple. They leverage state-of-art single-robot diffusion planning methods with classifical MAPF algorithms to solve multi-robot motion planning problems.\n* They also evaluate their approaches in a variety of simulated scenarios and show better performance. They also conduct rich ablation studies including planning time, different strategies.", "weaknesses": "* The novelty of the method seems limited. The paper seems simply combine diffusion planning methods and classifical MAPF algorithms. 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.\n* Lack of some experimental details and results. See questions.\n* The methods are not very efficient when the number of agents increases.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "3Q62bquPeT", "reviewer": "Reviewer_frGK", "summary": "This paper presents a novel approach for multi-robot motion planning (MRMP) that combines diffusion models with multi-agent pathfinding (MAPF) constraint strategies. This approach leverages single-robot diffusion models to plan multi-robot trajectories while avoiding collisions and scaling well to larger, complex environments. Extensive simulations demonstrate this approach’s success in generating smooth, collision-free paths with high adherence to data distribution.", "questions": "1. 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.\n\n2. Could you further clarify the computational trade-offs between the five MMD variants? It would help to know if certain strategies are more suitable for specific environments or robot counts.\n\n3. How effectively does the approach generalize beyond warehouse-like environments? Could it perform well in less structured or highly dynamic settings?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "This paper introduces a novel approach for multi-robot motion planning, particularly in combination MAPF with diffusion models. This approach sidesteps the challenge of multi-agent data collection by training on single-robot data, allowing the method to efficiently address the curse of dimensionality typically seen in large-scale multi-agent systems. Also, it incorporates MAPF-based constraint methods, such as Conflict-Based Search, to dynamically enforce collision-free paths.\n\nBy using an ensemble of diffusion models for each robot, the capability of scaling the approach to large environments with numerous robots, without retraining, is a notable advantage. This makes the method adaptable to a range of real-world applications.\n\nThis paper provides a solid comparison of multiple MMD variants, which helps to assess the strengths and weaknesses of different constraint strategies. This thorough analysis adds value to the paper’s contributions.\n\nThe simulations conducted in various scenarios help validate the approach. Also, the success rates and data adherence scores are well presented.", "weaknesses": "A major limitation is the reliance on single-robot data for policy learning. This assumption may not be sufficient for complex, dynamic environments where multi-robot interactions are essential. While multiple experiments demonstrate the effectiveness of this approach, exploring the differences between multi-agent and single-agent data, and how single-agent data can benefit cooperative multi-robot motion planning, would add valuable insight.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "75norRL3Nu", "reviewer": "Reviewer_WAyg", "summary": "The paper addresses the challenge of collision-free multi-robot motion planning (MRMP) using diffusion models, aiming to enable the coordination of multiple robots with limited training data by leveraging single-robot trajectories. The proposed Multi-robot Multi-model planning Diffusion (MMD) method integrates single-robot diffusion models with constraint-based MAPF (multi-agent pathfinding) techniques, enabling multi-robot trajectory diffusion. MMD adapts classical MAPF strategies, including Prioritized Planning (PP) and Conflict-Based Search (CBS), to impose spatial and temporal constraints within the diffusion process, ensuring collision avoidance. An ensemble of local diffusion models is employed for long-horizon planning by sequencing trajectories across different environment contexts.\n\nEvaluation is conducted through simulated tests across multiple scenarios and environments, including logistics-inspired settings with varying numbers of robots. Metrics used include success rates, data adherence (alignment of trajectories with data-derived patterns), and computation time. Comparisons are made with MAPF baselines and composite diffusion models trained with multi-robot data.", "questions": "1. I am curious to see how well the learning method MMD performs against bare GBP [3] as an additional baseline in highly-congested maps such as Circle and Weave setups and large maps such as 2 x 2 and 3 x 3 maps with increasing agents to 50 to further assess the scalability, with the same proposed metrics of SR and adherence. This will also shed light implicitly on how well GBP compares to classical MAPF algorithms, which benefits the MAPF community further. The code of GBP is publicly available [here](https://github.com/aalpatya/gbpplanner).\n\n2. Please discuss the potential advantages and disadvantages of integrating GBP to MMD, as stated above.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "MAPF can be considered a hierarchical planning method for multi-robots, consisting of a high-level \"negotiation\" mechanism and a low-level \"motion\" planner.\n\n1. It is interesting to see how the MPD [1] advantages are utilized in MAPF algorithms. Classical MAPF algorithms usually utilize RRT or PRM planners as underlying collision-avoidance planning. Indeed, utilizing a single-robot MPD model, which typically captures the local multimodality of planning behaviors as a learned smooth collision-avoidance mechanism, is a very interesting idea.\n\n2.  The significance of MMD lies in amortization [2] low-level planning with MPD, which can infer a batch of solution efficiently (i.e., with a forward pass) without RRT or PRM subroutines. This is crucial since high-level multi-agent negotiation may induce many constraints for low-level and thus significantly speed up the overall algorithm.\n\n3. The motivation is well-discussed, and the overall method is presented clearly.\n\n[1] Carvalho, Joao, et al. \"Motion planning diffusion: Learning and planning of robot motions with diffusion models.\" 2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 2023.\n\n[2] Amos, Brandon. \"Tutorial on amortized optimization.\" Foundations and Trends® in Machine Learning 16.5 (2023): 592-732.", "weaknesses": "1. It is unfortunate that this work does not consider Multi-Robot Planning with Gaussian Belief Propagation (GBP) [3], which I believe could seamlessly integrate with the MPD framework. [3] utilizes factor-graph formulation to communicate between agents, and it is straightforward to incorporate these signals into the guidance cost term Eq. 4. In contrast, MMD-CBS formulation has combinatoric negotiation between agents inherited from classical MAPF algorithms. There should be some discussions (as future works) on integrating GBP to MMD with potential advantages (e.g., distributed planning over an arbitrary time window, removing combinatoric negotiation via message-passing over factor graph) and disadvantages (e.g., high memory cost with many factors due to increasing trajectory length and number of agents, etc.).\n\n2. The experiment outline is thoughtful and supports the main claims with good metrics and benchmarks. However, I believe the paper would be much stronger if MMD (and its variants) were additionally compared to bare GBP [3] in these benchmarks of Sec 4.2 and the long-horizon setting of Sec 4.3.\n\n[3] Patwardhan, Aalok, Riku Murai, and Andrew J. Davison. \"Distributing collaborative multi-robot planning with Gaussian belief propagation.\" IEEE Robotics and Automation Letters 8.2 (2022): 552-559.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (Spotlight)