論文の概要: Optimizing Crowd-Aware Multi-Agent Path Finding through Local Broadcasting with Graph Neural Networks
- arxiv url: http://arxiv.org/abs/2309.10275v2
- Date: Mon, 25 Mar 2024 20:28:22 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-28 01:10:34.103744
- Title: Optimizing Crowd-Aware Multi-Agent Path Finding through Local Broadcasting with Graph Neural Networks
- Title（参考訳）: グラフニューラルネットワークを用いた局所放送による集合認識多エージェント経路の最適化
- Authors: Phu Pham, Aniket Bera,
- Abstract要約: 混在環境におけるマルチエージェントパス探索 (MAPF) は, 移動計画において困難な問題となる。
本稿では,この問題を解決するために,クラウド対応の分散強化学習手法であるCRAMPを紹介する。
CRAMPは, メースパンと衝突数で測定された溶液品質を最大59%改善し, 従来の方法と比較して最大35%改善した。
- 参考スコア（独自算出の注目度）: 15.88107215224685
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Multi-Agent Path Finding (MAPF) in crowded environments presents a challenging problem in motion planning, aiming to find collision-free paths for all agents in the system. MAPF finds a wide range of applications in various domains, including aerial swarms, autonomous warehouse robotics, and self-driving vehicles. Current approaches to MAPF generally fall into two main categories: centralized and decentralized planning. Centralized planning suffers from the curse of dimensionality when the number of agents or states increases and thus does not scale well in large and complex environments. On the other hand, decentralized planning enables agents to engage in real-time path planning within a partially observable environment, demonstrating implicit coordination. However, they suffer from slow convergence and performance degradation in dense environments. In this paper, we introduce CRAMP, a novel crowd-aware decentralized reinforcement learning approach to address this problem by enabling efficient local communication among agents via Graph Neural Networks (GNNs), facilitating situational awareness and decision-making capabilities in congested environments. We test CRAMP on simulated environments and demonstrate that our method outperforms the state-of-the-art decentralized methods for MAPF on various metrics. CRAMP improves the solution quality up to 59% measured in makespan and collision count, and up to 35% improvement in success rate in comparison to previous methods.
- Abstract（参考訳）: 混み合った環境におけるマルチエージェント経路探索(MAPF)は,システム内のすべてのエージェントに対して衝突のない経路を見つけることを目的として,動作計画において困難な問題を示す。
MAPFは、航空群、自律倉庫ロボット、自動運転車など、さまざまな分野の幅広い応用を見出している。
MAPFへの現在のアプローチは、一般的に中央集権と分散計画の2つの主要なカテゴリに分類される。
中央集権プランニングは、エージェントや状態の数が増加すると次元性の呪いに悩まされるため、大規模で複雑な環境ではうまくスケールしない。
一方、分散計画では、エージェントが部分的に観測可能な環境下でリアルタイムの経路計画に従事し、暗黙の協調を示すことができる。
しかし、それらは密集環境における緩やかな収束と性能劣化に悩まされている。
本稿では,グラフニューラルネットワーク(GNN)によるエージェント間の効率的なローカル通信を実現することにより,混雑環境における状況認識と意思決定の容易化を実現する,クラウド対応の分散強化学習手法であるCRAMPを紹介する。
シミュレーション環境でCRAMPを試験し,MAPFの最先端の分散化手法よりも優れた性能を示す。
CRAMPは, メースパンおよび衝突数で測定された溶液品質を最大59%改善し, 従来の方法と比較して最大35%改善した。
関連論文リスト
- Scalable Mechanism Design for Multi-Agent Path Finding [87.40027406028425]
MAPF (Multi-Agent Path Finding) は、複数のエージェントが同時に移動し、与えられた目標地点に向かって共有領域を通って衝突しない経路を決定する。
最適解を見つけることは、しばしば計算不可能であり、近似的な準最適アルゴリズムを用いることが不可欠である。
本稿では、MAPFのスケーラブルな機構設計の問題を紹介し、MAPFアルゴリズムを近似した3つの戦略防御機構を提案する。
論文 参考訳（メタデータ） (2024-01-30T14:26:04Z) - Learn to Follow: Decentralized Lifelong Multi-agent Pathfinding via
Planning and Learning [46.354187895184154]
マルチエージェントパスフィンディング(MAPF)問題は通常、グラフに制限されたエージェントの集合に対する競合のないパスの集合を見つけるよう要求する。
本研究では,エージェントの位置や目標に関する情報をすべて収集する中央制御器が存在しない場合の分散MAPF設定について検討する。
我々は,先行するエージェントに新たな目標を連続的に割り当てることを含むMAPFの実用上重要な寿命変化に焦点をあてる。
論文 参考訳（メタデータ） (2023-10-02T13:51:32Z) - AI planning in the imagination: High-level planning on learned abstract
search spaces [68.75684174531962]
我々は,エージェントが訓練中に学習する抽象的な検索空間において,エージェントが計画することを可能にする,PiZeroと呼ばれる新しい手法を提案する。
本研究では,旅行セールスマン問題,ソコバン問題,2048年,施設立地問題,パックマン問題など,複数の分野で評価を行った。
論文 参考訳（メタデータ） (2023-08-16T22:47:16Z) - Multi-Agent Terraforming: Efficient Multi-Agent Path Finding via
Environment Manipulation [12.401344261399613]
マルチエージェントパスフィニング(Multi-agent pathfinding)は、障害が散らばった環境において、開始時から目標地点まで、エージェントのチームが衝突のない経路を計画することに関心がある。
我々はMAPFの新たな拡張を導入し、Terraforming MAPF (tMAPF) と呼び、いくつかのエージェントが障害を移動して他のエージェントへの道をクリアする役割を担っている。
我々は、tMAPFに取り組むために、CBSとPBSという2つの最先端アルゴリズムを拡張し、静的な障害物設定で可能な限り優れた解を常に上回ることを示す。
論文 参考訳（メタデータ） (2022-03-20T12:18:35Z) - Learning Cooperation and Online Planning Through Simulation and Graph
Convolutional Network [5.505634045241288]
マルチエージェント協調環境のためのシミュレーションベースのオンライン計画アルゴリズム「SiCLOP」を導入する。
具体的には、SiCLOPはMCTS(Monte Carlo Tree Search)を補完し、協調学習にコーディネーショングラフ(CG)とグラフニューラルネットワーク(GCN)を使用する。
また、アクション空間を効果的に刈り取ることによりスケーラビリティも向上する。
論文 参考訳（メタデータ） (2021-10-16T05:54:32Z) - Locality Matters: A Scalable Value Decomposition Approach for
Cooperative Multi-Agent Reinforcement Learning [52.7873574425376]
協調型マルチエージェント強化学習(MARL)は,エージェント数で指数関数的に大きい状態空間と動作空間により,スケーラビリティの問題に直面する。
本稿では,学習分散実行パラダイムに局所報酬を組み込んだ,新しい価値に基づくマルチエージェントアルゴリズム LOMAQ を提案する。
論文 参考訳（メタデータ） (2021-09-22T10:08:15Z) - Effects of Smart Traffic Signal Control on Air Quality [0.0]
マルチエージェント深部強化学習(MARL)は交通システムにおいて実験的に研究されている。
MA2Cと呼ばれる、確立されたアドバンテージアクター・クリティカル(A2C)アルゴリズムのマルチエージェント版が最近開発され、エージェント間の通信の有望なアイデアを活用している。
この観点から、エージェントは他のエージェントと戦略を共有し、エージェントの数や多様性が増大しても学習プロセスを安定化させる。
論文 参考訳（メタデータ） (2021-07-06T02:48:42Z) - Decentralised Approach for Multi Agent Path Finding [6.599344783327053]
MAPF (Multi Agent Path Finding) は、空間的に拡張されたエージェントに対する競合のない経路の同定を必要とする。
これらは、Convoy Movement ProblemやTraning Schedulingといった現実世界の問題に適用できる。
提案手法であるDecentralized Multi Agent Path Finding (DeMAPF) は、MAPFを経路計画と割り当ての問題の系列として扱う。
論文 参考訳（メタデータ） (2021-06-03T18:07:26Z) - Optimizing Mixed Autonomy Traffic Flow With Decentralized Autonomous
Vehicles and Multi-Agent RL [63.52264764099532]
本研究では、完全分散制御方式を用いて、混合自律環境でのボトルネックのスループットを向上させる自動運転車の能力について検討する。
この問題にマルチエージェント強化アルゴリズムを適用し、5%の浸透速度で20%から40%の浸透速度で33%までのボトルネックスループットの大幅な改善が達成できることを実証した。
論文 参考訳（メタデータ） (2020-10-30T22:06:05Z) - Decentralized MCTS via Learned Teammate Models [89.24858306636816]
本稿では,モンテカルロ木探索に基づくトレーニング可能なオンライン分散計画アルゴリズムを提案する。
深層学習と畳み込みニューラルネットワークを用いて正確なポリシー近似を作成可能であることを示す。
論文 参考訳（メタデータ） (2020-03-19T13:10:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。