論文の概要: EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding
- arxiv url: http://arxiv.org/abs/2010.01367v2
- Date: Fri, 12 Mar 2021 19:00:29 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-11 11:36:16.182655
- Title: EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding
- Title(参考訳): EECBS:マルチエージェントパス探索のための境界下探索
- Authors: Jiaoyang Li, Wheeler Ruml, Sven Koenig
- Abstract要約: 明示的推定CBS(英: Explicit Estimation CBS、英: Explicit Estimation CBS)は、オンライン学習を用いて、各ハイレベルノードのソリューションのコストの不可避な推定値を得る、制限付き最適化型CBSである。
EECBSは、さまざまなMAPFインスタンス上で、最先端の有界MAPFアルゴリズムであるECBS、BCP-7、eMDD-SATよりもはるかに高速に動作する。
- 参考スコア(独自算出の注目度): 40.0986954496361
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Multi-Agent Path Finding (MAPF), i.e., finding collision-free paths for
multiple robots, is important for many applications where small runtimes are
necessary, including the kind of automated warehouses operated by Amazon. CBS
is a leading two-level search algorithm for solving MAPF optimally. ECBS is a
bounded-suboptimal variant of CBS that uses focal search to speed up CBS by
sacrificing optimality and instead guaranteeing that the costs of its solutions
are within a given factor of optimal. In this paper, we study how to decrease
its runtime even further using inadmissible heuristics. Motivated by Explicit
Estimation Search (EES), we propose Explicit Estimation CBS (EECBS), a new
bounded-suboptimal variant of CBS, that uses online learning to obtain
inadmissible estimates of the cost of the solution of each high-level node and
uses EES to choose which high-level node to expand next. We also investigate
recent improvements of CBS and adapt them to EECBS. We find that EECBS with the
improvements runs significantly faster than the state-of-the-art
bounded-suboptimal MAPF algorithms ECBS, BCP-7, and eMDD-SAT on a variety of
MAPF instances. We hope that the scalability of EECBS enables additional
applications for bounded-suboptimal MAPF algorithms.
- Abstract(参考訳): 複数ロボットの衝突のない経路を見つけるマルチエージェントパス探索(mapf)は、amazonが操作する自動倉庫など、小さなランタイムを必要とする多くのアプリケーションにとって重要である。
CBSはMAPFを最適に解くための二段階探索アルゴリズムである。
CBSは、最適化性を犠牲にしてCBSを高速化するために焦点探索を使い、その代わりに、そのソリューションのコストが最適な要因の範囲内であることを保証している。
本稿では,不許容ヒューリスティックスを用いて,ランタイムをさらに削減する方法を検討する。
明示的推定探索 (EES) によって動機づけられたCBS (EECBS) は,オンライン学習を用いて各高レベルのノードの解のコストの不許容推定値を取得し,次にどの高レベルのノードを拡張すべきかを選択する。
また、最近のCBSの改善について検討し、それをEECBSに適用する。
改良されたEECBSは,さまざまなMAPFインスタンス上で,最先端の有界MAPFアルゴリズムであるECBS,BCP-7,eMDD-SATよりもはるかに高速であることがわかった。
EECBSのスケーラビリティにより、有界最適MAPFアルゴリズムのさらなる応用が期待できる。
関連論文リスト
- 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) - Scalable Mechanism Design for Multi-Agent Path Finding [87.40027406028425]
MAPF (Multi-Agent Path Finding) は、複数のエージェントが同時に移動し、与えられた目標地点に向かって共有領域を通って衝突しない経路を決定する。
最適解を見つけることは、しばしば計算不可能であり、近似的な準最適アルゴリズムを用いることが不可欠である。
本稿では、MAPFのスケーラブルな機構設計の問題を紹介し、MAPFアルゴリズムを近似した3つの戦略防御機構を提案する。
論文 参考訳(メタデータ) (2024-01-30T14:26:04Z) - Learning Regions of Interest for Bayesian Optimization with Adaptive
Level-Set Estimation [84.0621253654014]
本稿では,高信頼領域を適応的にフィルタするBALLETというフレームワークを提案する。
理論的には、BALLETは探索空間を効率的に縮小することができ、標準BOよりも厳密な後悔を示すことができる。
論文 参考訳(メタデータ) (2023-07-25T09:45:47Z) - Solving Multi-Agent Target Assignment and Path Finding with a Single
Constraint Tree [9.518757918128799]
TAPF(Target-Assignment and Path-Finding problem)とTAPF(Target-Assignment and Path-Finding problem)は、エージェントに同時にターゲットを割り当てることを必要とする。
競合ベースのターゲティング・アサインメント(CBS-TA)は、TAPFに対処するための主要なアプローチである。
我々は,理論上,ITA-CBSは最適解を見つけることが保証され,実際は計算効率が高いことを示す。
論文 参考訳(メタデータ) (2023-07-02T20:52:16Z) - 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) - 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) - $\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) - Rethinking Performance Estimation in Neural Architecture Search [191.08960589460173]
本稿では,資源制約型システムにおける性能推定(PE)の体系的再考を行う。
BPEと強化学習,進化アルゴリズム,ランダム探索,異種アーキテクチャ探索などの様々な探索アルゴリズムを組み合わせることで,NASの1,000倍の高速化を実現した。
論文 参考訳(メタデータ) (2020-05-20T09:01:44Z) - Rethinking Differentiable Search for Mixed-Precision Neural Networks [83.55785779504868]
低ビット幅に量子化された重みとアクティベーションを持つ低精度ネットワークは、エッジデバイスでの推論を加速するために広く利用されている。
現在の解は均一であり、全てのフィルタに同じビット幅を使用する。
これは異なるフィルタの異なる感度を考慮せず、最適以下である。
混合精度ネットワークは、ビット幅を個々のフィルタ要求に調整することでこの問題に対処する。
論文 参考訳(メタデータ) (2020-04-13T07:02:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。