基于A*算法的多智能体路径规划（Multi-agent Path Finding，MAPF）学习笔记_ca*,hca*和whca*

目录

1、原始空间与抽象空间

2、局部修复A*算法（Local-Repair A* ，LRA*）

3、合作A*算法（Cooperative A*，CA*）

4、层次化合作A*算法（Hierarchical Cooperative A*，HCA*）[2]

5、带窗口的层次化合作A*算法（Windowed Hierarchical Cooperative A*，WHCA*）

6、个人总结

参考文献

---

本篇文章是David Silver大佬的《Cooperative Pathfinding》[1]的阅读笔记，总结多智能体合作A*算法的同时记录一些查阅到的相关概念。

1、原始空间与抽象空间

原始空间的抽象转换（abstraction transformation）类型：嵌入（Embedding）和同态映射（homomorphism）[2]。

• 嵌入方法：原始状态空间S抽象空间S'，例如抽象空间是原始空间的超图。由于原始空间所有的边都包含在抽象空间中，因此抽象空间S'中两点的距离（启发函数的值）始终小于等于原始空间中的距离。
• 同态映射：将原始空间S中的多个状态组合在一起成为抽象空间中的一个状态，称为同态映射。任意多对一的映射都是同态映射。

Valtorta’s theorem指出，在使用嵌入抽象（embedding transformations）时，如果在抽象空间中使用BFS（或称盲目搜索）计算启发函数，那么A*算法会遍历在原始空间使用BFS时遍历的所有节点，造成A*算法无法加速搜索。

文献[2]介绍了上述定理的推广，如果在原始空间中使用BFS或盲目搜索时会遍历到状态S，那么在原始空间使用A*算法搜索时，要么状态S本身会被遍历到，要么S在抽象空间中的映射会被遍历到。

该推广定理带来的启发是使用同态映射可以加速搜索，因为在抽象空间中搜索一个状态，等价于在原始空间中搜索了多个状态。

2、局部修复A*算法（Local-Repair A* ，LRA*）

在传统的A*算法中，智能体在规划路径时不考虑其他智能体的存在，因此可能导致路径冲突。Local Repair A*通过引入冲突检测和修复机制来解决这个问题。

LRA*为每个智能体规划路径时忽略其他智能体，然后智能体开始移动。当冲突即将发生时，就地解决。冲突检测方法为：

1. 对于每对智能体，检查它们的路径是否相交。路径相交表示智能体之间存在潜在的冲突。
2. 如果路径相交，进一步检查智能体在路径上的时间冲突，即智能体是否在同一时间段内占用相同的位置。
3. 如果存在冲突，标记冲突的智能体对。

冲突检测可以在每个时间步骤进行，以确保在路径规划过程中及时发现冲突。一旦检测到冲突，Local Repair A*会进行局部修复，例如调整智能体的速度或重新规划代理的路径，以解决冲突并继续向目标前进。

缺点：拥挤区域需要不断重新规划路线，几乎每一轮都需要对A*搜索进行完全的重新计算。每次改变路线都是独立进行的，会导致循环，同一位置可能在循环中多次访问。

3、合作A*算法（Cooperative A*，CA*）

合作A*将任务解耦为一系列单个智能体的搜索，使用三维的预约表（坐标+时间）避免多智能体的路径冲突。

智能体计划路线所经过的网格单元被标记为不可通过，将(x、y、t)存储为哈希表，后续智能体在搜索过程中会避开这些条目，从而防止其他智能体规划出相撞的路线，这样只会存储一小部分的网格位置。

缺点：无法解决一些特定的问题，例如一个智能体的路径阻塞住了另一个智能体的所有可行路径，如下图所示。

4、层次化合作A*算法（Hierarchical Cooperative A*，HCA*）[2]

为了加速A*搜索，文献[2]将原始空间抽象为一系列抽象空间，每层抽象空间都比下一层的更general，在抽象空间中计算启发函数。

层次化合作A*算法中的“层次”是一系列二维的、只考虑空间属性的抽象空间。层次化抽象的过程：

1. 具有最大度的状态（或节点）与周围指定半径内的节点合并为一个抽象状态，重复进行直到所有状态都被合并为某个抽象的状态，这样就创建了一个抽象层（或抽象空间）。
2. 接着在此抽象层中继续合并生成更高一层的抽象层。
3. 以此类推，直到生成一个只有一个抽象状态的最高级别的抽象空间（top-level）。原始搜索空间称为base level或bottom level。

直接在层次化空间中使用A*搜索，由于原始空间的问题会衍生出一系列在抽象空间中搜索最佳路径的问题，因此在原始空间求解一个问题所需要扩展的节点总数将是原始空间与所有抽象空间扩展节点的总和，这大大高于直接在原始空间使用BFS所需要扩展的节点数。

为了减少扩展节点的数量，需要进行数据复用。方法如下：

1. h*缓存（h*-caching）：当在抽象空间上搜索终止时，对于解路径上的每个抽象状态S，都已知到目标节点的精确的距离h*(S)。缓存h*可以在后续搜索相同终点路径中使用，也就是不需要继续调用上层搜索了。这改进了这个抽象层上的启发函数的质量，从而可能减少后续搜索所扩展的节点数。
2. 最优路径缓存（optimal-path caching）：如果一个状态X到目标节点的距离h*(X)已知，实际上最短路径也已知，因此可以直接把X到终点G的最短路径进行缓存，以后遇到相同的终点不需要再进行搜索。
3. P-g缓存（P-g caching）：在之前的搜索过程中，会遍历一些不在最短路径上的节点X，节点X虽然不在最短路径上，但是X到起点的距离g(X)是已知的。如果已知起点到终点的最短路径长度为P，那么有P<=g(X)+h*(X)，接着有h*(X)>=P-g(X)。由此可以看到P-g(X)是X到终点最短距离h*(X)的启发值。此外，对于在搜索终止时处于open列表中的节点S，不需要计算P-g，直接存储h(S)即可，因为h(S)>=P-g(S)。

此外，抽象的粒度，即组合的半径，对于搜索速度也有影响。

文献[1]介绍了第四种数据复用的方法：使用逆向可恢复A*算法（Reverse Resumable A* ，RRA*）在抽象域中搜索。

5、带窗口的层次化合作A*算法（Windowed Hierarchical Cooperative A*，WHCA*）

这是文献[1]提出的算法，为了解决上述算法的几个问题：

1. 智能体到达终点后应该继续合作，而不是待在原点，否则可能堵塞其他智能体的可行路径；
2. 智能体之间的优先级应该动态变化。如果固定优先级，可能会导致一些问题无解；
3. 智能体的路径规划与执行应该交替进行以提高效率，因为环境是动态变化的，如果规划路径时在整个地图上进行搜索并考虑全局因素，实际上有些情况并不会发生，造成效率低下。

WHCA*的主要方法为：进行路径搜索时，只在原始空间的w步内（称为窗口路径）进行合作搜索，一旦到达了w步，直接在抽象空间中搜索剩余路径，w步到达的中间点到终点的距离直接使用抽象距离替代。接着给智能体下发窗口路径，并只将窗口路径放进保留表中。因此只需要保持不同智能体的路径窗口之间无冲突。当智能体跑到窗口一半时，继续规划路径并滑动窗口。

并且，智能体到达终点后继续进行窗口搜索。智能体的目标不再是到达终点，而是完成窗口。

引入窗口的另一个好处是搜索时间被分散到每个智能体身上。

6、个人总结

个人认为层次化搜索的引入是为了解决那些无法快速得到搜索点到终点的距离的场景，这些场景下必须进行BFS搜索才能得到每个点到终点的距离，这会大大增加A*中获取启发值的成本，因此必须对原始空间进行抽象，减少搜索的状态来加速获取到终点的距离。

路径窗口的引入可以避免单智能体每次规划路径时考虑整条路径上的冲突，实际上环境是变化的，其他智能体的路径和预测状态也是变化的，提前考虑所有信息可能导致路径规划很慢，窗口路径会节省考虑很多可能不会发生的冲突的时间。并且引入窗口让智能体边走边规划，将规划时间分散到执行的时间上，也可以加速规划。

参考文献

[1] Silver D .Cooperative Pathfinding[C]//Proceedings of the First Artificial Intelligence and Interactive Digital Entertainment Conference, June 1-5, 2005, Marina del Rey, California, USA.2005.

[2] Holte R C, Perez M B, Zimmer R M, et al. Hierarchical A*: Searching abstraction hierarchies efficiently[C]//AAAI/IAAI, Vol. 1. 1996: 530-535.