論文の概要: Clique Analysis and Bypassing in Continuous-Time Conflict-Based Search
- arxiv url: http://arxiv.org/abs/2312.16106v1
- Date: Tue, 26 Dec 2023 16:21:15 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-27 14:45:07.084088
- Title: Clique Analysis and Bypassing in Continuous-Time Conflict-Based Search
- Title(参考訳): 連続時間衝突探索における斜め解析とバイパス
- Authors: Thayne T. Walker, Nathan R. Sturtevant and Ariel Felner
- Abstract要約: 本稿では,連続時間競合探索(CCBS)における対称性破りの強化について検討する。
我々は、コスト対称性と空間的衝突対称性を解消する双立制約を解消するバイパス法(B bypassing)という、CCBSの単価ドメインからの既知の拡張を適応する。
以上の結果から,これらの拡張が従来の技術に比べて統計的に有意な性能向上をもたらし,高密度グラフ上で同じ時間に最大10%あるいは20%以上のエージェントの問題を解くことを実証的に示している。
- 参考スコア(独自算出の注目度): 19.1809369667358
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: While the study of unit-cost Multi-Agent Pathfinding (MAPF) problems has been
popular, many real-world problems require continuous time and costs due to
various movement models. In this context, this paper studies symmetry-breaking
enhancements for Continuous-Time Conflict-Based Search (CCBS), a solver for
continuous-time MAPF. Resolving conflict symmetries in MAPF can require an
exponential amount of work. We adapt known enhancements from unit-cost domains
for CCBS: bypassing, which resolves cost symmetries and biclique constraints
which resolve spatial conflict symmetries. We formulate a novel combination of
biclique constraints with disjoint splitting for spatial conflict symmetries.
Finally, we show empirically that these enhancements yield a statistically
significant performance improvement versus previous state of the art, solving
problems for up to 10% or 20% more agents in the same amount of time on dense
graphs.
- Abstract(参考訳): MAPF(Multi-Agent Pathfinding)問題の研究は広く行われているが、現実の多くの問題は、様々な動きモデルによる連続的な時間とコストを必要とする。
本稿では,連続時間MAPFの解法である連続時間競合探索(CCBS)の対称性破りの強化について検討する。
MAPFにおける競合対称性の解消には指数関数的な作業が必要である。
我々は、コスト対称性と空間的衝突対称性を解消する双角的制約を解消するバイパス(B bypassing)という、CCBSの単価ドメインからの既知の拡張に適応する。
本稿では,空間衝突対称性に対する二方向制約と解離分割の新たな組み合わせを定式化する。
最後に,これらの拡張が従来の技術に比べて統計的に有意な性能向上をもたらすことを実証的に示し,高密度グラフ上で同じ時間に最大10%または20%以上のエージェントの問題を解く。
関連論文リスト
- TFMQ-DM: Temporal Feature Maintenance Quantization for Diffusion Models [52.454274602380124]
拡散モデルは非常に時間ステップ$t$に大きく依存し、良好なマルチラウンドデノジングを実現している。
本稿では,時間情報ブロック上に構築した時間的特徴保守量子化(TFMQ)フレームワークを提案する。
先駆的なブロック設計により、時間情報認識再構成(TIAR)と有限集合キャリブレーション(FSC)を考案し、完全な時間的特徴を整列させる。
論文 参考訳(メタデータ) (2023-11-27T12:59:52Z) - Beyond Sharing: Conflict-Aware Multivariate Time Series Anomaly
Detection [18.796225184893874]
本稿では,衝突を意識した異常検出アルゴリズムCADを紹介する。
その結果,バニラMMoEの粗悪な性能は,MTS定式化の入力出力ミスアライメント設定に起因していることが判明した。
CADは3つの公開データセットの平均F1スコアが0.943であることを示す。
論文 参考訳(メタデータ) (2023-08-17T11:00:01Z) - Robust Detection of Lead-Lag Relationships in Lagged Multi-Factor Models [61.10851158749843]
データ固有のリード-ラグ関係を発見することで、重要な洞察を得ることができる。
階層化多要素モデルにおけるリードラグ関係のロバスト検出のためのクラスタリング駆動手法を開発した。
論文 参考訳(メタデータ) (2023-05-11T10:30:35Z) - Beyond Exponentially Fast Mixing in Average-Reward Reinforcement
Learning via Multi-Level Monte Carlo Actor-Critic [61.968469104271676]
本稿では,アクター・アクターとアクター・アクター・アクター・アルゴリズムに埋め込まれた平均報酬に対して,マルチレベルモンテカルロ推定器を用いて混合時間に適応したRL手法を提案する。
不安定な報酬を伴うRL問題において,安定性に要求される技術的条件の緩和効果が,実用上優れた性能に変換されることを実験的に示す。
論文 参考訳(メタデータ) (2023-01-28T04:12:56Z) - PS-ARM: An End-to-End Attention-aware Relation Mixer Network for Person
Search [56.02761592710612]
モジュール・パーソン・サーチのための新しいアテンション・アウェア・リレーション・ミキサー(ARM)を提案する。
私たちのARMモジュールはネイティブで、きめ細かい監督やトポロジカルな仮定に依存していません。
我々のPS-ARMは、両方のデータセットで最先端のパフォーマンスを達成する。
論文 参考訳(メタデータ) (2022-10-07T10:04:12Z) - Continual Learning In Environments With Polynomial Mixing Times [13.533984338434106]
連続的強化学習における混合時間の影響について検討した。
平均報酬を直接最適化することで学習を高速化するモデルベースアルゴリズムのファミリーを提案する。
論文 参考訳(メタデータ) (2021-12-13T23:41:56Z) - Reinforcement Learning for Mean Field Games, with Applications to
Economics [0.0]
平均場ゲーム(MFG)および平均場制御問題(平均場制御問題、平均場制御問題、平均場制御問題、平均場制御問題、平均場制御問題、平均場制御問題、平均場制御問題)は、エージェントの連続体を持つゲームにおいてナッシュ平衡または社会的最適性を研究するためのフレームワークである。
本稿では,MFGとMFCのためのRLを用いた2つの時間スケールアプローチを提案する。
論文 参考訳(メタデータ) (2021-06-25T16:45:04Z) - Pairwise Symmetry Reasoning for Multi-Agent Path Finding Search [43.40580211016752]
マルチエージェントパス発見(mapf)は,協調エージェントのチームに対して,衝突のないパスを計画することを求める課題である。
MAPFが解決しにくい理由の1つは、ペアワイズ対称性と呼ばれる現象によるものであることを示しています。
対称性の発生を効率的に検出し、特殊な制約を用いて解決する様々な推論手法を提案します。
論文 参考訳(メタデータ) (2021-03-12T07:27:35Z) - 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) - Global Convergence of Policy Gradient for Linear-Quadratic Mean-Field
Control/Game in Continuous Time [109.06623773924737]
線形二乗平均場制御とゲームに対するポリシー勾配法について検討する。
線形速度で最適解に収束し, 合成シミュレーションにより検証した。
論文 参考訳(メタデータ) (2020-08-16T06:34:11Z) - Upper Confidence Primal-Dual Reinforcement Learning for CMDP with
Adversarial Loss [145.54544979467872]
マルコフ決定過程(CMDP)に対するオンライン学習の検討
本稿では,遷移モデルから標本化した軌跡のみを必要とする,新しいEmphupper confidence primal-dualアルゴリズムを提案する。
我々の分析では、ラグランジュ乗算過程の新たな高確率ドリフト解析を、高信頼強化学習の記念後悔解析に組み入れている。
論文 参考訳(メタデータ) (2020-03-02T05:02:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。