多智能体路径规划

给一群机器人同时规划各自到目标的路线，并保证彼此不相撞。

多智能体路径规划研究的是：地图上有多个智能体（机器人、AGV 等），各有起点和终点，要一起算出互不碰撞的路径。经典设定把地图离散成栅格或图、时间离散成步，每步每个智能体可以移到相邻格或原地等待。冲突主要有两种：同一时刻占同一格（顶点冲突），或相邻两个互换位置（交换冲突）。优化目标常用所有智能体到达时间之和，或最后一个到达的时间（makespan）。求最优解是 NP 难问题，常见算法有冲突搜索 CBS（先各自规划，发现冲突再加约束重规划）和优先级规划（按顺序规划，后规划的避让先规划的）。2019 年 Stern 等人的综述统一了各种变体的定义并给出栅格基准。它是仓储机器人集群调度的核心问题，和单机路径规划、局部避障（如 ORCA）互补。

例子电商仓库里大量搬运机器人把货架送到拣货台（亚马逊的 Kiva 系统是典型场景），调度系统每接到新任务都要给这些机器人重新分配互不冲突的路径。

也叫

多智能体寻路、多机器人路径规划、Multi-Agent Pathfinding

相关

路径规划、多机器人协作、A* 算法、多机调度系统、速度障碍法 / ORCA、自主移动机器人

来源

Wikipedia: Multi-agent pathfinding
Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks (arXiv 1906.08291)