Transient Multi-Agent Path Finding for Lifelong Navigation in Dense Environments

• URL: http://arxiv.org/abs/2412.04256v1
• Date: Thu, 05 Dec 2024 15:37:29 GMT
• Title: Transient Multi-Agent Path Finding for Lifelong Navigation in Dense Environments
• Authors: Jonathan Morag, Noy Gabay, Daniel koyfman, Roni Stern,
• Abstract summary: The Lifelong MAPF (LMAPF) problem is a well-studied online version of MAPF in which an agent receives a new target when it reaches its current target. We propose to solve LMAPF problems by solving a sequence of modified MAPF problems, in which the objective is for each agent to eventually visit its target. We refer to this MAPF variant as Transient MAPF (TMAPF) and propose several algorithms for solving it based on existing MAPF algorithms.
• Score: 9.000023855628958
• License:
• Abstract: Multi-Agent Path Finding (MAPF) deals with finding conflict-free paths for a set of agents from an initial configuration to a given target configuration. The Lifelong MAPF (LMAPF) problem is a well-studied online version of MAPF in which an agent receives a new target when it reaches its current target. The common approach for solving LMAPF is to treat it as a sequence of MAPF problems, periodically replanning from the agents' current configurations to their current targets. A significant drawback in this approach is that in MAPF the agents must reach a configuration in which all agents are at their targets simultaneously, which is needlessly restrictive for LMAPF. Techniques have been proposed to indirectly mitigate this drawback. We describe cases where these mitigation techniques fail. As an alternative, we propose to solve LMAPF problems by solving a sequence of modified MAPF problems, in which the objective is for each agent to eventually visit its target, but not necessarily for all agents to do so simultaneously. We refer to this MAPF variant as Transient MAPF (TMAPF) and propose several algorithms for solving it based on existing MAPF algorithms. A limited experimental evaluation identifies some cases where using a TMAPF algorithm instead of a MAPF algorithm with an LMAPF framework can improve the system throughput significantly.

Related papers

• Layered LA-MAPF: a decomposition of large agent MAPF instance to accelerate solving without compromising solvability [0.0]
  Multi-Agent Path Finding (MAPF) has been widely studied in recent years. Most existing MAPF algorithms assume that an agent occupies only a single grid in a grid-based map. We introduce textbfLayered LA-MAPF, a method that decomposes a MAPF instance involving geometric agents into clusters.
  arXiv  Detail & Related papers  (2024-10-22T16:34:24Z)
• MAPF-GPT: Imitation Learning for Multi-Agent Pathfinding at Scale [46.35418789518417]
  Multi-agent pathfinding (MAPF) is a problem that generally requires finding collision-free paths for multiple agents in a shared environment. Recently, learning-based approaches to MAPF have gained attention, particularly those leveraging deep reinforcement learning. We show that MAPF-GPT notably outperforms the current best-performing learnable MAPF solvers on a diverse range of problem instances.
  arXiv  Detail & Related papers  (2024-08-29T12:55:10Z)
• Scaling Lifelong Multi-Agent Path Finding to More Realistic Settings: Research Challenges and Opportunities [44.292720085661585]
  We present our winning approach to the 2023 League of Robot Runners LMAPF competition. The first challenge is to search for high-quality LMAPF solutions within a limited planning time. The second challenge is to alleviate myopic congestion and the effect of behaviors in LMAPF algorithms. The third challenge is to bridge the gaps between the LMAPF models used in the literature and real-world applications.
  arXiv  Detail & Related papers  (2024-04-24T19:37:18Z)
• 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)
• Decentralized Monte Carlo Tree Search for Partially Observable Multi-agent Pathfinding [49.730902939565986]
  Multi-Agent Pathfinding problem involves finding a set of conflict-free paths for a group of agents confined to a graph. In this study, we focus on the decentralized MAPF setting, where the agents may observe the other agents only locally. We propose a decentralized multi-agent Monte Carlo Tree Search (MCTS) method for MAPF tasks.
  arXiv  Detail & Related papers  (2023-12-26T06:57:22Z)
• Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding [29.76466191644455]
  Multi-Agent Path Finding (MAPF) is a fundamental problem in robotics that asks us to compute collision-free paths for a team of agents. We propose a new approach for MAPF where agents are guided to their destination by following congestion-avoiding paths. We evaluate the idea in two large-scale settings: one-shot MAPF, where each agent has a single destination, and lifelong MAPF, where agents are continuously assigned new destinations.
  arXiv  Detail & Related papers  (2023-08-22T07:17:39Z)
• Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
  We introduce an original variant of Monte-Carlo Tree Search (MCTS) tailored to multi-agent pathfinding. Specifically, we use individual paths to assist the agents with the the goal-reaching behavior. We also use a dedicated decomposition technique to reduce the branching factor of the tree search procedure.
  arXiv  Detail & Related papers  (2023-07-25T12:33:53Z)
• Conflict-Based Search for Explainable Multi-Agent Path Finding [7.734726150561088]
  In safety-critical applications, a human supervisor may want to verify that the plan is indeed collision-free. MAPF problem asks for a set of non-colliding paths that admits a short-enough explanation. Traditional MAPF algorithms are not equipped to directly handle explainable-MAPF. We adapt Conflict Based Search (CBS), a well-studied algorithm for MAPF, to handle explainable MAPF.
  arXiv  Detail & Related papers  (2022-02-20T23:13:14Z)
• Compilation-based Solvers for Multi-Agent Path Finding: a Survey, Discussion, and Future Opportunities [7.766921168069532]
  We show the lessons learned from past developments and current trends in the topic and discuss its wider impact. Two major approaches to optimal MAPF solving include (1) dedicated search-based methods, which solve MAPF directly, and (2) compilation-based methods that reduce a MAPF instance to an instance in a different well established formalism.
  arXiv  Detail & Related papers  (2021-04-23T20:13:12Z)
• Breaking the Curse of Many Agents: Provable Mean Embedding Q-Iteration for Mean-Field Reinforcement Learning [135.64775986546505]
  We exploit the symmetry of agents in multi-agent reinforcement learning (MARL) We propose MF-FQI algorithm that solves the mean-field MARL and establishes a non-asymptotic analysis for MF-FQI algorithm. We highlight that MF-FQI algorithm enjoys a "blessing of many agents" property in the sense that a larger number of observed agents improves the performance of MF-FQI algorithm.
  arXiv  Detail & Related papers  (2020-06-21T21:45:50Z)

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.