Analysis Of The Anytime MAPF Solvers Based On The Combination Of Conflict-Based Search (CBS) and Focal Search (FS)

• URL: http://arxiv.org/abs/2209.09612v1
• Date: Tue, 20 Sep 2022 11:05:14 GMT
• Title: Analysis Of The Anytime MAPF Solvers Based On The Combination Of Conflict-Based Search (CBS) and Focal Search (FS)
• Authors: Ilya Ivanashev, Anton Andreychuk, Konstantin Yakovlev
• Abstract summary: 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.
• Score: 2.320417845168326
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Conflict-Based Search (CBS) is a widely used algorithm for solving multi-agent pathfinding (MAPF) problems optimally. The core idea of CBS is to run hierarchical search, when, on the high level the tree of solutions candidates is explored, and on the low-level an individual planning for a specific agent (subject to certain constraints) is carried out. To trade-off optimality for running time different variants of bounded sub-optimal CBS were designed, which alter both high- and low-level search routines of CBS. Moreover, anytime variant of CBS does exist that applies Focal Search (FS) to the high-level of CBS - Anytime BCBS. However, no comprehensive analysis of how well this algorithm performs compared to the naive one, when we simply re-invoke CBS with the decreased sub-optimality bound, was present. This work aims at filling this gap. Moreover, we present and evaluate another anytime version of CBS that uses FS on both levels of CBS. Empirically, we show that its behavior is principally different from the one demonstrated by Anytime BCBS. Finally, we compare both algorithms head-to-head and show that using Focal Search on both levels of CBS can be beneficial in a wide range of setups.

Related papers

• Not All Pairs are Equal: Hierarchical Learning for Average-Precision-Oriented Video Retrieval [80.09819072780193]
  Average Precision (AP) assesses the overall rankings of relevant videos at the top list. Recent video retrieval methods utilize pair-wise losses that treat all sample pairs equally.
  arXiv  Detail & Related papers  (2024-07-22T11:52:04Z)
• 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)
• 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)
• Revisiting Random Channel Pruning for Neural Network Compression [159.99002793644163]
  Channel (or 3D filter) pruning serves as an effective way to accelerate the inference of neural networks. In this paper, we try to determine the channel configuration of the pruned models by random search. We show that this simple strategy works quite well compared with other channel pruning methods.
  arXiv  Detail & Related papers  (2022-05-11T17:59:04Z)
• Local Stochastic Bilevel Optimization with Momentum-Based Variance Reduction [104.41634756395545]
  We study Federated Bilevel Optimization problems. Specifically, we first propose the FedBiO, a deterministic gradient-based algorithm. We show FedBiO has complexity of $O(epsilon-1.5)$. Our algorithms show superior performances compared to other baselines in numerical experiments.
  arXiv  Detail & Related papers  (2022-05-03T16:40:22Z)
• $\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)
• Channel Pruning via Automatic Structure Search [109.83642249625098]
  We propose a new channel pruning method based on artificial bee colony algorithm (ABC), dubbed as ABCPruner. ABCPruner has been demonstrated to be more effective, which also enables the fine-tuning to be conducted efficiently in an end-to-end manner.
  arXiv  Detail & Related papers  (2020-01-23T14:51:19Z)

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.