Discrete-Guided Diffusion for Scalable and Safe Multi-Robot Motion Planning

Jinhao Liang, Sven Koenig, Ferdinando Fioretto · 2025

Read Discrete-Guided Diffusion for Scalable and Safe Multi-Robot Motion Planning by Jinhao Liang, Sven Koenig, Ferdinando Fioretto (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-20095.txt.

Introduction

Jinhao Liang, Sven Koenig, and Ferdinando Fioretto present a planning method for robot teams in this 2025 paper. Many robots in one shared space must each reach a goal without hitting each other. Grid-based planners scale well but give rough paths, while smooth planners give fine paths yet bog down as teams grow.

Their method joins the two styles. A grid solver first sketches safe routes, then a learning-based smoother polishes each path under clear limits. A light repair step fixes any path that breaks a rule. In hard test scenes the method scaled to one hundred robots with high success rates. It sets a new best mark for large teams, the authors report.

Catalog record

CREATORJinhao Liang, Sven Koenig, Ferdinando Fioretto
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE56 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-20095

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Discrete-Guided Diffusion for Scalable and Safe Multi-Robot Motion Planning Jinhao Liang, Sven Koenig, Ferdinando Fioretto Abstract Multi-Robot Motion Planning (MRMP) involves generating collision-free trajectories for multiple robots operating in a shared continuous workspace. While discrete multi-agent path finding (MAPF) methods are broadly adopted due to their scalability, their coarse discretization severely limits trajectory quality. In contrast, continuous optimization-based planners offer higher-quality paths but suffer from the curse of dimensionality, resulting in poor scalability with respect to the number of robots. This paper tackles the limitations of these two approaches by introducing a novel framework that integrates discrete MAPF solvers with constrained generative diffusion models. The resulting framework, called Discrete-Guided Diffusion (DGD), has three key characteristics: (1) it decomposes the original nonconvex MRMP problem into tractable subproblems with convex configuration spaces, (2) it combines discrete MAPF solutions with constrained optimization techniques to guide diffusion models capture complex spatiotemporal dependencies among robots, and (3) it incorporates a lightweight constraint repair mechanism to ensure trajectory feasibility. The proposed method sets a new state-of-the-art performance in large-scale, complex environments, scaling to 100 robots while achieving planning efficiency and high success rates. K eywords Diffusion Models \cdot Multi-Agent Path Planning \cdot Multi-Robot Motion Planning 1 Introduction Multi-Robot Motion Planning (MRMP) is a fundamental problem in robotics that requires generating collision-free trajectories for multiple robots operating in a shared environment. MRMP arises in diverse applications such as automated warehouses, coordinated drone fleets, and autonomous driving. Despite its importance, efficiently solving MRMP in complex environments remains a significant challenge due to the high dimensionality and combinatorial complexity Yu and LaValle 2013 . To address these challenges, two major paradigms have emerged. Optimization-based methods formulate the problem as a continuous, often nonconvex trajectory optimization problem and are capable of producing smooth, high-quality paths Marcucci et al. 2023 . However, their scalability is severely limited as the number of robots and obstacles increases. Another body of work considers a discretized version of MRMP, known as Multi-Agent Path Finding (MAPF). It discretizes the space and time, significantly reducing computational complexity Li et al. 2021 ; Okumura 2024 . MAPF algorithms scale to hundreds of robots, but their reliance on discretized grid-based movement and synchronized time steps limits their applicability in continuous and dynamic environments. To address these limitations, recent work has explored the use of generative models, particularly diffusion models, to learn distributions over trajectories in continuous spaces Xiao et al. 2022 ; Carvalho et al. 2023 . These models show promising results in single-robot planning as they enable diverse and high-quality trajectory generation. However, their extension to multi-robot settings introduces significant challenges: Diffusion models must capture complex inter-robot spatiotemporal dependencies while simultaneously avoiding collisions , a problem that becomes highly intractable as the number of robots and obstacles grows. Several recent approaches attempt to extend diffusion models to MRMP via gradient-based guidance Shaoul et al. 2024 ; Ding et al. 2025 . These methods are able to generate high quality trajectories, but are limited by two key challenges: First, the difficulty of ensuring the feasibility of the generated trajectories with respect to non-collision and kinodynamic constraints. This is hard since gradient-based guidance cannot natively guarantee global constraint satisfaction. Second, these models struggle in cluttered or dense environments, where the complexity of the configuration space increases. Recently, Liang et al. 2025 proposed an approach to ensure feasibility through repeated projections within the diffusion process. This is a promising solution, but it comes at a high computational overhead, due to the nonconvexity and high dimensionality of constraints. Figure 1: Overview of Discrete-Guided Diffusion. S1 shows that the nonconvex configuration space is approximated by multiple convex regions. The wheat regions denote the obstacles, and the green regions denote the free space. The robots move from their start \bullet to their goal positions \star . S2 illustrates that the local start and goal for each robot in each subproblem is determined by the spatiotemporal dependency obtained from MAPF solutions. S3 shows that the trajectory is generated by diffusion models guided by discrete spatiotemporal dependency. Collision is marked by ✸. S4 shows that the infeasible problem is repaired by constraint-aware diffusion models. Contribution. This paper addresses these challenges through a novel integration of discrete MAPF with continuous denoising diffusion. The proposed Discrete-Guided Diffusion (DGD), first decomposes the original MRMP problem into a sequence of local subproblems with convex configuration space, each defined by the spatiotemporal structure obtained from the MAPF solution. On each subproblem, a diffusion model is then used to generate trajectories guided by this spatiotemporal structure. To ensure feasibility, DGD relies on a lightweight projected guidance rendering each step of the diffusion process feasible, and enforced only when constraint violations are detected. The whole framework is schematically illustrated in Figure 1 . The effectiveness and efficiency of DGD is demonstrated both theoretically and practically across a range of challenging benchmarks with up to 100+ robots. 2 Related Work In this section, we review three research areas that form the foundation for our work: multi-robot motion planning (MRMP), discrete multi-agent path finding (MAPF), and generative models for motion planning. We summarize the key methods and challenges in each area, highlighting the scalability, constraint handling, and feasibility guarantees that motivate our proposed approach. Multi-robot Motion Planning. MRMP methods address trajectory generation for multiple robots in continuous space. There are two main approaches for MRMP: (1) Sampling-based algorithm, where constructs feasible trajectories by randomly sampling the state space Gammell et al. 2014 ; Shome et al. 2020 . While sampling-based planners are probabilistically complete, they require dense sampling and struggle to enforce continuous kinodynamic constraints, limiting their practical applications. (2) Optimization-based planner, where the planning problem is formulated as an optimization program, such as a sequential convex program Augugliaro et al. 2012 ; Park et al. 2020 and a mixed-integer program Mellinger et al. 2012 . While optimization-based methods can handle various constraints, extending them to the multi-robot case couples all robots into a single high-dimensional optimization problem, suffering from exponential growth in decision variables and local minima. Recently, Graph of Convex Sets (GCS) has been proposed to mitigate this issue for single robot motion planning by decomposing the environment into a collection of convex regions Marcucci et al. 2023 ; Chia et al. 2024 . However, applying GCS to MRMP is quite challenging due to the spatiotemporal dependencies among multiple robots. Discrete Multi-agent Path Finding. Multi-agent path finding (MAPF) focuses on a discretized version of MRMP by discretizing both time and space into steps and grids, respectively Stern et al. 2019 . The MAPF literature has produced highly scalable algorithms such as Conflict-Based Search (CBS) and its bounded-suboptimal variants Sharon et al. 2015 ; Li et al. 2021 ; Okumura 2024 . These planners can coordinate hundreds of agents with correctness and solution quality guarantees in grid worlds by resolving pairwise collisions in a low-dimensional discrete space and have been adopted in large automated-warehouse deployments. However, their reliance on synchronized, axis-aligned motions and fixed timesteps makes it difficult to transfer the resulting plans to real robots with continuous dynamics, kinodynamic limits, or tight clearances; post-processing heuristics such as temporal smoothing or continuous re-planning only partially mitigate this gap Hönig et al. 2018 . Generative

Read the complete text