Multi-Agent Path Finding

• 又称: MAPF, multi-agent pathfinding, multi-robot path planning
• 类别: Learning & autonomy › Multi-robot
• 标签: multi-robot, path-planning, warehouse-automation, coordination, graph-search

为在共享图上同时移动的多个智能体（例如栅格上的仓储机器人）计算无碰撞路径的问题，使每个智能体都能无冲突地到达其目标。

定义

多智能体路径规划（Multi-Agent Path Finding，MAPF）是为共享同一环境的一组智能体规划路径的问题，使每个智能体都能从起点到达目标，同时不会出现两个智能体在同一时刻占据同一位置，或沿同一条边互换位置的情况。环境通常建模为一张图，常常是栅格，时间被划分为离散的步，每一步中每个智能体要么移动到相邻顶点，要么等待。

MAPF 的解通常用总代价（所有智能体到达各自目标所用的总时间）或完工时间（直到最后一个智能体到达为止的时间）来评判。在这些目标下求最优解一般是 NP 困难的，因此该领域发展出了以最优性换取速度的算法。最优方法包括基于冲突的搜索（Conflict-Based Search，CBS），它先独立地为每个智能体规划，然后通过在搜索树中添加约束来消解冲突。次优方法，例如优先级规划（智能体逐个规划，并把先规划的智能体当作移动障碍物），可以扩展到规模大得多的团队。

终身 MAPF 是一种变体，智能体一到达旧目标就会收到新目标，这与仓储和分拣机器人的实际工作方式相符。此时规划持续运行，通常在一个有限的时间窗口内进行，吞吐量成为主要的衡量指标。

真实机器人也会打破教科书中的假设：它们有尺寸、加速度限制和执行延迟，因此 MAPF 规划通常要配合额外的协调层来执行，在部分机器人落后于计划时保证安全。基于学习的方法，包括从基于搜索的规划器进行模仿学习，是扩展到超大规模机群的一个活跃研究方向。

为何重要

仓库、工厂和分拣中心在共享的场地上运行着规模不断增长的移动机器人机群，其吞吐量取决于这些机器人协调得有多好。MAPF 提供了随着机群扩大仍能让机器人无碰撞、无死锁地持续运行的算法。

主要应用

• 仓库和履约中心的机器人机群
• 使用大量移动机器人的包裹分拣系统
• 协调工厂中的自动导引车
• 多无人机和机场地面交通协调
• 电子游戏中的角色移动和人群仿真

实际应用

运营仓库机群的团队通常把场地建模为栅格图或路线图，每个单元格的大小正好容纳一台机器人。中央规划器从订单系统接收目标并计算协调后的路径，通常采用每隔几秒重新规划一次的优先级搜索或时间窗口搜索，而不是对整个问题求最优解。路径被转换为带时间的路径点并发送给机器人，再由一个执行层（例如动作依赖图）确保机器人在前方机器人离开某个单元格之前不会进入该单元格。在真实系统上更改场地布局或算法之前，工程师会在完整机群规模的仿真中测量吞吐量、等待时间和死锁频率。

常见误解

• 每个机器人都可以独立规划自己的最短路径 — 独立的路径会发生碰撞，因此机器人必须在时间和空间上同时进行协调
• 最优 MAPF 可以扩展到任意机群规模 — 最优求解是 NP 困难的，因此大型机群依赖次优或基于时间窗口的方法
• MAPF 规划可以完全按计算结果执行 — 真实机器人会提前或延迟，因此执行需要自己的安全与协调层

谁需要了解

• 仓储自动化和机群管理工程师
• 多机器人规划研究人员
• AMR 和 AGV 系统集成商
• 从事物流的运筹学研究人员

相关技术

• 基于冲突的搜索（Conflict-Based Search）
• 优先级规划（Prioritized Planning）
• A 搜索（A Search）
• 机群管理系统（Fleet Management Systems）
• 模仿学习（Imitation Learning）

相关术语

• Swarm Robotics
• Motion Planning
• AMR

相关项目

• Nav2: ROS 2 navigation stack with path planning and obstacle avoidance for mobile robots
• ROS Motion Planning: One repo implementing 40+ classic and learning-based robot path planners as ROS plugins
• OMPL: Sampling-based motion planning library powering MoveIt and countless robotics applications
• Open X-Embodiment (OXE): Largest open robotics dataset: 1M+ episodes from 22 embodiments
• IR-SIM: Lightweight pure-Python 2D robot simulator for navigation, control and RL research
• Mesh Navigation: Robot navigation on 3D triangle meshes for rough outdoor terrain, from Nature Robots