多机器人规划：让机器人在同一片路口学会礼让同行

可视化演示

展示多机器人规划三大核心：路径规划（8×6网格3机器人R1/R2/R3独立A*寻路5障碍物避障）、冲突解决CBS（冲突检测R1/R2路径交叉CF→搜索树分支约束重路由→无冲突最优解）、集中式vs分布式对比（CBS全局最优但慢O(n^k） vs 优先级局部反应快速但次优O(n)),三模式切换理解多机器人协调全貌。

基本概念：共享空间里的早高峰

清晨的十字路口，四条路上都排满了赶时间的人。每个人的目标不同，但地面只有一个，空间是共享的。多机器人规划面对的问题一模一样：多台机器人在同一片物理空间中执行各自任务，它们共享工作空间、共享通道、共享路口，任何一个都不能把别人当成空气。

从单机器人规划到多机器人规划，最大的变化在于“协调”。单机器人只要考虑自己与静态障碍物的关系，而多机器人系统里，每一个移动的机器人对其他机器人来说都是“动态障碍”。你不仅要规划自己的路，还要预测别人怎么走、什么时候可能挡路、谁该让谁。这些交互带来了成倍增加的计算负担。

这就是为什么现实中的多机器人系统不能靠“把所有机器人两两配对检查一遍”来硬算。早高峰的交警不会挨个问每个司机“你和谁可能撞车”，他需要用规则、优先级、红绿灯来把平方级的混乱降下来——这也正是后面各种规划方法的目标。

集中式规划：总交警台的统一指挥

想象一座小城市，只有一个总交警台。交警通过摄像头看到所有车辆的位置和目的地，在电脑上算好每辆车的红绿灯时长和放行顺序，然后通过信号统一指挥。所有车辆都按这个全局方案行驶，理论上可以做到整体最优——这就是集中式规划。

集中式规划的核心思想，是把多台机器人当成一个整体看待。它不再分别考虑“机器人 1 的路径”和“机器人 2 的路径”，而是构造一个“联合状态空间”：把每个机器人的状态空间放在一起，形成一个更高维度的空间，然后在其中搜索一条整体路径。

集中式规划的优点非常诱人：全局一致，不会出现两台车互相矛盾的行动指令，能找到全局最优解。但它的代价也像总交警台一样明显——如果城市很大、车辆很多，指挥中心根本算不过来。每增加一台机器人，状态空间的维度就增加一维，搜索量呈指数爆炸。所以集中式规划只适合机器人数量较少、环境相对简单的场景。

分布式规划：没有总控的老司机们

现实中，大多数城市并没有一个全知全能的总交警台。每个司机靠眼睛观察、靠转向灯交流、靠默认的交通规则完成避让——这更像分布式规划。每台机器人先独立规划自己的路径，运行时通过局部感知和信息交换来调整，谁发现问题谁就让一步。

分布式规划也叫解耦规划，它的基本思路是“先各自为政，再局部协商”。每台机器人只对自己的路径负责，在运动过程中检测到与其他机器人的潜在冲突时，通过局部的速度调整、路径微调来化解。这种方式的优点是可以扩展到几十上百台机器人，某一台出故障也不会让整个系统瘫痪。

分布式规划像一群默契的老司机：没有中央指令，但靠着观察、让行和沟通就能在早晚高峰里穿行。代价是它很难保证全局最优——每台车只顾眼前的路况，可能两台车在局部反复互相避让，绕了远路。不过对大规模系统来说，“够用且能扩展”往往比“全局最优但算不动”更实际。

优先级规划：救护车先行的默契

城市的交通规则里，永远有一些车享有“优先权”：救护车鸣笛时，社会车辆纷纷让行。不是因为救护车更会开车，而是因为它被赋予了更高优先级。多机器人规划也大量使用这个思路：给每台机器人分配一个优先级编号，编号高的先规划，编号低的把高优先级机器人的轨迹当作“移动障碍物”来绕开。

优先级规划的计算逻辑非常清晰：按优先级从高到低依次求解。第一台机器人畅通无阻地规划自己的最优轨迹；第二台机器人规划时，必须避开第一台的轨迹；第三台要同时避开前两台……依此类推。高优先级者“插队”成功，低优先级者自动绕行或等待。

优先级规划虽不能保证全局最优，但计算量小、实现简单，而且实际效果非常好——这就是为什么绝大多数仓库里的 AGV 调度系统都在用类似“让行规则”。它把复杂的多机同时规划问题，拆成了一个个简单的单机避障问题，像排队过窄巷一样稳健。

速度障碍法：老司机的预判艺术

真正成熟的老司机，不会等两车快要贴上时才踩刹车。他会观察对方的车速和方向，心里快速算一笔账：“以他现在这个速度，三秒后正好会到我的车道。”于是提前轻点刹车或打一把方向，优雅地错开。速度障碍法（Velocity Obstacle）就是这个预判过程的数学化。

速度障碍法的核心是利用“相对速度”。把其他机器人的速度折算到自己身上来看，如果按照当前相对速度和方向继续走下去，会在未来某一时刻撞上对方，那么这个速度就落入了“碰撞锥”；反之则是安全速度。动态窗口法（DWA）进一步把这个思路工程化：在每个控制周期里，根据当前速度和加速度限制，圈出一个可行的速度窗口，在这个窗口内采样一批候选速度，分别打分，选出最优。

老司机的预判能让他不刹车也能错车，靠的就是对相对速度的敏感。速度障碍法也是如此——它不是看到障碍再绕路，而是在速度层面提前排除所有“危险速度”，让机器人在每一个瞬间都自动避开动态风险。这种反应式避障思路，正是无人机和移动机器人最常用的安全网。

死锁规避：四个方向谁也不让谁

最让人崩溃的交通场景是什么？不是慢，而是堵死：四个方向的车都涌进路口，互相别住，谁也无法前进。每个人都想等别人先动，结果谁都不动。在多机器人系统里，这种状态叫“死锁”，一旦出现，整个系统就停摆了。

死锁有四个经典必要条件：互斥、占有并等待、不可抢占、循环等待。多机器人场景中最常见的是“循环等待”——机器人 A 等着 B 让路，B 等着 C 让路，C 又等着 A 让路。判断死锁有一个高效工具：等待图。把每台机器人画成一个点，如果 A 在等 B，就画一条从 A 指向 B 的边；当这个图里出现闭环，就意味着循环等待发生了。

解决死锁的思路也随之而来：要么在设计阶段就避免形成环（比如优先级让行、单向通行规则）；要么在运行阶段检测到环后主动打破它（比如让某台机器人倒退、绕行或等待超时重规划）。这就像现实路口在堵死之后，总会有司机主动倒车让出空间，僵局才被打破。

工程应用：真正早高峰的落地答卷

城市交通规划最终要服务于真实生活，多机器人规划也一样。今天最典型的应用场景已经在我们身边批量出现：电商仓库里上千台 AGV 在货架间穿行取货，它们共享巷道、共用路口，却极少碰撞；城市低空物流中，无人机编队要在同一片空域里各自飞往目的地；园区安防巡逻中，多台机器人接力覆盖同一片区域。

这些真实系统的共同策略是“分层组合拳”：全局层做任务分配和粗略路径规划，局部的动态层用速度障碍法、动态窗口法做实时避碰，再叠加优先级规则和死锁检测兜底。任务分配本身也是一个经典优化问题——把哪台机器人派往哪个任务，才能使总代价最小？

回到开头的早高峰十字路口：真正的城市不会只靠一种方法解决交通问题，它同时有红绿灯、公交专用道、救护车优先、交警手势等多种机制。工程中的多机器人规划也一样，把集中式、分布式、优先级、速度障碍和死锁预防巧妙组合，才能让成百上千台机器人在同一片空间里各行其道、井然有序。

---

AI 应用场景

Python 演示

import mathimport random  class Robot:    """一台在窄巷中行驶的机器人，具有优先级和是否到达状态。"""     def __init__(self, name, start, goal, priority):        self.name = name        self.x, self.y = start        self.gx, self.gy = goal        self.priority = priority        self.speed = 2.0        self.done = False     def move(self, others):        """根据其他机器人位置决定前进还是等待。"""        if self.done:            return         # 发现前方有更高优先级的机器人挡路时，原地等待        for other in others:            if other.priority < self.priority and not other.done:                if abs(other.x - self.x) < 15 and abs(other.y - self.y) < 15:                    return  # 让行，原地等待         dx = self.gx - self.x        dy = self.gy - self.y        dist = math.hypot(dx, dy)        if dist < self.speed:            self.x, self.y = self.gx, self.gy            self.done = True            return         # 朝目标方向移动固定步长        self.x += self.speed * dx / dist        self.y += self.speed * dy / dist  def simulate():    """模拟两台机器人在同一巷道相向而行，用优先级让行避免碰撞。"""    robot_a = Robot("A", (0, 50), (100, 50), priority=1)    robot_b = Robot("B", (100, 50), (0, 50), priority=2)     for t in range(60):        robot_a.move([robot_b])        robot_b.move([robot_a])         if robot_a.done and robot_b.done:            print(f"t={t}: 两台机器人全部到达，全程无碰撞")            return         print(            f"t={t:02d} "            f"A=({robot_a.x:6.1f},{robot_a.y:5.1f}) "            f"B=({robot_b.x:6.1f},{robot_b.y:5.1f})"        )     print("达到最大时间步，仍未全部到达（可能死锁）")  if __name__ == "__main__":    random.seed(42)    simulate()

1. class Robot:定义一台机器人，包含位置、目标点、优先级和速度属性。
2. self.priority = priority记录该机器人的让行优先级，数值越小优先级越高。
3. def move(self, others):每步决策的核心方法，输入其他机器人列表，输出本次移动结果。
4. if other.priority < self.priority只有遇到比自己优先级更高的机器人才会让行，同级或更低则无视。
5. abs(other.x - self.x) < 15判断对方是否进入了自己的“等待区”，避免过早刹车。
6. return # 让行，原地等待让行就是什么都不做，当前位置保持不变。
7. self.x += self.speed * dx / dist用方向向量归一化后移动固定步长，实现匀速直线运动。
8. for t in range(60):最多模拟 60 个时间步，防止死锁时无限循环。
9. robot_a.move([robot_b])每步先让 A 决策，再让 B 决策，模拟分布式逐个决策过程。

常见误区

面试题