CTRMs: Learning to Construct Cooperative Timed Roadmaps for Multi-agent Path Planning in Continuous Spaces

• URL: http://arxiv.org/abs/2201.09467v1
• Date: Mon, 24 Jan 2022 05:43:59 GMT
• Title: CTRMs: Learning to Construct Cooperative Timed Roadmaps for Multi-agent Path Planning in Continuous Spaces
• Authors: Keisuke Okumura, Ryo Yonetani, Mai Nishimura, Asako Kanezaki
• Abstract summary: We propose a novel concept of roadmaps called cooperative timed roadmaps (CTRMs) CTRMs enable each agent to focus on its important locations around potential solution paths in a way that considers the behavior of other agents to avoid inter-agent collisions. We developed a machine-learning approach that learns a generative model from a collection of relevant problem instances and plausible solutions.
• Score: 20.389416558418382
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-agent path planning (MAPP) in continuous spaces is a challenging problem with significant practical importance. One promising approach is to first construct graphs approximating the spaces, called roadmaps, and then apply multi-agent pathfinding (MAPF) algorithms to derive a set of conflict-free paths. While conventional studies have utilized roadmap construction methods developed for single-agent planning, it remains largely unexplored how we can construct roadmaps that work effectively for multiple agents. To this end, we propose a novel concept of roadmaps called cooperative timed roadmaps (CTRMs). CTRMs enable each agent to focus on its important locations around potential solution paths in a way that considers the behavior of other agents to avoid inter-agent collisions (i.e., "cooperative"), while being augmented in the time direction to make it easy to derive a "timed" solution path. To construct CTRMs, we developed a machine-learning approach that learns a generative model from a collection of relevant problem instances and plausible solutions and then uses the learned model to sample the vertices of CTRMs for new, previously unseen problem instances. Our empirical evaluation revealed that the use of CTRMs significantly reduced the planning effort with acceptable overheads while maintaining a success rate and solution quality comparable to conventional roadmap construction approaches.

Related papers

• SIGMA: Sheaf-Informed Geometric Multi-Agent Pathfinding [4.801673346687721]
  The Multi-Agent Path Finding (MAPF) problem aims to determine the shortest and collision-free paths for multiple agents in a known, potentially obstacle-ridden environment. We introduce a new framework that applies sheaf theory to decentralized deep reinforcement learning, enabling agents to learn geometric cross-dependencies between each other. In particular, we incorporate a neural network to approximately model the consensus in latent space based on sheaf theory and train it through self-supervised learning.
  arXiv  Detail & Related papers  (2025-02-10T13:17:34Z)
• Multi-Agent Path Finding in Continuous Spaces with Projected Diffusion Models [57.45019514036948]
  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.
  arXiv  Detail & Related papers  (2024-12-23T21:27:19Z)
• SCoTT: Wireless-Aware Path Planning with Vision Language Models and Strategic Chains-of-Thought [78.53885607559958]
  A novel approach using vision language models (VLMs) is proposed for enabling path planning in complex wireless-aware environments. To this end, insights from a digital twin with real-world wireless ray tracing data are explored. Results show that SCoTT achieves very close average path gains compared to DP-WA* while at the same time yielding consistently shorter path lengths.
  arXiv  Detail & Related papers  (2024-11-27T10:45:49Z)
• Cooperative Path Planning with Asynchronous Multiagent Reinforcement Learning [4.640948267127441]
  shortest path problem (SPP) with multiple source-destination pairs (MSD) In this paper, we study the shortest path problem (SPP) with multiple source-destination pairs (MSD), namely MSD-SPP, to minimize average travel time of all shortest paths.
  arXiv  Detail & Related papers  (2024-09-01T15:48:14Z)
• Scalable Mechanism Design for Multi-Agent Path Finding [87.40027406028425]
  Multi-Agent Path Finding (MAPF) involves determining paths for multiple agents to travel simultaneously and collision-free through a shared area toward given goal locations. Finding an optimal solution is often computationally infeasible, making the use of approximate, suboptimal algorithms essential. We introduce the problem of scalable mechanism design for MAPF and propose three strategyproof mechanisms, two of which even use approximate MAPF algorithms.
  arXiv  Detail & Related papers  (2024-01-30T14:26:04Z)
• Learn to Follow: Decentralized Lifelong Multi-agent Pathfinding via Planning and Learning [46.354187895184154]
  Multi-agent Pathfinding (MAPF) problem generally asks to find a set of conflict-free paths for a set of agents confined to a graph. In this work, we investigate the decentralized MAPF setting, when the central controller that posses all the information on the agents' locations and goals is absent. We focus on the practically important lifelong variant of MAPF, which involves continuously assigning new goals to the agents upon arrival to the previous ones.
  arXiv  Detail & Related papers  (2023-10-02T13:51:32Z)
• Multi-Objective Policy Gradients with Topological Constraints [108.10241442630289]
  We present a new algorithm for a policy gradient in TMDPs by a simple extension of the proximal policy optimization (PPO) algorithm. We demonstrate this on a real-world multiple-objective navigation problem with an arbitrary ordering of objectives both in simulation and on a real robot.
  arXiv  Detail & Related papers  (2022-09-15T07:22:58Z)
• Multi-objective Conflict-based Search Using Safe-interval Path Planning [10.354181009277623]
  We present a new multi-objective conflict-based search (MO-CBS) approach that relies on a novel multi-objective safe interval path planning (MO-SIPP) algorithm for its low-level search. We present extensive numerical results to show that there is an order of magnitude improvement in the average low level search time. We also provide a case study to demonstrate the potential application of the proposed algorithms for construction site planning.
  arXiv  Detail & Related papers  (2021-08-02T09:42:08Z)
• Symmetry Breaking for k-Robust Multi-Agent Path Finding [30.645303869311366]
  k-Robust Conflict-BasedSearch (k-CBS) is an algorithm that produces coordinated and collision-free plan that is robust for up to k delays. We introduce a variety of pairwise symmetry breaking constraints, specific to k-robust planning, that can efficiently find compatible and optimal paths for pairs of conflicting agents.
  arXiv  Detail & Related papers  (2021-02-17T11:09:33Z)
• Decentralized MCTS via Learned Teammate Models [89.24858306636816]
  We present a trainable online decentralized planning algorithm based on decentralized Monte Carlo Tree Search. We show that deep learning and convolutional neural networks can be employed to produce accurate policy approximators.
  arXiv  Detail & Related papers  (2020-03-19T13:10:20Z)

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.