論文の概要: Large-scale, Dynamic and Distributed Coalition Formation with Spatial and Temporal Constraints

• arxiv url: http://arxiv.org/abs/2106.00379v1
• Date: Tue, 1 Jun 2021 10:41:49 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-02 21:21:45.890969
• Title: Large-scale, Dynamic and Distributed Coalition Formation with Spatial and Temporal Constraints
• Title（参考訳）: 空間的・時間的制約を伴う大規模・動的・分散連立形成
• Authors: Luca Capezzuto, Danesh Tarapore, and Sarvapali D. Ramchurn
• Abstract要約: 空間的制約問題 (CFSTP) と時間的制約問題 (CFSTP) はマルチエージェントタスク割り当て問題である。 完了したタスクの数を最大化するために、エージェントは連立を結成し、解散し、改革することで協力する必要がある。 D-CTSは、最初の大規模、動的、分散CFSTPベンチマークを設定。
• 参考スコア（独自算出の注目度）: 11.835884261097958
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: The Coalition Formation with Spatial and Temporal constraints Problem (CFSTP) is a multi-agent task allocation problem in which few agents have to perform many tasks, each with its deadline and workload. To maximize the number of completed tasks, the agents need to cooperate by forming, disbanding and reforming coalitions. The original mathematical programming formulation of the CFSTP is difficult to implement, since it is lengthy and based on the problematic Big-M method. In this paper, we propose a compact and easy-to-implement formulation. Moreover, we design D-CTS, a distributed version of the state-of-the-art CFSTP algorithm. Using public London Fire Brigade records, we create a dataset with $347588$ tasks and a test framework that simulates the mobilization of firefighters in dynamic environments. In problems with up to $150$ agents and $3000$ tasks, compared to DSA-SDP, a state-of-the-art distributed algorithm, D-CTS completes $3.79\% \pm [42.22\%, 1.96\%]$ more tasks, and is one order of magnitude more efficient in terms of communication overhead and time complexity. D-CTS sets the first large-scale, dynamic and distributed CFSTP benchmark.
• Abstract（参考訳）: 時間的制約問題と時間的制約問題(cfstp)による連立形成は、複数のエージェントがそれぞれ期限とワークロードで多くのタスクを実行しなければならないマルチエージェントタスク割り当て問題である。 完了したタスクの数を最大化するために、エージェントは連合を形成し、解散し、改革することで協力する必要がある。 CFSTPの元々の数学的プログラミングの定式化は、長大で問題のあるBig-M法に基づいているため、実装が難しい。 本稿では,コンパクトで実装が容易な定式化を提案する。 さらに、最先端CFSTPアルゴリズムの分散バージョンであるD-CTSを設計する。 ロンドン消防団の記録を使って、347588ドルのタスクと、動的環境における消防士の動員をシミュレートするテストフレームワークを備えたデータセットを作成します。 最先端の分散アルゴリズムであるDSA-SDPと比較して、150ドルのエージェントと3000ドルのタスクを持つ問題では、D-CTSは3.79\% \pm [42.22\%, 1.96\%]$以上のタスクを完了し、通信オーバーヘッドと時間複雑性の点で1桁の効率である。 D-CTSは、最初の大規模、動的、分散CFSTPベンチマークを設定。

関連論文リスト

• PARTNR: A Benchmark for Planning and Reasoning in Embodied Multi-agent Tasks [57.89516354418451]
  我々は,HumaN-Robotコラボレーション(PARTNR)における計画と推論タスクのベンチマークを示す。 大規模言語モデル(LLM)を用いた半自動タスク生成パイプラインを用いる。 我々は、計画、知覚、スキル実行の軸を越えて、PartinNRタスクにおける最先端のLCMを分析します。
  論文  参考訳（メタデータ） (2024-10-31T17:53:12Z)
• Conservative DDPG -- Pessimistic RL without Ensemble [48.61228614796803]
  DDPGは過大評価バイアス問題によって妨げられている。 このバイアスに対する伝統的な解決策は、アンサンブルに基づく方法を含んでいる。 本稿では,Q$-targetと行動クローン(BC)損失ペナルティを組み込んだ簡単なソリューションを提案する。
  論文  参考訳（メタデータ） (2024-03-08T23:59:38Z)
• A Dynamic LLM-Powered Agent Network for Task-Oriented Agent Collaboration [55.35849138235116]
  本稿では,様々なタスクやドメインに対する動的コミュニケーション構造において,候補からエージェントのチームを自動的に選択する手法を提案する。 具体的には, LLMを利用したエージェント協調のための動的LLMパワーエージェントネットワーク(textDyLAN$)というフレームワークを構築した。 我々は、コード生成、意思決定、一般的な推論、算術的推論タスクにおいて、適度な計算コストで、DyLANが強力なベースラインを上回ることを実証する。
  論文  参考訳（メタデータ） (2023-10-03T16:05:48Z)
• Digital Twin-Assisted Efficient Reinforcement Learning for Edge Task Scheduling [10.777592783012702]
  本稿では,RLの性能と収束性を改善するために,Digital Twin(DT)を用いたRLベースのタスクスケジューリング手法を提案する。 DT支援非同期Qラーニング(DTAQL)とDT支援Qラーニング(DTEQL)という2つのアルゴリズムがタスクスケジューリング決定を行うように設計されている。
  論文  参考訳（メタデータ） (2022-08-02T23:26:08Z)
• Controllable Dynamic Multi-Task Architectures [92.74372912009127]
  本稿では,そのアーキテクチャと重みを動的に調整し,所望のタスク選択とリソース制約に適合させる制御可能なマルチタスクネットワークを提案する。 本稿では,タスク親和性と分岐正規化損失を利用した2つのハイパーネットの非交互トレーニングを提案し,入力の嗜好を取り入れ,適応重み付き木構造モデルを予測する。
  論文  参考訳（メタデータ） (2022-03-28T17:56:40Z)
• Multi-Agent Routing and Scheduling Through Coalition Formation [13.302347777866757]
  この問題をマルチエージェントルーティングと協調形成(marsc)によるスケジューリングと呼ぶ。 私たちは、Time Windowsで重要なチームオリエンテーション問題を一般化していることを示しています。 リアルタイムシステムで一般的に使用されるEarliest Deadline Firstアプローチよりも最大3.25倍優れたソリューションを見つけます。
  論文  参考訳（メタデータ） (2021-05-02T11:53:44Z)
• A Cordial Sync: Going Beyond Marginal Policies for Multi-Agent Embodied Tasks [111.34055449929487]
  エージェントが協力して家具をリビングルームに移動させるという,新しいタスクFurnMoveを紹介した。 既存のタスクとは異なり、FurnMoveはエージェントが各タイミングで調整する必要がある。 既存の分散化されたアクションサンプリング手順は、表現力のある共同アクションポリシーを許さない。 SynC-policiesとCORDIALを用いて、我々のエージェントはFurnMoveで58%の完成率を達成する。
  論文  参考訳（メタデータ） (2020-07-09T17:59:57Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。 都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
  論文  参考訳（メタデータ） (2020-05-27T01:10:41Z)
• Anytime and Efficient Coalition Formation with Spatial and Temporal Constraints [18.029278336665012]
  現在の最先端の CFSTP ソルバである Coalition Formation with Look-Ahead (CFLA) アルゴリズムには2つの制限がある。 我々は、改善されたルックアヘッド(CFLA2)を備えた結合形成(Coalition Formation)と呼ばれる拡張を定義し、より良いパフォーマンスを実現する。 CFLA2におけるCFLAの限界を排除できないため、CFSTPを解くための新しいアルゴリズムも開発している。
  論文  参考訳（メタデータ） (2020-03-30T20:42:56Z)

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

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