論文の概要: Distributed Online Rollout for Multivehicle Routing in Unmapped
Environments
- arxiv url: http://arxiv.org/abs/2305.15596v1
- Date: Wed, 24 May 2023 22:06:44 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-26 18:22:12.715523
- 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.9449650062296822
- 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倍のコスト改善を実現する。
関連論文リスト
- The challenge of redundancy on multi-agent value factorisation [12.63182277116319]
協調型マルチエージェント強化学習(MARL)の分野において、標準パラダイムは集中型トレーニングと分散実行の利用である。
そこで我々は,LRP(Layerwise Relevance propagation)を利用して,結合値関数の学習と局所報酬信号の生成を分離する手法を提案する。
VDNとQmixの両方のベースラインの性能は冗長エージェントの数によって低下するが、RDNは影響を受けない。
論文 参考訳(メタデータ) (2023-03-28T20:41:12Z) - Distributed-Training-and-Execution Multi-Agent Reinforcement Learning
for Power Control in HetNet [48.96004919910818]
We propose a multi-agent Deep reinforcement learning (MADRL) based power control scheme for the HetNet。
エージェント間の協調を促進するために,MADRLシステムのためのペナルティベースQラーニング(PQL)アルゴリズムを開発した。
このように、エージェントのポリシーは、他のエージェントによってより容易に学習でき、より効率的なコラボレーションプロセスをもたらす。
論文 参考訳(メタデータ) (2022-12-15T17:01:56Z) - Multi-Agent Neural Rewriter for Vehicle Routing with Limited Disclosure
of Costs [65.23158435596518]
チームのマルコフゲームとして、部分的に観測可能なコストでマルチサイクルルーティング問題を解く。
我々のマルチエージェント強化学習アプローチである、いわゆるマルチエージェントニューラルリライタは、1エージェントニューラルリライタを利用して、反復的に書き換えるソリューションによって問題を解決する。
論文 参考訳(メタデータ) (2022-06-13T09:17:40Z) - Resource-Aware Distributed Submodular Maximization: A Paradigm for
Multi-Robot Decision-Making [3.5788754401889022]
Resource-Aware Distributed Greedyは、各ロボットのオンボードリソースを独立して考慮した最初のアルゴリズムである。
RAGは、中央集権化のトレードオフを、グローバルな準最適性、分散化、ほぼ最小のオンボード計算、通信、メモリリソースのトレードオフとバランス付けます。
論文 参考訳(メタデータ) (2022-04-15T15:47:05Z) - Dimension-Free Rates for Natural Policy Gradient in Multi-Agent
Reinforcement Learning [22.310861786709538]
協調型マルチエージェント強化学習のためのスケーラブルなアルゴリズムを提案する。
このアルゴリズムは,次元自由な統計量と計算量とで,グローバルな最適ポリシーに収束することを示す。
論文 参考訳(メタデータ) (2021-09-23T23:38:15Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。