🌀 nonlinear sciences

On dynamic multi-agent pathfinding methods: review, simulations and modifications

本文在一个统一的仿真框架内，对六种用于动态多智能体路径规划（D-MAPF）的路径搜索算法进行了系统性评估，并引入了一种名为 A** 的新型基于模板的方法，该方法将离线几何路径生成与在线时间自适应解耦，以提高在具有动态障碍物和部分可观测环境中的解质量。

原作者： Gabriel Fejziaj, Salama Hassona, Wieslaw Marszalek

发布于 2026-06-03

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Gabriel Fejziaj, Salama Hassona, Wieslaw Marszalek

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一个繁忙的仓库，里面有数十个送货机器人。它们的工作很简单：从 A 点到达 B 点，且不撞到货架、墙壁或彼此。但这里有一个转折：这个仓库并不是静态的。门会随机开启和关闭，叉车会意外地阻塞通道，而且机器人只能看到它们正前方的视野，无法看到整张地图。

这篇论文是一份关于不同的“导航大脑”在处理这种混乱场景时表现如何的成绩单。研究人员测试了六种不同的策略，以观察哪一种能让最多的机器人快速且安全地到达目标。

问题所在：“盲舞”

在现实世界中，机器人无法预见未来。它们可能会规划一条路径，却发现前方突然出现了一堵墙。如果它们每次遇到情况都必须停下来、观察四周并从头开始绘制一张全新的地图，就会浪费宝贵的时间。

研究人员想要找到处理这种“动态”混乱的最佳方式，其中包含：

障碍物移动： 墙壁会按既定计划出现和消失。
视野有限： 机器人的视野仅限于前方几步。
存在人群： 许多机器人同时尝试移动，因此它们必须避免互相碰撞。

六位竞争者

团队测试了六种不同的“大脑”（算法）：

Dijkstra（迪杰斯特拉）： “老派计算器”。它非常彻底但速度慢。每当地图发生变化时，它都会忽略捷径，重新绘制整个路径。这就像是因为书里改了一个字，就得把整本书重新读一遍。
D Lite：* “修补匠”。它不重绘整个地图，而只是修复损坏的部分。对于变化的场景，它比 Dijkstra 更快、更聪明。
Space-Time A (STA)：** “时间旅行者”。它不仅考虑“去哪里”，还考虑“何时去”。它规划的路径会考虑到时间，确保你不会恰好在另一个机器人也在那里的时候到达那个位置。
WHCA：* “窗口规划器”。它只看前方几步（一个很短的时间窗口），并分块进行规划。它很快，但可能会忽略大局。
M：* “外交官”。它让机器人先规划自己的路径。如果它们即将碰撞，它才会介入，专门为那两个机器人协商出一条绕行路线。
A（新星）：** “带有备选方案的旅行社”。这是作者创造的新方法。

明星选手：A**（旅行社）

作者专门为这种混乱、不可预测的世界设计了 A。它是如何工作的，可以用一个简单的类比来解释：

想象你正在前往一座城市旅行。与其只选择一条路线，不如在出发前请一位旅行社为你提供五种不同的路线选项（模板）：

路线 A 经过公园。
路线 B 沿着海岸线。
路线 C 穿过山脉。

旅行社会确保这些路线彼此之间非常不同，以便你拥有选择。

现在，想象你正在开车。突然，路线 A 出现了路障。

旧方法可能会惊慌失措，并试图从当前位置计算一条全新的路线，这非常耗时。
A 会说：“没问题！我已经准备好了路线 B 和 C。”它会迅速检查你现在是否可以合并到路线 B 或 C 上。如果可以，它会立即让你切换到新路径。如果不行，它会快速生成一些新的备份路线。

为什么这很酷？
它将“大局观”（寻找不同的道路）与“即时行动”（合并到道路上）分离开来。这让机器人在世界发生变化时仍能保持移动，因为它从未从零开始。

结果：谁赢了？

研究人员运行了数千次模拟，使用了不同数量的机器人和不同的地图布局。

获胜者（效率）： A 在让所有机器人以最少的总等待和行驶时间到达目标方面表现最佳。它是最高效的“团队成员”。
权衡： A 对计算机的负担有点“重”。因为它需要计算所有那些备份路线，所以它思考的时间比简单的算法要长。然而，它通过避免卡顿或采取糟糕的绕行路径所节省的时间弥补了这一点。
失败者：
- Dijkstra 在变化的世界中过于缓慢且效率低下。
- D Lite* 和 M* 表现尚可，但它们比 A 更容易陷入困境或采取更长的路径。
- WHCA* 和 STA* 非常可靠（它们很少发生碰撞），但它们在最小化总行程时间方面的效率不高。

核心结论

论文得出结论，对于拥挤、多变且难以观察的环境，A 方法是更优的选择。它就像一个聪明的旅行者，始终准备好了计划 B、C 和 D，即使在世界抛出变数时，也能让整个机器人集群平稳运行。

注：论文严格专注于这些计算机模拟。它并不声称这些结果适用于现实世界的医疗用途、高速公路上的自动驾驶汽车或其他特定行业；它仅仅证明了在测试环境中数学逻辑的表现更好。

技术摘要：动态多智能体路径规划方法的综述、仿真与改进

1. 问题定义

本文研究了动态多智能体路径规划（D-MAPF），这是一个处于动态环境、部分可观测性和智能体间协作交汇处的复杂规划问题。与地图固定的静态多智能体路径规划（MAPF）不同，D-MAPF 处理的是障碍物以未知时间表出现和消失的环境。此外，智能体在部分可观测性下运行，这意味着它们只有在进入特定的视野范围（通过射线检测）时才能检测到障碍物，而不是拥有环境的全局知识。

本研究聚焦于一个基于网格且采用四连通移动设置的环境，其中多个智能体必须同时到达各自的目标点。该问题受以下约束：

动态障碍物： 障碍物遵循确定性或随机性的调度（出现/消失时间），在被检测到之前，智能体无法获知这些信息。
优先级规划： 为了管理组合复杂度，系统采用了解耦方法，即智能体根据固定的优先级顺序进行顺序规划，并将先前规划的智能体视为共享预约表中的移动障碍物。
排除最优耦合求解器： 由于冲突搜索（CBS）等算法在需要频繁实时重规划且存在频繁环境变化的反应式场景中计算不可行，因此将其排除在外。

2. 研究方法

作者在一个统一的仿真框架内评估了六种具有代表性的算法。所有算法均使用相同的地图、障碍物调度、智能体参数和预约系统，以确保公平比较。

2.1 评估算法

Dijkstra： 作为基准静态规划器。它在每次重规划步骤中执行全均匀代价搜索，不具备启发式引导或时间感知能力，并将预约视为静态阻塞。
D Lite：* 一种专为动态环境设计的增量启发式搜索。它通过仅向受影响的图部分传播代价修正来修复现有路径，而不是从头开始重新计算。
时空 A (STA)：** 通过将时间引入状态表示（位置 + 时间步）来扩展 A*，从而通过预约表实现碰撞规避。
WHCA (窗口分层协作 A)：** 一种协作算法，将规划限制在固定的时间窗口内（例如 16 步），并迭代地向路标点（waypoints）规划。
M (M-Star)：* 一种多智能体算法，它独立规划路径，仅在检测到冲突时才将搜索空间扩展到联合配置。
A (提出的算法)：** 一种作为主要贡献引入的新颖方法。

2.2 提出的 A** 算法

A** 专为动态、部分可观测环境下的反应式规划而设计。其核心创新在于利用基于模板的方法，将离线几何路径生成与在线时间自适应进行解耦：

模板生成（离线/预计算）： 在初始化时或当智能体已知的障碍物集发生变化时，算法使用惩罚性 2D A* 搜索生成 $k$ $k$ 条候选路径（模板）。
- 在找到一条路径后，会在该路径的每个单元格遍历代价上增加一个固定惩罚值。
- 这会迫使随后的搜索寻找在几何上截然不同的路线，从而创建一组多样化的候选路径集。
- 已知的活跃动态障碍物会获得额外的惩罚，以引导模板远离危险区域。
在线重连（时间自适应）： 当触发重规划时（例如，障碍物阻塞了当前路径），A** 不会对整个空间进行搜索。相反，它尝试将智能体的当前位置与存储模板中的任何可达点进行重连。
- 它使用时空 A* 从当前位置计算到模板中特定点的“桥接”（bridge）。
- 它根据预期的绝对时间验证“尾部”（template 的剩余部分），以确保沿途没有动态障碍物激活。
- 选择能使总路径长度最小化的“桥接+尾部”组合。
回退机制： 如果重连到所有现有模板均失败，则从当前状态生成新的模板，并重复此过程。

3. 主要贡献

本文提出了五项具体贡献：

形式化与框架： 作者将 D-MAPF 正式化为在具有时间调度动态障碍物和单智能体视野范围的网格上的反应式、部分可观测问题。他们提供了一个仿真框架来实例化这一设定进行基准测试。
算法集成： 将六种不同的算法（Dijkstra, D* Lite, STA*, WHCA*, M*, A**）集成到一个通用框架中，实现了系统的基准测试和直接性能比较。
基于视觉的障碍物过滤器： 引入了一个透明的过滤器，在不修改核心搜索逻辑的情况下，为所有规划器强制执行部分可观测性，确保智能体仅对观察到的障碍物做出反应。
实证评估： 在 8 个基准地图、10 种智能体数量配置（1–10 个智能体）以及每种配置 100 次重复实验的基础上进行了全面评估。指标包括总代价（SoC）、完成时间（Makespan）、失败率和计算时间。
A 的特性描述：** 本文引入并评估了 A**，证明了其基于模板的方法能有效平衡动态环境中的解质量与重规划效率。

4. 实验结果

实验在 8 个地图（包括空旷、迷宫、随机和房间配置）上进行，动态障碍物在随机间隔内出现和消失。

解质量（总代价 - SoC）：
- 在智能体数量为 1 到 9 时，A 始终实现了最低的 SoC。
- 模板机制允许 A** 通过切换到预计算的几何差异化路径来绕过暂时阻塞的区域，减少了昂贵的在线绕行需求。
- 对于 10 个智能体，M* 得到的 SoC 略低于 A**，但 A** 仍保持竞争力。
- Dijkstra 表现出最高的 SoC（除 1 个智能体外），因为它缺乏时间感知，迫使智能体等待或采取更长的绕行路径。
计算效率：
- Dijkstra 和 D Lite* 最快，平均总计算时间低于 6 毫秒，这归功于它们的简单性和增量特性。
- A 的计算时间显著更高（范围从数百到数千毫秒）。这种开销源于生成 $k$ 个模板（需要进行 $k$ 次惩罚性 2D A* 运行）以及评估桥接（需要多次 STA* 搜索）。
- 重规划频率： 虽然 A** 的重规划频率比 WHCA* 或 Dijkstra 低（因为模板可以预见未来的冲突），但其单次重规划成本很高。因此，A** 的总计算时间在所有方法中是最高的。
鲁棒性（失败率）：
- STA* 和 WHCA* 的失败率最低（低于 11%），这归功于它们详尽的时间扩展搜索，更有可能在规划窗口内找到解。
- A 的失败率较高（平均 21%），作者将其归因于重规划逻辑的复杂性和动态环境的特定约束。
- D Lite* 和 M* 也显示出较高的失败率（20%），尤其是在智能体密集的配置中。

5. 重要性与主张

本文声称 A 在处理具有部分可观测性的 D-MAPF 方面代表了显著的进步。通过将几何多样性生成与时间可行性验证解耦，A** 在大多数配置下实现了卓越的解质量（最低 SoC），有效地在频繁变化和有限感知的环境中进行导航。

作者承认了这种权衡：A** 以更高的计算开销换取了更好的路径。然而，他们认为在优先考虑解质量（最小化总旅行时间/代价）而非纯粹重规划速度的场景中，基于模板的方法为传统的增量或窗口式规划器提供了一个稳健的替代方案。研究结论指出，虽然没有一种算法能在所有指标上都占据统治地位，但 A** 在最小化动态、部分可观测多智能体系统的总代价（SoC）方面特别有效。