論文の概要: Improving Continuous-time Conflict Based Search

• arxiv url: http://arxiv.org/abs/2101.09723v2
• Date: Tue, 2 Mar 2021 18:37:38 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-16 09:12:22.811701
• Title: Improving Continuous-time Conflict Based Search
• Title（参考訳）: 連続時間競合に基づく検索の改善
• Authors: Anton Andreychuk, Konstantin Yakovlev, Eli Boyarski and Roni Stern
• Abstract要約: Conflict-Based Search (CBS) はマルチエージェントパス探索 (MAPF) 問題を最適に解くための強力なフレームワークである。 Continuous-time CBS(CCBS)は、CBSの最近提案されたバージョンで、時間を差別することなく最適なソリューションを保証します。 コンフリクト(PC)、ディジョイン分割(DS)、ハイレベルエージェントをCCBSの連続時間設定に優先順位付けすることで、CBSの改善を成功させる方法を紹介します。
• 参考スコア（独自算出の注目度）: 19.36475688888736
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Conflict-Based Search (CBS) is a powerful algorithmic framework for optimally solving classical multi-agent path finding (MAPF) problems, where time is discretized into the time steps. Continuous-time CBS (CCBS) is a recently proposed version of CBS that guarantees optimal solutions without the need to discretize time. However, the scalability of CCBS is limited because it does not include any known improvements of CBS. In this paper, we begin to close this gap and explore how to adapt successful CBS improvements, namely, prioritizing conflicts (PC), disjoint splitting (DS), and high-level heuristics, to the continuous time setting of CCBS. These adaptions are not trivial, and require careful handling of different types of constraints, applying a generalized version of the Safe interval path planning (SIPP) algorithm, and extending the notion of cardinal conflicts. We evaluate the effect of the suggested enhancements by running experiments both on general graphs and $2^k$-neighborhood grids. CCBS with these improvements significantly outperforms vanilla CCBS, solving problems with almost twice as many agents in some cases and pushing the limits of multiagent path finding in continuous-time domains.
• Abstract（参考訳）: Conflict-Based Search (CBS) は、従来のマルチエージェントパス探索 (MAPF) 問題を最適に解くための強力なアルゴリズムフレームワークである。 Continuous-time CBS(CCBS)は、CBSの最近提案されたバージョンで、時間を差別することなく最適なソリューションを保証します。 しかし、CBSのスケーラビリティはCBSの既知の改善を含まないため制限されている。 本稿では,このギャップを解消し,CBS改善の成功,すなわちコンフリクト(PC)の優先順位付け,ディスジョイント分割(DS)とハイレベルヒューリスティックス(高レベルヒューリスティックス)をCCBSの継続的な時間設定に適応させる方法について検討する。 これらの適応は自明ではなく、異なる種類の制約の慎重な処理、セーフインターバルパス計画(SIPP)アルゴリズムの一般化バージョンの適用、およびカーディナルコンフリクトの概念の拡張を必要とする。 一般グラフと2^k$-neighborhoodグリッドの両方で実験を行い,提案手法の効果を評価した。 これらの改善を伴うCCBSは、バニラCCBSを大幅に上回り、場合によってはほぼ2倍のエージェントで問題を解決し、連続時間領域におけるマルチエージェントパスの発見の限界を押し広げる。

関連論文リスト

• Multi-agent Path Finding in Continuous Environment [11.325849006178737]
  本研究では,新たな連続環境競合探索(CE-CBS)アルゴリズムを提案する。 CE-CBSは、ハイレベル検索フレームワークのためのコンフリクトベースの検索(CBS)と低レベルパス計画のためのRT*を組み合わせる。 実験の結果、CE-CBSはMAPFの連続的な側面を連続的に考慮する他のアルゴリズムと競合していることがわかった。
  論文  参考訳（メタデータ） (2024-09-16T19:23:04Z)
• Last-Iterate Global Convergence of Policy Gradients for Constrained Reinforcement Learning [62.81324245896717]
  我々はC-PGと呼ばれる探索非依存のアルゴリズムを導入し、このアルゴリズムは(弱)勾配支配仮定の下でのグローバルな最終点収束を保証する。 制約付き制御問題に対して,我々のアルゴリズムを数値的に検証し,それらを最先端のベースラインと比較する。
  論文  参考訳（メタデータ） (2024-07-15T14:54:57Z)
• Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
  最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。 GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。 我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
  論文  参考訳（メタデータ） (2024-06-05T22:52:27Z)
• 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)
• On Pitfalls of Test-Time Adaptation [82.8392232222119]
  TTA(Test-Time Adaptation)は、分散シフトの下で堅牢性に取り組むための有望なアプローチとして登場した。 TTABは,10の最先端アルゴリズム,多種多様な分散シフト,および2つの評価プロトコルを含むテスト時間適応ベンチマークである。
  論文  参考訳（メタデータ） (2023-06-06T09:35:29Z)
• 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)
• Doubly Robust Off-Policy Actor-Critic: Convergence and Optimality [131.45028999325797]
  ディスカウント型MDPのための2倍堅牢なオフポリチックAC(DR-Off-PAC)を開発した。 DR-Off-PACは、俳優と批評家の両方が一定のステップで同時に更新される単一のタイムスケール構造を採用しています。 有限時間収束速度を研究し, dr-off-pac のサンプル複雑性を特徴とし, $epsilon$-accurate optimal policy を得る。
  論文  参考訳（メタデータ） (2021-02-23T18:56:13Z)
• Optimization Issues in KL-Constrained Approximate Policy Iteration [48.24321346619156]
  多くの強化学習アルゴリズムは、近似ポリシー反復(API)のバージョンと見なすことができる。 標準APIはしばしば動作が悪いが、KL-divergenceによる各ポリシー更新を以前のポリシーに正規化することで学習が安定化できることが示されている。 TRPO、MPO、VMPOなどの一般的な実用的なアルゴリズムは、連続ポリシーのKL分割に関する制約によって正規化を置き換える。
  論文  参考訳（メタデータ） (2021-02-11T19:35:33Z)
• 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)
• Bottom-Up Temporal Action Localization with Mutual Regularization [107.39785866001868]
  TALの最先端の解決策は、3つの行動指示相のフレームレベルの確率を評価することである。 学習手順を相互に規則化するための2つの規則化用語を導入する。 実験は2つの人気のTALデータセット、THUMOS14とActivityNet1.3で行われている。
  論文  参考訳（メタデータ） (2020-02-18T03:59:13Z)

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

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