論文の概要: Effectively Incorporating Weighted Cost-to-go Heuristic in Suboptimal
CBS
- arxiv url: http://arxiv.org/abs/2205.11624v2
- Date: Wed, 25 May 2022 16:50:29 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-29 08:02:20.358695
- Title: Effectively Incorporating Weighted Cost-to-go Heuristic in Suboptimal
CBS
- Title(参考訳): CBSにおける重み付きコスト・ツー・ゴーヒューリスティックの効果的導入
- Authors: Rishi Veerapaneni, Tushar Kusnur, Maxim Likhachev
- Abstract要約: Conflict-Based Search (CBS)は、低レベルのシングルエージェントプランナーと高レベルの制約ツリーを用いて競合を解決する、人気のあるマルチエージェントパス探索(MAPF)である。
コスト・ツー・ゴ・ゴ・ソルバは、競合と並行して特定の方法で重み付けすることで、より効果的に利用できることが示される。
- 参考スコア(独自算出の注目度): 17.003506320983455
- 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の第一理論関係を示し,本手法が自然な一般化であることを示す。
関連論文リスト
- Model-based Causal Bayesian Optimization [74.78486244786083]
乗算重み付き因果ベイズ最適化のための最初のアルゴリズム(CBO-MW)を提案する。
グラフ関連の量に自然に依存するCBO-MWに対する後悔の限界を導出する。
我々の実験は、共有モビリティシステムにおいて、ユーザの需要パターンを学習するためにCBO-MWをどのように使用できるかの現実的なデモを含む。
論文 参考訳(メタデータ) (2023-07-31T13:02:36Z) - Submodular Reinforcement Learning [77.97471858326077]
強化学習(RL)では、状態の報酬は通常加法的と見なされ、マルコフの仮定に従って、それらは以前に訪れた状態に対して$textitindependent$である。
カバー範囲制御、実験設計、情報経路計画といった多くの重要な応用において、報酬は自然にリターンを減少させ、すなわち、それらの価値は以前に訪れた同様の状態から減少する。
減少するリターンをキャプチャするサブモジュール集合関数をモデルとした,より汎用的で非付加的(かつ履歴に依存しない)報酬を最適化するパラダイムである$textitsubmodular RL$ (SubRL)を提案する。
論文 参考訳(メタデータ) (2023-07-25T09:46:02Z) - 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) - Latent State Marginalization as a Low-cost Approach for Improving
Exploration [79.12247903178934]
我々はMaxEntフレームワークにおける潜在変数ポリシーの採用を提案する。
我々は、潜在変数ポリシーが、潜在信念状態を持つ世界モデルの下で自然に現れることを示す。
提案手法を連続制御タスクに対して実験的に検証し, 有効限界化がよりよい探索とより堅牢な訓練につながることを示した。
論文 参考訳(メタデータ) (2022-10-03T15:09:12Z) - 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) - Effective Version Space Reduction for Convolutional Neural Networks [61.84773892603885]
アクティブラーニングでは、サンプリングバイアスは深刻な矛盾問題を引き起こし、アルゴリズムが最適な仮説を見つけるのを妨げる可能性がある。
本稿では,畳み込みニューラルネットワークを用いた能動学習について,バージョン空間削減の原理的レンズを用いて検討する。
論文 参考訳(メタデータ) (2020-06-22T17:40:03Z) - Decentralized MCTS via Learned Teammate Models [89.24858306636816]
本稿では,モンテカルロ木探索に基づくトレーニング可能なオンライン分散計画アルゴリズムを提案する。
深層学習と畳み込みニューラルネットワークを用いて正確なポリシー近似を作成可能であることを示す。
論文 参考訳(メタデータ) (2020-03-19T13:10:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。