論文の概要: Effectively Incorporating Weighted Cost-to-go Heuristic in Suboptimal CBS

• arxiv url: http://arxiv.org/abs/2205.11624v1
• Date: Mon, 23 May 2022 20:49:40 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-29 07:45:25.490213
• Title: Effectively Incorporating Weighted Cost-to-go Heuristic in Suboptimal CBS
• Title（参考訳）: CBSにおける重み付きコスト・ツー・ゴーヒューリスティックの効果的導入
• Authors: Rishi Veerapaneni, Tushar Kusnar, Maxim Likhachev
• Abstract要約: Conflict-Based Search (CBS)は、低レベルのシングルエージェントプランナーと高レベルの制約ツリーを用いて競合を解決する、人気のあるマルチエージェントパス探索(MAPF)である。 コスト・ツー・ゴ・ゴ・ソルバは、競合と並行して特定の方法で重み付けすることで、より効果的に利用できることが示される。
• 参考スコア（独自算出の注目度）: 15.069824783343183
• 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. All 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. Contrary to prevailing beliefs, we show that the cost-to-go heuristic can be used significantly more effectively by weighting it in a specific manner alongside the conflict heuristic. We introduce two variants of doing so and demonstrate that this change can lead to 2-100x speedups in certain scenarios. 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.
• Abstract（参考訳）: conflict-based search (cbs) は、低レベル単一エージェントプランナーと高レベル制約木を用いて競合を解決する、一般的なマルチエージェントパス探索 (mapf) ソルバである。 現代のmapfソルバの大部分は、低レベルプランナーを変更する方法が少なく、様々な戦略によってこの木のサイズを小さくすることでcbsを改善することに焦点を当てている。 既存のcbsメソッドの低レベルプランナーは、非重み付きコスト対ゴーヒューリスティックを使用しており、cbsサブオプティカルな方法も高レベル検索にコンフリクトヒューリスティックを用いている。 一般的な信念とは対照的に、コスト・ツー・ゴ・ゴ・ヒューリスティックは紛争ヒューリスティックと共に特定の方法で重み付けすることで、より効果的に利用できることが示される。 2つのバリエーションを導入し、この変更が特定のシナリオで2-100倍のスピードアップにつながることを示す。 さらに,我々の知識を最大限に活用するために,優先計画と有界準最適CBSの第一理論関係を示し,本手法が自然な一般化であることを示す。

関連論文リスト

• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。