論文の概要: Distributed Online Rollout for Multivehicle Routing in Unmapped Environments

• arxiv url: http://arxiv.org/abs/2305.15596v2
• Date: Mon, 12 Feb 2024 18:03:29 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-14 00:51:18.994745
• Title: Distributed Online Rollout for Multivehicle Routing in Unmapped Environments
• Title（参考訳）: 非マッピング環境におけるマルチ車両ルーティングのための分散オンラインロールアウト
• Authors: Jamison W. Weber, Dhanush R. Giriyan, Devendra R. Parkar, Andr\'ea W. Richa, Dimitri P. Bertsekas
• Abstract要約: 我々は、よく知られた多車両ルーティング問題に対して、完全に分散し、オンラインでスケーラブルな強化学習アルゴリズムを提案する。 エージェントはローカルクラスタに自己組織化し、各クラスタにローカルにマルチエージェントロールアウトスキームを独立に適用する。 提案アルゴリズムは, 放射半径の2倍と3倍の精度で, 基本方針よりも約2倍のコスト向上を実現している。
• 参考スコア（独自算出の注目度）: 0.8437187555622164
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work we consider a generalization of the well-known multivehicle routing problem: given a network, a set of agents occupying a subset of its nodes, and a set of tasks, we seek a minimum cost sequence of movements subject to the constraint that each task is visited by some agent at least once. The classical version of this problem assumes a central computational server that observes the entire state of the system perfectly and directs individual agents according to a centralized control scheme. In contrast, we assume that there is no centralized server and that each agent is an individual processor with no a priori knowledge of the underlying network (including task and agent locations). Moreover, our agents possess strictly local communication and sensing capabilities (restricted to a fixed radius around their respective locations), aligning more closely with several real-world multiagent applications. These restrictions introduce many challenges that are overcome through local information sharing and direct coordination between agents. We present a fully distributed, online, and scalable reinforcement learning algorithm for this problem whereby agents self-organize into local clusters and independently apply a multiagent rollout scheme locally to each cluster. We demonstrate empirically via extensive simulations that there exists a critical sensing radius beyond which the distributed rollout algorithm begins to improve over a greedy base policy. This critical sensing radius grows proportionally to the $\log^*$ function of the size of the network, and is, therefore, a small constant for any relevant network. Our decentralized reinforcement learning algorithm achieves approximately a factor of two cost improvement over the base policy for a range of radii bounded from below and above by two and three times the critical sensing radius, respectively.
• Abstract（参考訳）: 本研究では,ネットワーク,ノードのサブセットを占有するエージェント群,タスク群が与えられた場合,各タスクが少なくとも1回はエージェントに訪問されるという制約を満たした最小コストの動作列を求める。 この問題の古典的なバージョンは、システムの状態を完全に監視し、集中制御方式に従って個々のエージェントに指示する中央計算サーバを想定している。 対照的に、集中型サーバはなく、各エージェントは、基盤となるネットワーク(タスクとエージェントの位置を含む)の事前知識を持たない個々のプロセッサである、と仮定する。 さらに、エージェントは、厳密な局所的コミュニケーションとセンシング能力(それぞれの位置の固定半径に制限される)を持ち、現実世界の複数のマルチエージェントアプリケーションとより密接に連携している。 これらの制限は、ローカル情報共有とエージェント間の直接調整によって克服される多くの課題をもたらす。 この問題に対して,エージェントをローカルクラスタに自己組織化し,各クラスタに個別にマルチエージェントロールアウトスキームを適用する,完全分散,オンライン,スケーラブルな強化学習アルゴリズムを提案する。 我々は,分散ロールアウトアルゴリズムが欲望ベースポリシーよりも改善し始める臨界センシング半径が存在することを,広範囲なシミュレーションにより実証的に示す。 この臨界センシング半径は、ネットワークの大きさの$\log^*$関数に比例して増加し、従って、関連するネットワークに対して小さな定数である。 分散強化学習アルゴリズムは, 臨界センシング半径の2倍, 3倍の範囲のradiiのベースポリシーに対して, 約2倍のコスト改善を実現する。

関連論文リスト

• Performance-Aware Self-Configurable Multi-Agent Networks: A Distributed Submodular Approach for Simultaneous Coordination and Network Design [3.5527561584422465]
  本稿では、AlterNAting Coordination and Network-Design Algorithm(Anaconda)を紹介する。 Anacondaはスケーラブルなアルゴリズムで、ほぼ最適性を保証する。 地域モニタリングのシミュレーションシナリオを実演し,それを最先端のアルゴリズムと比較する。
  論文  参考訳（メタデータ） (2024-09-02T18:11:33Z)
• Networked Communication for Mean-Field Games with Function Approximation and Empirical Mean-Field Estimation [59.01527054553122]
  分散エージェントは、経験的システムの単一かつ非エポゾディックな実行から平均フィールドゲームにおける平衡を学ぶことができる。 既存の設定に関数近似を導入し,Munchausen Online Mirror Descent 方式で描画する。 また, エージェントが局所的な周辺地域に基づいて, グローバルな経験分布を推定できる新しいアルゴリズムも提供する。
  論文  参考訳（メタデータ） (2024-08-21T13:32:46Z)
• DePAint: A Decentralized Safe Multi-Agent Reinforcement Learning Algorithm considering Peak and Average Constraints [1.1549572298362787]
  本稿では,この問題を解決するために,モーメントに基づく分散勾配法DePaintを提案する。 これは、ピーク制約と平均制約の両方を考慮した、プライバシ保存で完全に分散化されたマルチエージェント強化学習アルゴリズムとしては初めてのものである。
  論文  参考訳（メタデータ） (2023-10-22T16:36:03Z)
• Multi-Agent Neural Rewriter for Vehicle Routing with Limited Disclosure of Costs [65.23158435596518]
  チームのマルコフゲームとして、部分的に観測可能なコストでマルチサイクルルーティング問題を解く。 我々のマルチエージェント強化学習アプローチである、いわゆるマルチエージェントニューラルリライタは、1エージェントニューラルリライタを利用して、反復的に書き換えるソリューションによって問題を解決する。
  論文  参考訳（メタデータ） (2022-06-13T09:17:40Z)
• AoI-Aware Resource Allocation for Platoon-Based C-V2X Networks via Multi-Agent Multi-Task Reinforcement Learning [22.890835786710316]
  本稿は,小隊の無線リソース管理を意識した情報年齢(AoI)の問題について検討する。 複数の自律型プラトンは、C-V2X通信技術を利用して、協力的認識メッセージ(CAM)をフォロワーに広める。 我々は,マルチエージェント強化学習(marl)に基づく分散リソース割当フレームワークを活用し,各小隊リーダ(pl)がエージェントとして行動し,環境と相互作用して最適方針を学ぶ。
  論文  参考訳（メタデータ） (2021-05-10T08:39:56Z)
• Competing Adaptive Networks [56.56653763124104]
  適応エージェントのチーム間での分散競争のためのアルゴリズムを開発する。 本稿では,生成的対向ニューラルネットワークの分散学習への応用について述べる。
  論文  参考訳（メタデータ） (2021-03-29T14:42:15Z)
• Learning Connectivity for Data Distribution in Robot Teams [96.39864514115136]
  グラフニューラルネットワーク(GNN)を用いたアドホックネットワークにおけるデータ分散のためのタスク非依存,分散化,低レイテンシ手法を提案する。 当社のアプローチは、グローバル状態情報に基づいたマルチエージェントアルゴリズムを各ロボットで利用可能にすることで機能させます。 我々は,情報の平均年齢を報酬関数として強化学習を通じて分散gnn通信政策を訓練し,タスク固有の報酬関数と比較してトレーニング安定性が向上することを示す。
  論文  参考訳（メタデータ） (2021-03-08T21:48:55Z)
• Decentralized Control with Graph Neural Networks [147.84766857793247]
  分散コントローラを学習するグラフニューラルネットワーク(GNN)を用いた新しいフレームワークを提案する。 GNNは、自然分散アーキテクチャであり、優れたスケーラビリティと転送性を示すため、タスクに適している。 分散コントローラの学習におけるGNNの可能性を説明するために、群れとマルチエージェントパス計画の問題を検討する。
  論文  参考訳（メタデータ） (2020-12-29T18:59:14Z)
• Multi-Agent Decentralized Belief Propagation on Graphs [0.0]
  対話的部分観測可能なマルコフ決定過程(I-POMDP)の問題点を考察する。 本稿では,この問題に対する分散的信念伝達アルゴリズムを提案する。 我々の研究は、ネットワーク化されたマルチエージェントI-POMDPのための分散的信念伝播アルゴリズムの最初の研究である。
  論文  参考訳（メタデータ） (2020-11-06T18:16:26Z)
• F2A2: Flexible Fully-decentralized Approximate Actor-critic for Cooperative Multi-agent Reinforcement Learning [110.35516334788687]
  分散マルチエージェント強化学習アルゴリズムは複雑なアプリケーションでは実践的でないことがある。 本稿では,大規模で汎用的なマルチエージェント設定を扱える,柔軟な完全分散型アクター批判型MARLフレームワークを提案する。 当社のフレームワークは,大規模環境におけるスケーラビリティと安定性を実現し,情報伝達を低減できる。
  論文  参考訳（メタデータ） (2020-04-17T14:56:29Z)

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

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