上篇讲了多机器人系统架构的三个维度——通信、协调、任务分配。这篇深入聊路径协调这是多机器人系统里最容易出问题的环节。几十台机器人在同一空间运动路径冲突是必然的。两台机器人同时要到同一个路口谁先走四台机器人在十字路口互相堵住怎么办一台机器人坏了停在路中间其他机器人怎么绕行这些问题不解决多机器人系统就只是一堆各自为政的单机机器人。路径协调的质量直接决定了系统的整体效率。一、路径冲突的类型多机器人路径冲突主要有三种顶点冲突——两台机器人在同一时刻到达同一个位置。最直接的碰撞。边冲突——两台机器人在同一时刻沿同一条边相向而行。头对头撞上。追尾冲突——后面的机器人速度比前面快在同一时刻到达同一位置。def check_conflict(path_a, path_b, time_step): 检查两条路径是否有冲突 for t in range(max(len(path_a), len(path_b))): pos_a path_a[min(t, len(path_a)-1)] pos_b path_b[min(t, len(path_b)-1)] # 顶点冲突 if pos_a pos_b: return True, ft{t}: 顶点冲突 at {pos_a} # 边冲突交换位置 if t 0: prev_a path_a[min(t-1, len(path_a)-1)] prev_b path_b[min(t-1, len(path_b)-1)] if pos_a prev_b and pos_b prev_a: return True, ft{t}: 边冲突 return False, 无冲突二、集中式路径规划CBS算法Conflict-Based SearchCBS是集中式多机器人路径规划的经典算法。思路是先给每台机器人独立规划最短路径检查有没有冲突。如果有冲突加约束重新规划——机器人A在t5时不能出现在位置X或者机器人B在t5时不能从X走到Y。def cbs(robots, map): # 1. 独立规划 paths {} for robot in robots: paths[robot.id] a_star(robot.start, robot.goal, map) # 2. 检测冲突 root Node(paths, constraints[]) open_list [root] while open_list: node pop_best(open_list) conflict detect_conflict(node.paths) if not conflict: return node.paths # 找到无冲突解 # 3. 分支给冲突的两台机器人各加一条约束 robot_a, robot_b, time, location conflict # 分支1约束机器人A child1 copy(node) child1.add_constraint(robot_a, location, time) child1.replan(robot_a) open_list.append(child1) # 分支2约束机器人B child2 copy(node) child2.add_constraint(robot_b, location, time) child2.replan(robot_b) open_list.append(child2)CBS保证找到全局最优解总路径代价最小但计算量随机器人数量指数增长。适合小规模10-20台的场景。三、分布式路径协调优先级规划大规模场景下集中式算法算不动。分布式方案更实用——给每台机器人分配一个优先级高优先级的机器人先规划路径低优先级的把高优先级的路径当作动态障碍物来避让。def priority_planning(robots, map): # 按优先级排序 robots.sort(keylambda r: r.priority, reverseTrue) planned_paths {} for robot in robots: # 已规划的路径作为动态障碍 dynamic_obstacles list(planned_paths.values()) path a_star_with_avoidance( robot.start, robot.goal, map, dynamic_obstacles ) planned_paths[robot.id] path return planned_paths这种方案计算快但不保证最优——低优先级的机器人可能绕很大的弯。而且优先级分配会影响结果质量。工程上的折中方案把机器人分成几组组内用集中式CBS组间用优先级。这样计算量和解质量都能接受。四、死锁检测与解除死锁是多机器人系统的噩梦。最简单的死锁两台机器人在窄走廊两端面对面谁也不让谁。死锁检测——如果多台机器人在连续N个时间步内都没有移动或者移动距离极小就判定为死锁。死锁解除——检测到死锁后选一台机器人让它退让倒车到最近的避让点让其他机器人先通过。def detect_deadlock(robots, threshold10): 检测死锁连续N步没有移动的机器人 stuck [] for robot in robots: if robot.steps_without_moving threshold: stuck.append(robot) if len(stuck) 2: # 检查是否互相阻塞 for i in range(len(stuck)): for j in range(i1, len(stuck)): if are_blocking(stuck[i], stuck[j]): return True, (stuck[i], stuck[j]) return False, None def resolve_deadlock(robot_a, robot_b): 解除死锁优先级低的退让 if robot_a.priority robot_b.priority: robot_b.reverse_to_waiting_spot() else: robot_a.reverse_to_waiting_spot()更复杂的死锁比如4台机器人在十字路口互相堵住需要更智能的解除策略——可能需要多台机器人同时退让或者重新规划所有涉及的路径。有些系统会设置一个死锁解除专员角色——专门的进程负责监控全局死锁状态一旦检测到死锁就强制介入。它有权暂停某些机器人的运动、重新分配路径优先级、甚至临时修改地图标记某些通道为单向通行。这种集中式的死锁管理在实际项目中效果很好。五、面试高频追问QCBS算法的时间复杂度是多少A最坏情况是指数级的O(2^n)因为每次冲突产生两个分支。实际中冲突不多时接近多项式。对于大规模场景通常用改进版ECBSEnhanced CBS允许次优解来换取速度。Q实际项目中怎么处理死锁A预防比解除更重要。设计路径时留出避让点宽一点的道口机器人走到避让点就停下来等。交通规则里规定下坡让上坡重载优先。实在死锁了再人工介入或者自动退让。Q时间窗口机制怎么避免冲突A把路径分成若干段每段分配一个时间窗口。机器人只有在时间窗口内才能进入该段路径。时间窗口由中央调度器统一管理不会分配冲突的窗口。Q多机器人导航和单机器人导航的代码差异大吗A单机器人导航只需要一个Nav2实例。多机器人需要每台机器人一个独立的Nav2实例不同命名空间外加一个协调层路径预留、死锁检测。协调层是额外开发的Nav2本身不支持多机器人协调。路径协调是多机器人系统里最考验工程能力和耐心的部分。算法选型要综合考虑规模大小、实时性和解质量。下一篇我们聊人机交互设计。多机器人路径协调的三种方案集中式CBS最优但慢、分布式优先级规划快但次优、时间窗口工程常用。死锁检测和解除是必备的安全机制。上一篇第275篇 多机器人系统架构下一篇聊人机交互设计。如果这篇文章对你有帮助欢迎点赞支持一下你的鼓励是我持续更新的动力