当前位置：首页 > news >正文

【调度算法】MAPF多智能体路径规划问题

news 来源：原创 2025/7/14 2:06:40

参考链接：https://blog.csdn.net/qq_43353179/article/details/129396325
在这篇博客的基础上对一些省略的部分进行补充。
网站：https://mapf.info/

可行性判断

1. k-鲁棒性（k-robust MAPF）

在经典 MAPF 中，只要所有智能体的路径不发生冲突（即无“位置冲突”或“边冲突”），就认为是一个可行解。

而在k-robust MAPF中，除了要求路径之间无冲突，还要求每个智能体在每个时间步上拥有额外的“延迟空间”，即：即使该智能体在当前时刻被延迟最多 $k$ 个时间步，它的路径也不会和其他智能体发生冲突。

这是一种增强的可行性条件，目的是提高路径对动态干扰（如通信延迟、路径阻挡等）的鲁棒性。

假设我们有一个 k-robust MAPF 问题，k=2，含义是：

假设智能体 A 的路径是 [t=0位置0 → t=1位置1 → t=2位置2 → …]
那么我们要确保：
- 如果智能体 A 在任意某一步最多被延迟2个时间步（即实际到达时间是 t+1 或 t+2），仍然不会在路径上与其他智能体产生冲突。

这类似于把每个位置“膨胀”为一个时间窗口（t, t+1, …, t+k），在这个时间段内，智能体能安全地占据这个位置。

你可以把这理解为“线性规划”的松弛变量概念。原问题追求最短时间，但在 k-robust 中，我们“留白”k个时间单位，容许一定程度的不确定性。

k 越大，系统鲁棒性越强，但规划难度越高。

2. 队形规则（Formation Constraints）

在某些多智能体任务中（例如无人机编队、机器人集群），不仅要求各个机器人完成自己的目标，还需要它们之间保持一定的空间关系或结构形式，这就是所谓的队形（formation）。

具体约束形式可能包括：

保持相对位置不变：
- 如编队飞行中，所有无人机始终保持一个“V”字形或正方形阵型。
- 比如智能体 B 要始终在 A 的正后方一格。
同步移动：
- 队形内的机器人必须同时出发、同时到达，或者严格在同一时间执行动作。
避免“散乱移动”：
- 所有机器人必须尽量在视觉、通信或控制范围内移动，避免一个机器人先到终点，其他人远远落后。
保持几何约束或通信连通性：
- 队形规则可以基于图论模型，如机器人之间构成的连接图始终是连通的。

加入了“结构不变性”的约束后，路径规划就不再是“各走各的”，而是要协调好整体行为。

4. 总结

约束类型	本质含义	目标	难度
k-鲁棒性	每步允许最多延迟 k 个时间步仍不冲突	增强对不确定性/延迟/干扰的容忍能力	中等偏上
队形规则	多智能体保持特定几何结构或通信图不变	实现群体协调/协同行为（如编队、同步）	难度较高

任务规划

1. 匿名 MAPF（Anonymous MAPF）

在匿名 MAPF中，有一组智能体和一组目标点，但不要求哪一个智能体对应哪一个目标。只需要让所有目标都被“某个智能体”到达就行。换句话说，智能体和目标之间没有固定的“身份绑定”，任务是“可交换”的。

类比滴滴打车：有多个乘客发起订单（目标点），有多辆车（智能体）在路上；系统只要把每辆车合理分配到一个订单上就行，不要求某辆特定的车接特定乘客。

这类问题调度灵活性更高；且通常比标准 MAPF 更容易规划，因为目标分配可以优化整体路径。求解思路为：先做最小成本完美匹配，为智能体和目标建立“最优匹配”，然后用标准 MAPF 求解无冲突路径规划。

2. 分组 MAPF（Colored MAPF）

这是介于标准 MAPF 与匿名 MAPF 之间的一个变种。智能体被分成若干组（group），每组可以看作是一个“颜色”（color），组内的智能体和目标是可以自由匹配的，但组间不能混淆。每个智能体必须被分配到与自己同组的目标之一，但不指定具体哪个。

类比外卖派单系统：假设美团外卖分了东区、西区、南区三个区域；每个配送员（智能体）只配送自己所在区域的订单（目标点），但同一组内可以自由调配。

这类问题是一个带颜色分组的最小成本匹配 + 路径规划问题；相比匿名 MAPF，多了“组别约束”，因此规划复杂度增加。

3. 动态 MAPF（Online / Lifelong MAPF）

在传统 MAPF 中，任务是一次性分配的，智能体从起点到终点后任务就结束了。
而在动态 MAPF中，智能体在执行路径任务的同时，新的任务源源不断地到来，每个智能体会在一个长期运行的系统中不断接收和完成新任务。

是最接近自动化系统日常运作的情况，如快递机器人、仓库调度机器人、自动停车系统。

4. 总结

类型	是否指定目标	是否允许任务重复分配	应用场景示例	相比标准 MAPF 特点
匿名 MAPF	❌ 不指定	一次性分配	滴滴打车、车位分配	可优化目标分配，计算更高效
分组 MAPF	⭕ 指定组别	一次性分配	外卖区域派单	增加组别约束，难度介于匿名与标准
动态 MAPF	⭕/❌ 均可	✅ 持续任务	仓储物流、快递机器人	实时性要求高，复杂度较大

Benchmark

多智能体路径规划（MAPF）的基准测试（benchmarks）包括两个主要的基准测试集：基于网格的MAPF基准测试和Asprilo框架。

1. 基于网格的MAPF基准测试（Grid-based MAPF Benchmark）

这个基准测试集包含了24张不同类型的地图，每张地图有25个场景，每个场景包含1000个问题。这些地图来自多种来源，包括真实城市地图、视频游戏地图、开放网格、带随机障碍的网格、迷宫式网格和房间式网格。所有地图均来自MovingAI路径规划库。

地图类型：

城市地图：从真实城市中提取的地图，例如柏林、波士顿和巴黎。
视频游戏地图：从《龙腾世纪：起源》（Dragon Age Origins）和《龙腾世纪2》（Dragon Age 2）中提取的地图。
开放网格：无障碍的N×N网格，例如8×8、16×16和32×32的网格。
带随机障碍的网格：在N×N网格中随机放置障碍物。
迷宫式网格：类似迷宫的网格，具有复杂的通道和障碍。
房间式网格：类似房间布局的网格，包含多个独立区域。

场景和问题设置：

场景：每个场景包含多个源和目标顶点对，这些顶点对是从地图的最大连通区域中随机选择的。
问题：从每个场景中选择任意数量的源-目标对，形成一个MAPF问题。例如，可以选择前两个源-目标对形成一个包含两个智能体的问题，然后逐步增加智能体数量。

评估方法：

评估流程：对于选定的MAPF算法、地图类型和场景，逐步增加智能体数量，直到算法在合理时间内无法解决问题为止。例如，从两个智能体开始，逐步增加到三个、四个……直到算法无法在30秒内解决问题。
评估指标：
- Solved：在规定时间内解决的问题数量。
- Min 和 Max：在所有场景中，算法能够解决的最少和最多的智能体数量。

2. Asprilo框架（Asprilo Framework）

Asprilo是一个公开可用的框架，用于模拟自动化仓库。它包括定义和生成标准自动化仓库规划问题的工具，以及验证和可视化解决这些问题的计划的工具。Asprilo特别适用于MAPF研究，因为它可以生成与MAPF问题相关的场景。

场景类型：

完整仓库场景：智能体需要在仓库中移动箱子，从一个地方运送到另一个地方。
仅移动场景：智能体只需要从一个地方移动到另一个地方，类似于经典的MAPF问题。

使用方法：

问题生成：Asprilo可以生成多种类型的自动化仓库规划问题，其中M领域（domain M）特别适合MAPF研究。
验证和可视化：Asprilo提供了工具来验证生成的计划是否有效，并可以可视化这些计划的执行过程。

可行性判断

1. k-鲁棒性（k-robust MAPF）

2. 队形规则（Formation Constraints）

4. 总结

任务规划

1. 匿名 MAPF（Anonymous MAPF）

2. 分组 MAPF（Colored MAPF）

3. 动态 MAPF（Online / Lifelong MAPF）

4. 总结

Benchmark

1. 基于网格的MAPF基准测试（Grid-based MAPF Benchmark）

2. Asprilo框架（Asprilo Framework）

相关文章：