論文の概要: Revisiting the Complexity Analysis of Conflict-Based Search: New
Computational Techniques and Improved Bounds
- arxiv url: http://arxiv.org/abs/2104.08759v1
- Date: Sun, 18 Apr 2021 07:46:28 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-22 09:52:32.448259
- Title: Revisiting the Complexity Analysis of Conflict-Based Search: New
Computational Techniques and Improved Bounds
- Title（参考訳）: コンフリクトベース探索の複雑性解析の再検討--新しい計算手法と改良境界
- Authors: Ofir Gordon, Yuval Filmus, Oren Salzman
- Abstract要約: 最適解に対する最先端のアプローチは Conflict-Based Search (CBS) である
CBSの複雑性分析を再検討し、最悪の場合のアルゴリズムの実行時間に厳密な制限を与える。
- 参考スコア（独自算出の注目度）: 5.158632635415881
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The problem of Multi-Agent Path Finding (MAPF) calls for finding a set of
conflict-free paths for a fleet of agents operating in a given environment.
Arguably, the state-of-the-art approach to computing optimal solutions is
Conflict-Based Search (CBS). In this work we revisit the complexity analysis of
CBS to provide tighter bounds on the algorithm's run-time in the worst-case.
Our analysis paves the way to better pinpoint the parameters that govern (in
the worst case) the algorithm's computational complexity.
Our analysis is based on two complementary approaches: In the first approach
we bound the run-time using the size of a Multi-valued Decision Diagram (MDD)
-- a layered graph which compactly contains all possible single-agent paths
between two given vertices for a specific path length.
In the second approach we express the running time by a novel recurrence
relation which bounds the algorithm's complexity. We use generating
functions-based analysis in order to tightly bound the recurrence.
Using these technique we provide several new upper-bounds on CBS's
complexity. The results allow us to improve the existing bound on the running
time of CBS for many cases. For example, on a set of common benchmarks we
improve the upper-bound by a factor of at least $2^{10^{7}}$.
- Abstract（参考訳）: マルチエージェントパス探索(mapf)の問題は、与えられた環境で動作するエージェント群に対して、コンフリクトフリーパスのセットを見つけることである。
おそらく、最適なソリューションを計算するための最先端のアプローチは、Conflict-Based Search (CBS)である。
本研究では,CBSの複雑性解析を見直し,最悪の場合のアルゴリズムの実行時間に厳密な制限を与える。
我々の分析は、アルゴリズムの計算複雑性を(最悪の場合)支配するパラメータをより正確に特定する方法を舗装する。
最初のアプローチでは、指定された2つの頂点間の全ての単一エージェントパスをコンパクトに含む階層グラフであるMulti-valued Decision Diagram (MDD) のサイズを用いてランタイムをバインドする。
第2のアプローチでは、アルゴリズムの複雑さを束縛する新しい繰り返し関係によって実行時間を表現する。
再帰を厳密に束縛するために,生成関数に基づく解析を用いる。
これらの手法を用いることで、CBSの複雑さに関するいくつかの新しい上限を提供する。
その結果,cbsの稼働時間に関する既存のバウンドを多くのケースで改善することが可能となった。
例えば、一般的なベンチマークのセットでは、最低でも$2^{10^{7}}$の係数で上限を改善する。
関連論文リスト
- Query-Efficient Correlation Clustering with Noisy Oracle [17.11782578276788]
共同マルチアーマッドバンド(PE-CMAB)における純粋探索のパラダイムに根ざしたオンライン学習問題の2つの新しい定式化を導入する。
我々は,サンプリング戦略と古典近似アルゴリズムを組み合わせるアルゴリズムを設計し,それらの理論的保証について検討する。
本研究は, PE-CMABの場合のクラスタリング時アルゴリズムの最初の例であり, 基礎となるオフライン最適化問題はNP-hardである。
論文 参考訳（メタデータ） (2024-02-02T13:31:24Z) - Decision Diagram-Based Branch-and-Bound with Caching for Dominance and
Suboptimality Detection [9.175779296469194]
本稿では動的プログラミングモデルの構造を利用して探索を高速化する新しい要素を提案する。
鍵となる考え方は、検索中にキャッシュされた拡張しきい値に問い合わせることによって、同じ動的プログラミング状態に対応するノードの繰り返し拡張を防止することである。
このキャッシング機構によって引き起こされるプルーニングは、アルゴリズムによって拡張されたノード数を著しく削減できることを示す実験である。
論文 参考訳（メタデータ） (2022-11-22T10:18:33Z) - Finite-Time Error Bounds for Greedy-GQ [20.51105692499517]
We show that Greedy-GQ algorithm converges fast-time error。
我々の分析は、ステップサイズを選択するために、より高速な収束ステップサイズを提供する。
論文 参考訳（メタデータ） (2022-09-06T15:04:57Z) - Enhanced Methods for the Weight Constrained Shortest Path Problem [18.567812400186092]
WCSPP(Weight Constrained Shortest Path Problem)は、AIにおいてよく研究されているが、難しいトピックである。
本稿では, A* 探索に基づく WCSPP に対する2つの新しい解法を提案する。
我々は,大規模で現実的な問題事例の集合に対して,アルゴリズムの性能を実証的に評価した。
論文 参考訳（メタデータ） (2022-07-29T15:32:45Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳（メタデータ） (2021-06-08T15:54:44Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z) - Refined bounds for algorithm configuration: The knife-edge of dual class
approximability [94.83809668933021]
トレーニングセットが、トレーニングセット上でのパラメータの平均メトリックのパフォーマンスが、予想される将来的なパフォーマンスに最も近いことを保証するために、どの程度の規模が必要かを調査する。
この近似が L-無限ノルムの下で成り立つなら、強いサンプル複雑性境界を与えることができる。
我々は、コンピュータ科学において最も強力なツールの一つである整数プログラミングの文脈において、我々の限界を実証的に評価する。
論文 参考訳（メタデータ） (2020-06-21T15:32:21Z) - Beyond Worst-Case Analysis in Stochastic Approximation: Moment
Estimation Improves Instance Complexity [58.70807593332932]
近似問題に対する勾配に基づく手法のオラクル複雑性について検討する。
最悪のケースの複雑さではなく、インスタンス依存の複雑さに焦点を当てます。
提案アルゴリズムとその解析はモーメント推定の成功を理論的に正当化する。
論文 参考訳（メタデータ） (2020-06-08T09:25:47Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳（メタデータ） (2020-05-09T02:48:23Z) - Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。
ラグランジアン分解に基づく新しい手法を提案する。
ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
論文 参考訳（メタデータ） (2020-02-24T17:55:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。