Cost Splitting for Multi-Objective Conflict-Based Search

• URL: http://arxiv.org/abs/2211.12885v1
• Date: Wed, 23 Nov 2022 11:44:20 GMT
• Title: Cost Splitting for Multi-Objective Conflict-Based Search
• Authors: Cheng Ge, Han Zhang, Jiaoyang Li, Sven Koenig
• Abstract summary: We focus on the Multi-Objective Conflict-Based Search (MO-CBS) algorithm, a state-of-the-art MO-MAPF algorithm. We show that the standard splitting strategy used by MO-CBS can lead to duplicate search nodes and hence can duplicate the search effort that MO-CBS needs to make. We propose two new splitting strategies for MO-CBS, namely cost splitting and disjoint cost splitting.
• Score: 27.757328432175157
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Multi-Objective Multi-Agent Path Finding (MO-MAPF) problem is the problem of finding the Pareto-optimal frontier of collision-free paths for a team of agents while minimizing multiple cost metrics. Examples of such cost metrics include arrival times, travel distances, and energy consumption.In this paper, we focus on the Multi-Objective Conflict-Based Search (MO-CBS) algorithm, a state-of-the-art MO-MAPF algorithm. We show that the standard splitting strategy used by MO-CBS can lead to duplicate search nodes and hence can duplicate the search effort that MO-CBS needs to make. To address this issue, we propose two new splitting strategies for MO-CBS, namely cost splitting and disjoint cost splitting. Our theoretical results show that, when combined with either of these two new splitting strategies, MO-CBS maintains its completeness and optimality guarantees. Our experimental results show that disjoint cost splitting, our best splitting strategy, speeds up MO-CBS by up to two orders of magnitude and substantially improves its success rates in various settings.

Related papers

• MGCBS: An Optimal and Efficient Algorithm for Solving Multi-Goal Multi-Agent Path Finding Problem [5.580214316179672]
  The MG-MAPF problem requires each agent to visit pre-assigned multiple goal points at least once without conflict. We propose the Multi-Goal Conflict-Based Search (MGCBS), which is based on Decoupling the goal Safe interval visiting order search and the Single-agent pathfinding. Our method can consistently obtain optimal results and execute up to 7 times faster than the state-of-the-art method in our evaluation.
  arXiv  Detail & Related papers  (2024-04-30T12:49:54Z)
• Once for Both: Single Stage of Importance and Sparsity Search for Vision Transformer Compression [63.23578860867408]
  We investigate how to integrate the evaluations of importance and sparsity scores into a single stage. We present OFB, a cost-efficient approach that simultaneously evaluates both importance and sparsity scores. Experiments demonstrate that OFB can achieve superior compression performance over state-of-the-art searching-based and pruning-based methods.
  arXiv  Detail & Related papers  (2024-03-23T13:22:36Z)
• Learning to Rematch Mismatched Pairs for Robust Cross-Modal Retrieval [49.07523607316323]
  In real-world scenarios, massive multimodal data are harvested from the Internet, which inevitably contains Partially Mismatched Pairs (PMPs) Previous efforts tend to mitigate this problem by estimating a soft correspondence to down-weight the contribution of PMPs. We propose L2RM, a general framework based on Optimal Transport (OT) that learns to rematch mismatched pairs.
  arXiv  Detail & Related papers  (2024-03-08T07:09:30Z)
• 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)
• Hybrid Relation Guided Set Matching for Few-shot Action Recognition [51.3308583226322]
  We propose a novel Hybrid Relation guided Set Matching (HyRSM) approach that incorporates two key components. The purpose of the hybrid relation module is to learn task-specific embeddings by fully exploiting associated relations within and cross videos in an episode. We evaluate HyRSM on six challenging benchmarks, and the experimental results show its superiority over the state-of-the-art methods by a convincing margin.
  arXiv  Detail & Related papers  (2022-04-28T11:43:41Z)
• Estimation of Reliable Proposal Quality for Temporal Action Detection [71.5989469643732]
  We propose a new method that gives insights into moment and region perspectives simultaneously to align the two tasks by acquiring reliable proposal quality. For the moment perspective, Boundary Evaluate Module (BEM) is designed which focuses on local appearance and motion evolvement to estimate boundary quality. For the region perspective, we introduce Region Evaluate Module (REM) which uses a new and efficient sampling method for proposal feature representation.
  arXiv  Detail & Related papers  (2022-04-25T14:33:49Z)
• 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)
• 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)
• 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)
• MuCAN: Multi-Correspondence Aggregation Network for Video Super-Resolution [63.02785017714131]
  Video super-resolution (VSR) aims to utilize multiple low-resolution frames to generate a high-resolution prediction for each frame. Inter- and intra-frames are the key sources for exploiting temporal and spatial information. We build an effective multi-correspondence aggregation network (MuCAN) for VSR.
  arXiv  Detail & Related papers  (2020-07-23T05:41:27Z)

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.