論文の概要: Where Paths Collide: A Comprehensive Survey of Classic and Learning-Based Multi-Agent Pathfinding

• arxiv url: http://arxiv.org/abs/2505.19219v1
• Date: Sun, 25 May 2025 16:28:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-27 16:58:42.98687
• Title: Where Paths Collide: A Comprehensive Survey of Classic and Learning-Based Multi-Agent Pathfinding
• Title（参考訳）: where Paths Collide: 古典的, 学習的パスフィニングに関する総合的な調査
• Authors: Shiyue Wang, Haozheng Xu, Yuhan Zhang, Jingran Lin, Changhong Lu, Xiangfeng Wang, Wenhao Li,
• Abstract要約: MAPF(Multi-Agent Path Finding)は、人工知能とロボット工学の基本的な問題である。 この調査は、MAPF研究における古典的アルゴリズムアプローチと新たな学習手法との長年の隔たりを橋渡しする。
• 参考スコア（独自算出の注目度）: 19.93293239540926
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Multi-Agent Path Finding (MAPF) is a fundamental problem in artificial intelligence and robotics, requiring the computation of collision-free paths for multiple agents navigating from their start locations to designated goals. As autonomous systems become increasingly prevalent in warehouses, urban transportation, and other complex environments, MAPF has evolved from a theoretical challenge to a critical enabler of real-world multi-robot coordination. This comprehensive survey bridges the long-standing divide between classical algorithmic approaches and emerging learning-based methods in MAPF research. We present a unified framework that encompasses search-based methods (including Conflict-Based Search, Priority-Based Search, and Large Neighborhood Search), compilation-based approaches (SAT, SMT, CSP, ASP, and MIP formulations), and data-driven techniques (reinforcement learning, supervised learning, and hybrid strategies). Through systematic analysis of experimental practices across 200+ papers, we uncover significant disparities in evaluation methodologies, with classical methods typically tested on larger-scale instances (up to 200 by 200 grids with 1000+ agents) compared to learning-based approaches (predominantly 10-100 agents). We provide a comprehensive taxonomy of evaluation metrics, environment types, and baseline selections, highlighting the need for standardized benchmarking protocols. Finally, we outline promising future directions including mixed-motive MAPF with game-theoretic considerations, language-grounded planning with large language models, and neural solver architectures that combine the rigor of classical methods with the flexibility of deep learning. This survey serves as both a comprehensive reference for researchers and a practical guide for deploying MAPF solutions in increasingly complex real-world applications.
• Abstract（参考訳）: MAPF(Multi-Agent Path Finding)は、人工知能とロボティクスの基本的な問題であり、開始地点から指定された目標に移動する複数のエージェントの衝突のない経路の計算を必要とする。 倉庫、都市交通、その他の複雑な環境において自律的なシステムがますます普及するにつれて、MAPFは理論上の課題から現実のマルチロボット協調の重要な実現方法へと進化してきた。 この包括的調査は、MAPF研究における古典的アルゴリズムアプローチと新しい学習手法との長年の隔たりを橋渡しする。 本稿では,コンフリクトベース検索,優先度ベース検索,大規模近傍探索,SAT,SMT,CSP,ASP,MIPの形式化),データ駆動型手法(強化学習,教師あり学習,ハイブリッド戦略)を包含する統合フレームワークを提案する。 200以上の論文にまたがる実験的な実践を体系的に分析することで、古典的な手法は、学習に基づくアプローチ(典型的には10-100エージェント)と比較して、大規模インスタンス(1000以上のエージェントを持つ200から200までのグリッド)でテストされる。 評価指標,環境タイプ,ベースライン選択を包括的に分類し,標準化されたベンチマークプロトコルの必要性を強調した。 最後に,ゲーム理論を考慮した混合モチベーションMAPF,大規模言語モデルによる言語グランドプランニング,古典的手法の厳密さと深層学習の柔軟性を組み合わせたニューラルソルバアーキテクチャなど,将来的な方向性を概説する。 この調査は、研究者の包括的なリファレンスであり、ますます複雑な現実世界のアプリケーションにMAPFソリューションをデプロイするための実践的なガイドである。

関連論文リスト

• Large Language Model Agent: A Survey on Methodology, Applications and Challenges [88.3032929492409]
  大きな言語モデル(LLM)エージェントは、目標駆動の振る舞いと動的適応能力を持ち、人工知能への重要な経路を示す可能性がある。 本調査は, LLMエージェントシステムを方法論中心の分類法により体系的に分解する。 私たちの作業は、エージェントの構築方法、コラボレーション方法、時間の経過とともにどのように進化するか、という、統一されたアーキテクチャの視点を提供します。
  論文  参考訳（メタデータ） (2025-03-27T12:50:17Z)
• A Comprehensive Survey on Multi-Agent Cooperative Decision-Making: Scenarios, Approaches, Challenges and Perspectives [6.277211882332452]
  多エージェント協調意思決定は、複数のエージェントが協力して、確立されたタスクを完了し、特定の目的を達成する。 これらの技術は、自律運転、ドローンナビゲーション、災害救助、シミュレートされた軍事的対立といった現実のシナリオに広く応用されている。
  論文  参考訳（メタデータ） (2025-03-17T17:45:46Z)
• SIGMA: Sheaf-Informed Geometric Multi-Agent Pathfinding [4.801673346687721]
  MAPF(Multi-Agent Path Finding)問題は、既知の、潜在的に障害物のある環境において、複数のエージェントに対して最も短く、衝突のない経路を決定することを目的としている。 本稿では,分散化された深層強化学習にせん断理論を適用し,エージェント同士の幾何学的相互依存性を学習できるようにする新しい枠組みを提案する。 特に,ニューラルネットワークを組み込んで,せん断理論に基づく潜在空間のコンセンサスを概ねモデル化し,自己教師型学習を通じて学習する。
  論文  参考訳（メタデータ） (2025-02-10T13:17:34Z)
• POGEMA: A Benchmark Platform for Cooperative Multi-Agent Pathfinding [76.67608003501479]
  POGEMAは、学習のための高速環境、問題インスタンスジェネレータ、可視化ツールキットを含む、総合的なツールセットである。 また、プライマリ評価指標に基づいて計算されるドメイン関連メトリクスの範囲を規定する評価プロトコルを導入し、定義する。 この比較の結果は、様々な最先端のMARL、検索ベース、ハイブリッド手法を含む。
  論文  参考訳（メタデータ） (2024-07-20T16:37:21Z)
• An Extensible Benchmark Suite for Learning to Simulate Physical Systems [60.249111272844374]
  我々は、統一されたベンチマークと評価プロトコルへの一歩を踏み出すために、一連のベンチマーク問題を導入する。 本稿では,4つの物理系と,広く使用されている古典的時間ベースおよび代表的なデータ駆動手法のコレクションを提案する。
  論文  参考訳（メタデータ） (2021-08-09T17:39:09Z)
• Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning [89.31889875864599]
  マルチエージェントシステムにおける学習に有効なモデルベース強化学習アルゴリズムを提案する。 我々の理論的な貢献は、MFCのモデルベース強化学習における最初の一般的な後悔の限界である。 コア最適化問題の実用的なパラメトリゼーションを提供する。
  論文  参考訳（メタデータ） (2021-07-08T18:01:02Z)

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

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