論文の概要: Analysis Of The Anytime MAPF Solvers Based On The Combination Of
Conflict-Based Search (CBS) and Focal Search (FS)
- arxiv url: http://arxiv.org/abs/2209.09612v1
- Date: Tue, 20 Sep 2022 11:05:14 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-21 19:03:11.390693
- Title: Analysis Of The Anytime MAPF Solvers Based On The Combination Of
Conflict-Based Search (CBS) and Focal Search (FS)
- Title（参考訳）: コンフリクトベース探索 (cbs) と焦点探索 (fs) の組み合わせに基づくanytime mapfソルバの解析
- Authors: Ilya Ivanashev, Anton Andreychuk, Konstantin Yakovlev
- Abstract要約: 競合ベースの探索 (CBS) は多エージェントパスフィンディング問題を最適に解くために広く用いられているアルゴリズムである。
CBSのバウンテッド・サブ最適の異なる変種を走らせるためのトレードオフ最適性を設計した。
CBSの双方のレベルのFocal Searchは、幅広いセットアップにおいて有益であることを示す。
- 参考スコア（独自算出の注目度）: 2.320417845168326
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Conflict-Based Search (CBS) is a widely used algorithm for solving
multi-agent pathfinding (MAPF) problems optimally. The core idea of CBS is to
run hierarchical search, when, on the high level the tree of solutions
candidates is explored, and on the low-level an individual planning for a
specific agent (subject to certain constraints) is carried out. To trade-off
optimality for running time different variants of bounded sub-optimal CBS were
designed, which alter both high- and low-level search routines of CBS.
Moreover, anytime variant of CBS does exist that applies Focal Search (FS) to
the high-level of CBS - Anytime BCBS. However, no comprehensive analysis of how
well this algorithm performs compared to the naive one, when we simply
re-invoke CBS with the decreased sub-optimality bound, was present. This work
aims at filling this gap. Moreover, we present and evaluate another anytime
version of CBS that uses FS on both levels of CBS. Empirically, we show that
its behavior is principally different from the one demonstrated by Anytime
BCBS. Finally, we compare both algorithms head-to-head and show that using
Focal Search on both levels of CBS can be beneficial in a wide range of setups.
- Abstract（参考訳）: conflict-based search (cbs) はマルチエージェントパスファイニング(mapf)問題を最適に解くために広く用いられているアルゴリズムである。
cbsの核となる考え方は階層的探索を行い、高レベルにおいて解候補のツリーを探索し、低レベルにおいては特定のエージェント(特定の制約に従属する)の個別計画を実行することである。
CBSの高次・低次探索ルーチンを変更するため、制限付き準最適CBSの異なる変種を走らせるためのトレードオフ最適性を設計した。
さらに、CBSの高レベルなCBS - Anytime BCBSにFocal Search(FS)を適用する、CBSのあらゆるバリエーションが存在する。
しかし、cbsのサブオプティビティのバウンドが低下しただけの場合、このアルゴリズムがナイーブに比較していかにうまく機能するかの包括的な分析は行われなかった。
この仕事はこのギャップを埋めることを目指している。
さらに,CBSの両レベルにおいてFSを使用するCBSの任意のバージョンを提示し,評価する。
実験により,その挙動はAnytime BCBSが示したものとは大きく異なることがわかった。
最後に、両アルゴリズムを真っ向から比較し、CBSの両レベルでFocal Searchを使用することは、幅広い設定において有益であることを示す。
関連論文リスト
- Multi-agent Path Finding in Continuous Environment [11.325849006178737]
本研究では,新たな連続環境競合探索(CE-CBS)アルゴリズムを提案する。
CE-CBSは、ハイレベル検索フレームワークのためのコンフリクトベースの検索(CBS)と低レベルパス計画のためのRT*を組み合わせる。
実験の結果、CE-CBSはMAPFの連続的な側面を連続的に考慮する他のアルゴリズムと競合していることがわかった。
論文 参考訳（メタデータ） (2024-09-16T19:23:04Z) - Not All Pairs are Equal: Hierarchical Learning for Average-Precision-Oriented Video Retrieval [80.09819072780193]
平均精度(AP)は、関連ビデオのランキングを上位リストで評価する。
最近のビデオ検索手法は、全てのサンプル対を等しく扱うペアワイズ損失を利用する。
論文 参考訳（メタデータ） (2024-07-22T11:52:04Z) - ITA-ECBS: A Bounded-Suboptimal Algorithm for the Combined Target-Assignment and Path-Finding Problem [20.090818762687565]
ITA-ECBS は ITA-CBS の最初の有界-準最適変種である。
54,033例中87.42%でCBS-TAより高速に動作している。
論文 参考訳（メタデータ） (2024-04-08T06:36:42Z) - 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) - Revisiting Random Channel Pruning for Neural Network Compression [159.99002793644163]
チャネル(または3Dフィルタ)プルーニングは、ニューラルネットワークの推論を加速する有効な方法である。
本稿では,ランダムな探索により,プルーンドモデルのチャネル構成を決定することを試みる。
この単純な戦略は、他のチャネルプルーニング手法と比較して非常にうまく機能することを示す。
論文 参考訳（メタデータ） (2022-05-11T17:59:04Z) - Local Stochastic Bilevel Optimization with Momentum-Based Variance
Reduction [104.41634756395545]
具体的には、まず、決定論的勾配に基づくアルゴリズムであるFedBiOを提案する。
FedBiOの複雑性は$O(epsilon-1.5)$である。
本アルゴリズムは数値実験において,他のベースラインと比較して優れた性能を示す。
論文 参考訳（メタデータ） (2022-05-03T16:40:22Z) - $\beta$-DARTS: Beta-Decay Regularization for Differentiable Architecture
Search [85.84110365657455]
本研究では,DARTSに基づくNAS探索過程を正規化するために,ベータデカイと呼ばれるシンプルだが効率的な正規化手法を提案する。
NAS-Bench-201の実験結果から,提案手法は探索過程の安定化に有効であり,探索されたネットワークを異なるデータセット間で転送しやすくする。
論文 参考訳（メタデータ） (2022-03-03T11:47: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) - Channel Pruning via Automatic Structure Search [109.83642249625098]
そこで我々は,ABCPrunerと呼ばれる人工蜂コロニーアルゴリズム(ABC)に基づく新たなチャネルプルーニング手法を提案する。
ABCPrunerはより効果的であることが証明されており、細調整をエンドツーエンドで効率的に行うことができる。
論文 参考訳（メタデータ） (2020-01-23T14:51:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。