arXiv:2505.19219cs.AIcs.LG2025-05综述被引 14

系统梳理经典与学习型多智能体路径规划方法,揭示评估差异并推动标准化。

Where Paths Collide: A Comprehensive Survey of Classic and Learning-Based Multi-Agent Pathfinding

  • 构建统一框架整合搜索、编译与数据驱动三类方法
  • 发现经典方法在200×200网格上支持超1000智能体,学习方法多限于10-100个
  • 提出评估标准建议,适合研究者与工程部署者参考

多智能体路径规划(MAPF)是人工智能与机器人领域的基础问题,要求为多个智能体从起点到目标点计算无碰撞路径。随着自主系统在仓储、城市交通等复杂环境日益普及,MAPF已从理论挑战演变为多机器人协同的关键技术。本综述弥合了经典算法与新兴学习方法之间的长期分歧。我们提出一个统一框架,涵盖基于搜索的方法(如冲突基础搜索、优先级搜索、大邻域搜索)、基于编译的方法(SAT、SMT、CSP、ASP、MIP建模)以及数据驱动技术(强化学习、监督学习与混合策略)。通过对200余篇论文的实验实践进行系统分析,我们发现评估方法存在显著差异:经典方法通常在最大达200×200网格、1000+智能体的大规模实例上测试,而学习方法主要集中于10至100智能体规模。本文提供评估指标、环境类型和基线选择的全面分类,强调建立标准化基准协议的必要性。最后,我们展望未来方向,包括考虑博弈论的混合动机MAPF、基于大语言模型的语言引导规划,以及融合经典严谨性与深度学习灵活性的神经求解架构。本综述既可作为研究人员的全面参考,也可作为复杂现实应用中部署MAPF解决方案的实用指南。

原文摘要 · Abstract (English)

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.

多智能体路径规划综述机器人

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。