ITA-ECBS: A Bounded-Suboptimal Algorithm for the Combined Target-Assignment and Path-Finding Problem

• URL: http://arxiv.org/abs/2404.05223v2
• Date: Sun, 21 Apr 2024 09:55:23 GMT
• Title: ITA-ECBS: A Bounded-Suboptimal Algorithm for the Combined Target-Assignment and Path-Finding Problem
• Authors: Yimin Tang, Sven Koenig, Jiaoyang Li,
• Abstract summary: We introduce ITA-ECBS, the first bounded-suboptimal variant of ITA-CBS. We show that it runs faster than ECBS-TA in 87.42% of 54,033 test cases.
• Score: 20.090818762687565
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Multi-Agent Path Finding (MAPF), i.e., finding collision-free paths for multiple robots, plays a critical role in many applications. Sometimes, assigning a target to each agent also presents a challenge. The Combined Target-Assignment and Path-Finding (TAPF) problem, a variant of MAPF, requires one to simultaneously assign targets to agents and plan collision-free paths for agents. Several algorithms, including CBM, CBS-TA, and ITA-CBS, optimally solve the TAPF problem, with ITA-CBS being the leading algorithm for minimizing flowtime. However, the only existing bounded-suboptimal algorithm ECBS-TA is derived from CBS-TA rather than ITA-CBS. So, it faces the same issues as CBS-TA, such as searching through multiple constraint trees and spending too much time on finding the next-best target assignment. We introduce ITA-ECBS, the first bounded-suboptimal variant of ITA-CBS. Transforming ITA-CBS to its bounded-suboptimal variant is challenging because different constraint tree nodes can have different assignments of targets to agents. ITA-ECBS uses focal search to achieve efficiency and determines target assignments based on a new lower bound matrix. We show that it runs faster than ECBS-TA in 87.42% of 54,033 test cases.

Related papers

• 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)
• 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)
• Solving Multi-Agent Target Assignment and Path Finding with a Single Constraint Tree [9.518757918128799]
  Combined Target-Assignment and Path-Finding problem (TAPF) requires simultaneously assigning targets to agents. Conflict-Based Search with Target Assignment (CBS-TA) is a leading approach to address TAPF. We show that, in theory, ITA-CBS is guaranteed to find an optimal solution and, in practice, is computationally efficient.
  arXiv  Detail & Related papers  (2023-07-02T20:52:16Z)
• Patch-aware Batch Normalization for Improving Cross-domain Robustness [55.06956781674986]
  Cross-domain tasks present a challenge in which the model's performance will degrade when the training set and the test set follow different distributions. We propose a novel method called patch-aware batch normalization (PBN) By exploiting the differences between local patches of an image, our proposed PBN can effectively enhance the robustness of the model's parameters.
  arXiv  Detail & Related papers  (2023-04-06T03:25:42Z)
• 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)
• $\beta$-DARTS: Beta-Decay Regularization for Differentiable Architecture Search [85.84110365657455]
  We propose a simple-but-efficient regularization method, termed as Beta-Decay, to regularize the DARTS-based NAS searching process. Experimental results on NAS-Bench-201 show that our proposed method can help to stabilize the searching process and makes the searched network more transferable across different datasets.
  arXiv  Detail & Related papers  (2022-03-03T11:47:14Z)
• 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)
• EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding [40.0986954496361]
  Explicit Estimation CBS (EECBS) is a bounded-suboptimal variant of CBS that uses online learning to obtain inadmissible estimates of the cost of the solution of each high-level node. EECBS runs significantly faster than the state-of-the-art bounded-suboptimal MAPF algorithms ECBS, BCP-7, and eMDD-SAT on a variety of MAPF instances.
  arXiv  Detail & Related papers  (2020-10-03T14:19:00Z)
• Multi Agent Path Finding with Awareness for Spatially Extended Agents [0.5156484100374058]
  Path finding problems involve identification of a plan for conflict free movement of agents over a common road network. In this paper, we consider spatially extended agents which have a size comparable to the length of the road on which they travel. An optimal multi agent path finding approach for spatially-extended agents was proposed in the eXtended Conflict Based Search (XCBS) algorithm.
  arXiv  Detail & Related papers  (2020-09-20T05:40:04Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  We present a multi-robot allocation algorithm that decouples the key computational challenges of sequential decision-making under uncertainty and multi-agent coordination. We validate our results over a wide range of simulations on two distinct domains: multi-arm conveyor belt pick-and-place and multi-drone delivery dispatch in a city.
  arXiv  Detail & Related papers  (2020-05-27T01:10:41Z)

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.