論文の概要: Cost Splitting for Multi-Objective Conflict-Based Search
- arxiv url: http://arxiv.org/abs/2211.12885v1
- Date: Wed, 23 Nov 2022 11:44:20 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-24 16:18:35.169781
- Title: Cost Splitting for Multi-Objective Conflict-Based Search
- Title（参考訳）: 多目的衝突探索のためのコスト分割
- Authors: Cheng Ge, Han Zhang, Jiaoyang Li, Sven Koenig
- Abstract要約: 我々は,最新のMO-MAPFアルゴリズムであるMO-CBS (Multi-Objective Conflict-Based Search) アルゴリズムに注目した。
提案手法では,MO-CBS が使用する標準分割戦略が検索ノードの重複につながる可能性があり,MO-CBS が行わなければならない探索作業を重複させる可能性があることを示す。
そこで本研究では,MO-CBSの新たな分割戦略として,コスト分割とコスト分割の2つを提案する。
- 参考スコア（独自算出の注目度）: 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.
- Abstract（参考訳）: 多目的多目的経路探索(MO-MAPF)問題は、複数のコストメトリクスを最小化しながら、エージェントチームにとって衝突のない経路のパレート最適フロンティアを見つける問題である。
このようなコストメトリクスの例としては、到着時間、移動距離、エネルギー消費量などがある。本論文では、最先端のmo-mapfアルゴリズムである多目的コンフリクトベース探索(mo-cbs)アルゴリズムに焦点を当てる。
提案手法では,MO-CBSが使用する標準分割戦略が検索ノードの重複を招き,MO-CBSが行わなければならない探索作業を重複させる可能性があることを示す。
そこで本研究では,mo-cbのコスト分割とコスト分割という2つの新しい分割戦略を提案する。
この2つの新たな分割戦略を組み合わせれば,MO-CBSは完全性と最適性を保証する。
実験結果から,MO-CBSを最大2桁の速度で高速化し,様々な環境での成功率を大幅に向上させることが示唆された。
関連論文リスト
- MGCBS: An Optimal and Efficient Algorithm for Solving Multi-Goal Multi-Agent Path Finding Problem [5.580214316179672]
MG-MAPF問題は、各エージェントが少なくとも1回は衝突することなく、予め割り当てられた複数のゴールポイントを訪問する必要がある。
そこで本研究では,単一エージェントパスフィンディング(Single-Adnt pathfinding)とセーフ区間探索(Single-Adnt pathfinding)の分離に基づくMulti-Goal Conflict-Based Search (MGCBS)を提案する。
提案手法は, 常に最適な結果を得ることができ, 評価において最先端の手法よりも最大7倍高速に実行することができる。
論文 参考訳（メタデータ） (2024-04-30T12:49:54Z) - Once for Both: Single Stage of Importance and Sparsity Search for Vision Transformer Compression [63.23578860867408]
重要度評価と疎度評価を1段階にまとめる方法について検討する。
重要度と疎度の両方を同時に評価するコスト効率の高いOFBを提案する。
実験により、OFBは最先端のサーチベースおよびプルーニングベース手法よりも優れた圧縮性能が得られることが示された。
論文 参考訳（メタデータ） (2024-03-23T13:22:36Z) - Learning to Rematch Mismatched Pairs for Robust Cross-Modal Retrieval [49.07523607316323]
実世界のシナリオでは、大規模なマルチモーダルデータは、必然的にPMP(Partially Mismatched Pairs)を含むインターネットから収集される。
従来の取り組みでは、PMPの貢献度を下げるためのソフトな対応を推定することで、この問題を軽減する傾向があった。
我々は、ミスマッチペアの再マッチを学習する最適輸送(OT)に基づく一般的なフレームワークであるL2RMを提案する。
論文 参考訳（メタデータ） (2024-03-08T07:09:30Z) - Effective Integration of Weighted Cost-to-go and Conflict Heuristic within Suboptimal CBS [21.394413249216395]
Conflict-Based Search (CBS)は、低レベルのシングルエージェントプランナーと高レベルの制約ツリーを用いて競合を解決する、人気のあるマルチエージェントパス探索(MAPF)である。
CBSの主張とは対照的に、重み付けされたコスト・ツー・ゴーは紛争と共に効果的に利用できることが示されている。
論文 参考訳（メタデータ） (2022-05-23T20:49:40Z) - Hybrid Relation Guided Set Matching for Few-shot Action Recognition [51.3308583226322]
本稿では,2つの鍵成分を組み込んだHybrid Relation Guided Set Matching (HyRSM) 手法を提案する。
ハイブリッドリレーションモジュールの目的は、エピソード内の関連関係とクロスビデオの完全活用により、タスク固有の埋め込みを学習することである。
我々は,HyRSMを6つの挑戦的ベンチマークで評価した。
論文 参考訳（メタデータ） (2022-04-28T11:43:41Z) - Estimation of Reliable Proposal Quality for Temporal Action Detection [71.5989469643732]
提案手法では,時間的視点と地域的視点を同時に把握し,信頼性の高い提案品質を取得することによって2つの課題を整合させる手法を提案する。
バウンダリ評価モジュール (BEM) は, 境界品質を推定するために, 局所的な外観と動きの進化に焦点を当てた設計である。
地域の観点からは,提案する特徴表現に対して,新しい効率的なサンプリング手法を用いた領域評価モジュール(REM)を導入する。
論文 参考訳（メタデータ） (2022-04-25T14:33:49Z) - Multi-objective Conflict-based Search Using Safe-interval Path Planning [10.354181009277623]
低レベル探索のための新しい多目的セーフインターバルパス計画法 (MO-SIPP) アルゴリズムを利用するMO-CBS(Multi-objective conflict-based search)を提案する。
我々は, 平均低レベル探索時間において, 等級が大幅に改善されていることを示すために, 広範囲な数値計算結果を示す。
また,建設現場計画における提案アルゴリズムの適用可能性を示すケーススタディも提示する。
論文 参考訳（メタデータ） (2021-08-02T09:42:08Z) - Decoupled and Memory-Reinforced Networks: Towards Effective Feature
Learning for One-Step Person Search [65.51181219410763]
歩行者検出と識別サブタスクを1つのネットワークで処理するワンステップ方式を開発しました。
現在のワンステップアプローチには2つの大きな課題があります。
本稿では,これらの問題を解決するために,分離メモリ強化ネットワーク(DMRNet)を提案する。
論文 参考訳（メタデータ） (2021-02-22T06:19:45Z) - Multi-objective Conflict-based Search for Multi-agent Path Finding [10.354181009277623]
マルチオブジェクトパスプランナーは通常、パスの長さなどの単一の目的を最適化しながら、パスのアンサンブルを計算します。
本稿では、マルチオブジェクトコンフリクトベース検索(MO-CBS)という、いわゆる次元の呪いをバイパスする手法を紹介します。
論文 参考訳（メタデータ） (2021-01-11T10:42:38Z) - EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding [40.0986954496361]
明示的推定CBS(英: Explicit Estimation CBS、英: Explicit Estimation CBS)は、オンライン学習を用いて、各ハイレベルノードのソリューションのコストの不可避な推定値を得る、制限付き最適化型CBSである。
EECBSは、さまざまなMAPFインスタンス上で、最先端の有界MAPFアルゴリズムであるECBS、BCP-7、eMDD-SATよりもはるかに高速に動作する。
論文 参考訳（メタデータ） (2020-10-03T14:19:00Z) - MuCAN: Multi-Correspondence Aggregation Network for Video
Super-Resolution [63.02785017714131]
ビデオ超解像(VSR)は、複数の低解像度フレームを使用して、各フレームに対して高解像度の予測を生成することを目的としている。
フレーム間およびフレーム内は、時間的および空間的情報を利用するための鍵となるソースである。
VSRのための効果的なマルチ対応アグリゲーションネットワーク(MuCAN)を構築した。
論文 参考訳（メタデータ） (2020-07-23T05:41:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。