Multi-Agent Path Finding in Continuous Spaces with Projected Diffusion Models

• URL: http://arxiv.org/abs/2412.17993v1
• Date: Mon, 23 Dec 2024 21:27:19 GMT
• Title: Multi-Agent Path Finding in Continuous Spaces with Projected Diffusion Models
• Authors: Jinhao Liang, Jacob K. Christopher, Sven Koenig, Ferdinando Fioretto,
• Abstract summary: Multi-Agent Path Finding (MAPF) is a fundamental problem in robotics. This work proposes a novel approach that integrates constrained optimization with diffusion models for MAPF in continuous spaces.
• Score: 57.45019514036948
• License:
• 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.

Related papers

• Simultaneous Multi-Robot Motion Planning with Projected Diffusion Models [57.45019514036948]
  Simultaneous MRMP Diffusion (SMD) is a novel approach integrating constrained optimization into the diffusion sampling process to produce kinematically feasible trajectories. The paper introduces a comprehensive MRMP benchmark to evaluate trajectory planning algorithms across scenarios with varying robot densities, obstacle complexities, and motion constraints.
  arXiv  Detail & Related papers  (2025-02-05T20:51:28Z)
• Merging Models on the Fly Without Retraining: A Sequential Approach to Scalable Continual Model Merging [75.93960998357812]
  Deep model merging represents an emerging research direction that combines multiple fine-tuned models to harness their capabilities across different tasks and domains. Current model merging techniques focus on merging all available models simultaneously, with weight matrices-based methods being the predominant approaches. We propose a training-free projection-based continual merging method that processes models sequentially.
  arXiv  Detail & Related papers  (2025-01-16T13:17:24Z)
• Go With the Flow: Fast Diffusion for Gaussian Mixture Models [13.03355083378673]
  Schr"odinger Bridges (SB) are diffusion processes that steer, in finite time, a given initial distribution to another final one while minimizing a suitable cost functional. We propose latentmetrization of a set of SB policies for steering a system from one distribution to another. We showcase the potential this approach in low-to-dimensional problems such as image-to-image translation in the space of an autoencoder.
  arXiv  Detail & Related papers  (2024-12-12T08:40:22Z)
• DiffSG: A Generative Solver for Network Optimization with Diffusion Model [75.27274046562806]
  Diffusion generative models can consider a broader range of solutions and exhibit stronger generalization by learning parameters. We propose a new framework, which leverages intrinsic distribution learning of diffusion generative models to learn high-quality solutions.
  arXiv  Detail & Related papers  (2024-08-13T07:56:21Z)
• Deciphering Movement: Unified Trajectory Generation Model for Multi-Agent [53.637837706712794]
  We propose a Unified Trajectory Generation model, UniTraj, that processes arbitrary trajectories as masked inputs. Specifically, we introduce a Ghost Spatial Masking (GSM) module embedded within a Transformer encoder for spatial feature extraction. We benchmark three practical sports game datasets, Basketball-U, Football-U, and Soccer-U, for evaluation.
  arXiv  Detail & Related papers  (2024-05-27T22:15:23Z)
• Accelerating Search-Based Planning for Multi-Robot Manipulation by Leveraging Online-Generated Experiences [20.879194337982803]
  Multi-Agent Path-Finding (MAPF) algorithms have shown promise in discrete 2D domains, providing rigorous guarantees. We propose an approach for accelerating conflict-based search algorithms by leveraging their repetitive and incremental nature.
  arXiv  Detail & Related papers  (2024-03-29T20:31:07Z)
• Few Shot Generative Model Adaption via Relaxed Spatial Structural Alignment [130.84010267004803]
  Training a generative adversarial network (GAN) with limited data has been a challenging task. A feasible solution is to start with a GAN well-trained on a large scale source domain and adapt it to the target domain with a few samples, termed as few shot generative model adaption. We propose a relaxed spatial structural alignment method to calibrate the target generative models during the adaption.
  arXiv  Detail & Related papers  (2022-03-06T14:26:25Z)
• A Bayesian Multiscale Deep Learning Framework for Flows in Random Media [0.0]
  Fine-scale simulation of complex systems governed by multiscale partial differential equations (PDEs) is computationally expensive and various multiscale methods have been developed for addressing such problems. In this work, we introduce a novel hybrid deep-learning and multiscale approach for multiscale PDEs with limited training data. For demonstration purposes, we focus on a porous media flow problem. We use an image-to-image supervised deep learning model to learn the mapping between the input permeability field and the multiscale basis functions.
  arXiv  Detail & Related papers  (2021-03-08T23:11:46Z)
• Multimodal Trajectory Prediction via Topological Invariance for Navigation at Uncontrolled Intersections [45.508973373913946]
  We focus on decentralized navigation among multiple non-communicating rational agents at street intersections without traffic signs or signals. Our key insight is that the geometric structure of the intersection and the incentive of agents to move efficiently and avoid collisions (rationality) reduces the space of likely behaviors. We design Multiple Topologies Prediction (MTP), a data-driven trajectory-prediction mechanism that reconstructs trajectory representations of high-likelihood modes in multiagent intersection scenes.
  arXiv  Detail & Related papers  (2020-11-08T02:56:42Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.