論文の概要: Effective Integration of Weighted Cost-to-go and Conflict Heuristic within Suboptimal CBS
- arxiv url: http://arxiv.org/abs/2205.11624v5
- Date: Sun, 24 Mar 2024 20:03:38 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-28 02:09:26.899990
- Title: Effective Integration of Weighted Cost-to-go and Conflict Heuristic within Suboptimal CBS
- Title（参考訳）: CBSにおける重み付きコスト・ツー・ゴーと競合ヒューリスティックの有効統合
- Authors: Rishi Veerapaneni, Tushar Kusnur, Maxim Likhachev,
- Abstract要約: Conflict-Based Search (CBS)は、低レベルのシングルエージェントプランナーと高レベルの制約ツリーを用いて競合を解決する、人気のあるマルチエージェントパス探索(MAPF)である。
CBSの主張とは対照的に、重み付けされたコスト・ツー・ゴーは紛争と共に効果的に利用できることが示されている。
- 参考スコア（独自算出の注目度）: 21.394413249216395
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Conflict-Based Search (CBS) is a popular multi-agent path finding (MAPF) solver that employs a low-level single agent planner and a high-level constraint tree to resolve conflicts. The vast majority of modern MAPF solvers focus on improving CBS by reducing the size of this tree through various strategies with few methods modifying the low level planner. Typically low level planners in existing CBS methods use an unweighted cost-to-go heuristic, with suboptimal CBS methods also using a conflict heuristic to help the high level search. In this paper, we show that, contrary to prevailing CBS beliefs, a weighted cost-to-go heuristic can be used effectively alongside the conflict heuristic in two possible variants. In particular, one of these variants can obtain large speedups, 2-100x, across several scenarios and suboptimal CBS methods. Importantly, we discover that performance is related not to the weighted cost-to-go heuristic but rather to the relative conflict heuristic weight's ability to effectively balance low-level and high-level work. Additionally, to the best of our knowledge, we show the first theoretical relation of prioritized planning and bounded suboptimal CBS and demonstrate that our methods are their natural generalization. Update March 2024: We found that the relative speedup decreases to around 1.2-10x depending on how the conflict heuristic is computed (see appendix for more details).
- Abstract（参考訳）: Conflict-Based Search (CBS) は、低レベルのシングルエージェントプランナーと高レベルの制約ツリーを用いて競合を解決する、人気のあるマルチエージェントパス探索(MAPF)解決器である。
現代のMAPF解決者の大多数は、低レベルプランナーを変更する手法がほとんどない様々な戦略により、この木のサイズを減らし、CBSを改善することに重点を置いている。
既存のCBS方式の低レベルプランナーは、非重み付けのコスト・ツー・ゴー・ヒューリスティック(英語版)を用いており、CBS方式は競合ヒューリスティック(英語版)を用いてハイレベル検索を支援する。
本稿では,CBSの信条とは対照的に,重み付けされたコスト・ツー・ゴーヒューリスティックは,2つの可能な変種における競合ヒューリスティックと併用して効果的に利用できることを示す。
特に、これらの変種のうちの1つは、いくつかのシナリオと準最適CBS手法で、大きなスピードアップ、2-100xを得ることができる。
重要なのは、性能が重み付けされたコスト・ツー・ゴ・ゴ・ヒューリスティックではなく、低レベルの作業と高レベルの作業とを効果的にバランスさせる相対的な競合ヒューリスティック・ウェイト(英語版)の能力に関連していることである。
さらに,我々の知識を最大限に活用するために,優先計画と有界準最適CBSの理論的関係を初めて示し,本手法がそれらの自然な一般化であることを実証する。
アップデート2024年3月:コンフリクトヒューリスティックの計算方法によって、相対的なスピードアップが1.2-10倍程度に低下することを発見した(詳細は付録を参照)。
関連論文リスト
- Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。
GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。
我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
論文 参考訳（メタデータ） (2024-06-05T22:52:27Z) - Optimising Calls to Large Language Models with Uncertainty-Based Two-Tier Selection [80.63946798650653]
決定は、より優れた性能を持つ大型LCMを使うか、より少ないコストで使用するかに重点を置いている。
我々は,LLMの世代間不確実性のみを意思決定基準として,より単純な解を提案する。
実験の結果、この単純な解はコストと性能を最適にバランスさせ、27の試験装置中25の既存手法よりも優れていることがわかった。
論文 参考訳（メタデータ） (2024-05-03T14:38:59Z) - Estimating Barycenters of Distributions with Neural Optimal Transport [93.28746685008093]
本稿では,Wasserstein Barycenter問題を解くための新しいスケーラブルなアプローチを提案する。
我々の手法は最近のNeural OTソルバをベースとしている。
また,提案手法の理論的誤差境界も確立する。
論文 参考訳（メタデータ） (2024-02-06T09:17:07Z) - Model-based Causal Bayesian Optimization [74.78486244786083]
乗算重み付き因果ベイズ最適化のための最初のアルゴリズム(CBO-MW)を提案する。
グラフ関連の量に自然に依存するCBO-MWに対する後悔の限界を導出する。
我々の実験は、共有モビリティシステムにおいて、ユーザの需要パターンを学習するためにCBO-MWをどのように使用できるかの現実的なデモを含む。
論文 参考訳（メタデータ） (2023-07-31T13:02:36Z) - Efficient Diffusion Training via Min-SNR Weighting Strategy [78.5801305960993]
拡散学習をマルチタスク学習問題として扱い,Min-SNR-$gamma$と呼ばれるシンプルなアプローチを導入する。
本結果は,従来の重み付け手法よりも3.4$times$高速で収束速度が大幅に向上したことを示す。
さらに効果的で、ImageNetの256times256$ベンチマークで2.06の新たなFIDスコアを達成した。
論文 参考訳（メタデータ） (2023-03-16T17:59:56Z) - TransPath: Learning Heuristics For Grid-Based Pathfinding via
Transformers [64.88759709443819]
探索の効率を顕著に向上させると考えられる,インスタンス依存のプロキシを学習することを提案する。
私たちが最初に学ぶことを提案するプロキシは、補正係数、すなわち、インスタンスに依存しないコスト・ツー・ゴの見積もりと完璧な見積もりの比率である。
第2のプロキシはパス確率であり、グリッドセルが最も短いパスに横たわっている可能性を示している。
論文 参考訳（メタデータ） (2022-12-22T14:26:11Z) - Cost Splitting for Multi-Objective Conflict-Based Search [27.757328432175157]
我々は,最新のMO-MAPFアルゴリズムであるMO-CBS (Multi-Objective Conflict-Based Search) アルゴリズムに注目した。
提案手法では,MO-CBS が使用する標準分割戦略が検索ノードの重複につながる可能性があり,MO-CBS が行わなければならない探索作業を重複させる可能性があることを示す。
そこで本研究では,MO-CBSの新たな分割戦略として,コスト分割とコスト分割の2つを提案する。
論文 参考訳（メタデータ） (2022-11-23T11:44:20Z) - Analysis Of The Anytime MAPF Solvers Based On The Combination Of
Conflict-Based Search (CBS) and Focal Search (FS) [2.320417845168326]
競合ベースの探索 (CBS) は多エージェントパスフィンディング問題を最適に解くために広く用いられているアルゴリズムである。
CBSのバウンテッド・サブ最適の異なる変種を走らせるためのトレードオフ最適性を設計した。
CBSの双方のレベルのFocal Searchは、幅広いセットアップにおいて有益であることを示す。
論文 参考訳（メタデータ） (2022-09-20T11:05:14Z) - Improving Continuous-time Conflict Based Search [19.36475688888736]
Conflict-Based Search (CBS) はマルチエージェントパス探索 (MAPF) 問題を最適に解くための強力なフレームワークである。
Continuous-time CBS(CCBS)は、CBSの最近提案されたバージョンで、時間を差別することなく最適なソリューションを保証します。
コンフリクト(PC)、ディジョイン分割(DS)、ハイレベルエージェントをCCBSの連続時間設定に優先順位付けすることで、CBSの改善を成功させる方法を紹介します。
論文 参考訳（メタデータ） (2021-01-24T14:34:25Z) - 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) - Multi Agent Path Finding with Awareness for Spatially Extended Agents [0.5156484100374058]
経路発見問題は、共通の道路ネットワーク上のエージェントの衝突のない移動計画を特定することを含む。
本稿では,走行する道路の長さに匹敵する大きさの空間拡張剤について検討する。
eXtended Conflict Based Search (XCBS)アルゴリズムにおいて,空間拡張エージェントに対する最適マルチエージェントパス探索手法を提案した。
論文 参考訳（メタデータ） (2020-09-20T05:40:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。