EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding

• URL: http://arxiv.org/abs/2010.01367v2
• Date: Fri, 12 Mar 2021 19:00:29 GMT
• Title: EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding
• Authors: Jiaoyang Li, Wheeler Ruml, Sven Koenig
• Abstract summary: 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.
• Score: 40.0986954496361
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-Agent Path Finding (MAPF), i.e., finding collision-free paths for multiple robots, is important for many applications where small runtimes are necessary, including the kind of automated warehouses operated by Amazon. CBS is a leading two-level search algorithm for solving MAPF optimally. ECBS is a bounded-suboptimal variant of CBS that uses focal search to speed up CBS by sacrificing optimality and instead guaranteeing that the costs of its solutions are within a given factor of optimal. In this paper, we study how to decrease its runtime even further using inadmissible heuristics. Motivated by Explicit Estimation Search (EES), we propose Explicit Estimation CBS (EECBS), a new bounded-suboptimal variant of CBS, that uses online learning to obtain inadmissible estimates of the cost of the solution of each high-level node and uses EES to choose which high-level node to expand next. We also investigate recent improvements of CBS and adapt them to EECBS. We find that EECBS with the improvements 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. We hope that the scalability of EECBS enables additional applications for bounded-suboptimal MAPF algorithms.

Related papers

• 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)
• 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)
• Learning Regions of Interest for Bayesian Optimization with Adaptive Level-Set Estimation [84.0621253654014]
  We propose a framework, called BALLET, which adaptively filters for a high-confidence region of interest. We show theoretically that BALLET can efficiently shrink the search space, and can exhibit a tighter regret bound than standard BO.
  arXiv  Detail & Related papers  (2023-07-25T09:45:47Z)
• 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)
• 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)
• Effective Integration of Weighted Cost-to-go and Conflict Heuristic within Suboptimal CBS [21.394413249216395]
  Conflict-Based Search (CBS) is a popular multi-agent path finding (MAPF) that employs a low-level single agent planner and a high-level constraint tree to resolve conflicts. We show that, contrary to prevailing CBS beliefs, a weighted cost-to-go can be used effectively alongside the conflict.
  arXiv  Detail & Related papers  (2022-05-23T20:49:40Z)
• $\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)
• Rethinking Performance Estimation in Neural Architecture Search [191.08960589460173]
  We provide a novel yet systematic rethinking of performance estimation (PE) in a resource constrained regime. By combining BPE with various search algorithms including reinforcement learning, evolution algorithm, random search, and differentiable architecture search, we achieve 1, 000x of NAS speed up with a negligible performance drop.
  arXiv  Detail & Related papers  (2020-05-20T09:01:44Z)
• Rethinking Differentiable Search for Mixed-Precision Neural Networks [83.55785779504868]
  Low-precision networks with weights and activations quantized to low bit-width are widely used to accelerate inference on edge devices. Current solutions are uniform, using identical bit-width for all filters. This fails to account for the different sensitivities of different filters and is suboptimal. Mixed-precision networks address this problem, by tuning the bit-width to individual filter requirements.
  arXiv  Detail & Related papers  (2020-04-13T07:02:23Z)

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.