【MAPF】SCRIMP算法：面向多智能体路径规划的可扩展通信方法

  📢本篇文章是博主多智能体路径规划（MAPF）领域学习时，用于个人学习、研究或者欣赏使用，并基于博主对相关等领域的一些理解而记录的学习摘录和笔记，若有不当和侵权之处，指出后将会立即改正，还望谅解。文章分类在👉强化学习专栏：   【MAPF】多智能体路径规划—(2)《SCRIMP算法：面向多智能体路径规划的可扩展通信方法》

【MAPF】SCRIMP算法：面向多智能体路径规划的可扩展通信方法

目录

• • 1. 算法背景：从MAPF到多智能体强化学习
  • 2. SCRIMP算法核心思想
  • 3. SCRIMP的观测编码与通信机制
  • 4. 网络输出、奖励函数与冲突处理
  • 5. Episodic Buffer与内在奖励机制
  • 6. 训练方式与算法流程
  • 7. 实验结果、消融分析与优缺点
  • 8. 代码结构与运行方式
  • 9. 总结
  • 参考资料

1. 算法背景：从MAPF到多智能体强化学习

  在多智能体系统中，一个非常经典的问题是：很多个智能体如何在同一个环境中，从各自的起点走到各自的终点，同时避免相互碰撞？

  这个问题被称为 Multi-Agent Path Finding，简称 MAPF**，中文通常叫做 多智能体路径规划。

举个简单例子：

• 仓库里有很多搬运机器人；
• 每个机器人都有自己的目标货架或终点；
• 它们都在同一张网格地图上移动；
• 机器人之间不能撞到一起；
• 也不能两个机器人同时抢同一个格子；
• 还要尽可能快地完成任务。

这听起来像是一个“走迷宫”的问题，但难点在于： 不是一个人在走，而是一群人在同时走。

当智能体数量变多时，问题会迅速变难。传统搜索算法虽然在小规模问题上效果不错，但在大规模、动态、实时场景中往往会遇到计算量爆炸的问题。

SCRIMP 正是为了解决这个问题而提出的。它试图用 强化学习 + 模仿学习 + 可扩展通信机制，让多智能体在局部视野下学会协作式路径规划。

MAPF 可以形式化描述为：

给定一个图：

G

=

(

V

,

E

)

G = (V, E)

G=(V,E)

其中：

• $V$
• $E$

有

n

n

n 个智能体：

A

=

{

a

1

,

a

2

,

⋯
 

,

a

n

}

A = \\{a_1, a_2, \\cdots, a_n\\}

A={a1​,a2​,⋯,an​}

每个智能体

a

i

a_i

ai​ 都有：

• 起点 $s_i$
• 目标点 $g_i$

智能体在每个时间步可以执行一个动作：

a

i

t

∈

{

上

,

下

,

左

,

右

,

停留

}

a_i^t \\in \\{\\text{上}, \\text{下}, \\text{左}, \\text{右}, \\text{停留}\\}

ait​∈{上,下,左,右,停留}

目标是让所有智能体都从起点到达目标点，并且避免冲突。

在 MAPF 中，最常见的冲突有两种。

第一种是 顶点冲突，即两个智能体在同一时刻进入同一个格子：

p

i

t

+

1

=

p

j

t

+

1

p_i^{t+1} = p_j^{t+1}

pit+1​=pjt+1​

例如：

Agent 1 想走到 (3, 4)
Agent 2 也想走到 (3, 4)

这就会发生顶点冲突。

第二种是 交换冲突，即两个智能体在同一时间步交换位置：

p

i

t

=

p

j

t

+

1

,

p

j

t

=

p

i

t

+

1

p_i^t = p_j^{t+1}, \\quad p_j^t = p_i^{t+1}

pit​=pjt+1​,pjt​=pit+1​

例如：

t 时刻：
Agent 1 在 A
Agent 2 在 B

t+1 时刻：
Agent 1 去 B
Agent 2 去 A

这相当于两个智能体“迎面相撞”。

传统 MAPF 方法中，常见的有：

• A*
• Conflict-Based Search，CBS
• OD-M*
• 优先级规划方法
• 启发式搜索方法

这些方法的优点是：

• 理论清晰；
• 在小规模场景中效果好；
• 有些方法可以给出较强的最优性保证。

但是缺点也很明显：

在真实机器人系统中，每个机器人通常只能看到周围一小块区域，而不是整张地图。

因此，一个更现实的设定是：

每个智能体只能根据自己的局部观测，以及与其他智能体交换的有限信息，做出下一步动作。

这就引出了多智能体强化学习方法。

强化学习的基本思想是：

智能体通过与环境交互，不断试错，根据奖励信号学习一个策略。

对于单个智能体，策略可以写成：

π

(

a

∣

o

)

\\pi(a|o)

π(a∣o)

表示在观测

o

o

o 下选择动作

a

a

a 的概率。

对于多智能体，每个智能体都有自己的观测和动作：

π

i

(

a

i

∣

o

i

)

\\pi_i(a_i | o_i)

πi​(ai​∣oi​)

但问题在于：

• 每个智能体只能看到局部信息；
• 其他智能体也在同时行动；
• 环境对单个智能体来说是非平稳的；
• 多个智能体之间需要协作，而不是各走各的。

因此，单纯把普通强化学习算法直接套到 MAPF 上，往往效果不稳定。

2. SCRIMP算法核心思想

SCRIMP 的全称是：

Scalable Communication for Reinforcement- and Imitation-Learning-Based Multi-Agent Pathfinding

可以翻译为：

面向强化学习与模仿学习多智能体路径规划的可扩展通信方法。

它主要解决三个问题。

首先是 局部视野太小。在论文实验中，每个智能体的视野可以非常小，例如只看到

3

×

3

3 \\times 3

3×3 的局部区域。如果没有通信，智能体很难知道更远处发生了什么，也难以提前协调路径。

其次是 通信容易爆炸。如果每个智能体都和所有其他智能体交换信息，那么智能体数量一多，通信量就会迅速增加。比如：

• 8 个智能体还好；
• 64 个智能体就比较复杂；
• 128 个智能体时，通信和决策都会变得很困难。

所以通信机制必须是 可扩展的。

最后是 冲突时如何决定谁先走。在 MAPF 中，经常会出现两个智能体都想走到同一个格子的情况。这时不能简单随机决定，因为随机可能导致：

• 长时间死锁；
• 两个智能体反复互相让路；
• 整体路径效率下降。

SCRIMP 提出了一种基于价值估计的随机打破平局机制，让智能体在冲突时更合理地决定“谁先走”。

SCRIMP 的整体结构可以概括为三个核心模块：

整体流程如下：

局部观测
↓
观测编码器
↓
智能体消息表示
↓
Transformer通信模块
↓
融合其他智能体信息
↓
输出动作策略 / 状态价值 / 阻塞预测

简单理解：

每个智能体先看自己周围的情况，然后把自己的信息编码成一条“消息”，再通过通信模块和其他智能体交换信息，最后决定下一步怎么走。

3. SCRIMP的观测编码与通信机制

SCRIMP 中，每个智能体的观测主要分为两部分。

第一部分是 局部视野矩阵。每个智能体只观察自己周围的一个小窗口，例如：

3

×

3

3 \\times 3

3×3

局部视野中包含多种信息，例如：

• 障碍物位置；
• 其他智能体位置；
• 自己的目标方向；
• 其他智能体目标信息；
• 启发式路径信息。

这部分可以看成一组多通道的局部地图，类似于图像中的 RGB 通道，只不过这里不是颜色，而是不同语义的信息通道。

第二部分是 低维向量特征。除了局部地图，SCRIMP 还会给智能体一些额外向量信息，例如：

• 当前智能体到目标的距离；
• 当前动作信息；
• 上一步奖励；
• 历史位置信息；
• 内在奖励相关信息。

这些向量特征可以帮助智能体理解自己当前处于什么状态。

观测编码器的作用是把原始观测转换为神经网络可以处理的高维表示。

对于局部地图，SCRIMP 使用卷积网络进行编码：

局部地图
↓
卷积层
↓
池化层
↓
卷积层
↓
特征向量

对于额外的低维向量，则使用全连接层进行编码。

最后，两部分特征会被拼接起来，形成智能体的状态表示：

h

i

t

=

f

encoder

(

o

i

t

)

h_i^t = f_{\\text{encoder}}(o_i^t)

hit​=fencoder​(oit​)

其中：

• $o_i^t$
• $h_i^t$
• $f_{\text{encoder}}$

SCRIMP 最核心的创新之一，就是引入了基于 Transformer 的通信模块。

在多智能体系统中，每个智能体都可以看成一个 token。假设有

n

n

n 个智能体，那么可以得到

n

n

n 个消息表示：

M

t

=

m

1

t

,

m

2

t

,

⋯
 

,

m

n

t

M^t = {m_1^t, m_2^t, \\cdots, m_n^t}

Mt=m1t​,m2t​,⋯,mnt​

Transformer 的自注意力机制可以让每个智能体根据需要关注其他智能体的信息。

也就是说：

智能体不需要平均接收所有人的信息，而是可以学习“谁的信息对我更重要”。

这非常适合多智能体协作。

假设有三个机器人：

Agent 1：正在向目标移动
Agent 2：马上会和 Agent 1 发生冲突
Agent 3：离 Agent 1 很远

对于 Agent 1 来说，Agent 2 的信息显然更重要，Agent 3 的信息没那么重要。

注意力机制要做的事情就是：

给 Agent 2 更高权重
给 Agent 3 更低权重

数学上，自注意力可以写成：

Attention

(

Q

,

K

,

V

)

softmax

(

Q

K

T

d

k

)

V

\\text{Attention}(Q, K, V) \\text{softmax} \\left( \\frac{QK^T}{\\sqrt{d_k}} \\right)V

Attention(Q,K,V)softmax(dk​

​QKT​)V

其中：

• $Q$
• $K$
• $V$
• $d_k$

对于智能体

i

i

i，它会根据自己的 Query 去和其他智能体的 Key 计算相似度，然后对 Value 加权求和。

每个智能体先生成自己的消息：

m

i

t

=

f

m

(

h

i

t

)

m_i^t = f_m(h_i^t)

mit​=fm​(hit​)

然后所有智能体的消息进入 Transformer 通信模块：

m

~

∗

i

t

=

f

∗

comm

(

m

1

t

,

m

2

t

,

⋯
 

,

m

n

t

)

\\tilde{m}*i^t = f*{\\text{comm}}(m_1^t, m_2^t, \\cdots, m_n^t)

m~∗it=f∗comm(m1t​,m2t​,⋯,mnt​)

其中：

• $m_i^t$
• ${\tilde{m}}_i^t$
• $f_{\text{comm}}$

这样，智能体

i

i

i 的表示中就融合了其他智能体的信息。

如果智能体数量很多，所有智能体之间全连接通信会产生较大负担。SCRIMP 通过一种简单方式限制通信范围：

只让距离足够近的智能体进行有效通信。

也就是说，如果两个智能体距离太远，那么它们之间的注意力会被屏蔽掉。

可以理解为：

离我近的机器人：需要重点交流
离我远的机器人：暂时不用管

这样既保留了关键协作信息，又避免通信规模随着智能体数量无限膨胀。

4. 网络输出、奖励函数与冲突处理

SCRIMP 网络结构如下：

SCRIMP 的网络最后有多个输出头，分别负责不同任务。

第一个是 动作策略输出。策略头输出每个动作的概率：

π

i

(

a

i

t

∣

o

i

t

,

M

t

)

\\pi_i(a_i^t | o_i^t, M^t)

πi​(ait​∣oit​,Mt)

动作空间一般包括：

上、下、左、右、停留

网络会输出一个概率分布，例如：

上：0.10
下：0.05
左：0.20
右：0.55
停留：0.10

然后智能体根据这个概率选择动作。

第二个是 状态价值输出。价值头用于估计当前状态的长期收益：

V

i

(

s

t

)

V_i(s_t)

Vi​(st​)

它表示：

从当前状态开始，智能体未来大概还能获得多少累计奖励。

在强化学习训练中，价值函数可以帮助降低策略梯度估计的方差，使训练更加稳定。

第三个是 阻塞预测输出。SCRIMP 还设计了一个 blocking 输出，用来预测某个智能体是否阻塞了其他智能体的路径。

例如：

Agent 1 停在某个关键通道上
Agent 2、Agent 3 都过不去

这时 Agent 1 就可能处于 blocking 状态。

通过预测 blocking，模型可以学会：

有时候自己不只是要向目标前进，还要避免挡住别人。

强化学习中，奖励函数非常关键。SCRIMP 的奖励设计大致包括以下几类。

每移动一步都会有小的负奖励：

r

move

<

0

r_{\\text{move}} < 0

rmove​<0

这样可以鼓励智能体尽快到达目标，而不是在地图上乱逛。

如果智能体到达自己的目标点，会获得正向奖励：

r

goal

>

0

r_{\\text{goal}} > 0

rgoal​>0

如果发生冲突或碰撞，会给较大的负奖励：

r

collision

<

0

r_{\\text{collision}} < 0

rcollision​<0

这可以让智能体学会避免危险动作。

如果智能体挡住了别人的路径，也会受到惩罚：

r

block

<

0

r_{\\text{block}} < 0

rblock​<0

这点很重要。因为在多智能体协作中，一个智能体到达自己的目标并不代表任务结束。如果它停在了关键位置，可能会导致其他智能体无法完成任务。

在 MAPF 中，经常会出现多个智能体竞争同一个位置的情况。例如：

Agent 1 想进入格子 C
Agent 2 也想进入格子 C

如果两个都走，就会碰撞。 如果两个都不走，可能会死锁。 所以必须决定谁优先。

SCRIMP 的做法不是简单固定优先级，而是基于价值估计进行随机优先级分配。

假设智能体

i

i

i 和智能体

j

j

j 发生冲突，SCRIMP 会估计：

• 如果让 $i$
• 如果让 $j$

然后根据价值差异决定优先级概率。

如果让智能体

i

i

i 走可以带来更大的长期团队收益，那么

i

i

i 获得更高优先级。

可以用如下形式理解：

Δ

i

=

V

team

(

s

′

∗

i

 move

)

−

V

∗

team

(

s

i

 stay

′

)

\\Delta_i = V_{\\text{team}}(s'*{i\\text{ move}}) – V*{\\text{team}}(s'_{i\\text{ stay}})

Δi​=Vteam​(s′∗i move)−V∗team(si stay′​)

其中：

• $s_{i\text{ move}}^{\prime }$
• $s_{i\text{ stay}}^{\prime }$
• ${\Delta }_i$

如果：

Δ

i

>

Δ

j

\\Delta_i > \\Delta_j

Δi​>Δj​

则说明让智能体

i

i

i 先走更有利。

最后可以通过 softmax 得到优先级概率：

P

i

=

exp

⁡

(

Δ

i

)

∑

j

exp

⁡

(

Δ

j

)

P_i = \\frac{\\exp(\\Delta_i)} {\\sum_j \\exp(\\Delta_j)}

Pi​=∑j​exp(Δj​)exp(Δi​)​

这样做的好处是：

5. Episodic Buffer与内在奖励机制

SCRIMP 的另一个重要设计是 Episodic Buffer，即情节缓存。

在 MAPF 中，很多时候智能体离目标很远。如果只依赖“到达目标”这个奖励，那么智能体可能要走很多步之后才知道自己做得对不对。

这会导致强化学习中的经典问题：

奖励稀疏，学习困难。

为了解决这个问题，SCRIMP 使用内在奖励鼓励智能体探索新的区域。

每个智能体会维护一个缓存，记录自己在当前 episode 中访问过的位置。

如果智能体走到了一个之前没怎么探索过的新区域，就给予一定的内在奖励：

r

i

int

>

0

r_i^{\\text{int}} > 0

riint​>0

如果它一直在熟悉区域打转，则不给奖励，甚至可能给负向信号。

内在奖励可以简单理解为：

r

i

int

=

{

ϕ

(

β

−

δ

)

,

如果当前位置足够新 

0

,

否则

r_i^{\\text{int}} = \\begin{cases} \\phi(\\beta – \\delta), & \\text{如果当前位置足够新} \\ 0, & \\text{否则} \\end{cases}

riint​={ϕ(β−δ),​如果当前位置足够新 0,​否则​

其中：

• $\delta$
• $\varphi$
• $\beta$

这类内在奖励可以鼓励智能体不要总是原地徘徊，而是主动探索可能通向目标的新路径。

6. 训练方式与算法流程

SCRIMP 并不是只用强化学习训练，而是结合了：

模仿学习的思想是：

先让模型模仿传统规划器或专家策略，学会基本走法。

这相当于给强化学习一个较好的初始化，避免模型从完全随机策略开始探索。在 MAPF 中，专家可以来自传统规划算法生成的路径。

模仿学习只能让模型学会“像专家一样走”，但专家策略不一定适合所有情况。因此还需要强化学习继续优化策略。

SCRIMP 使用 PPO 进行训练。

PPO 的目标函数可以写成：

L

CLIP

(

θ

)

=

E

t

[

min

⁡

(

r

t

(

θ

)

A

^

t

,

clip

(

r

t

(

θ

)

,

1

−

ϵ

,

1

+

ϵ

)

A

^

t

)

]

L^{\\text{CLIP}}(\\theta)= \\mathbb{E}_t \\left[ \\min \\left( r_t(\\theta)\\hat{A}_t, \\text{clip}(r_t(\\theta), 1-\\epsilon, 1+\\epsilon)\\hat{A}_t \\right) \\right]

LCLIP(θ)=Et​[min(rt​(θ)A^t​,clip(rt​(θ),1−ϵ,1+ϵ)A^t​)]

其中：

r

t

(

θ

)

=

π

θ

(

a

t

∣

s

t

)

π

θ

old

(

a

t

∣

s

t

)

r_t(\\theta)= \\frac{ \\pi_\\theta(a_t|s_t) }{ \\pi_{\\theta_{\\text{old}}}(a_t|s_t) }

rt​(θ)=πθold​​(at​∣st​)πθ​(at​∣st​)​

含义如下：

• ${\pi }_{\theta }$
• ${\pi }_{{\theta }_{\text{old}}}$
• ${\hat{A}}_t$
• $ϵ$

PPO 的核心思想是：

每次更新策略时不要走得太猛，避免新策略和旧策略差异过大。

这可以提升训练稳定性。

下面用伪代码总结 SCRIMP 的整体流程：

初始化策略网络 pi_theta
初始化价值网络 V_theta
初始化 episodic buffer

for episode in range(num_episodes):

初始化 MAPF 环境
获取每个智能体的局部观测

for t in range(max_steps):

for each agent i:
编码局部观测 o_i
生成消息 m_i

使用 Transformer 通信模块融合多智能体消息

for each agent i:
输出动作概率 pi_i
输出状态价值 V_i
输出 blocking 预测

根据策略采样动作

如果发生动作冲突:
使用基于价值的 tie–breaking 机制决定优先级

执行动作，环境更新

计算外在奖励
根据 episodic buffer 计算内在奖励

存储轨迹数据

使用 PPO 更新策略网络
使用价值损失更新价值网络
使用 blocking 辅助损失更新预测头

7. 实验结果、消融分析与优缺点

SCRIMP 主要和以下方法进行对比：

• ODrM*
• DHC
• PICO
• PRIMAL / PRIMAL2 类方法

从论文实验结果来看，SCRIMP 在很多设置下取得了更好的综合表现，尤其是在智能体数量较多、障碍物密度较高、需要较强协作的任务中。

主要优势包括：

论文中还做了多组消融实验，用来验证每个模块是否真的有用。

如果去掉通信模块，智能体只能根据自己的局部观测决策。这样在简单场景中可能还能勉强完成任务，但在复杂场景中性能会明显下降。原因很直观：

多智能体路径规划不是单打独斗，而是需要互相配合。

如果不使用完整的 Transformer 通信结构，而是使用更弱的通信方式，模型性能也会下降。这说明：

Transformer 的自注意力机制确实帮助智能体筛选了更重要的协作信息。

如果没有内在奖励，智能体更容易在熟悉区域内徘徊，探索效率下降。尤其在复杂地图中，智能体需要尝试绕路、避让、寻找通道。内在奖励可以帮助它们更积极地探索新路径。

如果冲突时只是随机决定谁先走，可能会出现不稳定现象。基于价值的优先级机制可以让系统更关注长期团队收益，而不是短期局部动作。

总结来看，SCRIMP 有以下优点。

第一，适合大规模多智能体。通过可扩展通信机制，SCRIMP 能够在更多智能体的场景中保持较好表现。

第二，局部视野下仍然有效。即使每个智能体只能看到很小的局部区域，也可以通过通信获得其他智能体的信息。

第三，通信机制更灵活。基于 Transformer 的注意力机制可以自动学习“该听谁的”。

第四，冲突处理更合理。基于价值的 tie-breaking 机制比简单随机或固定优先级更适合复杂协作任务。

第五，探索能力更强。Episodic Buffer 和内在奖励可以帮助智能体跳出局部循环，探索更多可能路径。

当然，SCRIMP 也不是完美的。

首先，网络结构较复杂。相比普通强化学习方法，SCRIMP 包含：

• 卷积编码器；
• Transformer 通信模块；
• LSTM；
• 多个输出头；
• PPO 训练；
• 模仿学习；
• 内在奖励机制。

整体实现复杂度较高。

其次，训练成本较高。多智能体强化学习本身训练就比较困难，再加上通信模块和复杂奖励设计，需要较多计算资源。

最后，仍依赖仿真环境。虽然论文中展示了 Gazebo 机器人仿真实验，但真实物理机器人部署仍然可能面临：

• 传感器噪声；
• 定位误差；
• 通信延迟；
• 动力学约束；
• 地图变化。

8. 代码结构与运行方式

官方代码仓库给出了 SCRIMP 的实现。仓库中主要文件包括：

SCRIMP/
├── alg_parameters.py
├── driver.py
├── episodic_buffer.py
├── eval_model.py
├── mapf_gym.py
├── model.py
├── net.py
├── runner.py
├── util.py
├── requirements.txt
└── od_mstar3/

根据官方 README，代码要求 Python 3.7，并通过 pip install -r requirements.txt 安装依赖。运行前需要进入 od_mstar3 文件夹执行 python3 setup.py build_ext –inplace 编译扩展模块，然后回到根目录运行 driver.py 开始训练。官方 README 还说明了关键文件用途，例如 alg_parameters.py 用于训练参数，mapf_gym.py 定义 MAPF 强化学习环境，net.py 定义网络结构，episodic_buffer.py 实现内在奖励所需的 episodic buffer。

克隆代码：

git clone https://github.com/marmotlab/SCRIMP.git
cd SCRIMP

安装依赖：

pip install -r requirements.txt

编译 OD-M* 模块：

cd od_mstar3
python3 setup.py build_ext –inplace
cd ..

可以用下面方式检查是否编译成功：

import od_mstar3.cpp_mstar

如果没有报错，说明编译成功。

训练参数主要在：

alg_parameters.py

中设置。

常见可调参数包括：

N_AGENTS
WORLD_SIZE
OBSTACLE_PROB
LEARNING_RATE
MAX_EPISODE_LENGTH

这些参数分别控制：

• 智能体数量；
• 地图大小；
• 障碍物密度；
• 学习率；
• 每个 episode 的最大步数。

启动训练：

python driver.py

模型评估相关代码在：

eval_model.py

中。

可以根据训练保存的模型权重进行测试，观察在不同智能体数量、地图大小和障碍物密度下的表现。

9. 总结

如果用一句话概括 SCRIMP：

SCRIMP 是一种面向多智能体路径规划的强化学习算法，它让每个智能体在局部观测的基础上，通过 Transformer 通信机制和其他智能体交换信息，并结合价值优先级与内在奖励，实现更加稳定、可扩展的协作导航。

再通俗一点：

每个机器人不再只顾自己走，而是学会“看局部、听队友、让关键路、少挡人、一起到终点”。

本文介绍了多智能体强化学习中的 SCRIMP 算法。

SCRIMP 主要面向 MAPF 问题，也就是多智能体路径规划问题。它的核心贡献包括：

从方法设计上看，SCRIMP 的思想非常清晰：

局部观测解决现实性
通信模块解决协作性
价值机制解决冲突性
内在奖励解决探索性
PPO训练解决稳定性

因此，SCRIMP 不只是一个 MAPF 算法，也可以看成多智能体强化学习中“通信 + 协作 + 探索”的一个典型案例。

参考资料