Solving Multi-Agent Target Assignment and Path Finding with a Single Constraint Tree

• URL: http://arxiv.org/abs/2307.00663v2
• Date: Mon, 23 Oct 2023 06:24:38 GMT
• Title: Solving Multi-Agent Target Assignment and Path Finding with a Single Constraint Tree
• Authors: Yimin Tang, Zhongqiang Ren, Jiaoyang Li, Katia Sycara
• Abstract summary: 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.
• Score: 9.518757918128799
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Combined Target-Assignment and Path-Finding problem (TAPF) requires simultaneously assigning targets to agents and planning collision-free paths for agents from their start locations to their assigned targets. As a leading approach to address TAPF, Conflict-Based Search with Target Assignment (CBS-TA) leverages both K-best target assignments to create multiple search trees and Conflict-Based Search (CBS) to resolve collisions in each search tree. While being able to find an optimal solution, CBS-TA suffers from scalability due to the duplicated collision resolution in multiple trees and the expensive computation of K-best assignments. We therefore develop Incremental Target Assignment CBS (ITA-CBS) to bypass these two computational bottlenecks. ITA-CBS generates only a single search tree and avoids computing K-best assignments by incrementally computing new 1-best assignments during the search. We show that, in theory, ITA-CBS is guaranteed to find an optimal solution and, in practice, is computationally efficient.

Related papers

• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  We introduce a novel greedy-style subset selection algorithm for batch acquisition. Our experiments on the red fluorescent proteins show that our proposed method achieves the baseline performance in 1.69x fewer queries.
  arXiv  Detail & Related papers  (2024-06-21T05:57:08Z)
• ITA-ECBS: A Bounded-Suboptimal Algorithm for the Combined Target-Assignment and Path-Finding Problem [20.090818762687565]
  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.
  arXiv  Detail & Related papers  (2024-04-08T06:36:42Z)
• Optimal Task Assignment and Path Planning using Conflict-Based Search with Precedence and Temporal Constraints [5.265273282482319]
  This paper examines the Task Assignment and Path Finding with Precedence and Temporal Constraints (TAPF-PTC) problem. We augment Conflict-Based Search (CBS) to simultaneously generate task assignments and collision-free paths that adhere to precedence and temporal constraints. Experimentally, we demonstrate that our algorithm, CBS-TA-PTC, can solve highly challenging bomb-defusing tasks with precedence and temporal constraints efficiently.
  arXiv  Detail & Related papers  (2024-02-13T20:07:58Z)
• 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)
• TreeDQN: Learning to minimize Branch-and-Bound tree [78.52895577861327]
  Branch-and-Bound is a convenient approach to solving optimization tasks in the form of Mixed Linear Programs. The efficiency of the solver depends on the branchning used to select a variable for splitting. We propose a reinforcement learning method that can efficiently learn the branching.
  arXiv  Detail & Related papers  (2023-06-09T14:01:26Z)
• Optimal Multi-Agent Path Finding for Precedence Constrained Planning Tasks [0.7742297876120561]
  We consider an extension to this problem, Precedence Constrained Multi-Agent Path Finding (PC-MAPF) We propose a novel algorithm, Precedence Constrained Conflict Based Search (PC-CBS), which finds makespan-optimal solutions for this class of problems. We benchmark the performance of this algorithm over various warehouse assembly, and multi-agent pickup and delivery tasks, and use it to evaluate the sub-optimality of a recently proposed efficient baseline.
  arXiv  Detail & Related papers  (2022-02-08T07:26:45Z)
• Combined Depth Space based Architecture Search For Person Re-identification [70.86236888223569]
  We aim to design a lightweight and suitable network for person re-identification (ReID) We propose a novel search space called Combined Depth Space (CDS), based on which we search for an efficient network architecture, which we call CDNet. We then propose a low-cost search strategy named the Top-k Sample Search strategy to make full use of the search space and avoid trapping in local optimal result.
  arXiv  Detail & Related papers  (2021-04-09T02:40:01Z)
• Decoupled and Memory-Reinforced Networks: Towards Effective Feature Learning for One-Step Person Search [65.51181219410763]
  One-step methods have been developed to handle pedestrian detection and identification sub-tasks using a single network. There are two major challenges in the current one-step approaches. We propose a decoupled and memory-reinforced network (DMRNet) to overcome these problems.
  arXiv  Detail & Related papers  (2021-02-22T06:19:45Z)
• Multi-objective Conflict-based Search for Multi-agent Path Finding [10.354181009277623]
  Multi-objective path planners typically compute an ensemble of paths while optimizing a single objective, such as path length. This article presents an approach named Multi-objective Conflict-based Search (MO-CBS) that bypasses this so-called curse of dimensionality.
  arXiv  Detail & Related papers  (2021-01-11T10:42:38Z)
• Learning Optimal Tree Models Under Beam Search [27.92120639502327]
  Existing tree models suffer from the training-testing discrepancy. We develop the concept of Bayes optimality under beam search and calibration under beam search. We propose a novel algorithm for learning optimal tree models under beam search.
  arXiv  Detail & Related papers  (2020-06-27T17:20: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.