Multi-agent Path Finding in Continuous Environment

• URL: http://arxiv.org/abs/2409.10680v1
• Date: Mon, 16 Sep 2024 19:23:04 GMT
• Title: Multi-agent Path Finding in Continuous Environment
• Authors: Kristýna Janovská, Pavel Surynek,
• Abstract summary: A new Continuous Environment Conflict-Based Search (CE-CBS) algorithm is proposed in this work. CE-CBS combines conflict-based search (CBS) for the high-level search framework with RRT* for low-level path planning. Experimental results show that CE-CBS is competitive w.r.t. to other algorithms that consider continuous aspect in MAPF with continuous time.
• Score: 11.325849006178737
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We address a variant of multi-agent path finding in continuous environment (CE-MAPF), where agents move along sets of smooth curves. Collisions between agents are resolved via avoidance in the space domain. A new Continuous Environment Conflict-Based Search (CE-CBS) algorithm is proposed in this work. CE-CBS combines conflict-based search (CBS) for the high-level search framework with RRT* for low-level path planning. The CE-CBS algorithm is tested under various settings on diverse CE-MAPF instances. Experimental results show that CE-CBS is competitive w.r.t. to other algorithms that consider continuous aspect in MAPF such as MAPF with continuous time.

Related papers

• POGEMA: A Benchmark Platform for Cooperative Multi-Agent Navigation [76.67608003501479]
  We introduce and specify an evaluation protocol defining a range of domain-related metrics computed on the basics of the primary evaluation indicators. The results of such a comparison, which involves a variety of state-of-the-art MARL, search-based, and hybrid methods, are presented.
  arXiv  Detail & Related papers  (2024-07-20T16:37:21Z)
• Optimal and Bounded Suboptimal Any-Angle Multi-agent Pathfinding [13.296796764344169]
  We present the first optimal any-angle multi-agent pathfinding algorithm. Our planner is based on the Continuous Conflict-based Search (CCBS) algorithm and an optimal any-angle variant of the Safe Interval Path Planning (TO-AA-SIPP) We adapt two techniques from classical MAPF to the any-angle setting, namely Disjoint Splitting and Multi-Constraints.
  arXiv  Detail & Related papers  (2024-04-25T07:41:47Z)
• 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)
• An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [65.268245109828]
  We study the real-valued pure exploration problem in the multi-armed bandit (R-CPE-MAB) Existing methods in the R-CPE-MAB can be seen as a special case of the so-called transductive linear bandits. We propose an algorithm named the gap-based exploration (CombGapE) algorithm, whose sample complexity matches the lower bound.
  arXiv  Detail & Related papers  (2023-06-15T15:37:31Z)
• Continuous Monte Carlo Graph Search [61.11769232283621]
  Continuous Monte Carlo Graph Search ( CMCGS) is an extension of Monte Carlo Tree Search (MCTS) to online planning. CMCGS takes advantage of the insight that, during planning, sharing the same action policy between several states can yield high performance. It can be scaled up through parallelization, and it outperforms the Cross-Entropy Method (CEM) in continuous control with learned dynamics models.
  arXiv  Detail & Related papers  (2022-10-04T07:34:06Z)
• Analysis Of The Anytime MAPF Solvers Based On The Combination Of Conflict-Based Search (CBS) and Focal Search (FS) [2.320417845168326]
  Conflict-Based Search (CBS) is a widely used algorithm for solving multi-agent pathfinding problems optimally. To trade-off optimality for running time different variants of bounded sub-optimal CBS were designed. We show that Focal Search on both levels of CBS can be beneficial in a wide range of setups.
  arXiv  Detail & Related papers  (2022-09-20T11:05:14Z)
• POGEMA: Partially Observable Grid Environment for Multiple Agents [64.88759709443819]
  POGEMA is a sandbox for challenging partially observable multi-agent pathfinding (PO-MAPF) problems. It can be tailored to a variety of PO-MAPF, which can serve as an excellent testing ground for planning and learning methods.
  arXiv  Detail & Related papers  (2022-06-22T09:39:50Z)
• The Multi-Agent Pickup and Delivery Problem: MAPF, MARL and Its Warehouse Applications [2.969705152497174]
  We study two state-of-the-art solutions to the multi-agent pickup and delivery problem based on different principles. Specifically, a recent MAPF algorithm called conflict-based search (CBS) and a current MARL algorithm called shared experience actor-critic (SEAC) are studied.
  arXiv  Detail & Related papers  (2022-03-14T13:23:35Z)
• 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)
• Improving Continuous-time Conflict Based Search [19.36475688888736]
  Conflict-Based Search (CBS) is a powerful framework for optimally solving multi-agent path finding (MAPF) problems. Continuous-time CBS (CCBS) is a recently proposed version of CBS that guarantees optimal solutions without the need to discretize time. We show how to adapt successful CBS improvements, namely, prioritizing conflicts (PC), disjoint splitting (DS), and high-levelagents, to the continuous time setting of CCBS.
  arXiv  Detail & Related papers  (2021-01-24T14:34:25Z)
• Semi-Supervised Learning with Variational Bayesian Inference and Maximum Uncertainty Regularization [62.21716612888669]
  We propose two generic methods for improving semi-supervised learning (SSL) The first integrates weight perturbation (WP) into existing "consistency regularization" (CR) based methods. The second method proposes a novel consistency loss called "maximum uncertainty regularization" (MUR)
  arXiv  Detail & Related papers  (2020-12-03T09:49:35Z)

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.