論文の概要: Factorization of Multi-Agent Sampling-Based Motion Planning
- arxiv url: http://arxiv.org/abs/2304.00342v1
- Date: Sat, 1 Apr 2023 15:50:18 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-04 18:34:29.919378
- Title: Factorization of Multi-Agent Sampling-Based Motion Planning
- Title（参考訳）: マルチエージェントサンプリングに基づくモーションプランニングの因子化
- Authors: Alessandro Zanardi, Pietro Zullo, Andrea Censi, Emilio Frazzoli
- Abstract要約: 現代のロボティクスは、共有環境内で複数のエンボディエージェントを動作させることが多い。
標準的なサンプリングベースのアルゴリズムは、ロボットの関節空間における解の探索に使用できる。
我々は、因子化の概念をサンプリングベースアルゴリズムに統合し、既存の手法への最小限の変更しか必要としない。
本稿では, PRM* のサンプル複雑性の観点から解析的ゲインを導出し, RRG の実証結果を示す。
- 参考スコア（独自算出の注目度）: 72.42734061131569
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Modern robotics often involves multiple embodied agents operating within a
shared environment. Path planning in these cases is considerably more
challenging than in single-agent scenarios. Although standard Sampling-based
Algorithms (SBAs) can be used to search for solutions in the robots' joint
space, this approach quickly becomes computationally intractable as the number
of agents increases. To address this issue, we integrate the concept of
factorization into sampling-based algorithms, which requires only minimal
modifications to existing methods. During the search for a solution we can
decouple (i.e., factorize) different subsets of agents into independent
lower-dimensional search spaces once we certify that their future solutions
will be independent of each other using a factorization heuristic.
Consequently, we progressively construct a lean hypergraph where certain
(hyper-)edges split the agents to independent subgraphs. In the best case, this
approach can reduce the growth in dimensionality of the search space from
exponential to linear in the number of agents. On average, fewer samples are
needed to find high-quality solutions while preserving the optimality,
completeness, and anytime properties of SBAs. We present a general
implementation of a factorized SBA, derive an analytical gain in terms of
sample complexity for PRM*, and showcase empirical results for RRG.
- Abstract（参考訳）: 現代のロボティクスは、共有環境内で作動する複数の具体化エージェントを含むことが多い。
このような場合のパスプランニングは、シングルエージェントのシナリオよりもかなり難しい。
標準的なサンプリングベースアルゴリズム(SBA)は、ロボットの関節空間における解の探索に利用できるが、エージェントの数が増えるにつれて、この手法はすぐに計算的に難解になる。
この問題に対処するために、既存の手法に最小限の変更しか必要としないサンプリングベースアルゴリズムに分解の概念を統合する。
解の探索中、エージェントの異なる部分集合(すなわち分解)を独立した低次元の探索空間に分解し、それらの将来の解が分解ヒューリスティックを用いて互いに独立であることを証明する。
その結果、ある(ハイパー)エッジがエージェントを独立したサブグラフに分割するリーンハイパーグラフを徐々に構築する。
最良の場合、このアプローチは探索空間の次元性の成長を指数関数からエージェント数における線形へと減少させることができる。
平均して、SBAの最適性、完全性、および任意の時間特性を保ちながら、高品質な解を見つけるのに必要なサンプルは少ない。
本稿では,因子化sbaの汎用実装を行い,prm*のサンプル複雑性の観点から分析的なゲインを導出し,rrgの実証結果を示す。
関連論文リスト
- Scalable Decentralized Algorithms for Online Personalized Mean Estimation [12.002609934938224]
本研究は,各エージェントが実数値分布からサンプルを収集し,その平均値を推定する,オーバーアーキシング問題の簡易版に焦点を当てた。
1つは信念の伝播からインスピレーションを得ており、もう1つはコンセンサスに基づくアプローチを採用している。
論文 参考訳（メタデータ） (2024-02-20T08:30:46Z) - Optimal Multi-Distribution Learning [88.3008613028333]
マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。
本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-12-08T16:06:29Z) - Sample-Efficient Multi-Agent RL: An Optimization Perspective [103.35353196535544]
一般関数近似に基づく汎用マルコフゲーム(MG)のためのマルチエージェント強化学習(MARL)について検討した。
汎用MGに対するマルチエージェントデカップリング係数(MADC)と呼ばれる新しい複雑性尺度を導入する。
我々のアルゴリズムは既存の研究に匹敵するサブリニアな後悔を与えることを示す。
論文 参考訳（メタデータ） (2023-10-10T01:39:04Z) - Partially Observable Multi-Agent Reinforcement Learning with Information Sharing [33.145861021414184]
部分的に観察可能なゲーム(POSG)の一般的な枠組みにおける証明可能なマルチエージェント強化学習(RL)について検討する。
我々は,エージェント間での情報共有の可能性,経験的マルチエージェントRLにおける一般的な実践,コミュニケーションを伴うマルチエージェント制御システムの標準モデルを活用することを提唱する。
論文 参考訳（メタデータ） (2023-08-16T23:42:03Z) - On the Complexity of Multi-Agent Decision Making: From Learning in Games
to Partial Monitoring [105.13668993076801]
マルチエージェント強化学習(MARL)理論における中心的な問題は、構造条件やアルゴリズムの原理がサンプル効率の学習保証につながるかを理解することである。
本稿では,複数のエージェントを用いた対話型意思決定のための一般的な枠組みとして,この問題について考察する。
マルチエージェント意思決定における統計的複雑性を特徴付けることは、単一エージェント決定の統計的複雑性を特徴付けることと等価であることを示す。
論文 参考訳（メタデータ） (2023-05-01T06:46:22Z) - Relational Reasoning via Set Transformers: Provable Efficiency and
Applications to MARL [154.13105285663656]
置換不変エージェントフレームワークを用いたMARL(Multi-A gent R einforcement Learning)は,実世界のアプリケーションにおいて大きな実証的成功を収めた。
残念なことに、このMARL問題の理論的理解は、多くのエージェントの呪いと、既存の著作における関係推論の限定的な探索によって欠落している。
モデルフリーアルゴリズムとモデルベースアルゴリズムの最適度差は各エージェント数に独立して対数的であり、多くのエージェントの呪いを和らげる。
論文 参考訳（メタデータ） (2022-09-20T16:42:59Z) - Permutation Invariant Policy Optimization for Mean-Field Multi-Agent
Reinforcement Learning: A Principled Approach [128.62787284435007]
本稿では,平均場近似ポリシ最適化(MF-PPO)アルゴリズムを提案する。
我々は,MF-PPOが収束のサブ線形速度で世界的最適政策を達成することを証明した。
特に、置換不変ニューラルアーキテクチャによって引き起こされる誘導バイアスは、MF-PPOが既存の競合より優れていることを示す。
論文 参考訳（メタデータ） (2021-05-18T04:35:41Z) - Multi-objective Conflict-based Search for Multi-agent Path Finding [10.354181009277623]
マルチオブジェクトパスプランナーは通常、パスの長さなどの単一の目的を最適化しながら、パスのアンサンブルを計算します。
本稿では、マルチオブジェクトコンフリクトベース検索(MO-CBS)という、いわゆる次元の呪いをバイパスする手法を紹介します。
論文 参考訳（メタデータ） (2021-01-11T10:42:38Z) - Statistically Guided Divide-and-Conquer for Sparse Factorization of
Large Matrix [2.345015036605934]
統計的問題をスパース係数回帰として定式化し、分割コンカレントアプローチでそれに取り組む。
第1段階分割では、タスクを1組の同時並列推定(CURE)問題に単純化するための2つの潜時並列アプローチについて検討する。
第2段階分割では、CUREの全解を効率的に追跡するために、一連の単純な増分経路からなる段階学習手法を革新する。
論文 参考訳（メタデータ） (2020-03-17T19:12:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。