多机器人路径规划(MAPF)综述-Toy模板网

这篇具有很好参考价值的文章主要介绍了多机器人路径规划(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 算法的数学描述：

$I n p u t :< 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)
$A c t i o n : a : V$ -> $V$ ，即 $a (v) = v^{'}$ , 表示机器人执行动作 $a$ 后，从顶点 $v$ 移动到顶点 $v^{'}$ . 在经典 MAPF 算法中，每个机器人有两种 actions:
- $w ai t$ : 待在原地， $w ai t (v) = v$
- $m o v e$ : 移动到下一个相邻顶点， $\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$ 的单机规划路径( $s in g l e$ - $a g e n t$ $pl an$ , 在 CBS 中定义为 $p a t h$ )
$O u tp u t : so l u t i o n$
- $so l u t i o n$ : k 个机器人的单机规划路径集合(a set of $k$ single-agent plans)

总结:
对于经典 MAPF 问题:

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

冲突类型

为什么要定义冲突？
既然涉及到多机，每条单机规划路径之间的交叉或重合是很难避免的，这样就必然导致机器人产生碰撞，为了在算法层面解决这个问题，就将路径之间产生的交集定义为冲突．如果 $so l u t i o n$ 中的所有 $s in g l e$ - $a g e n t$ $pl an$ 都没有冲突，那么这个 $so l u t i o n$ 是 $v ai l d$ ．

多机器人路径规划(MAPF)综述
设 $\pi_i$ 和 $\pi_j$ 为两条 $s in g l e$ - $a g e n t$ $pl an$ .

顶点冲突(Vertex conflict)
- 在同一时间步 $x$ ，机器人 $i$ 和 $j$ 同时占据了顶点 $v$ , 即 $\pi_i[x] = \pi_j[x]$ , 如图(b)，绿机器人和蓝机器人将在下一时间步同时占据顶点 $C$
边冲突(Edge conflict)
- 在同一时间步 $x$ ，机器人 $i$ 和 $j$ 同时穿越边 $(v, v^{'})$ , 即 $\pi_i[x] = \pi_j[x]$ $an d$ $\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 问题的解( $so l u t i o n$ ), 一般有以下两个标准：

$M ak es p an$ : $so l u t i o n$ 中最长的 $p a t h$ 长度，也就是最长时间步 $max_{1\leqslant i\leqslant k}|\pi_i|$ . 类比一下，相当于选取一个木桶最长的那块板．
$Sum\space of\space costs$ : 时间步总数: $\sum_{1\leqslant i\leqslant k}|\pi_i|$ . 类比一下，相当于选取一个木桶所有木板的长度之和．