論文の概要: Improving Learnt Local MAPF Policies with Heuristic Search
- arxiv url: http://arxiv.org/abs/2403.20300v1
- Date: Fri, 29 Mar 2024 17:16:20 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-01 15:05:12.186670
- Title: Improving Learnt Local MAPF Policies with Heuristic Search
- Title(参考訳): ヒューリスティック検索による学習型ローカルMAPFポリシーの改善
- Authors: Rishi Veerapaneni, Qian Wang, Kevin Ren, Arthur Jakobsson, Jiaoyang Li, Maxim Likhachev,
- Abstract要約: MAPF (Multi-Adnt Path Finding) は、エージェントのチームが目標地点に到達するための衝突のない経路を見つける問題である。
MAPFに対する現在の機械学習アプローチでは、このポテンシャルの表面を掻き傷始めた手法が提案されている。
我々は,学習ポリシーを用いた検索のモデルに依存しないいくつかの方法を示し,政策の成功率とスケーラビリティを著しく向上させる。
- 参考スコア(独自算出の注目度): 24.06091123268885
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Multi-agent path finding (MAPF) is the problem of finding collision-free paths for a team of agents to reach their goal locations. State-of-the-art classical MAPF solvers typically employ heuristic search to find solutions for hundreds of agents but are typically centralized and can struggle to scale when run with short timeouts. Machine learning (ML) approaches that learn policies for each agent are appealing as these could enable decentralized systems and scale well while maintaining good solution quality. Current ML approaches to MAPF have proposed methods that have started to scratch the surface of this potential. However, state-of-the-art ML approaches produce "local" policies that only plan for a single timestep and have poor success rates and scalability. Our main idea is that we can improve a ML local policy by using heuristic search methods on the output probability distribution to resolve deadlocks and enable full horizon planning. We show several model-agnostic ways to use heuristic search with learnt policies that significantly improve the policies' success rates and scalability. To our best knowledge, we demonstrate the first time ML-based MAPF approaches have scaled to high congestion scenarios (e.g. 20% agent density).
- Abstract(参考訳): MAPF (Multi-Adnt Path Finding) は、エージェントのチームが目標地点に到達するための衝突のない経路を見つける問題である。
最先端の古典的MAPFソルバは通常、数百のエージェントのソリューションを見つけるためにヒューリスティック検索を採用するが、通常は集中型であり、短いタイムアウトで実行するとスケールするのに苦労する。
各エージェントのポリシーを学習する機械学習(ML)アプローチは、優れたソリューション品質を維持しながら、分散システムを有効にし、適切にスケールできることをアピールしている。
MAPFに対する現在のMLアプローチでは、このポテンシャルの表面を掻き傷始めた手法が提案されている。
しかし、最先端のMLアプローチは、単一のタイムステップのみを計画し、成功率とスケーラビリティが劣る"ローカル"なポリシーを生成します。
本研究の主な考え方は,出力確率分布のヒューリスティックな探索手法を用いて,デッドロックを解消し,完全な地平線計画を可能にすることにより,ML局所ポリシーを改善することである。
学習ポリシーを用いたヒューリスティック検索のモデルに依存しないいくつかの方法を示し,政策の成功率と拡張性を大幅に向上させる。
我々の知る限り、MLベースのMAPFアプローチが初めて、高い混雑シナリオ(エージェント密度の20%など)にスケールしたことを実証する。
関連論文リスト
- Ensembling Prioritized Hybrid Policies for Multi-agent Pathfinding [18.06081009550052]
MARL(Multi-Agent Reinforcement Learning)をベースとしたMAPF(Multi-Agent Path Finding)が最近注目されている。
いくつかのMARL-MAPFメソッドは、あるエージェントが知覚できる情報を豊かにするためにコミュニケーションを使用する。
優先度付きハイブリッドポリシ(EPH)を組み込む新しい手法を提案する。
論文 参考訳(メタデータ) (2024-03-12T11:47:12Z) - Scalable Mechanism Design for Multi-Agent Path Finding [87.40027406028425]
MAPF (Multi-Agent Path Finding) は、複数のエージェントが同時に移動し、与えられた目標地点に向かって共有領域を通って衝突しない経路を決定する。
最適解を見つけることは、しばしば計算不可能であり、近似的な準最適アルゴリズムを用いることが不可欠である。
本稿では、MAPFのスケーラブルな機構設計の問題を紹介し、MAPFアルゴリズムを近似した3つの戦略防御機構を提案する。
論文 参考訳(メタデータ) (2024-01-30T14:26:04Z) - Decentralized Monte Carlo Tree Search for Partially Observable
Multi-agent Pathfinding [49.730902939565986]
マルチエージェントパスフィンディング問題は、グラフに閉じ込められたエージェントのグループに対するコンフリクトフリーパスのセットを見つけることである。
本研究では、エージェントが他のエージェントをローカルにのみ観察できる分散MAPF設定に焦点を当てた。
MAPFタスクのための分散マルチエージェントモンテカルロ木探索法を提案する。
論文 参考訳(メタデータ) (2023-12-26T06:57:22Z) - Learn to Follow: Decentralized Lifelong Multi-agent Pathfinding via
Planning and Learning [46.354187895184154]
マルチエージェントパスフィンディング(MAPF)問題は通常、グラフに制限されたエージェントの集合に対する競合のないパスの集合を見つけるよう要求する。
本研究では,エージェントの位置や目標に関する情報をすべて収集する中央制御器が存在しない場合の分散MAPF設定について検討する。
我々は,先行するエージェントに新たな目標を連続的に割り当てることを含むMAPFの実用上重要な寿命変化に焦点をあてる。
論文 参考訳(メタデータ) (2023-10-02T13:51:32Z) - Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding [29.76466191644455]
MAPF(Multi-Agent Path Finding)は、ロボット工学における基本的な問題であり、エージェントのチームに対して衝突のない経路の計算を求める。
本稿では,MAPFにエージェントを誘導する手法を提案する。
各エージェントが1つの宛先を持つワンショットMAPFと、エージェントが常に新しい宛先を割り当てる終身MAPFの2つの大規模設定でこのアイデアを評価する。
論文 参考訳(メタデータ) (2023-08-22T07:17:39Z) - Provably Learning Nash Policies in Constrained Markov Potential Games [90.87573337770293]
マルチエージェント強化学習(MARL)は、複数のエージェントによるシーケンシャルな意思決定問題に対処する。
制約マルコフゲーム(Constrained Markov Games, CMGs)は、安全なMARL問題の自然な定式化である。
論文 参考訳(メタデータ) (2023-06-13T13:08:31Z) - Local Optimization Achieves Global Optimality in Multi-Agent
Reinforcement Learning [139.53668999720605]
本稿では,各エージェントのローカルポリシーをバニラPPOと同様に更新するマルチエージェントPPOアルゴリズムを提案する。
マルコフゲームにおける標準正則条件と問題依存量により、我々のアルゴリズムはサブリニアレートで大域的最適ポリシーに収束することを示す。
論文 参考訳(メタデータ) (2023-05-08T16:20:03Z) - Distributed Heuristic Multi-Agent Path Finding with Communication [7.854890646114447]
大規模ロボットシステムにはMAPF(Multi-Agent Path Finding)が不可欠である。
近年,部分観測可能な環境下での分散警察の学習に強化学習(RL)を適用している。
本稿では,深層学習とコミュニケーションを組み合わせることで,MAPFの新たな学習手法を提案する。
論文 参考訳(メタデータ) (2021-06-21T18:50:58Z) - POMP: Pomcp-based Online Motion Planning for active visual search in
indoor environments [89.43830036483901]
本稿では, 屋内環境におけるオブジェクトのアクティブビジュアルサーチ(AVS)の最適ポリシーを, オンライン設定で学習する問題に焦点をあてる。
提案手法はエージェントの現在のポーズとRGB-Dフレームを入力として使用する。
提案手法を利用可能なAVDベンチマークで検証し,平均成功率0.76,平均パス長17.1とした。
論文 参考訳(メタデータ) (2020-09-17T08:23:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。