Multi-Agent Path Finding in Continuous Spaces with Projected Diffusion Models
Jinhao Liang, Jacob K. Christopher, Sven Koenig, Ferdinando Fioretto · 2024
Read Multi-Agent Path Finding in Continuous Spaces with Projected Diffusion Models by Jinhao Liang, Jacob K. Christopher, Sven Koenig, Ferdinando Fioretto (2024) 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-2412-17993.txt.
Introduction
Jinhao Liang, Jacob Christopher, Sven Koenig, and Ferdinando Fioretto plan collision-free routes for many robots at once using diffusion models, in a 2024 paper. Steering a fleet through a shared space is hard. It grows harder in open continuous spaces, where classic methods need the world chopped into a grid and bog down as fleets grow. Diffusion models, borrowed from image generation, have shown skill at drawing smooth single-robot paths through such spaces.
The catch is that generated paths can break the rules, letting robots collide or move impossibly. The authors fuse the generator with constrained optimization, a method that enforces rules while it shapes the output. The blend produces whole sets of robot trajectories that respect collision bans and motion limits from the start. Tests across simulated scenes of varying dimension show the approach holds up where plain diffusion planning fails.
Catalog record
| CREATOR | Jinhao Liang, Jacob K. Christopher, Sven Koenig, Ferdinando Fioretto |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 34 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-17993
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Multi-Agent Path Finding in Continuous Spaces with Projected Diffusion Models Jinhao Liang, Jacob K. Christopher, Sven Koenig, Ferdinando Fioretto Abstract Multi-Agent Path Finding (MAPF) is a fundamental problem in robotics, requiring the computation of collision-free paths for multiple agents moving from their respective start to goal positions. Coordinating multiple agents in a shared environment poses significant challenges, especially in continuous spaces where traditional optimization algorithms struggle with scalability. Moreover, these algorithms often depend on discretized representations of the environment, which can be impractical in image-based or high-dimensional settings. Recently, diffusion models have shown promise in single-agent path planning, capturing complex trajectory distributions and generating smooth paths that navigate continuous, high-dimensional spaces. However, directly extending diffusion models to MAPF introduces new challenges since these models struggle to ensure constraint feasibility, such as inter-agent collision avoidance. To overcome this limitation, this work proposes a novel approach that integrates constrained optimization with diffusion models for MAPF in continuous spaces. This unique combination directly produces feasible multi-agent trajectories that respect collision avoidance and kinematic constraints. The effectiveness of our approach is demonstrated across various challenging simulated scenarios of varying dimensionality. A Preprint 1 Introduction Multi-agent path finding (MAPF) is a critical problem in robotics and autonomous systems, where the goal is to compute collision-free paths for multiple agents navigating from their respective start positions to designated goals in a shared environment Stern et al. (2019) . This problem finds formulation in numerous domains, such as gaming, automated warehouses, and aircraft taxing Li et al. (2021a) . The problem is inherently challenging due to the high-dimensional joint configuration space and the need for coordination among multiple agents to avoid collision. The complexity increases exponentially with the number of agents, making scalability a significant issue for traditional MAPF algorithms. Additionally, existing studies typically consider discrete environments Stern et al. (2019) ; Hopcroft et al. (1984) , thus further limiting their applicability in scenarios in-the-wild. The complexity of MAPF in continuous or high-dimensional environments calls for approaches that move beyond traditional discretized methods. Within this context, trajectory optimization has recently been tackled using diffusion models, a powerful class of generative models originally developed for tasks in image and signal processing Song and Ermon (2019) ; Ho et al. (2020) . These models approximate high-dimensional probability distributions by iteratively denoising sampled trajectories, leveraging strong inductive biases that provide effective heuristics even for very complex distributions. Their adaptability has accelerated their adoption across diverse engineering domains, including single-agent robotic path planning Carvalho et al. (2023) ; Christopher et al. (2024) . By learning the underlying distribution of (feasible) trajectories, diffusion models can produce diverse solutions that may be missed by traditional planners due to inductive bias. Additionally, these models possess the ability to generate smooth trajectories that effectively navigate high-dimensional spaces with complex obstacles while directly processing real-world representations of the environment. However, despite their potential, current diffusion models face significant challenges in generating feasible trajectories. Existing approaches often rely on costly rejection sampling methods, which attempt to identify a feasible subset from a larger set of initially generated trajectories, if such a subset exists at all Carvalho et al. (2023) ; Christopher et al. (2024) . Additionally, despite their adoption in single-agent scenarios, extending diffusion models to MAPF presents additional challenges. The introduction of multiple agents requires the consideration of collision avoidance among agents, as well as kinematic constraints. To address this limitation, this paper proposes a novel integration of constrained optimization in diffusion processes tailored to MAPF in continuous spaces. The proposed method leverages the projection-based method for diffusion models Christopher et al. (2024) , which has been recently introduced to steer the learned data distribution to satisfy some constraints of interest. This approach reformulates the sampling process as a constrained optimization problem, projecting the outputs of DMs at each sampling step into the feasible region. However, the MAPF feasible region is defined by a set of nonconvex nonlinear constraints (NNCs), which massively complicates the application of these diffusion models in scenarios with a large number of agents or with moving objects. To address this limitation and enhance computational efficiency, we propose an augmented Lagrangian method that relaxes the NNCs, making the proposed approach suitable for complex applications where classical MAPF algorithms fall short. This novel integration enables generative diffusion models to generate, for the first time, collision-free trajectories for scenarios involving dozens of agents and obstacles. The paper’s contributions are summarized as follows: 1. We introduce a novel formulation of MAPF in continuous spaces using diffusion models, enabling the simultaneous generation of trajectories for all agents in a single framework. 2. To address the challenge of constraint satisfaction, we adapt the projection mechanism for MAPF by embedding constraints directly into the diffusion process, projecting the generated solutions into the feasible region. 3. Given the computational intractability of MAPF in continuous spaces, especially with a large number of agents, we develop an augmented Lagrangian approach to accelerate the projection process. This enhancement significantly reduces computational overhead, making the method scalable and practical for real-world applications. 4. We assess the ability of our approach to generate feasible MAPF trajectory empirically over several challenging scenarios, which include maps with narrow corridors, dense obstacles, and a large number of agents. 2 Related Work Multi-Agent Path Finding. The classical MAPF problem assumes that time and the environment are discretized into time steps and grids, respectively Stern et al. (2019) . Under this assumption, numerous search algorithms have been developed to efficiently obtain near-optimal solutions for MAPF in discrete environments, even for scenarios involving hundreds of agents Li et al. (2019) ; Li et al. (2021b) ; Okumura et al. (2022a) ; Li et al. (2021b) . While this assumption significantly reduces the complexity of MAPF, it creates a gap between the problem’s formulation and real-world applications, posing challenges in many domains Shaoul et al. (2024) . Some studies attempt to generalize MAPF to continuous environments using probabilistic roadmaps Kavraki et al. (1996) and rapidly exploring random trees LaValle (1998) . Another line of research formulates MAPF as a constrained optimization problem with continuous variables, employing methods such as sequential convex programming Augugliaro et al. (2012) ; Chen et al. (2015) and the alternating direction method of multipliers Chen et al. (2023) . However, these methods often fail to find any solution if there are a large number of agents and obstacles, even if one exists. Path Finding with Generative Models. There has been a growing interest in leveraging generative models for path finding problems. Existing studies primarily focus on using diffusion models to solve single-agent path finding problems Janner et al. (2022) ; Carvalho et al. (2023) . Besides these approaches, Okumura et al. utilizes a conditional variational autoencoder to predict cooperative timed roadmaps to aid in solving MAPF in continuous spaces. Shaoul et al. uses diffusion models to generate a trajectory for a single agent and employs classical searching algorithms to determine the final solutions. However, these methods do not ensure the feasibility of the diffusion model outputs and cannot directly generate collision-free paths. In contrast, our approach integrates optimization techniques into diffusion models to directly generate feasible MAPF solutions in continuous spaces, even in scenarios with a significant number