MAPF(Multi-Agent Path Finding) 就是多机器人路径规划，追求在约束内无碰撞地高效规划最佳路径。

简介

多智能体路径规划（multi-agent path finding，MAPF）是为多个智能体规划路径的问题，关键约束是多个智能体同时沿着规划路径行进而不会发生冲突。

对不同起始位置的多个智能体到他们各自目标位置的路径规划问题，关键约束是在保证智能体之间互相不碰撞的前提下到达目标位置，并保证路径规划的速度和质量。

传统MAPF挑战：环境的动态变化和智能体的数量增加，基于搜索的MAPF算法通过引入优先规划、大领域搜索和复杂的启发式函数来优化改进算法的性能；而基于强化学习的MAPF算法在解决动态和变化环境的MAPF表现出巨大的潜力。

按照规划方式不同：MAPF算法分为集中式规划算法和分布式规划算法。

集中式规划算法是最经典和最常用的MAPF算法，主要分为：基于A*搜索、基于冲突搜索、基于代价增长树和基于规约四种算法；

分布式执行算法分为专家演讲型，改进通信型和任务分解型三种算法

1. 集中式规划

   集中式规划方法由一个中央控制器来为所有智能体规划路径，它的前提假设是中央规划器掌握了所有智能体的起始位置、目标位置和障碍物位置等信息。集中式规划算法是最经典和常用的MAPF 算法，在求解的速度和质量上都达到较好的效果。

2. 分布式执行算法

   分布式执行算法主要是基于强化学习的算法，前提假设是每个智能体只掌握了视野内（一定范围内）智能体和障碍物的位置等信息，智能体根据当前策略不断和环境进行交互，获取环境下一到达状态和该动作奖励，计算并更新策略，目标是最大化累积奖励，最后找到一个最大化累积奖励的动作序列，完成多智能体路径规划任务。这类算法可以扩展到高密度和动态的部分可观察的环境中，高效解决现实世界中的多智能体路径实时再规划问题。

3. 当前研究

   MAPF 的研究主要有两大方向，一是如何改进现有的算法，二是在实际应用中如何处理约束。在实际应用场景中要考虑机器的速度、加速度、转角，以及各种干扰的约束，而多智能体路径规划将这些设定进行抽象化，将运动控制离散为时间步，将研究的重点集中在求解速度和质量上。

经典 MAPF 问题

问题描述

K个智能体的经典MAPF问题定义为一个元组 $(G,s,t)$ 其中 $G=(V,E)$ 是一个无向图, 无向图中的节点, $v\in V$ 是智能体可以占据的位置，边 $(n,n^{\prime})\in E$ 表示智能体从节点 $n$ 移动到 $n‘$ 的连线，$k$ 代表智能体的数量 $a_1,a_2,a_3…a_k$ , $s$ 是初始位置的集合，每个智能体都有一个初始位置 $s_i\in s$ , $t$ 是目标位置的集合，每个智能体都有一个目标位置 $t_i\in t$.

在经典MAPF 问题中，时间被离散为时间步长。在每个时间步长中，每个智能体可以执行一个动作，一般有五种类型的动作：向上、向下、向左、向右和等待。

一个单智能体的路径规划是从起始位置到目标位置一系列动作的集合 $\pi=(a_1,a_2,a_3,…,a_n)$ k 个智能体的路径规划问题就是 k 条路径的集合 $\Pi=(\pi_1,\pi_2,…,\pi_k)$, 其中第 $i$ 个智能体对应路径 $π_i$。

输入输出：

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

假设：

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

冲突定义：

• 需要根据具体问题场景清楚定义出冲突种类和边界

a. 边冲突

b. 顶点冲突

c. 跟随冲突

d. 循环冲突

e. 对向冲突

目标函数：

用来评估 MAPF 解决方案最常见的三个目标函数是：
$$
\begin{aligned}&L_1 =max:t(\pi_i)\&L_2 =\sum_{1\leq i\leq k}t(\pi_i)\&L_3 =\sum_{1\leq i\leq k}l(\pi_i)\end{aligned}
$$
$L_1$: 表示最晚到达目标位置的智能体所花费的时间

$L_2$: 表示所有agents到达目标位置花费的总时间3

$L_3$: 表示所有智能体到达目标位置的路径长度总和

机器人在终点的状态：

• 在终点消失(disappear at target)

• 此状态下，一旦该机器人到达目标点，该目标点在算法中会设置为空白(clear)状态，之后，其他机器人的路径可以经过这个点

• 在终点保持(stay at target)

• 此状态下，一旦该机器人到达目标点，该目标点在算法中会设置为障碍物(obstacle)状态，变成障碍物，之后，其他机器人的路径不能经过这个点

主流技术范式

范式类别	核心思想	优点	挑战/适用场景
基于优化/搜索的集中式规划	将多智能体系统视为一个整体，在全局空间内搜索无碰撞的联合路径1。	解的质量高（可最优）；理论上完备。	可扩展性差：状态空间随智能体数量指数级增长4；对动态环境适应性弱。
基于协调的分布式规划	对智能体进行时空解耦，通过协调机制（如优先级、规则）实现避碰1。	计算效率高，可扩展性强；易于实现。	难以保证全局最优；需精心设计协调机制以避免死锁1。
基于学习的规划	智能体通过与动态环境及其他智能体交互，学习出协同策略，典型代表为多智能体强化学习4 8。	适应性强，能处理高动态、不确定环境；具备在线反应能力。	样本效率低、训练难；可解释性弱；仿真到现实的迁移是巨大挑战4。
博弈与控制的融合规划	用微分博弈建模智能体间的交互，结合控制理论进行求解，是近年来的重要趋势 5。	为合作、竞争、混合动机等复杂交互提供了严格的数学框架；能分析系统均衡与稳定性5。	求解复杂，对大规模系统计算负担重；通常需结合学习方法（如RL）求解5。

集中式规划算法

MAPF 集中式规划算法的前提假设是中央规划器掌握了全局信息，即所有智能体的起始位置、目标位置和障碍物位置信息等

基于A*的搜索算法

A* 在小规模智能体环境中是最佳搜索算法。它维护两个顶点列表：开放列表和关闭列表。最初将开始节点放入开放列表中，在每次迭代中，在开放列表中搜索相邻节点，并把起始节点放入关闭列表中。对于每个新生成的开放列表中的节点，A* 算法计算以下几个值：

1. $g(n)$ 从源节点到 $n$ 节点的最短路径代价
2. $parent(n)$ 是该节点的父节点
3. $h(n)$ 从 $n$ 节点到目标节点的启发式路径代价估计值

如果 $h^(n)$是节点 $n$ 到目标节点的完美启发式函数，如果知道每个节点的 $h^(n)$，即可以选择出从源节点到目标节点的最短路径，A* 算法选择 open-list 中 $g(n)+h(n)$ 最小的节点计算其周围的节点，并将此节点放入close-list 中，依次迭代下去直至找到目标节点。

A* 算法应用到多智能体

A* 搜索在MAPF 中的状态一般被称为 k - agent 状态空间，其状态数等于将 $v$ 个智能体分别放置在 $v$ 个不同节点状态数，一种放置方法对应于一种状态。简单的方法将 A* 搜索启发式函数应用到 MAPF 中，是全局启发式函数等于所有智能体各自启发式函数之和。在 $k-agent$ 的搜索空间内，最大的搜索空间为 $|v|^k$ ,分支因子（每个节点产生子节点的数量，假定为 $n$ 联通问题）为$|n|^k$，因为 A* 必须沿着最优路径扩展所有的节点，因此A* 算法在解决大规模智能体的 MAPF 问题时效率和质量都不高。

A* 算法拓展

对 A* 提出两个有效的拓展：因子分解与独立检测

因子分解（operator decomposition，OD）：OD设计用于改进k - agent 搜索空间的分支因子指数增长的缺陷。具体做法如下：将智能体按任意顺序排序，得到原顶点( $s ( 1 ) , s ( 2 ) , . . . , s ( k ) $) ，此时只考虑第一个智能体的行为，会生成一组顶点，表示第一个智能体在时间步1的可能位置，还包括其他智能体在时间步0的位置，这些节点全添加至open-list中，此时在展开第二个节点，只考虑第二个智能体的动作，会生成第二组节点，表示第二个智能体在时间步1的位置，以及第一个agent在时间步1的位置和其他智能体在时间步0的位置，依次迭代下去，在第 k 层状态节点时表达了所有智能体在时间步1的所有可能位置，能够表达同时一时间步长所有agent的位置节点称为full节点，继续搜索，直至到达表示目($ t ( 1 ) , t ( 2 ) , . . . , t ( k )$ ) 的full节点。

优点：有 OD 的A* 与无OD的A* 相比，其明显优势在于分支因子。OD大幅缩减了A* 搜索的分支因子，OD A* 引入了大量的中间状态节点，使得A* 搜索的深度加深了k 倍。在MAPF 中，由于加入启发式函数对中间状态节点进行剪枝，因此OD的引入是有益的。

独立检测（independence detection，ID）：D 试图将带有 $k -agent$ 的MAPF 问题分解为含有更少智能体的更小的MAPF 问题。其工作原理如下：

首先，每个智能体为自己找到一个最优路径方案，同时忽略所有其他智能体，然后开始独立检测，如果一对智能体的计划之间存在冲突，这些智能体就合并为一个单一的元智能体。然后，用 $A* +OD$ 求出其中两个智能体的最优解，忽略其他所有智能体。这个过程以迭代的方式继续，在每次迭代中检测到单个冲突，合并冲突（元）智能体，然后用 $A* +OD$ 进行最优解决。当智能体的计划之间没有冲突时，进程停止。

优点：在最坏的情况下，ID 最终会将所有智能体合并到一个元智能体，并解决生成智能体的MAPF 问题。ID 是一个非常通用的框架的MAPF 求解器，ID 能够提高多数MAPF 问题求解的效率。

$M算法$：与$A$ 相似搜索 k-agent 搜索空间，为改进分支因子，M*动态的改变搜索空间的分支因子。

具体做法：起初，每当扩展一个节点时，只生成一个节点，该节点对于所有单个智能体的最佳路径，因此对于 $k$ 个智能体生成k条最佳路径，但每个智能体沿着各自路径移动，可能会生成一个节点表示一对智能体 $i$ 与 $j$ 之间的冲突，将 $i$ 与 $j$ 加入冲突集合中，重新展开搜索，对于不在冲突集的agent，只考虑单个智能体其最优路径上的动作。

基于冲突的搜索算法

CBS原理

基于冲突搜索算法（CBS）是目前最常用的算法，目前求解MAPF 速度和质量最好的算法大都是在基于冲突搜索算法上进行改进和优化。

主要思想：高层搜索和低层搜索，构建一棵二叉搜索树查找解。在根节点为所有智能体单独规划路径，然后通过添加限制的方式消解冲突，每个节点规划路径考虑节点被添加的限制并忽略其他智能体。底层执行带有约束的单机规划，例如用传统 A* 算法，顶层遍历底层的规划路径，检查路径之间是否有冲突，如果有冲突则施加约束重新进行底层单机规划，直到所有底层路径无冲突为止

具体的工作原理：

• 顶层：使用约束树结构解决底层冲突，包括约束（根据冲突得到）、当前的计算的全局路径、全局代价cost
  生成树：从父节点到子节点，根据当前的约束进行拆分为两个子约束，根据当前的约束计算得出全局路径，根据计算得到的solution计算出全局cost，找到整个约束树最小的cost，判断子节点是否还用冲突，如果有则继续迭代，直至没有为止

• 底层：单机搜索，采用经典的A*算法

优点：它的特点在于求解速度快，相比其他方法能够求解更大规模的问题。

缺点：是实现难度较高。原有的用A* 整体规划求解MAPF 问题需要在扩展同时考虑各个智能体之间的冲突，生成大量无意义的节点，影响搜索的效率。CBS 通过添加限制解决冲突，求解速度更快。

基于CBS的改进算法

代价增长树搜索算法

代价增长树搜索（increasing cost tree search，ICTS）算法将MAPF 问题分解为两个问题：找到每个智能体的代价和找到这些代价的有效解决问题方案。

ICTS搜索算法

ICTS并不直接搜索k-agent搜索空间，而是将两个搜索过程结合到一起：高层搜索与底层搜索

• 高层搜索：找出每个智能体的最优路径的cost

• 底层搜索：对高层搜索的节点状态进行验证是否存在一组最优解。

举例说明，以 $k=2$ 的任务图为例：

按照宽度优先的原则选择 node 建立深度优先的MMD；

对于一对agent进行MMD叉乘，消去具有冲突的路径；

底层搜索：检测是否存在最佳路径。

基于ICTS搜索算法的改进算法

基于规约的算法

规约方法是从理论到实践的各种计算机领域中使用的最突出的技术之一。MAPF 问题是NP-hard 的问题，可以将MAPF 问题规约为其他已解决的标准问题，如布尔可满足性（satisfaction fiability，SAT）、约束满足问题（constraint satisfaction problems，CSP）、约束优化问题（constraint optimization problems，COP）、答案集编程（answer set programming，ASP）。许多MAPF问题可建模为CSP 或者COP。

优势：使用规约算法的主要好处是当前通用的规约求解器非常高效，并且变得越来越好。特别是现在的SAT求解器非常高效，能处理上万个变量。

基础实现

基本的 MAPF 问题应从离线规划开始，逐步识别、融合路径， 得到多实例的规划结果，也就是：“为每个智能体规划最优路径，再加入协调”，这是当前非常主流且实用的方法。

这是一种经典的分层思想：先独立，后协调。其优势在于结构清晰，可模块化实现。

1. 三层规划与协调回路

[任务层] → 为每个智能体计算一条从起点到终点的初始最优路径（例如使用改进的A*、Dijkstra算法）。
↓
[协调层] → 检测所有初始路径之间的潜在冲突（时空碰撞）。通过协调策略（如优先级、预约、轻微绕行）进行路径调整，生成一组无冲突的“协调后路径”。
↓
[执行层] → 智能体执行协调后的路径。同时，一个监控与重规划模块持续运行，当出现突发障碍（如行人）或偏差时，触发局部重新规划或全局协调回路。

这个架构的关键在于，协调是一个持续的过程，而不仅仅是一次性的预处理。

2. 协调机制的具体实现方案

从易到难

协调机制	如何操作	优点	缺点	适用你的场景
基于优先级	为智能体分配固定或动态优先级。低优先级智能体需为高优先级者“让路”，在其路径的冲突时空点进行等待或绕行。	实现简单，计算快，天然避免死锁。	可能不公平，总体效率未必最优。	适合车辆类型/任务有主次之分的场景。
基于时空预约	将环境（特别是关键路口、窄道）离散化为时空网格。智能体需提前“预约”其路径所占用的网格（位置+时间），预约成功才执行。	冲突规避彻底，适合共享结构化环境。	中心化调度器可能成为瓶颈；对时间同步要求高。	非常适合野外有固定通道或路口的环境。
基于速度调节	不改变路径几何形状，而是通过加速、减速、等待来调整智能体到达潜在冲突点的时间。	保持路径最优，能耗低。	协调空间有限，对复杂冲突效果不佳。	可作为其他机制的补充，用于微调。
基于协同避碰	在检测到冲突时，为相关智能体共同计算一个局部、轻微偏离原路径的协同绕行轨迹（例如使用互惠速度障碍法RVO）。	去中心化，反应快速，适应动态环境。	可能陷入局部振荡，需要良好的底层控制器。	非常适合应对行人等突发动态障碍。

3. 如何有效规避死锁

死锁常发生在对称、狭窄的空间（如两车在通道迎面相遇）。解决方案包括：

• 死锁预测与预防：在协调层进行“前瞻性模拟”，如果检测到未来可能发生相互等待的循环，则主动重新为其中一个智能体分配一条不同的路径。
• 引入随机扰动或破局规则：当检测到死锁（如所有车辆速度为零超过阈值），强制让某个智能体执行一个预设的“解脱机动”（如倒车到最近汇车点）。
• 将环境设计为有向环路：在规划层面，尽可能让主要交通流形成单向循环，从根本上减少对头相遇的可能。

分布式执行算法

近年来，经典的MAPF 算法已经能够解决大部分路径规划问题。**然而这些问题的前提假设都是中央规划器掌握完整的地图信息和所有智能体的位置等信息，并且集中式方法需要收集地图信息和所有智能体的信息以规划最优路径，导致消耗大量的计算资源。**随着技术的发展，去中心化的方法越来越流行，智能体在与环境交互过程中，通过和一定距离范围内的其他智能体通信来规划路径，泛化性较好，可以扩展到大规模智能体的环境。

单智能体强化学习算法对比

多智能体强化学习算法对比

基于深度强化学习的多智能体路径规划

使用RL 方法解决MAPF 问题面临的许多挑战，例如环境奖励稀疏、环境动态复杂等。任何一种强化学习算法直接应用于MAPF 问题都会出现学习速度慢和学习质量不高的问题。针对以上问题，研究人员采用了各种组合技术对基于强化学习的MAPF 方法进行改进，使得强化学习的MAPF 方法能够扩展到上千个智能体的环境，并且求解的质量和效率得到大大的提高。按照改进技术的特点，大致将基于RL 的MAPF 方法分为专家演示型、改进通信性和任务分解型三类，不同类型算法的优缺点总结于表8。

专家演示型

专家演示型方法主要采用强化学习和模仿学习（imitation learning，IL）和相结合的方法

PRIMAL（pathfinding via reinforcement and imitation multi-agent learning），一种新的MAPF 框架

工作流程：在每一回合开始，随机选择是基于RL 或者基于IL 进行学习，在基于RL 学习中，在每个时间步长，每个智能体从环境中获取其观察值和奖励值并输入到神经网络，神经网络输出一个动作。不同智能体的动作按照随机顺序依次执行。基于IL 的方法中，由经典的MAPF 规划器作为专家经验，对所有智能体动作进行协调规划。它结合了RL 和IL 去学习完全去中心化的策略。

在这个框架中，智能体处于部分可观察环境当中，只能观察到有限视野内的信息，智能体学习考虑其他智能体的位置对自己的影响，从而有利于整个集体而不仅仅是自己的最优路径。通过同时学习单个智能体路径（基于RL）和模仿集中式专家经验（IL），智能体最终学习到一个去中心化的策略，同时包含了智能体之间的协调合作。

改进通信型

在高密度智能体的MAPF中，系统需要多个智能体在环境完全不可知的情况下相互关联，因此需要智能体之间进行通信。在大规模智能体的 MAPF 中，为了加强协调与合作，智能体之间往往会进行通信，多智能体强化学习往往采用广播通信的方式，信息被传播到一定范围内的其他所有智能体。虽然相对于非通信的方式具有较大的改进，但需要大量的宽带，并在实践中引起额外的系统开销和延迟。

请求应答机制（DCC），其训练过程如图5所示，选择通信流程共分四个模块：第一模块是局部观察输入，智能体在每个时间步获得6x6的方格形状作为输入；第二个模块是观察编码，将智能体的局部观察输入通过卷积神经网络GRU进行编码；第三个模块是选择判断单元，观察编码修改局部观察后输入到Q网络中，比较去掉该智能体和有该智能体的Q值变化来判断邻居智能体的信息是否对自己有用；第四个单元是通信模块，智能体选择通信后，将信息进行聚合，随后输入Q网络得到下一步的动作。

任务分解型

大型动态环境的MAPF是具有挑战性的，每个智能体不仅需要有效到达目标，同时避免与其他智能体或对象冲突，因此将任务进行分解是一种重要的方法

混合策略方法（HPL）：将MAPF问题分解为两个子任务：到达目标和避免冲突。训练框架流程图如下图所示。

为了完成每一项任务，利用RL 的方法，如深度蒙特卡洛树搜索、Q混合网络和策略梯度方法，来设计智能体观察值到动作的映射，最后将学习到达目标策略和避免碰撞策略混合为一个策略。接下来，引入策略混合机制，最终得到一个单一的混合策略，该策略允许每个智能体表现出两类行为-个人行为（到达目标）和合作行为（避免与其他智能体发生冲突）

其他基于RL的MAPF算法

主要的算法有：

1. 针对MAPF环境的特点，在MADRL基础上进行改进的MAPF算法；
2. 将基于RL的MAPF 算法和传统算法或者其他领域先进技术相结合的算法；
3. 针对MAPF 应用在机场调度、自动仓库和无人机等实际应用场景，如何处理实际约束而提出的解决方案。

参考资料

• http://mapf.info/
• https://arxiv.org/pdf/1906.08291
• https://zhuanlan.zhihu.com/p/613639712
• https://blog.csdn.net/m0_66988867/article/details/134307785
• 刘志飞, 舄曹, 蔦赖, 等. 多智能体路径规划综述[J]. Journal of Computer Engineering & Applications, 2022, 58(20).

文章链接：
https://www.zywvvd.com/notes/study/algorithm/graph/mapf-summary/mapf-summary/