【调度算法】LaCAM快速多智能体路径搜索算法
原文链接：https://ojs.aaai.org/index.php/AAAI/article/view/26377
GitHub：https://kei18.github.io/lacam/
LaCAM is a search-based, sub-optimal, complete, quick, and scalable MAPF algorithm.
LaCAM 是一种基于搜索的、次优的、完整的、快速且可扩展的多智能体路径查找（MAPF）算法。
一句话总结：LaCAM 是一种面向快速规划的 MAPF 算法，通过将冲突作为“延迟处理+成本感知”的搜索变量，使得算法能在大规模、实时性场景下实现高效且鲁棒的多智能体路径规划。
出发点
多智能体路径规划（MAPF）问题（不会的看这篇：https://blog.csdn.net/weixin_44624036/article/details/147922672?spm=1011.2415.3001.5331）旨在为多个智能体在图上分配无碰撞路径，是多机器人协调的基础。在实际应用中，如自动化仓库中的车队操作，需要实时解决包含数千个智能体的MAPF问题。MAPF算法的设计需要在质量和速度之间进行权衡：从质量角度看，求解MAPF的最优解是NP-hard问题；从速度角度看，次优算法可以在牺牲解的质量的情况下快速解决大规模MAPF实例。因此，开发快速的次优算法具有实际价值。
定义
lazy constraints addition search for MAPF (LaCAM)
惰性约束添加搜索的多智能体路径规划（MAPF）算法【我自己翻译的】
先看一下什么是惰性约束（Lazy constraints）。惰性约束（lazy constraints） 指的是：并不一开始就加入到模型中求解器的全部约束条件，而是在求解过程中按需动态添加的一类约束。
也就是说，从命名上看，LaCAM算法求解MAPF问题的思路应该是，先不考虑智能体发冲突约束，随便生成一个初始解，对这个解进行基本的可行性验证，如果发现该初始解对应的路径规划方案存在冲突，则将该冲突添加到冲突约束里，更新初始解。
这种思路避免了在初始模型中加入大量潜在“无用”的约束，能够在大规模智能体调度问题上表现出较高的求解效率。
两级搜索策略
原文描述：
LaCAM is a two-level search. At the high-level, it explores a sequence of configurations; each search node corresponds to one configuration. For each high-level node, it also performs a low-level search that creates constraints. A constraint specifies which agent is where in the next configu ration. The low-level search proceeds lazily, creating a minimal successor each time the corresponding high-level node is invoked.
LaCAM 是一种双层次搜索算法。在高层次上，它探索一系列配置；每个搜索节点对应一个配置。对于每个高层次节点，它还执行一个低层次搜索，创建约束。约束指定哪个智能体在下一个配置中的位置。低层次搜索是惰性进行的，每次调用相应的高层次节点时都会创建一个最小后继节点。
一开始看半天没看明白，后来结合算法的实现细节，可算是拼凑出了个大概。即：
- 高层搜索：每个高层节点是一个全局配置 (v₁, v₂, …, vₙ)，代表所有智能体的位置组合（在论文中是元组）。高层节点使用深度优先搜索（DFS）。
- 低层搜索：每个低层节点代表一个智能体的动作空间，即该智能体下一步能移动到的所有位置的集合。低层节点使用广度优先搜索（BFS）。
- 全局配置更新：低层搜索完成后，智能体的位置可能发生改变，因此需要更新全局配置信息，即更新高层节点。
那么问题来了，LaCAM为啥在高层搜索中采用深度优先搜索，而在低层搜索中采用广度优先搜索呢？
高层采用DFS的关键思想是，优先深入到可能是目标配置的路径上，然后再回溯修正冲突，是一种“先做后改”的策略。DFS能够快速找到一条完整的可行解路径（哪怕 sub-optimal），可用作初始解。此外，LaCAM 是 lazy constraints addition，初期不追求最优解，而是先找到一条解再逐步修正。
而低层节点就像“地基”，必须稳、全，所以要BFS保证不遗漏任何可行动作。BFS 可以在动作空间中穷尽所有可行动作，帮助生成所有可能的“邻接配置”。此外，BFS更适合处理带约束的动作图搜索问题（如避免冲突），可以更方便地判断是否存在一条不违反已有约束的路径。
搜索过程
论文里通过一个简单的例子介绍了LaCAM算法的逐步搜索和扩展新状态的过程，下边是该过程的配图。
鉴于论文里的一大串英文原文我实在是没看明白，对这张图的描述采用GPT老师的版本：
- 每个高层节点代表一个配置（例如两个智能体的位置如 (a,c)、(b,c) 等）；
- 每个低层搜索是针对其中某一个智能体，尝试移动它并检测会不会违反约束（例如碰撞）；
- 如果低层搜索生成了新配置（新的高层状态），就将其加入到 Open 集合里，等待继续探索；
- 若生成的配置在之前已经出现过，或因为冲突无法生成新配置，那么就不再扩展高层节点。
这里注意两点可能会好理解一些：
- 论文举例的两个智能体的位置是元组 (a,c)，这里的元组不代表XY坐标，而是对智能体位置的简单标记，即智能体1在标记为a的位置，智能体2在标记为b的位置。如果是三个智能体那就是(a,b,c)。当智能体位置发生改变时，比如高级节点由(a,c)→(a,d)，意为智能体1位置不变，智能体2位置从c移动到d。
- 所谓“高级”、“低级”，不是说智能体或者位置节点啥的等级，而是指两种搜索方式关注的点不太一样。高级搜索关注智能体的整体状态，低级搜索关注智能体的局部移动。智能体的局部移动受到冲突的约束，同时会影响智能体的整体状态，使得高级节点发生更新。
即：高级节点存储所有智能体当前的配置状态，也就是每个智能体的当前位置。这个层次做的是“整体状态”的搜索。低级节点针对一个特定智能体，生成可能的移动方式（也就是 successor），并检查是否满足已有约束。
GPT老师给出了一个形象的类比：高层搜索——指挥官，低层搜索——士兵。
| 角色 | 类比作用 |
|---|---|
| 高层 | 指挥官，看的是整体局势，要知道每个智能体现在在哪 |
| 低层 | 士兵，具体去操作“怎么动”，一步一步试探路径，同时遵守高层给出的“规则（约束）” |
我自己对这个搜索过程的理解是：高层节点是全局配置，低层节点是每个智能体的运动空间，高层节点用深度优先搜索先随机选择一个智能体，对于这个选定的智能体用广度优先搜索探索其所有动作空间。如果高层节点用广度优先搜索的话，那应该是高层节点依次选择每个智能体，生成所有可能的新的全局配置。
算法终止条件
既然深度优先搜索和广度优先搜索都是全局搜索算法，那为什么LaCAM是次优的算法呢？这个算法的终止条件是什么？
为什么 LaCAM 是“次优（sub-optimal）”算法？
虽然深度优先搜索（DFS）和广度优先搜索（BFS）都是全局搜索算法，但 LaCAM 被称为“次优”是因为它不保证找到代价最小（即 Sum-of-Cost 最小）的解。这主要源于以下几点：
- LaCAM 使用了 Lazy Constraint Addition 的思想
- 它不在一开始就生成所有冲突约束（如 CBS 那样），而是遇到冲突才添加约束；
- 这相当于：先走一条“看起来通的路”，遇到障碍再修正，而不是一开始规划全局最优路径。
- 高层 DFS 优先找“可行解”而非“最优解”
- 高层使用 DFS 意味着它更偏向于快速找到第一个无冲突的解，不保证遍历所有可能配置；
- 也就是说，如果更优的解在“另一条分支”上，LaCAM 不会回溯去找。
- 没有使用最优性保障的启发式函数（如 A* or admissible heuristic）
- LaCAM 的搜索策略没有设计成一定要找到全局最优解；
- 相比之下，像 CBS-Optimal 或 A*-based MAPF 算法，通常会通过代价函数 + 启发式来严格保障最优性。
LaCAM 的终止条件是什么？
LaCAM 的搜索过程在找到一个满足所有约束的可行路径时终止，当搜索到一个高层节点，其包含的全局配置表示：
- 所有智能体都已到达各自的目标位置；
- 并且路径中没有任意时间步的冲突（即满足当前所有累积的约束）；
此时，LaCAM 停止搜索，返回当前的解作为结果。注意，它不再继续搜索是否有代价更小的解。所以这个解是可行解，但不是最优解（因此是次优算法）。