CBS（Conflict-Based Search，冲突基搜索）是一种用于多智能体路径规划问题的分支限界法，它的主要目标是让多个智能体在共享环境中找到最优的无碰撞路径。CBS的特点是采用分层结构，分为高层冲突解决和低层路径规划，将路径冲突检测与冲突解决分开考虑，从而在搜索效率和解的质量之间取得平衡。
01 高层冲突解决
高层冲突解决主要负责检测多个智能体之间的冲突，并通过为冲突智能体生成不同的约束条件，将问题分解为更小的子问题。每当检测到冲突时，CBS会为冲突的智能体创建约束，避免它们在同一时刻出现在同一位置。通过递归地分解冲突并优先处理路径代价较低的解，直到找到所有智能体无冲突的路径为止。
步骤：
1. 初始状态：假设每个智能体Ai都有一个初始的最短路径Pi，这是在不考虑冲突情况下的最优路径。
2. 冲突检测：算法会检查所有路径P1,P2,...Pn，找到冲突。例如，如果两个智能体Ai和Aj在同一时刻t出现在相同位置(x, y)，这就是一个冲突，记为(Ai, Aj, (x, y), t)。
3. 冲突分解：对于每个冲突(Ai, Aj, (x, y), t)， CBS生成两个子节点，每个子节点对应一个智能体的约束：
（1）子节点1：为智能体Ai添加约束，限制其在时间t不能进入位置(x, y)，记为Ci=(x, y, t)。
（2）子节点2：为智能体Aj添加类似约束Cj=(x, y, t)。
通过这种方式，CBS将冲突分解成两个可能的路径规划问题，其中至少有一个智能体必须改变其路径以避免冲突。
4. 优先队列：将这两个子节点存入优先队列，按总代价（如路径总长度）排序，每次选择总代价最小的解进行处理。代价可以表示为cost(P1, P2, ..., Pn)，即所有智能体路径的总长度。
5. 迭代：从优先队列中取出当前总代价最小的节点，重复冲突检测和分解，直到找到一个无冲突的解。
通过这种方式，高层只负责约束生成和冲突管理，不断通过生成约束来缩小解的空间。
02 低层路径规划
低层路径规划则专注于为单个智能体计算在满足高层约束下的最优路径。每当高层生成新的约束时，低层会针对受约束的智能体重新规划路径，确保其避开冲突点。低层使用经典的路径搜索算法（如A*算法）计算智能体的最短路径，并在局部调整智能体路径的同时保持整体搜索效率。
步骤：
1. 单智能体路径规划：当高层为某个智能体Ai生成了约束Ci（如在时间t避免位置(x, y)），低层会使用路径搜索算法（如A*算法）Ai为计算新的路径Pi，满足以下条件：
-
路径P i 避开所有高层约束C i ，即P i 不包含任何被禁止的状态，如(x, y, t)。
-
路径P i 在满足约束的前提下尽可能短。
2. 路径搜索：假设智能体Ai当前路径起点为si，目标为gi，其路径规划的任务是找到一条从si到gi的最短路径Pi，使得：
且在所有时间t满足约束条件Ci（即Ai不会在约束的时间和位置出现）。
3. 局部更新：低层只会为受约束的智能体重新计算路径，其他未受约束的智能体保持其原始路径不变，这大大减少了计算开销。
4. 反馈高层：当低层为智能体规划出新路径Pi后，会将其反馈给高层。如果低层路径计算没有违反新的约束且无冲突，则算法终止；如果仍有冲突，则高层继续生成新的约束并递归分解。
总结
高层冲突解决：管理约束生成和冲突检测，每当发现冲突时生成约束并将问题分解为子问题，直到找到无冲突解。其核心在于分支限界法和冲突递归分解。
低层路径规划：基于高层的约束条件，为受影响的智能体重新规划最短路径，确保路径符合约束。它采用经典的路径搜索算法，独立计算单个智能体的路径。
CBS算法已有基于Python的库，通过运行“pip install cbs-mapf”安装这个库，即可在Python项目中使用它。
参考文献
[1] Sharon G, Stern R, Felner A, et al. Conflict-based search for optimal multi-agent pathfinding[J]. Artificial intelligence, 2015, 219: 40-66.
[2] Hönig W, Kiesel S, Tinka A, et al. Conflict-based search with optimal task assignment[C]//Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems. 2018.
[3] Huang T, Koenig S, Dilkina B. Learning to resolve conflicts for multi-agent path finding with conflict-based search[C]//Proceedings of the AAAI conference on artificial intelligence. 2021, 35(13): 11246-11253.
[4] CBS算法Python库网站：https://pypi.org/project/cbs-mapf/
作者 | 王星凯
本文转载自久章智能微信公众号（原文发布于 2024-10-20），内容保持原貌。扫码关注公众号「久章智能」，第一时间获取智能决策系列文章。阅读原文 ↗