論文の概要: Scaling Lifelong Multi-Agent Path Finding to More Realistic Settings: Research Challenges and Opportunities
- arxiv url: http://arxiv.org/abs/2404.16162v1
- Date: Wed, 24 Apr 2024 19:37:18 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-26 16:02:40.911671
- Title: Scaling Lifelong Multi-Agent Path Finding to More Realistic Settings: Research Challenges and Opportunities
- Title（参考訳）: より現実的な環境へ向けた生涯マルチエージェントパスのスケーリング:研究課題と機会
- Authors: He Jiang, Yulun Zhang, Rishi Veerapaneni, Jiaoyang Li,
- Abstract要約: 我々は2023年のLMAPFコンペティションに勝利のアプローチを提示する。
最初の課題は、限られた計画時間内で高品質なLMAPFソリューションを探すことである。
第2の課題は、LMAPFアルゴリズムにおける筋萎縮と行動の影響を緩和することである。
第3の課題は、文学と現実世界の応用で使用されるLMAPFモデルのギャップを埋めることである。
- 参考スコア（独自算出の注目度）: 44.292720085661585
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Multi-Agent Path Finding (MAPF) is the problem of moving multiple agents from starts to goals without collisions. Lifelong MAPF (LMAPF) extends MAPF by continuously assigning new goals to agents. We present our winning approach to the 2023 League of Robot Runners LMAPF competition, which leads us to several interesting research challenges and future directions. In this paper, we outline three main research challenges. The first challenge is to search for high-quality LMAPF solutions within a limited planning time (e.g., 1s per step) for a large number of agents (e.g., 10,000) or extremely high agent density (e.g., 97.7%). We present future directions such as developing more competitive rule-based and anytime MAPF algorithms and parallelizing state-of-the-art MAPF algorithms. The second challenge is to alleviate congestion and the effect of myopic behaviors in LMAPF algorithms. We present future directions, such as developing moving guidance and traffic rules to reduce congestion, incorporating future prediction and real-time search, and determining the optimal agent number. The third challenge is to bridge the gaps between the LMAPF models used in the literature and real-world applications. We present future directions, such as dealing with more realistic kinodynamic models, execution uncertainty, and evolving systems.
- Abstract（参考訳）: MAPF(Multi-Agent Path Finding)は、複数のエージェントを衝突なしに開始点から目標へ移動させる問題である。
Lifelong MAPF (LMAPF) は、エージェントに新たな目標を継続的に割り当てることでMAPFを拡張する。
我々は2023年のLMAPFコンペで優勝したロボットランナーのLMAPFに対して,いくつかの興味深い研究課題と今後の方向性を提示する。
本稿では,3つの主要な研究課題について概説する。
最初の課題は、多数のエージェント(例えば1万個)や非常に高いエージェント密度(例えば97.7%)に対して、限られた計画時間(例えば1ステップあたり1秒)で高品質なLMAPFソリューションを探すことである。
我々は、より競争力のあるルールベースのMAPFアルゴリズムや最先端MAPFアルゴリズムの並列化など、今後の方向性を示す。
第2の課題は、LMAPFアルゴリズムにおける混雑と筋活動の影響を緩和することである。
本稿では,渋滞軽減のための移動誘導や交通ルールの開発,将来予測とリアルタイム検索の導入,最適なエージェント数の決定など,今後の方向性を示す。
第3の課題は、文学と現実世界の応用で使用されるLMAPFモデルのギャップを埋めることである。
我々は,より現実的なキノダイナミックモデル,実行の不確実性,システムの進化といった今後の方向性を提示する。
関連論文リスト
- Deploying Ten Thousand Robots: Scalable Imitation Learning for Lifelong Multi-Agent Path Finding [20.289593818360938]
Lifelong Multi-Agent Path Finding (LMAPF) はMAPFの変種であり、エージェントは絶えず新しい目標に割り当てられる。
近年,この分野は個別の局所観測に基づいて,一段階の動作を反応的に生成する学習的手法を取り入れている。
本研究は,新しい通信モジュールと系統的な単一ステップ衝突分解とグローバルガイダンス技術を導入した模倣学習に基づくLMAPFソルバを提案する。
論文 参考訳（メタデータ） (2024-10-28T18:13:15Z) - 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) - Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。
具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。
また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
論文 参考訳（メタデータ） (2023-07-25T12:33:53Z) - The Study of Highway for Lifelong Multi-Agent Path Finding [30.329065698451902]
現代のフルフィルメント倉庫では、エージェントが地図を横切り、終りのないタスクを完了し、そこへ到着する。
この課題に対処する目的は、スループットを最大化しながら、有限のランタイムで各エージェントのパスを見つけることである。
我々は,一発MAPFで主に研究されるハイウェイの考え方を探求し,エージェントが同じ方向に移動するように促すことにより,問題の複雑さを低減する。
論文 参考訳（メタデータ） (2023-04-09T11:21:22Z) - Traj-MAE: Masked Autoencoders for Trajectory Prediction [69.7885837428344]
軌道予測は、危険を予測して信頼性の高い自動運転システムを構築する上で重要な課題である。
本稿では,運転環境におけるエージェントの複雑な動作をよりよく表現する,軌道予測のための効率的なマスク付きオートエンコーダを提案する。
複数エージェント設定と単一エージェント設定の両方の実験結果から,Traj-MAEが最先端手法と競合する結果が得られることが示された。
論文 参考訳（メタデータ） (2023-03-12T16:23:27Z) - Multi-objective Conflict-based Search Using Safe-interval Path Planning [10.354181009277623]
低レベル探索のための新しい多目的セーフインターバルパス計画法 (MO-SIPP) アルゴリズムを利用するMO-CBS(Multi-objective conflict-based search)を提案する。
我々は, 平均低レベル探索時間において, 等級が大幅に改善されていることを示すために, 広範囲な数値計算結果を示す。
また,建設現場計画における提案アルゴリズムの適用可能性を示すケーススタディも提示する。
論文 参考訳（メタデータ） (2021-08-02T09:42:08Z) - Compilation-based Solvers for Multi-Agent Path Finding: a Survey,
Discussion, and Future Opportunities [7.766921168069532]
このトピックの過去の発展と現在の傾向から学んだ教訓を示し、その広範な影響について議論します。
最適MAPF解決のための2つの主要なアプローチは、(1)MAPFを直接解決する専用の検索ベース手法、(2)MAPFインスタンスを異なる確立された形式でインスタンスに還元するコンパイルベース手法である。
論文 参考訳（メタデータ） (2021-04-23T20:13:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。