MAPF-GPT: Imitation Learning for Multi-Agent Pathfinding at Scale

📄 arXiv: 2409.00134v5 📥 PDF

作者: Anton Andreychuk, Konstantin Yakovlev, Aleksandr Panov, Alexey Skrynnik

分类: cs.MA, cs.AI, cs.LG

发布日期: 2024-08-29 (更新: 2025-04-08)

💡 一句话要点

MAPF-GPT：基于模仿学习的大规模多智能体路径规划

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture) 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 多智能体路径规划 模仿学习 Transformer 零样本学习 深度学习 路径规划 人工智能

📋 核心要点

  1. 现有MAPF学习方法通常依赖强化学习，并需要额外的单智能体规划或通信组件，增加了复杂性。
  2. 论文提出MAPF-GPT，一个基于模仿学习和Transformer的大规模MAPF基础模型，无需额外启发式或通信。
  3. 实验表明，MAPF-GPT在多种MAPF问题上优于现有可学习方法，并具备零样本学习能力和高效的推理速度。

📝 摘要（中文）

多智能体路径规划（MAPF）问题旨在为共享环境中多个智能体寻找无碰撞路径。即使在限制性假设下，最优MAPF求解也是NP-hard问题。然而，高效的解决方案对于自动化仓库和交通运输系统等众多应用至关重要。近年来，基于学习的MAPF方法受到关注，特别是那些利用深度强化学习的方法。通常，这些基于学习的MAPF求解器会增加额外的组件，如单智能体规划或通信机制。与此不同，本文完全依赖于模仿学习，利用大量专家MAPF解决方案数据集和基于Transformer的神经网络，创建了一个名为MAPF-GPT的MAPF基础模型。该模型无需额外的启发式方法或通信即可生成动作，并展示了在训练数据集中未出现过的MAPF问题上的零样本学习能力。实验表明，MAPF-GPT在各种问题实例上显著优于当前性能最佳的可学习MAPF求解器，并且在推理过程中具有计算效率。

🔬 方法详解

问题定义：多智能体路径规划（MAPF）旨在为多个智能体在共享环境中找到无碰撞的路径。现有基于学习的MAPF方法，如基于强化学习的方法，通常需要额外的组件（如单智能体规划或智能体间通信）来辅助求解，这增加了算法的复杂性，并且可能限制了其泛化能力。此外，如何有效地利用专家知识来指导学习也是一个挑战。

核心思路：论文的核心思路是利用模仿学习，直接从大量的专家MAPF解决方案中学习。通过训练一个强大的神经网络模型（MAPF-GPT），使其能够模仿专家的行为，从而在新的MAPF问题中生成合理的动作。这种方法避免了强化学习中复杂的奖励函数设计和探索过程，也无需手动设计启发式规则或通信协议。

技术框架：MAPF-GPT的整体框架包括两个主要部分：一是专家数据生成模块，用于生成大量的MAPF问题及其对应的最优或近似最优解；二是Transformer模型训练模块，使用生成的专家数据来训练一个基于Transformer的神经网络模型。该模型以当前MAPF问题的状态作为输入，输出每个智能体的动作。在推理阶段，MAPF-GPT直接根据当前状态生成动作，无需额外的规划或通信步骤。

关键创新：论文的关键创新在于提出了一个完全基于模仿学习的MAPF基础模型MAPF-GPT。与以往的MAPF学习方法不同，MAPF-GPT不依赖于强化学习或额外的启发式规则，而是直接从专家数据中学习。此外，MAPF-GPT利用Transformer模型强大的序列建模能力，能够有效地处理多智能体之间的复杂交互关系。

关键设计：MAPF-GPT的关键设计包括：1) 使用大量的专家数据进行训练，保证模型的泛化能力；2) 采用Transformer模型作为核心架构，利用其强大的序列建模能力；3) 设计合适的输入表示，将MAPF问题的状态编码为Transformer可以处理的序列；4) 优化训练过程，例如使用合适的学习率和正则化方法，以避免过拟合。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，MAPF-GPT在多种MAPF问题实例上显著优于当前性能最佳的可学习MAPF求解器。具体来说，MAPF-GPT在解决大规模MAPF问题时，成功率和求解时间都优于对比方法。此外，MAPF-GPT还展示了良好的零样本学习能力，能够在未见过的MAPF问题上生成合理的动作，这表明其具有较强的泛化能力。

🎯 应用场景

MAPF-GPT在自动化仓库、交通运输系统、游戏AI等领域具有广泛的应用前景。它可以用于优化仓库机器人的路径规划，提高物流效率；可以用于智能交通系统中车辆的路径规划，减少交通拥堵；还可以用于游戏AI中角色的路径规划，提高游戏体验。该研究的实际价值在于提供了一种高效、可扩展的MAPF解决方案，有望推动这些领域的发展。

📄 摘要（原文）

Multi-agent pathfinding (MAPF) is a problem that generally requires finding collision-free paths for multiple agents in a shared environment. Solving MAPF optimally, even under restrictive assumptions, is NP-hard, yet efficient solutions for this problem are critical for numerous applications, such as automated warehouses and transportation systems. Recently, learning-based approaches to MAPF have gained attention, particularly those leveraging deep reinforcement learning. Typically, such learning-based MAPF solvers are augmented with additional components like single-agent planning or communication. Orthogonally, in this work we rely solely on imitation learning that leverages a large dataset of expert MAPF solutions and transformer-based neural network to create a foundation model for MAPF called MAPF-GPT. The latter is capable of generating actions without additional heuristics or communication. MAPF-GPT demonstrates zero-shot learning abilities when solving the MAPF problems that are not present in the training dataset. We show that MAPF-GPT notably outperforms the current best-performing learnable MAPF solvers on a diverse range of problem instances and is computationally efficient during inference.