Multi-Robot Motion Planning with Diffusion Models

## Abstract

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. View video demonstrations in our supplementary material, and our code at: https://github.com/yoraish/mmd .

## 1 Introduction

Multi-robot motion planning (MRMP) is 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 warehouses, for example, hundreds of mobile robots and robotic manipulators need to coordinate with each other to transport and exchange items while avoiding collisions. Learning motions 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, it is unclear how to best incorporate demonstrations in MRMP. In fact, MRMP at its simplest form, where robots are only concerned with finding short trajectories between start and goal configurations, is already known to be computationally intractable (Hopcroft & Wilfong, )—significantly 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 as a multi-agent path finding problem (MAPF) (Stern et al., ) by discretizing space and time. While the latest MAPF planners (Li et al., ; Okumura, ) can compute near-optimal plans and scale to hundreds of agents, they make strong assumptions, such as constant velocities and rectilinear movements that limit their real-world application and reduce their ability to generate complex behaviors learned from demonstrations.

In single-agent motion planning, methods that learn to plan from data (Xiao et al., ) have been widely used to circumvent similar limitations resulting from inaccurate models (Vemula et al., ), partial observability (Choudhury et al., ) and slow planning (Sohn et al., ; Qureshi et al., ).
More recently, diffusion models (DM) have emerged as the generative model of choice for learning visuomotor manipulation policies from demonstrations (Chi et al., ), motion planning (Carvalho et al., ), and reinforcement learning (Janner et al., ). However, there has been relatively little work on 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 a data-efficient and scalable multi-robot diffusion planning algorithm, Multi-robot Multi-model planning Diffusion (MMD), that addresses both these challenges by combining constraint-based MAPF planners with diffusion models.
Importantly, our approach calls for learning only *single-robot diffusion models*, which does away with the difficulty of obtaining multi-robot interaction data and breaks the curse of dimensionality. MMD generates collision-free trajectories by *constraining* single-robot diffusion models using our
novel spatio-temporal guiding functions and choosing constraint placement via strategies inspired by MAPF algorithms.
Our contributions in this paper are threefold:

- •
We propose a data-efficient framework for multi-robot diffusion planning inspired by constraint-based search algorithms.
- •
We provide a comparative analysis of the performance of five MMD algorithms, each based on a different MAPF algorithm, shedding light on their applicability to coordinating robots leveraging diffusion models for planning.
- •
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 results from varied motion planning problems in simulated scenarios motivated by logistics environments suggest that our approach scales favorably with both the number of agents and the size of the environment when compared to alternatives.

## 2 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. 3 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 $\mathcal{R}_{i}$, MRMP seeks a set of collision-free trajectories, one for each robot, that optimize a given objective function.
Let $\mathcal{S}^{i}$ be the state space of a single robot and a state be $\mathbf{s}^{i}:=[\mathbf{q}^{i},\dot{\mathbf{q}}^{i}]^{\intercal}\in\mathcal{S
}^{i}$ where $\mathbf{q}^{i}$ and $\dot{\mathbf{q}}^{i}$ are the configuration and velocity of the robot.
Each robot has an assigned start state $\mathbf{s}^{i}_{\text{start}}\in\mathcal{S}^{i}$ and binary termination (goal) condition $\mathcal{T}^{i}:\mathcal{S}^{i}\to\{0,1\}$.
An MRMP solution is a multi-robot trajectory $\boldsymbol{\tau}=\{\boldsymbol{\tau}^{1},\cdots\boldsymbol{\tau}^{n}\}$, where $\boldsymbol{\tau}^{i}:[0,T^{i}]\to\mathcal{S}^{i}$ represents the trajectory of robot $\mathcal{R}_{i}$ over the time interval $[0,T^{i}]$, with $T^{i}$ being the terminal time. In practice, we uniformly discretize the time horizon into $H$ time steps and optimize over a sequence of states $\boldsymbol{\tau}^{i}=\{\mathbf{s}^{i}_{1},\mathbf{s}^{i}_{2},...,\mathbf{s}^{
i}_{H}\}$.
Subscripts, e.g., $\boldsymbol{\tau}^{i}_{t}$, indicate indexing into a trajectory.
Each trajectory $\boldsymbol{\tau}^{i}$ must avoid collisions between robots and with obstacles in the environment.
In MRMP, robots share a workspace $\mathcal{W}$ (i.e., $\mathcal{W}\subseteq\mathbb{R}^{3}$ for general robots and $\mathcal{W}\subseteq\mathbb{R}^{2}$ for robots on the plane) and occupy some volume or area within $\mathcal{W}$, which we denote as $\mathcal{R}_{i}(\mathbf{q}^{i})\subseteq\mathcal{W}$ for robot $\mathcal{R}_{i}$ in configuration $\mathbf{q}^{i}$.

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 objective then becomes $\mathcal{J}(\boldsymbol{\tau})=\frac{1}{n}\sum_{i=1}^{n}\text{cost}(
\boldsymbol{\tau}^{i})$. When learning from data, we are interested in *data adherence*, i.e., the trajectories should match the underlying trajectory distribution. We define $\text{cost}_{\text{data}}(\boldsymbol{\tau})=\frac{1}{n}\sum_{i=1}^{n}\text{
cost}_{\text{data}}(\boldsymbol{\tau}^{i})$ to quantify how well, on average, trajectories in $\boldsymbol{\tau}$ follow their underlying data distribution. This metric is task-specific; we provide some examples in Sec. 4.

### 2.2 Multi-Agent Path Finding (MAPF)

The MAPF problem, a simpler form of MRMP, seeks the shortest collision-free paths $\Pi=\{\boldsymbol{\pi}^{1},\boldsymbol{\pi}^{2},\cdots\boldsymbol{\pi}^{n}\}$ for $n$ agents on a graph. This graph approximates their configuration space, with vertices corresponding to configurations and edges to transitions. Each path $\boldsymbol{\pi}^{i}=\{\mathbf{q}^{i}_{1},\cdots\mathbf{q}^{i}_{H}\}$ is a trajectory without velocity that need not be dynamically feasible.
In MAPF studies, constraint-based algorithms have become popular due to their simplicity and scalability. These algorithms are effective, 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 a configuration $\mathbf{q}^{i}$ for $\mathcal{R}_{i}$ leads to a collision at time (or interval) $t$, this can be prevented by applying the constraint set $C=\{\langle\mathcal{R}_{i},\mathbf{q}^{i},t\rangle\}$ to the path $\boldsymbol{\pi}^{i}$, thereby preventing the configuration from being used at that time.
Several MAPF algorithms, including Prioritized Planning (PP) (Erdmann & Lozano-Perez, ) and Conflict-Based Search (CBS) (Sharon et al., ), use this mechanism to force single-agent planning queries to avoid states that would lead to collisions. We detail these methods in Sec. 3 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 a denoising process to recover a dynamically-feasible trajectory from noise (Carvalho et al., ; Janner et al., ). 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 on a task objective $\mathcal{O}$, for example, goal condition and collision avoidance. Specifically, given a task objective $\mathcal{O}$, motion planning diffusion models aim to sample from the posterior distribution of trajectories:

$$ $\displaystyle\operatorname*{arg\,max}_{\boldsymbol{\tau}^{i}}\log p( \boldsymbol{\tau}^{i}|\mathcal{O})=\operatorname*{arg\,max}_{\boldsymbol{\tau} ^{i}}\left(\log p(\mathcal{O}|\boldsymbol{\tau}^{i})+\log p(\boldsymbol{\tau}^ {i})\right)$ (1) $\displaystyle=\operatorname*{arg\,min}_{\boldsymbol{\tau}^{i}}\left(-\log p( \mathcal{O}|\boldsymbol{\tau}^{i})-\log p(\boldsymbol{\tau}^{i})\right)= \operatorname*{arg\,min}_{\boldsymbol{\tau}^{i}}\left(\mathcal{J}(\boldsymbol{ \tau}^{i})-\log p(\boldsymbol{\tau}^{i})\right)$ $$

The first term of the objective, $\mathcal{J}(\boldsymbol{\tau}^{i})$, can be interpreted as a standard motion planning objective (Carvalho et al., ), in which we try to minimize a cost function (or, equivalently, maximize a reward function). The second term, $\log p(\boldsymbol{\tau}^{i})$, is the prior corresponding to the data adherence discussed in Sec. 2.1.

Diffusion models are a type of score-based model (Song et al., ), where the focus is on learning the score function (the gradient of the data distribution’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 diffusion inference process consists of a $K$-step denoising process that takes a noisy trajectory ${}^{K}\boldsymbol{\tau}^{i}$ and recovers a feasible trajectory ${}^{0}\boldsymbol{\tau}^{i}$, which also follows the data distribution. We use the notation ${}^{0}\boldsymbol{\tau}^{i},^{1}\boldsymbol{\tau}^{i},\cdots,^{K}\boldsymbol{
\tau}^{i}$ to denote the evolution of the trajectory in the diffusion process.
To generate a trajectory ${}^{0}\boldsymbol{\tau}^{i}$ from a noise trajectory ${}^{K}\boldsymbol{\tau}^{i}\sim\mathcal{N}(\mathbf{0},\mathbf{I})$, we use Langevin dynamics sampling (Ho et al., ), an iterative process that is a type of Markov Chain Monte Carlo method. At each denoising step $k\in\{K,\dots,1\}$, a trajectory-space mean $\mu^{i}_{k-1}$ is sampled from the network $\mu_{\theta}$:

$$ $\mu^{i}_{k-1}=\mu_{\theta}(^{k}\boldsymbol{\tau}^{i})$ (2) $$

Now, with the variance prescribed by a deterministic schedule $\{\beta_{k}\mid k\in\{K,\cdots,1\}\}$, the next trajectory in the denoising sequence is sampled from the following distribution:

$$ ${}^{k-1}\boldsymbol{\tau}^{i}\sim\mathcal{N}\big{(}\mu^{i}_{k-1}+\underbrace{ \eta\beta_{k-1}\nabla_{\boldsymbol{\tau}}\mathcal{J}(\mu_{k-1}^{i})}_{\text{ Guidance}},\beta_{k-1}\big{)}$ (3) $$

The term $\nabla_{\boldsymbol{\tau}}\mathcal{J}(\mu_{k-1}^{i})$ is the gradient of additional trajectory-space objectives (described in Eq. 1) 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 $\mathcal{J}=\lambda_{\text{obj}}\mathcal{J}_{\text{obj}}+\lambda_{\text{smooth
}}\mathcal{J}_{\text{smooth}}$ to penalize trajectories in collision with objects via $\mathcal{J}_{\text{obj}}$ and to encourage the trajectory to be dynamically feasible via $\mathcal{J}_{\text{smooth}}$. We denote the trajectory generation process queried with a start state $\mathbf{s}^{i}_{\text{start}}$, goal condition $\mathcal{T}^{i}$, and costraint set $C$ (Sec. 3.1) as $f_{\theta}^{i}(\mathbf{s}^{i}_{\text{start}},\mathcal{T}^{i},C)$.

Figure: Algorithm 1 MMD-CBS sketch. Colored lines are only in MMD-PP, MMD-ECBS
Refer to caption: extracted/5900305/figures/mmd_figure/mmd_fig_colliding_paths.png

## 3 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 imposes constraints on diffusion models to generate collision-free trajectories, addressing three main questions: how, when, and where to impose them. First, we discuss integrating spatio-temporal 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 to sequence multiple models for long-horizon planning.

### 3.1 Constraints in Diffusion Models

An intuitive and effective constraint for multi-robot motion planning in robotics is the sphere constraint
(^1^11The sphere constraint generalizes the MAPF vertex constraint, as it constrains robots from visiting the point of collision itself instead of a single colliding configuration corresponding to a vertex in a graph. In MAPF, the point of collision and the graph vertex coincide.)
(Li et al., ; Shaoul et al., ).
It is defined by a point $p\in\mathcal{W}$ and restricts robots from being closer to $p$ than a radius $r\in\mathbb{R}$ at a certain time range $\mathbf{t}:=[t-\Delta t,t+\Delta t]$.
The sphere constraint can be imposed as a soft-constraint on a diffusion model by incorporating it in its guiding function $\mathcal{J}(\cdot)$. This can be done by adding a cost term $\mathcal{J}_{\text{c}}$ that repels the robots from the sphere’s center point $p$. Let ${}^{k}\boldsymbol{\tau}^{i}$ be the generated trajectory for $\mathcal{R}_{i}$ at step $k$ of the diffusion denoising process, and $\langle\mathcal{R}_{i},S_{r}(p),\mathbf{t}\rangle$ be a sphere constraint centered at $p$ with radius $r$ over time interval $\mathbf{t}$. The guidance cost term for $\mathcal{R}_{i}$ can be defined as:

$$ $\mathcal{J}_{\text{c}}(^{k}\boldsymbol{\tau}^{i}_{t}):=\sum_{t\in\mathbf{t}} \max\left(\epsilon\cdot r-d\left({\mathcal{R}_{i}(^{k}\boldsymbol{\tau}^{i}_{t }),p}\right),\;0\right)$ (4) $$

with $d\left({\mathcal{R}_{i}(^{k}\boldsymbol{\tau}^{i}_{t}),p}\right)$ as the distance from point $p$ to $\mathcal{R}_{i}$ at ${}^{k}\boldsymbol{\tau}^{i}_{t}$, and $\epsilon\geq 1$ a padding factor.

### 3.2 Constraining Strategies

To determine *when* and *where* to apply constraints on 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. 1 provides a summary of these methods and we elaborate upon them here.

MMD-PP.
Prioritized Planning sequentially plans paths for robots $\mathcal{R}_{i}\;\forall\;i\in\{1,\dots n\}$. This ordering of robots is treated as a priority ordering in that, on each call, robot $\mathcal{R}_{i}$ must generate a path $\boldsymbol{\pi}^{i}$ that avoids all $\mathcal{R}_{j}$ that previously planned. Robot $\mathcal{R}_{i}$ does so by respecting the constraints $C:=\{\langle\mathcal{R}_{i},\mathbf{q}^{i},t\rangle\mid\mathcal{R}_{i}(\mathbf
{q}^{i})\cap\mathcal{R}_{j}(\boldsymbol{\pi}^{j}_{t})\neq\emptyset\;\forall t\}$.
To translate this approach to trajectory generation 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 high-priority robot $\mathcal{R}_{j}$ be modeled with $M_{j}$ spheres and $p^{j}_{m}$ and $r^{j}_{m}$ be the position and radius of the $m^{\text{th}}$ sphere at time $t$. Then, lower-priority robot $\mathcal{R}_{i}$ generates a trajectory under the constraint set $\{\langle\mathcal{R}_{i},S_{r^{j}_{m}}(p^{j}_{m}),t\rangle\mid m\in\{1,\cdots M
_{j}\},j\prec i\}$, where $\prec$ indicates priority precedence. In Alg. 1, $\langle\mathcal{R}_{i},\boldsymbol{\tau}\rangle$ means that all trajectories of $\mathcal{R}_{j\neq i}$ in $\boldsymbol{\tau}$ 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 $N_{\text{root}}$ in the CT, planning paths for each agent independently, and storing these paths in $N_{\text{root}}.\Pi$.
CBS repeatedly extracts nodes $N$ from the CT and inspects $N.\Pi$ for conflicts. If no conflicts exist, the algorithm terminates, returning $N.\Pi$. Otherwise, CBS selects a conflict time $t$ where agents $\mathcal{R}_{i}$ and $\mathcal{R}_{j}$ collide at positions $\mathbf{q}^{i}=\boldsymbol{\pi}^{i}_{t}$ and $\mathbf{q}^{j}=\boldsymbol{\pi}^{j}_{t}$ in $N.\Pi$.
CBS then splits node $N$ into two new CT nodes, $N_{i}$ and $N_{j}$, each inheriting the (initially empty) constraint set $N.C$ and paths $N.\Pi$ from $N$, and incorporating a new constraint for preventing the respective agent from occupying the conflict position at time $t$. For example, $N_{i}.C\leftarrow N.C\cup\{\langle\mathcal{R}_{i},\mathbf{q}^{i},t\rangle\}$ for $\mathcal{R}_{i}$.
Paths for $\mathcal{R}_{i}$ and $\mathcal{R}_{j}$ are then replanned using low-level planners under the updated constraints in $N_{i}.C$ and $N_{j}.C$. The new CT nodes, with updated paths in $N_{i}.\Pi$ and $N_{j}.\Pi$, are added to the CT.
*MMD-CBS* follows the general CBS structure. It keeps a CT of nodes $N$, each with trajectories $N.\boldsymbol{\tau}$, 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. 1 for an illustration and Sec. A.4 for parameter values).

MMD-ECBS. Enhanced-CBS (ECBS) (Barer et al., ) 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 in diffusion-based trajectory generation, MMD-ECBS imposes two types of soft constraints: “weak” and “strong.” For each robot $\mathcal{R}_{j}$ with a trajectory in the CT node $N$, a weak soft-constraint that forbids $\mathcal{R}_{i}$ from colliding with any other $\mathcal{R}_{j}$ with $\boldsymbol{\tau}^{j}\in N.\boldsymbol{\tau}$ is imposed. This is done in a similar way to MMD-PP but with a 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-robot solutions to guide replanning enhances the efficiency of CBS (Shaoul et al., ). This is primarily because the motion planning problem between a CT node and 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 Janner et al. () and further refined in Zhou et al. ().
Adding this functionality to MMD-CBS and MMD-ECBS 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 in learning trajectory distributions within specific contexts. However, they face challenges in modeling complex trajectory distributions and generalizing to diverse contexts (e.g., significantly different obstacle layouts). To tackle this issue, we propose utilizing an ensemble of local diffusion models rather than a single model for a single robot. Each local model is trained to capture the trajectory distribution of a particular motion pattern within a local map segment, and we combine multiple models sequentially for long-horizon single-robot planning.
This approach offers three advantages: (1) Easier learning with simple, demonstrable motion patterns. (2) Better generalization across different contexts. (3) Effective scaling for large maps, aiding long-term planning.

During online planning, given a specific single-robot task $\mathcal{O}^{i}$ (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 et al. (), this is done by sampling from the local models in parallel, while incorporating a cross-conditioning term that constrains the local trajectories to connect seamlessly.
Let $\boldsymbol{\tau}^{i,l}$ be a local trajectory sampled from a local probability distribution $p^{l}$. The goal of the single-robot planner is to sample from the posterior distribution of trajectories:

$$ $\displaystyle\operatorname*{arg\,max}_{\boldsymbol{\tau}^{i}}$ $\displaystyle\log p(\boldsymbol{\tau}^{i}|\mathcal{O})=\operatorname*{arg\,max }_{\boldsymbol{\tau}^{i,1},\dots,\boldsymbol{\tau}^{i,L}}\log p(\boldsymbol{ \tau}^{i,1},\dots,\boldsymbol{\tau}^{i,L}|\mathcal{O})$ (5a) subject to $\displaystyle\boldsymbol{\tau}^{i,l}_{1}=\boldsymbol{\tau}^{i,l-1}_{H_{l-1}}, \forall l=1,\dots,L$ (5b) $$

Following Eq. 1, the new objective becomes:

$$ $\displaystyle\operatorname*{arg\,min}_{\boldsymbol{\tau}^{i,1},\dots, \boldsymbol{\tau}^{i,L}}\left(\mathcal{J}(\boldsymbol{\tau}^{i,1},\dots, \boldsymbol{\tau}^{i,L})-\sum_{l=1}^{L}\log p(\boldsymbol{\tau}^{i,l})\right)$ (6) $$

In practice, MMD ensures proper sequencing of the $L$ local diffusion models by introducing constraints requiring the last state of the trajectory from model $l$ to be equal to the first state from model $l+1$ (see Eq. 5b) and treating generation of local trajectories as inpainting (Lugmayr et al., ).
(^2^22Another option is to add a guidance term penalizing discontinuity. This approach is more flexible as it can optimize for connection points that are learned as well (e.g., via classifier guidance on the connection itself).)

Figure: (a) Empty map.
Refer to caption: extracted/5900305/figures/envs/empty_isaac_env.png

## 4 Experimental Analysis

We tested MMD’s efficacy in learning multi-robot trajectories on increasingly complex maps with varying numbers of holonomic ground robots in a simulated warehouse, modeling robots as 2D 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 $n$ robots begins by randomly picking start and goal states on a map for various algorithms to compute valid trajectories $\boldsymbol{\tau}$ (or MAPF paths $\Pi$) between. We evaluated the methods by success rate, the percentage of problems solved with no collision within a time limit, and data adherence, the average alignment of $\boldsymbol{\tau}^{i}\in\boldsymbol{\tau}$ with the dataset motion patterns. Data adherence uses a map-specific function $\text{cost}_{\text{data}}(\boldsymbol{\tau}^{i})$, scoring $1$ for 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.

Drop-Region map (Fig. 3(i)) simulates package drop-off chutes. Motion demonstrations are trajectories between random states that include a pause at one of sixteen drop-off regions—next to any chute edge midpoint. Adherence is met for $\boldsymbol{\tau}^{i}$, i.e., $\text{cost}_{\text{data}}(\boldsymbol{\tau}^{i})=1$, if it includes such a pause. Otherwise, it is zero.

Conveyor map (Fig. 3(e)) features narrow passages with directional motion requirements. Demonstrations connect random states with trajectories that pass along the top corridor to the left, or through the bottom corridor to the right. Trajectory $\boldsymbol{\tau}^{i}$ adheres to data if it similarly passes through either corridor before reaching its goal.

Highways map (Fig. 3(a)), requires counter-clockwise movement around a central obstacle—a pattern shown in its associated data. This map can be seen as a modular building block for larger multi-robot environments with its required motion pattern promoting easier coordination. Adherence is met for $\boldsymbol{\tau}^{i}$ if its cumulative motion within the map is counter-clockwise.

Empty map (Fig. 2(a)) 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(f)). In our larger scale experiments (Sec. 4.3) trajectories are computed within $2\times 2$ and $3\times 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.

Figure: (a) Highways map.
Refer to caption: extracted/5900305/figures/envs/highways_isaac_env.png

### 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-Composite, a state-of-the-art motion planning diffusion model (MPD) (Carvalho et al., ) that we trained on multi-robot data we collected in two maps: Empty and Highways. We created three models: for $3$, $6$, and $9$ 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-Composite 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 a search-based planning viewpoint, a compelling way to integrate motion data into multi-agent planning is by reducing MRMP to MAPF and forming cost maps to direct algorithms like ECBS (Cohen et al., ). This sacrifices dynamic feasibility, limiting solutions to a 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. 3(j)). We created 180 motion planning problems, 10 per group size across three maps, and assessed two search-based methods: A*Data-ECBS and A*-ECBS. The former plans single-robot paths with A* using map-specific statistical cost maps, where edges have lower costs if those are visited more frequently by the map’s dataset trajectories (discretized to map cells). The latter uses uniform costs (i.e., has no knowledge of the data) and is reported only to provide context for A*Data-ECBS’s performance.

We find that integrating motion data into statistical cost maps yields mixed outcomes: it enhances adherence in the Highways map by around $35\%$ compared to A*-ECBS but decreases success rates. In other maps, this approach finds collision-free paths, but falls short in managing complex motion distributions.
In contrast, our results for running MMD methods for the same planning problems show that those can solve complex trajectory generation tasks with high data adherence scores across all methods, and for some, with high success rates too.

Figure: (a) *Circle* setup.
Refer to caption: extracted/5900305/figures/envs/empty_circle15_env.png

Analyzing MMD Constraining Strategies.
Further analysis reveals a trend familiar from the MAPF literature. MMD-CBS struggles with scalability, reaching the time limit with more than $9$ robots. MMD-ECBS significantly outperforms MMD-CBS, and accelerated versions further improve performance.
MMD-PP finds efficiency in requiring only one inference pass per robot, however, because the constraints on 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-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 on robot interactions (Fig. 4(f)). In the *circle* setup, robots move between opposite points on a circle, likely colliding at the center. In the *weave* setup (inspired by Tajbakhsh et al. ()), robots begin on opposite points of a square, aiming to switch places.
CBS-based methods 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.

Figure: (a) $2\times 2$ map.
Refer to caption: extracted/5900305/figures/envs/multitile_2x2_env.png

### 4.3 Sequenced Diffusion Models for Long-Horizon Planning

We present a 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 a 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 a relaxed 240-second time frame. A standout feature of the sequencing method is its ability to create trajectories that follow a task-skeleton: passing through a 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(f)) 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.

## 5 Related Work

Multi-Robot Motion Planning.
Due to the PSPACE-hardness of MRMP (Hopcroft & Wilfong, ), most practical algorithms make various approximations to relax the planning problem. Some of the most successful MRMP methods reduce the problem to a multi-agent path finding problem (MAPF) (Stern et al., ) by discretizing state and time and assuming zero-volume shapes, constant velocities and rectilinear movements (Chen et al., ).
However, this introduces a gap between the MAPF formulation and MRMP which is problematic in many domains.
To relax the restriction of planning on a grid, recent works (Solis et al., ; Hönig et al., ) have generalized MAPF algorithms to continuous state spaces by using sampling-based motion planners to construct probabilistic roadmaps (PRM)  (Kavraki et al., ) for robots.

More generally, *coupled* MRMP algorithms, like Sanchez & Latombe (); Solovey et al. () apply sampling-based planners like PRM and RRT (Karaman & Frazzoli, ) to the composite configuration space of all the robots. This approach guarantees completeness but struggles to scale with the number of robots as the configuration space grows exponentially.
Conversely, *decoupled* algorithms like prioritized planning (Erdmann & Lozano-Perez, ) and Leroy et al. () 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., ) plan independently for every robot and loosely couple them to resolve conflicts.

Planning with Diffusion Models.
Lately, there has been a surge of interest in applying diffusion models (Sohl-Dickstein et al., ) to solve sequential decision making tasks, including planning and reinforcement learning (Ubukata et al., ).
Diffuser (Janner et al., ) first proposed the idea of using diffusion models for trajectory planning and showed how classifier-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., ), for learning visuomotor policies (Chi et al., ), and for offline decision-making (Ajay et al., ).
Most of these works have been limited to single-agent planning with two notable exceptions.
Jiang et al. () learn a joint motion distribution for multi-agent motion prediction using a diffusion model. By contrast, we focus on generating kinodynamically feasible and collision-free trajectories without having to learn a joint distribution.
Concurrent work by Mishra et al. () uses spatial-temporal factor graphs to compose modular generative models for solving long-horizon bimanual coordination tasks. By contrast, our approach can scale diffusion models to dozens of robots and complex environments by leveraging multi-agent search algorithms.

## 6 Conclusion

In this paper, we present Multi-robot Multi-model planning Diffusion (MMD), a multi-robot motion planner that learns to generate smooth collision-free trajectories for dozens of robots in complex environments.
Our key contribution is showing how single robot diffusion models can be effectively combined with state-of-the-art multi-agent search algorithms to generate data-driven multi-robot trajectories.
By learning only single-robot 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 overcomes many of the limitations of popular model-based MAPF algorithms, such as state discretization, 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 allowing for more flexibility in MMD’s planning horizon. As it stands, MMD generates trajectories of fixed duration—a limitation it inherits from diffusion planning. Sequencing models helps extend the time horizon but still, it must be determined a priori.
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 an interesting next step.

## 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 [https://github.com/yoraish/mmd](https://github.com/yoraish/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 in Sec. 4 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

The work was supported by the National Science Foundation under Grant IIS-2328671 and the CMU Manufacturing Futures Institute, made possible by the Richard King Mellon Foundation.
We thank Mohit Sharma and Ilan Mitnikov for fruitful discussions.

## Appendix 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 an additional discussion on 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 a 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. In our case, where the data-driven objective function scoring trajectories is 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 to explore first, as they are more likely to lead to collision-free solutions quickly. This is similar to the algorithm GCBS-H outlined in Barer et al. (). Resembling their outcomes, we also observed a 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., ). MMD makes use of this property. In contrast to the original CBS, where CT nodes $N$ store a single path for each robot within $N.\Pi$, MMD stores trajectory batches for each robot $\mathcal{R}_{i}$ within $N.\boldsymbol{\tau}$. That is, $N.\boldsymbol{\tau}^{i}$ may be a set of $B\in\mathbb{Z}^{>0}$ trajectories, with $B$ being a batch size. MMD-PP follows similarly, storing a batch of trajectories for each robot. When planning for $\mathcal{R}_{i}$, MMD generates a batch of trajectories under the currently active constraint set $N.C^{i}$ (see Fig. 1). Once the batch is generated, MMD iterates over the new resulting trajectories $N.\boldsymbol{\tau}^{i}$ and marks the one with the least collisions as the representative trajectory for $\mathcal{R}_{i}$. In 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 trajectories to compute the number of conflicts within CT nodes. When a conflict-free CT node is found (e.g., there are no collisions between representative trajectories), MMD returns the representative trajectories of $N.\boldsymbol{\tau}$ as the solution.

### A.2 Experimental Evaluation: Additional Results

We provide additional quantitative and qualitative results for our first two experiment sets, outlined in Table 1, Table 2, 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. 2, Fig. 3(j), and Fig. 5(f)). 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 it takes to generate those.
To this end, we include results for the average acceleration per robot (column A in Table 1 and Table 2), as a proxy for smoothness, and the runtime for trajectory generation (column T).

**Table 1: Comparison of methods by number of agents in the Empty environment (left) and the Highways environment (right). S is the success rate (%), D the data adherence score (see Sec. 4), T is the average planning time (seconds), and A is average acceleration (length units/$s^{2}$), a proxy for smoothness. Despite being computationally efficient, the composite baseline struggles to maintain high data adherence scores. Here, MMD is MMD-xECBS.**
| Empty Map | Highways Map |  |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| $n$ | Method | S$\uparrow$ | D$\uparrow$ | T$\downarrow$ | A$\downarrow$ | $n$ | Method | S$\uparrow$ | D$\uparrow$ | T$\downarrow$ | A$\downarrow$ |
| 3 | MMD | 100% | 0.999 | 3.4 | 0.002 | 3 | MMD | 100% | 0.96 | 3.3 | 0.042 |
| MPD-C | 100% | 1.000 | 2.1 | 0.010 | MPD-C | 100% | 0.98 | 2.1 | 0.032 |  |  |
| 6 | MMD | 100% | 0.995 | 7.0 | 0.002 | 6 | MMD | 98% | 0.97 | 6.9 | 0.045 |
| MPD-C | 62% | 0.331 | 2.2 | 0.142 | MPD-C | 0% | - | - | - |  |  |
| 9 | MMD | 100% | 0.991 | 11.1 | 0.002 | 9 | MMD | 96% | 0.97 | 10.7 | 0.043 |
| MPD-C | 0% | - | - | - | MPD-C | 0% | - | - | - |  |  |

**Table 2: Additional results for a subset of our MMD and MAPF evaluation. Table columns are similar to Table 1. We omit acceleration information from the MAPF methods as those plan on a grid graph and assume constant velocities.**
| Highways Map | Conveyor Map | Drop-Region Map |  |  |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| $n$ | Method | S$\uparrow$ | D$\uparrow$ | T$\downarrow$ | A$\downarrow$ | S$\uparrow$ | D$\uparrow$ | T$\downarrow$ | A$\downarrow$ | S$\uparrow$ | D$\uparrow$ | T$\downarrow$ | A$\downarrow$ |
| 3 | MMD-xECBS | 100% | 0.93 | 3.6 | 0.04 | 100% | 0.87 | 3.9 | 0.10 | 100% | 1.00 | 3.7 | 0.05 |
| 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 | 100% | 0.93 | 4.3 | 0.04 | 100% | 0.80 | 4.2 | 0.09 | 100% | 0.97 | 4.2 | 0.05 |  |
| MMD-CBS | 100% | 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*Data-ECBS | 100% | 0.87 | 3.4 | - | 100% | 0.03 | 0.2 | - | 100% | 0.27 | 0.2 | - |  |
| A*-ECBS | 100% | 0.57 | 0.1 | - | 100% | 0.00 | 0.5 | - | 100% | 0.27 | 0.2 | - |  |
| 6 | MMD-xECBS | 100% | 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 | 14.2 | 0.05 | 100% | 0.93 | 18.9 | 0.10 | 100% | 1.00 | 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 |  |
| A*Data-ECBS | 100% | 0.88 | 4.5 | - | 100% | 0.17 | 1.1 | - | 100% | 0.13 | 0.9 | - |  |
| A*-ECBS | 100% | 0.55 | 0.7 | - | 100% | 0.05 | 2.4 | - | 100% | 0.12 | 1.1 | - |  |
| 9 | MMD-xECBS | 100% | 0.97 | 12.7 | 0.05 | 100% | 0.93 | 14.6 | 0.11 | 100% | 0.94 | 12.9 | 0.06 |
| MMD-ECBS | 100% | 0.97 | 15.0 | 0.05 | 100% | 0.92 | 19.6 | 0.09 | 100% | 0.96 | 15.5 | 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% | 0.96 | 43.8 | 0.05 | 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*Data-ECBS | 100% | 0.88 | 14.0 | - | 100% | 0.10 | 2.7 | - | 100% | 0.22 | 1.3 | - |  |
| A*-ECBS | 100% | 0.51 | 3.4 | - | 100% | 0.06 | 3.4 | - | 100% | 0.19 | 0.8 | - |  |
| 12 | MMD-xECBS | 100% | 0.99 | 15.8 | 0.04 | 100% | 0.94 | 23.1 | 0.13 | 100% | 0.87 | 22.9 | 0.07 |
| MMD-ECBS | 100% | 0.99 | 17.6 | 0.04 | 100% | 0.95 | 28.4 | 0.10 | 100% | 0.88 | 29.6 | 0.06 |  |
| MMD-PP | 80% | 0.99 | 18.4 | 0.05 | 30% | 0.86 | 16.9 | 0.10 | 0% | - | - | - |  |
| MMD-CBS | 0% | - | - | - | 0% | - | - | - | 0% | - | - | - |  |
| MMD-xCBS | 30% | 0.97 | 54.6 | 0.05 | 10% | 1.00 | 53.5 | 0.19 | 0% | - | - | - |  |
| A*Data-ECBS | 80% | 0.83 | 19.7 | - | 100% | 0.14 | 3.8 | - | 100% | 0.22 | 4.0 | - |  |
| A*-ECBS | 100% | 0.52 | 6.0 | - | 100% | 0.03 | 4.0 | - | 100% | 0.23 | 4.4 | - |  |
| 15 | MMD-xECBS | 100% | 0.97 | 24.3 | 0.05 | 90% | 0.96 | 38.3 | 0.14 | 100% | 0.80 | 35.7 | 0.07 |
| MMD-ECBS | 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% | - | - | - | 0% | - | - | - |  |
| MMD-CBS | 0% | - | - | - | 0% | - | - | - | 0% | - | - | - |  |
| MMD-xCBS | 0% | - | - | - | 0% | - | - | - | 0% | - | - | - |  |
| A*Data-ECBS | 50% | 0.85 | 32.0 | - | 100% | 0.11 | 14.4 | - | 100% | 0.24 | 7.7 | - |  |
| A*-ECBS | 100% | 0.47 | 10.5 | - | 100% | 0.04 | 13.4 | - | 100% | 0.21 | 9.3 | - |  |
| 20 | MMD-xECBS | 100% | 0.96 | 46.1 | 0.05 | 0% | - | - | - | 0% | - | - | - |
| MMD-ECBS | 60% | 0.97 | 51.8 | 0.05 | 0% | - | - | - | 0% | - | - | - |  |
| MMD-PP | 0% | - | - | - | 0% | - | - | - | 0% | - | - | - |  |
| MMD-CBS | 0% | - | - | - | 0% | - | - | - | 0% | - | - | - |  |
| MMD-xCBS | 0% | - | - | - | 0% | - | - | - | 0% | - | - | - |  |
| A*Data-ECBS | 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 | - |  |

Average Acceleration Per Robot. Despite showing little information, since the composite baseline quickly failed to produce valid trajectories, Table 1 offers valuable insights nonetheless. The A column provides a glance into the reason for composite-model’s failure. Consistent with our observations, we notice that the average acceleration per robot in the $6$-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. 6 for an example.
We have trained MPD-Composite to convergence using our datasets (Sec. A.6) and performed additional tuning, however, its generated motions struggled to capture the smooth, dynamically feasible transitions as the number of robots grew to $9$.
MMD, however, produced better and larger-scale trajectories. Table 1 shows MMD keeping low average accelerations per robot. In larger teams of robots, we notice the acceleration remaining mostly constant within each map even when the number of robots grows. This shows that robots produce similar motions within each map regardless of congestion levels—a 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, as those only require a single inference pass for multi-robot trajectory generation, this is not 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 is tightly related to the number of 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 2 are inconsistent across maps. Interestingly, the planning time for A*Data-ECBS in the Highways map was significantly higher than that of A*-ECBS. This comes with the added benefit of the produced paths better adhering to data. In the other two maps, which have more challenging underlying motion data distributions, the difference between A*Data-ECBS and A*-ECBS was insignificant, though so were the data adherence scores. It is unclear to us how to effectively incorporate demonstrations from data into MAPF solvers without compromising their ability to scale.

Figure: (a) *
Refer to caption: extracted/5900305/figures/appendix_figures/mmd_xecbs_empty_3.png

### A.3 Additional Qualitative Results

To better capture the behavior of the various trajectory generators discussed in this paper, Fig. 6 shows a series of images of generated trajectories in two problems. We keep the number of robots low for clarity. Videos are available in our supplementary materials as well.

### A.4 Implementation Details

We implemented all of our algorithms in Python and ran our experiments on a laptop with an Intel Core i9-12900H CPU, 32GB RAM (5.2GHz), and Nvidia GeForce RTX 3080Ti Laptop GPU (16 GB). We based our diffusion planning implementation on the official code of Carvalho et al. () and used an exponential variance schedule. The guidance function cost components we used were $\mathcal{J}_{\text{smooth}}$ to encourage dynamically feasible trajectory generation with GPMP, $\mathcal{J}_{\text{obj}}$ for obstacle avoidance (both from Carvalho et al. ()), and $\mathcal{J}_{\text{c}}$ for constraint satisfaction. We set the weights $\lambda_{\text{smooth}}=8\mathrm{e}{-2}$, $\lambda_{\text{obj}}=2\mathrm{e}{-2}$, and $\lambda_{\text{c}}=2\mathrm{e}{-1}$ for strong soft-constraints and $\lambda_{\text{c}}=2\mathrm{e}{-2}$ for weak soft-constraints.

In our experiments, the size of each local map was $2\times 2$ units, and the diameter of each disk robot was $0.1$ units.
The radius for CBS sphere constraints was the disk robot radius multiplied by a margin, resulting in a radius value of $0.12$ units, and the time interval $\Delta t$ was $0.08$ seconds (2 time steps).

### A.5 Experimental Evaluation: Additional Details

This section provides details about our experimental setup, namely the data adherence scoring function $\text{cost}_{\text{data}}(\boldsymbol{\tau}^{i})$ that we used to evaluate trajectories $\boldsymbol{\tau}^{i}$ in 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 an 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. 4 briefly outlined the data adherence score functions for each map, and we provide more specific definitions here.

Drop-Region map (Fig. 3(i)) simulates package drop-off chutes.
Adherence is met for $\boldsymbol{\tau}^{i}$, i.e., $\text{cost}_{\text{data}}(\boldsymbol{\tau}^{i})=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. 3(e)) features narrow passages with directional motion requirements. Trajectory $\boldsymbol{\tau}^{i}$ adheres to data if it includes a section that enters the top corridor from the right and leaves it from the left, or 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. 3(a)), requires counter-clockwise movement around a central obstacle. The origin of the map is at the middle of the centeral obstacle. For each state transition of a trajectory $\boldsymbol{\tau}^{i}$, from $\boldsymbol{\tau}^{i}_{t}$ to $\boldsymbol{\tau}^{i}_{t+1}$, the angle between the vectors pointing from the origin to $\mathbf{q}^{i}_{t+1}$ and to $\mathbf{q}^{i}_{t}$ is computed. $\mathbf{q}^{i}_{t}$ is the associated configuration at $\boldsymbol{\tau}^{i}_{t}$. We define adherence to be met for $\boldsymbol{\tau}^{i}$ if its cumulative angle is positive, i.e., counter-clockwise.

Empty map (Fig. 2(a)) is our simplest. Trajectories $\boldsymbol{\tau}^{i}$, which have $H$ time steps, are scored based on the fraction of their steps that lie within a margin of a straight-line interpolation between a initial and final configurations $\mathbf{q}^{i}_{1},\mathbf{q}^{i}_{H}$ in $\boldsymbol{\tau}^{i}$. Specifically, let $l$ be the distance between the first and last configurations in $\boldsymbol{\tau}^{i}$, and let $m$ be the number of trajectory configurations whose distance to the line $\mathbf{q}^{i}_{H}-\mathbf{q}^{i}_{1}$ is less than $\frac{l}{10}$.
We define $\text{cost}_{\text{data}}(\boldsymbol{\tau}^{i}):=\frac{m}{H}$.

#### A.5.2 Large Scale Experiments

To mimic real-world scenarios, we have staggered the start times of robots in our large scale experiments in Sec. 4.3. There, robots began moving 10 time steps apart. Robots in motion were required to avoid static robots, which may be stopped in high-density regions.

### A.6 Baseline Details

Our experiments include two families of baselines: composite models and MAPF methods. Both baselines attempt to produce trajectories (or paths) that distribute according to an underlying motion pattern that is reflected in a dataset.
This section comes to provide additional details regarding these baseline methods.

Composite Models. Training composite models requires two components. The first is a dataset of multi-robot motions, and the second is a model that can be trained to generate trajectories that resemble those in the data. Given that obtaining multi-robot motion datasets is generally intractable as it requires solving an MRMP problem for each datapoint, in this paper we focus on single-robot data and construct our multi-robot datasets from collision-free subsets of 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 is that it is difficult to learn multi-robot trajectory generation from composed single-robot data, and not that it is a 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*Data-ECBS and A*-ECBS, are 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^{*}_{\epsilon}$ (Pearl & Kim, ). We set the focal list bound to $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 in MMD. All robots in our experiments travelled on a 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. It 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 $t$ and $t^{\prime}$ may still cause an edge conflict). This affected runtime.
To encode dataset demonstrations in A*Data-ECBS, we created cost maps for each evaluation map as discussed in Sec. 4.2. To do so in a given map, we iterate over all its dataset entries, and follow each trajectory, keeping track of which discretized cells (centered at states $s$) it visited. For each cell that the trajectory visited, we find the first trajectory state outside of its center $s$, call it $s^{\prime}$, and increment a count for the outgoing graph (directed) edge from $s$ that aligns best with the line between $s$ and $s^{\prime}$. Eventually, we assign directed edge costs of $1+\frac{10}{m}$ with $m$ being the number of trajectories that incremented this edge or $1$ if none have.
Our A*Data-ECBS and A*-ECBS implementation was done in Python.

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 6
presentation: 4
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.
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?
3. 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.
soundness: 4
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.
2. The experiment setting is diverse with varying levels of difficulties.
3. The writing is clear and structured and the paper is easy to read.
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.
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
2. In Sec. 4.2, it would be good to discuss the computational complexity between A* and MMD.
3. 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.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 2
questions: * How is the single-robot diffusion models training? Which dataset? Is it a single-robot dataset or a multi-robot dataset?
* 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?
* The performances of MPD are very low even if the number of agents is less than 5. Is it normal?
soundness: 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.
* 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.
* 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.
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.
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.
* Lack of some experimental details and results. See questions.
* The methods are not very efficient when the number of agents increases.

---

confidence: 3
contribution: 4
initial_rating: 8
presentation: 4
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.

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

3. How effectively does the approach generalize beyond warehouse-like environments? Could it perform well in less structured or highly dynamic settings?
soundness: 3
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.

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

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

The simulations conducted in various scenarios help validate the approach. Also, the success rates and data adherence scores are well presented.
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.
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.

---

confidence: 4
contribution: 4
initial_rating: 6
presentation: 4
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).

2. Please discuss the potential advantages and disadvantages of integrating GBP to MMD, as stated above.
soundness: 3
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.

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

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

3. The motivation is well-discussed, and the overall method is presented clearly.

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

[2] Amos, Brandon. "Tutorial on amortized optimization." Foundations and Trends® in Machine Learning 16.5 (2023): 592-732.
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.

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

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

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

Meta-review: This paper introduces the Multi-robot Multi-model planning Diffusion (MMD) method, which addresses a key challenge in multi-robot motion planning (MRMP) by leveraging single-robot diffusion models combined with Multi-Agent Path Finding (MAPF) constraints. The proposed approach scales diffusion-based motion planning to dozens of robots by imposing collision avoidance constraints derived from MAPF strategies like Conflict-Based Search (CBS). The authors demonstrate the effectiveness of this framework in generating collision-free, data-adherent trajectories across various logistics-inspired simulated environments. By efficiently utilizing single-robot data, the work establishes a new benchmark for scalable diffusion-based planning in multi-agent scenarios.

The paper’s novelty lies in its integration of diffusion models with MAPF strategies, addressing the exponential complexity inherent in multi-robot systems without requiring multi-agent datasets. The method is validated through extensive experiments across diverse environments, including different robot densities and map configurations, showcasing strong empirical performance. The authors also provide thorough ablations and comparisons with relevant baselines, supporting the robustness and scalability of their approach. The clarity and presentation of the paper, including detailed methodological explanations and visualizations, further contribute to its strengths.

The paper has some limitations. The experiments are primarily focused on structured, logistics-inspired environments, leaving the generalization to dynamic or less structured settings underexplored. While the proposed method significantly improves scalability, there is room for optimization in computational efficiency, particularly as the number of robots increases. Despite these minor weaknesses, the paper’s contributions are significant. It provides a novel solution to a critical problem in robotics, with strong empirical results and clear potential for future research.

Decision: Accept (Spotlight)