多机器人路径规划(MAPF)综述

参考文献:

• Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks

这篇综述详细介绍了多机器人路径规划问题(Multi-Agent Path Finding, MAPF)统一的描述形式和研究 MAPF 问题需要参考的术语定义，并介绍了评估 MAPF 算法的标准数据集.

文中介绍了一个关于 MAPF 非常重要的网站 : http://mapf.info, 里面实时更新 MAPF 问题研究的最新进展，包括最新的论文和全球研究 MAPF 问题的组织机构.

以下是对这篇综述比较有价值的部分进行总结：

Introduction

看论文首先要知道论文干了啥，这样后续看论文就会有重点，一般先看看摘要和 introduction 的后半部分，然后看看 conclusion．这篇综述是一篇 2019 年的论文，论文开头说关于 MAPF 的研究近年来涌现，但关于 MAPF 问题的描述形式和变量细节的定义却众说纷纭，对初学者很不友好．回想看过的 MAPF 算法论文，确实一语中的，比起经典算法，这种对一个研究方向的全局概述才更算是大部分初学者的引路人．

文章的主要贡献：

• 介绍 MAPF 问题的统一描述形式和术语定义
• 建立基准数据集(benchmarks) 和算法评估标准

MAPF 的定义:

原文:

• MAPF is an important type of multi-agent planning problem in which the task is to plan paths for multiple agents, where the key constraint is that the agents will be able to follow these paths concurrently without colliding with each other.

总结:

• MAPF(Multi-Agent Path Finding) 问题要干什么，其实从名字来说已经说的很清楚了: 就是多机器人路径规划，再关键一点，就是无碰撞(no collision)的路径规划

主要应用场景:

• 仓储物流
• 自动驾驶
• 机器人集群相关：比如无人机编队

经典 MAPF 算法(Classical MAPF)

定义

理解一个算法首先先把算法玩起来，玩起来的前提是知道算法的输入输出，这就够了．从输入输出就能从总体上了解这个算法能干什么，之后再深入算法细节，就不至于在冗杂的参数和复杂的算法细节中迷失，从而事半功倍．

注：MAPF 算法，有时也叫求解器(solver)，从编程视角来说，叫求解器可能更贴切一些．

Classical MAPF 算法的数学描述：

• $Input:<G,s,t>$, 其中：
  • 无向图 $G=(V,E)$，$V$ 为图 $G$ 的顶点， $E$ 为图 $G$ 的边
  • 映射 $s:[1,...,k]$ -> $V$ 将一个机器人映射到一个顶点，描述每个机器人(agent)的起始(source)节点
  • 映射 $t:[1,...,k]$ -> $V$ 一个机器人映射到一个顶点，描述每个机器人(agent)的目标(target)节点
• 在经典 MAPF 算法中，连续时间被离散化为时间步(这也是很多 MAPF 算法中 time step 的起源)，在每一个时间步(time step )，机器人可以做一个动作(Action)
• $Action:a:V$ -> $V$，即 $a(v)=v^{\prime }$, 表示机器人执行动作 $a$ 后，从顶点 $v$ 移动到顶点 $v^{\prime }$. 在经典 MAPF 算法中，每个机器人有两种 actions:
  • $wait$: 待在原地，$wait(v)=v$
  • $move$: 移动到下一个相邻顶点，$move(v)=v^{\prime }，(v,v^{\prime })\in E$
• 设 $\pi =(a_1,...,a_n)$ 为一串动作序列．对于一个机器人 $i$，设 ${\pi }_i[x]$ 为机器人 $i$ 从起点 $s(i)$ 出发， 执行 $\pi =(a_1,...,a_n)$ 中的前 $x$ 个动作(action)后到达的位置，即 ${\pi }_i[x]=a_x(a_{x-1}(\cdot \cdot \cdot a_1(s(i)))$. 如果机器人 $i$ 从起点 $s(i)$ 出发， 完整的执行完 $\pi$ 后，到达目标点 $t(i)$，即 ${\pi }_i[|\pi |]=t(i)$，称 $\pi$ 为机器人 $i$ 的单机规划路径($single$-$agent$ $plan$, 在 CBS 中定义为 $path$)
• $Output:solution$
  • $solution$: k 个机器人的单机规划路径集合(a set of $k$ single-agent plans)

总结:
对于经典 MAPF 问题:

• 输入: 地图+机器人起始位置+机器人目标位置)
• 输出: 全局路径(多个带时间步的单机规划路径)

冲突类型

为什么要定义冲突？
既然涉及到多机，每条单机规划路径之间的交叉或重合是很难避免的，这样就必然导致机器人产生碰撞，为了在算法层面解决这个问题，就将路径之间产生的交集定义为冲突．如果 $solution$ 中的所有 $single$-$agent$ $plan$ 都没有冲突，那么这个 $solution$ 是 $vaild$．

设 ${\pi }_i$ 和 ${\pi }_j$ 为两条 $single$-$agent$ $plan$.

• 顶点冲突(Vertex conflict)
  • 在同一时间步 $x$，机器人 $i$ 和 $j$ 同时占据了顶点 $v$, 即 ${\pi }_i[x]={\pi }_j[x]$ , 如图(b)， 绿机器人和蓝机器人将在下一时间步同时占据顶点 $C$
• 边冲突(Edge conflict)
  • 在同一时间步 $x$，机器人 $i$ 和 $j$ 同时穿越边 $(v,v^{\prime })$, 即 ${\pi }_i[x]={\pi }_j[x]$ $and$ ${\pi }_i[x+1]={\pi }_j[x+1]$ , 如图(a)， 绿机器人和蓝机器人将在下一时间步同时穿越边 $(A,B)$
• 跟随冲突(Following conflict)
  • ${\pi }_i[x+1]={\pi }_j[x]$
  • 一台机器人在下一时间步要占据的节点是另一台机器人当前占据的节点，如图©
  • 形象一点解释，跟随冲突意味着跟车太近，没有保持车距，如果有意外情况容易撞上
• 轮换冲突(Cycle conflict)
  • 一图胜千言，如图(d), 一圈机器人产生了一圈的跟随冲突，当禁止跟随冲突的情况下这种情况会造成死锁
  • 描述：${\pi }_i[x+1]={\pi }_{i+1}[x],{\pi }_{i+1}[x+1]={\pi }_{i+2}[x],\cdot \cdot \cdot ,{\pi }_{j-1}[x+1]={\pi }_j[x],{\pi }_j[x+1]={\pi }_i[x]$
• 交换冲突(Swapping conflict)
  • 非常经典的冲突， ${\pi }_i[x+1]={\pi }_j[x],{\pi }_j[x+1]={\pi }_i[x]$
  • 如图(e), 两个机器人互换位置．
  • 在经典 MAPF 算法中，交换冲突有时被分进边冲突类型，因为显然两个机器人在同一时间步同时占据了一条边

机器人在终点的状态

由于每个机器人到达自己目标点的时间步不一致，所以需要定义机器人到目标点的状态．这个性质主要影响怎么去编程，跟算法没有多大关系．

• 在终点消失(disappear at target)
  • 此状态下，一旦该机器人到达目标点，该目标点在算法中会设置为空白(clear)状态，之后，其他机器人的路径可以经过这个点
• 在终点保持(stay at target)
  • 此状态下，一旦该机器人到达目标点，该目标点在算法中会设置为障碍物(obstacle)状态，变成障碍物，之后，其他机器人的路径不能经过这个点

目标函数

目标函数用于评估 MAPF 问题的解($solution$), 一般有以下两个标准：

• $Makespan$: $solution$ 中最长的 $path$ 长度，也就是最长时间步 $ma{x}_{1⩽i⩽k}|{\pi }_i|$. 类比一下，相当于选取一个木桶最长的那块板．
• $Sumofcosts$: 时间步总数: ${\sum }_{1⩽i⩽k}|{\pi }_i|$. 类比一下，相当于选取一个木桶所有木板的长度之和．

当然这只是一般的标准，根据具体情况还可以设计别的评估函数，例如机器人总的等待时间($wait$动作)，这就见仁见智了．

MAPF 问题的延伸

上一部分介绍的是经典 MAPF 问题，经典 MAPF 问题基于以下假设：

• 时间离散化为时间步
• 一个时间步机器人执行一个动作
• 一个时间步内，机器人占据一个顶点

松弛以上假设，可以得到各种各样的 MAPF 问题变形．

带权图

这部分其实就是把经典 MAPF 的描述形式扩展了一下，把图的抽象扩展成带权图，例如在机器人规划领域广泛使用的欧式空间(栅格地图，矩阵等等)，$move$ 操作演变成上下左右或者更大的步数跳跃，例如数据结构题里面模仿象棋马走日的广度优先搜索．　　　　

可行性判断

在经典 MAPF 问题中，可行性的判断标准唯一：没有冲突($noconflicts$),　变形的可行性判断规则有：

• 鲁棒性判断
  • $k-robust$ MAPF 保证每个机器人在每个时间步有 $k$ 个时间步的延迟裕量，这相比于经典 MAPF 的条件是加强的．有点类似于高中数学几何型线性规划的思想.
• 队形规则
  • 这个与多机队形有关，例如无人机编队，详细可以阅读原文献中的参考文献

路径规划和运动规划

经典 MAPF 问题考虑的仅仅是理想情况的路径规划，但在实际问题中，机器人大小、机器人运动学约束都是非常重要的影响因子，经典算法需要进行特定的优化．

任务规划

• 匿名 MAPF(Anonymous MAPF): 类似于滴滴打车，多个机器人需要到多个终点，但不规定哪台机器人必须到哪个终点
• 分组 MAPF(Colored MAPF): 匿名 MAPF的变种，类似于外卖的区域性派单
• 动态 MAPF(Online MAPF): 也叫 “Liftlong MAPF”, 南加州大名鼎鼎的 Jiaoyang Li 组就是研究这个的

Benchmark

这是这篇文章的第二个重点，介绍了评估 MAPF 算法的数据集和算法评估方法. 这里不涉及算法理论方面的东西，细节比较多，这里就不多介绍了，大家感兴趣可以看看原文章．