論文の概要: GRAPE-S: Near Real-Time Coalition Formation for Multiple Service
Collectives
- arxiv url: http://arxiv.org/abs/2310.12480v1
- Date: Thu, 19 Oct 2023 05:36:00 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-20 16:46:52.838716
- Title: GRAPE-S: Near Real-Time Coalition Formation for Multiple Service
Collectives
- Title(参考訳): grape-s: 複数サービス集団のリアルタイム連立形成
- Authors: Grace Diehl and Julie A. Adams
- Abstract要約: GRAPEとサービスモデルを統合し、GRAPE-SとPair-GRAPE-Sを生成する。
GRAPE-Sは、ターゲット領域の連立形成要求を満たし、ほぼリアルタイムで最適解を生成する。
Pair-GRAPE-Sはドメイン要件を満たし、ほぼリアルタイムで最適解を生成する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Robotic collectives for military and disaster response applications require
coalition formation algorithms to partition robots into appropriate task teams.
Collectives' missions will often incorporate tasks that require multiple
high-level robot behaviors or services, which coalition formation must
accommodate. The highly dynamic and unstructured application domains also
necessitate that coalition formation algorithms produce near optimal solutions
(i.e., >95% utility) in near real-time (i.e., <5 minutes) with very large
collectives (i.e., hundreds of robots). No previous coalition formation
algorithm satisfies these requirements. An initial evaluation found that
traditional auction-based algorithms' runtimes are too long, even though the
centralized simulator incorporated ideal conditions unlikely to occur in
real-world deployments (i.e., synchronization across robots and perfect,
instantaneous communication). The hedonic game-based GRAPE algorithm can
produce solutions in near real-time, but cannot be applied to multiple service
collectives. This manuscript integrates GRAPE and a services model, producing
GRAPE-S and Pair-GRAPE-S. These algorithms and two auction baselines were
evaluated using a centralized simulator with up to 1000 robots, and via the
largest distributed coalition formation simulated evaluation to date, with up
to 500 robots. The evaluations demonstrate that auctions transfer poorly to
distributed collectives, resulting in excessive runtimes and low utility
solutions. GRAPE-S satisfies the target domains' coalition formation
requirements, producing near optimal solutions in near real-time, and
Pair-GRAPE-S more than satisfies the domain requirements, producing optimal
solutions in near real-time. GRAPE-S and Pair-GRAPE-S are the first algorithms
demonstrated to support near real-time coalition formation for very large,
distributed collectives with multiple services.
- Abstract(参考訳): 軍事・災害対応アプリケーションのためのロボット集合体は、ロボットを適切なタスクチームに分割する連立アルゴリズムを必要とする。
集団の任務は、しばしば複数の高度なロボットの行動やサービスを必要とするタスクを組み込む。
高度に動的で非構造化されたアプリケーションドメインはまた、連立形成アルゴリズムが、非常に大きな集団(すなわち数百のロボット)を持つほぼリアルタイム(すなわち5分)に、ほぼ最適な解(95%ユーティリティ)を生成する必要がある。
以前の連立形成アルゴリズムはこれらの要件を満たすものではない。
最初の評価では、従来のオークションベースのアルゴリズムのランタイムが長すぎることが判明した。
ヘドニックゲームベースのGRAPEアルゴリズムは、ほぼリアルタイムでソリューションを生成できるが、複数のサービス集合に適用することはできない。
GRAPEとサービスモデルを統合し、GRAPE-SとPair-GRAPE-Sを生成する。
これらのアルゴリズムと2つのオークションベースラインを、最大1000台のロボットによる集中型シミュレータを用いて評価し、最大500台のロボットによる評価をシミュレートした。
評価の結果、オークションは分散集団にはあまり移行せず、過度なランタイムと低いユーティリティソリューションを生み出している。
GRAPE-Sは、ターゲット領域の連立要求を満たし、ほぼリアルタイムでほぼ最適解を生成し、Pair-GRAPE-Sはドメイン要求を満足し、ほぼリアルタイムで最適な解を生成する。
GRAPE-SとPair-GRAPE-Sは、複数のサービスを持つ非常に大規模な分散集団に対して、リアルタイムに近い連立形成をサポートする最初のアルゴリズムである。
関連論文リスト
- A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation [61.08720171136229]
結合構造生成はマルチエージェントシステムにおける基本的な計算問題である。
我々はCSGの多エージェントパス探索アルゴリズムであるSALDAEを開発し、連立構造グラフ上で運用する。
論文 参考訳(メタデータ) (2025-02-14T15:21:27Z) - Cluster-Based Multi-Agent Task Scheduling for Space-Air-Ground Integrated Networks [60.085771314013044]
低高度経済は、コミュニケーションやセンシングなどの分野で発展する大きな可能性を秘めている。
本稿では,SAGINにおけるマルチUAV協調タスクスケジューリング問題に対処するため,クラスタリングに基づく多エージェントDeep Deterministic Policy Gradient (CMADDPG)アルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-12-14T06:17:33Z) - Generalizability of Graph Neural Networks for Decentralized Unlabeled Motion Planning [72.86540018081531]
ラベルなしの動作計画では、衝突回避を確保しながら、ロボットのセットを目標の場所に割り当てる。
この問題は、探査、監視、輸送などの応用において、マルチロボットシステムにとって不可欠なビルディングブロックを形成している。
この問題に対処するために、各ロボットは、その400ドルのアネレストロボットと$k$アネレストターゲットの位置のみを知っている分散環境で対処する。
論文 参考訳(メタデータ) (2024-09-29T23:57:25Z) - Asynchronous Fractional Multi-Agent Deep Reinforcement Learning for Age-Minimal Mobile Edge Computing [14.260646140460187]
計算集約的な更新のタイムラインを調査し、AoIを最小化するためにタスク更新とオフロードポリシーを共同で最適化する。
具体的には、エッジ負荷のダイナミクスを考慮し、期待時間平均AoIを最小化するためにタスクスケジューリング問題を定式化する。
提案アルゴリズムは,実験における最良基準アルゴリズムと比較して平均AoIを最大52.6%削減する。
論文 参考訳(メタデータ) (2024-09-25T11:33:32Z) - SPACE: A Python-based Simulator for Evaluating Decentralized Multi-Robot Task Allocation Algorithms [1.52292571922932]
本研究では,分散マルチロボットタスクアロケーション(MRTA)アルゴリズムの研究,評価,比較を支援するPythonベースのシミュレータであるSPACE(Swarm Planning and Control Evaluation)を提案する。
SPACEは、Pythonプラグインとして意思決定アルゴリズムを実装し、直感的なGUIでエージェントの動作木を簡単に構築し、エージェント間通信とローカルタスク認識のための組み込みサポートを活用することで、コアアルゴリズム開発を効率化する。
論文 参考訳(メタデータ) (2024-09-06T12:38:24Z) - Faster Optimal Coalition Structure Generation via Offline Coalition Selection and Graph-Based Search [61.08720171136229]
本稿では,3つの革新的手法のハイブリッド化に基づく問題に対する新しいアルゴリズムSMARTを提案する。
これらの2つの手法は動的プログラミングに基づいており、評価のために選択された連立関係とアルゴリズムの性能の強力な関係を示す。
我々の手法は、問題にアプローチする新しい方法と、その分野に新しいレベルの精度をもたらす。
論文 参考訳(メタデータ) (2024-07-22T23:24:03Z) - Serverless Federated AUPRC Optimization for Multi-Party Collaborative
Imbalanced Data Mining [119.89373423433804]
有効指標としてAUPRC(Area Under Precision-Recall)を導入した。
サーバーレスのマルチパーティ共同トレーニングは、サーバーノードのボトルネックを避けることで通信コストを削減できる。
本稿では,AUPRCを直接最適化する ServerLess biAsed sTochastic gradiEnt (SLATE) アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-08-06T06:51:32Z) - The Viability of Domain Constrained Coalition Formation for Robotic
Collectives [0.0]
軍事・災害対応アプリケーションは、複数の協調作業を行うロボット集団の能力の恩恵を受けることができる。
協調形成アルゴリズムは、適切なタスクチームへの集合ロボットの割り当てを促進する可能性がある。
この写本は、非常に大規模な集団のための連立形成アルゴリズムの設計に固有の課題を特定する。
論文 参考訳(メタデータ) (2023-06-08T23:28:41Z) - Decentralized Training of Foundation Models in Heterogeneous
Environments [77.47261769795992]
GPT-3 や PaLM のようなトレーニング基盤モデルは、非常に高価である。
ヘテロジニアスネットワーク上での分散型システムにおけるモデル並列化を用いた大規模基盤モデルのトレーニングに関する最初の研究について述べる。
論文 参考訳(メタデータ) (2022-06-02T20:19:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。