CBS(Conflict-Based Search)算法详解

本文最后更新于：2026年3月10日晚上

CBS(Conflict-Based Search)是解决多智能体路径规划(MAPF)问题的经典算法，通过高层搜索和低层搜索的两层架构，高效地找到无冲突的最优路径。本文详细介绍 CBS 算法原理、流程及其变种。

简介

CBS（Conflict-Based Search）是由 Ariel Felner 等人在 2012 年提出的一种 MAPF 算法。它的核心思想是将 MAPF 问题分解为两个层次的搜索：

低层搜索：为每个智能体单独规划路径（忽略其他智能体）
高层搜索：检测冲突并通过添加约束来消解冲突

CBS 是目前解决 MAPF 问题速度和质量最好的算法之一，许多后续的改进算法都是在 CBS 基础上发展而来的。

CBS 算法在集中式规划算法中的位置

基本概念

MAPF 问题回顾

MAPF 问题的输入：

图 $G = (V, E)$：表示环境的拓扑结构
$k$ 个智能体：每个智能体 $a_i$ 有起点 $s_i$ 和终点 $t_i$

目标：为每个智能体找到一条从起点到终点的路径，使得：

所有智能体的路径无冲突
最小化某个目标函数（如总路径长度、最大完成时间等）

冲突类型

CBS 中定义了两种基本冲突类型：

冲突类型	描述	示例
顶点冲突	两个智能体在同一时刻占据同一节点	时刻 $t$，$a_1$ 和 $a_2$ 都在节点 $v$
边冲突	两个智能体在同一时刻沿同一条边相向移动	时刻 $t$，$a_1$ 从 $u$ 到 $v$，$a_2$ 从 $v$ 到 $u$

图中展示了 MAPF 问题中的常见冲突类型

冲突的数学表示：

顶点冲突：$(a_i, a_j, v, t)$ 表示智能体 $a_i$ 和 $a_j$ 在时刻 $t$ 同时占据节点 $v$
边冲突：$(a_i, a_j, u, v, t)$ 表示智能体 $a_i$ 和 $a_j$ 在时刻 $t$ 发生边冲突

约束

约束用于限制某个智能体的行为，是 CBS 解决冲突的核心机制：

约束类型	描述	表示
顶点约束	禁止智能体在特定时刻访问特定节点	$(a_i, v, t)$
边约束	禁止智能体在特定时刻 traversing 特定边	$(a_i, u, v, t)$

约束树（Constraint Tree）

CBS 在高层维护一棵约束树（CT），树的每个节点包含：

约束集合：从根节点到当前节点的路径上积累的所有约束
解：满足当前约束集的所有智能体路径
代价：当前解的总代价（通常用 $SIC$ 即 Sum of Individual Costs）

约束树是一棵二叉树，每次检测到冲突时，将当前节点分裂为两个子节点。

CBS 算法中约束树的结构示意图

CBS 算法流程

高层搜索

高层搜索负责检测冲突并管理约束树：

CBS-High-Level():
  1. 创建根节点 ROOT：
     - constraints = {} (空约束集)
     - solution = 为每个智能体计算无约束的最短路径
     - cost = SIC(solution)
  
  2. 将 ROOT 加入 OPEN 列表（优先队列，按 cost 排序）
  
  3. while OPEN 非空:
       a. 从 OPEN 中取出 cost 最小的节点 N
       
       b. 验证 N.solution，检测第一个冲突：
          - 若无冲突：返回 N.solution（找到最优解）
          - 若有冲突 conflict = (a_i, a_j, ...)：继续
       
       c. 对冲突中的每个智能体，创建一个子节点：
          for each agent a in {a_i, a_j}:
            i. 创建新节点 N'
            ii. N'.constraints = N.constraints + 新约束
                (对 a_i 添加约束，禁止其在冲突时刻访问冲突位置)
            iii. N'.solution = N.solution
            iv. 对智能体 a 重新规划路径（满足新约束）
            v. 若规划成功：
               - 更新 N'.solution 中 a 的路径
               - N'.cost = SIC(N'.solution)
               - 将 N' 加入 OPEN

低层搜索

低层搜索为单个智能体规划满足约束的路径，通常使用带约束的 A* 算法：

CBS-Low-Level(agent a, constraints C, goal g):
  1. 初始化：
     - OPEN = {start}
     - g(start) = 0
     - f(start) = h(start, goal)
  
  2. while OPEN 非空:
       a. 取出 f 值最小的节点 n
       
       b. 若 n 是目标：返回路径
       
       c. for each 邻居 n':
           i. 计算新代价 g_new = g(n) + cost(n, n')
           
           ii. 检查约束：
               - 顶点约束：若 (a, n', t) 在 C 中，跳过
               - 边约束：若 (a, n, n', t-1) 在 C 中，跳过
           
           iii. 若 g_new < g(n')：
                - 更新 g(n') = g_new
                - 更新 f(n') = g_new + h(n', goal)
                - 将 n' 加入 OPEN
  
  3. 返回失败（无可行路径）

完整算法示例

考虑一个简单的例子：2 个智能体在 2x3 网格中：

初始状态：
  a1 在 (0,0)，目标 (0,2)
  a2 在 (1,0)，目标 (1,2)

网格：
  a1  .  g1
  a2  .  g2

第 1 轮（根节点）：

低层搜索：
- a1 的路径：(0,0) → (0,1) → (0,2)
- a2 的路径：(1,0) → (1,1) → (1,2)
高层验证：无冲突
返回解

带冲突的例子：

初始状态：
  a1 在 (0,0)，目标 (1,1)
  a2 在 (1,0)，目标 (0,1)

无约束路径：
  a1: (0,0) → (0,1) → (1,1)
  a2: (1,0) → (0,0) → (0,1)  ← 与 a1 在 (0,1) 有顶点冲突

CBS 处理过程：

根节点 ROOT：
  - 约束：{}
  - 解：a1: (0,0)→(0,1)→(1,1), a2: (1,0)→(0,0)→(0,1)
  - 冲突：(a1, a2, (0,1), t=1)

分裂为两个子节点：

节点 A（约束 a1）：
  - 约束：{(a1, (0,1), t=1)}
  - a1 重规划：(0,0) → (1,0) → (1,1)
  - 解：a1: (0,0)→(1,0)→(1,1), a2: (1,0)→(0,0)→(0,1)
  - 无冲突，返回此解

节点 B（约束 a2）：
  - 约束：{(a2, (0,1), t=1)}
  - a2 重规划：(1,0) → (1,1) → (0,1)
  - 解：a1: (0,0)→(0,1)→(1,1), a2: (1,0)→(1,1)→(0,1)
  - 无冲突，也可作为解

最优性证明

CBS 保证找到最优解（最小化 SIC）。

证明思路：

完备性：CBS 最终会探索所有可能的约束组合。如果解存在，CBS 必然能找到。
最优性：
- OPEN 列表按 cost 排序，总是先扩展代价最小的节点
- 当找到无冲突解时，该解的代价不超过 OPEN 中任何其他节点
- 由于约束只增加不减少，子节点的代价不会比父节点小
- 因此第一个找到的无冲突解就是最优解

关键性质：

每个冲突分裂为两个子节点，分别约束冲突的两个智能体
这种分裂保证了至少有一个子节点能找到解（如果解存在）
约束树的深度最多为冲突数量

时间复杂度分析

设：

$N$：节点数量
$E$：边数量
$k$：智能体数量
$C$：冲突数量

低层搜索复杂度：$O(N \log N)$（单次 A*）

高层搜索复杂度：

最坏情况：约束树大小为 $O(2^C)$
每个节点需要 $O(k)$ 次低层搜索
总复杂度：$O(k \cdot N \log N \cdot 2^C)$

空间复杂度：$O(k \cdot N \cdot 2^C)$

实际性能：CBS 在实践中通常比最坏情况好得多，因为：

大多数冲突可以通过简单的约束解决

好的启发式可以快速找到解

许多约束树分支会提前终止

CBS 变种算法

CBS 的成功催生了许多改进算法，以下是主要变种：

CBS 及其变种算法在 MAPF 集中式规划算法中的位置

ICBS（Improved CBS）

改进点：优化冲突选择策略

核心思想：不是随机选择冲突，而是优先选择"更容易解决"的冲突。

冲突优先级：

优先选择涉及路径较短的智能体的冲突
优先选择发生时间较早的冲突

优势：减少约束树的规模，提高搜索效率

CBSH（CBS with Heuristics）

改进点：为高层搜索添加启发式

核心思想：估计从当前节点到目标（无冲突解）的距离。

启发式函数：

基于冲突图计算下界
使用 CG（Conflict Graph）或 DG（Dependency Graph）

公式：
$$
h(N) = \text{MVC}(CG(N))
$$

其中 $CG(N)$ 是节点 $N$ 的冲突图，MVC 是最小顶点覆盖。

优势：更好地指导搜索方向，减少不必要的节点扩展

ECBS（Enhanced CBS）

改进点：允许次优解以换取速度

核心思想：引入有界次优性（Bounded Suboptimality）

机制：

使用膨胀因子 $w \geq 1$
低层搜索使用 $f = g + w \cdot h$
高层搜索的 OPEN 列表也使用加权排序

保证：
$$
\text{cost(solution)} \leq w \cdot \text{cost(optimal)}
$$

优势：在需要快速响应的场景中，可以在可接受的误差范围内大幅提高速度

CBS with Disjoint Splitting

改进点：改进约束分裂方式

传统分裂：冲突 $(a_1, a_2, v, t)$ 分裂为：

节点 A：约束 $(a_1, v, t)$
节点 B：约束 $(a_2, v, t)$

Disjoint 分裂：

节点 A：约束 $(a_1, v, t)$
节点 B：约束 $a_2$ 不能在时刻 $t$ 访问 $v$（正面约束 vs 负面约束）

优势：两个子节点的搜索空间互补，避免重复搜索

CBS with Bypasses

改进点：在分裂前尝试"绕行"

核心思想：当检测到冲突时，先尝试为冲突智能体找到一条代价相同但避开冲突的"绕行路径"。

流程：

检测到冲突 $(a_1, a_2, v, t)$
尝试为 $a_1$ 找到绕行路径（代价相同，避开 $(v, t)$）
若找到，更新解，不分裂节点
若找不到，按传统方式分裂

优势：减少约束树的深度

算法对比

算法	最优性	速度	适用场景
CBS	✓	中	通用
ICBS	✓	快	冲突较多的场景
CBSH	✓	快	大规模问题
ECBS	次优	很快	实时系统
CBS-Disjoint	✓	快	冲突密集场景
CBS-Bypass	✓	快	存在等价路径的场景

代码实现

Python 伪代码实现

from heapq import heappush, heappop
from typing import Dict, List, Set, Tuple

class Constraint:
    """约束类"""
    def __init__(self, agent: int, location: Tuple, time: int):
        self.agent = agent
        self.location = location
        self.time = time

class Conflict:
    """冲突类"""
    def __init__(self, agent1: int, agent2: int, location: Tuple, time: int):
        self.agent1 = agent1
        self.agent2 = agent2
        self.location = location
        self.time = int

class CTNode:
    """约束树节点"""
    def __init__(self):
        self.constraints: Set[Constraint] = set()
        self.solution: Dict[int, List] = {}  # agent -> path
        self.cost: float = float('inf')
    
    def __lt__(self, other):
        return self.cost < other.cost

def cbs(agents: List, starts: Dict, goals: Dict, graph) -> Dict:
    """CBS 主算法"""
    # 1. 初始化根节点
    root = CTNode()
    for agent in agents:
        root.solution[agent] = astar_constrained(
            starts[agent], goals[agent], graph, root.constraints, agent
        )
    root.cost = compute_sic(root.solution)
    
    # 2. 初始化 OPEN 列表
    open_list = []
    heappush(open_list, root)
    
    # 3. 主循环
    while open_list:
        node = heappop(open_list)
        
        # 4. 检测冲突
        conflict = find_first_conflict(node.solution)
        
        if conflict is None:
            return node.solution  # 找到无冲突解
        
        # 5. 分裂节点
        for agent in [conflict.agent1, conflict.agent2]:
            # 创建新约束
            new_constraint = Constraint(
                agent, conflict.location, conflict.time
            )
            
            # 创建子节点
            child = CTNode()
            child.constraints = node.constraints | {new_constraint}
            child.solution = node.solution.copy()
            
            # 重新规划受影响智能体的路径
            new_path = astar_constrained(
                starts[agent], goals[agent], graph, 
                child.constraints, agent
            )
            
            if new_path is not None:
                child.solution[agent] = new_path
                child.cost = compute_sic(child.solution)
                heappush(open_list, child)
    
    return None  # 无解

def astar_constrained(start, goal, graph, constraints, agent):
    """带约束的 A* 搜索"""
    open_list = [(heuristic(start, goal), 0, start, [])]
    closed = set()
    
    while open_list:
        f, g, current, path = heappop(open_list)
        
        if current == goal:
            return path + [current]
        
        state = (current, len(path))
        if state in closed:
            continue
        closed.add(state)
        
        for neighbor in graph.neighbors(current):
            # 检查约束
            if is_constrained(agent, neighbor, len(path) + 1, constraints):
                continue
            
            new_g = g + graph.cost(current, neighbor)
            new_f = new_g + heuristic(neighbor, goal)
            heappush(open_list, (new_f, new_g, neighbor, path + [current]))
    
    return None

def find_first_conflict(solution: Dict) -> Conflict:
    """检测第一个冲突"""
    # 获取最大路径长度
    max_time = max(len(path) for path in solution.values())
    
    for t in range(max_time):
        # 检测顶点冲突
        positions = {}
        for agent, path in solution.items():
            pos = path[min(t, len(path) - 1)]  # 终点等待
            if pos in positions:
                return Conflict(agent, positions[pos], pos, t)
            positions[pos] = agent
        
        # 检测边冲突
        # ... (略)
    
    return None

def compute_sic(solution: Dict) -> float:
    """计算 Sum of Individual Costs"""
    return sum(len(path) - 1 for path in solution.values())

实际应用

CBS 算法在以下场景中有广泛应用：

自动化仓库：多台 AGV（自动导引车）协同搬运货物
机器人导航：多机器人在同一环境中协同工作
无人机编队：多架无人机避免碰撞
游戏 AI：多角色 NPC 协同移动
交通调度：多车辆在交叉路口协调通行

与其他 MAPF 算法的对比

集中式 MAPF 算法的分类与 CBS 在其中的位置

算法	类型	最优性	复杂度	适用规模
A* + OD	集中式	✓	指数级	小规模
CBS	集中式	✓	指数级	中等规模
ICTS	集中式	✓	指数级	中等规模
M*	集中式	✓	指数级	小规模
优先级规划	分解式	✗	多项式	大规模
ORCA	分布式	✗	多项式	大规模

参考资料

经典论文

CBS: Conflict-Based Search For Optimal Multi-Agent Pathfinding - 原始 CBS 论文
Improved CBS (ICBS) - 改进的 CBS
CBSH: CBS with Heuristics - 带启发式的 CBS
ECBS: Bounded Suboptimal CBS - 有界次优 CBS

代码仓库

libMultiRobotPlanning：C++ 实现的 MAPF 算法库
Python MAPF：Python 实现的路径规划算法

简介