Dijkstra、A*与CBS：多智能体路径规划算法选型与实战-北京尧图网络

1. 从游戏寻路到多机协同三种路径规划算法的真实分工很多人第一次接触路径规划是在游戏里看到角色自动绕过障碍物走到目标点。但真正把这套东西落地到实际项目里你会发现单智能体的最短路径和多智能体的协同避障完全是两个难度量级的问题。Dijkstra、A*、CBS这三个算法恰好代表了从能走通到走得快再到大家一起走还不撞的三个阶段。我做过不少仓储机器人调度和游戏AI寻路的项目踩过的坑基本都集中在这三个算法的边界条件和切换时机上。这篇文章适合谁看如果你正在做AGV调度、游戏AI、无人机编队或者单纯想搞明白路径规划到底怎么从理论落到代码那接下来的内容应该能帮你省掉不少查文档和试错的时间。我会把每个算法的核心逻辑拆开讲清楚更重要的是告诉你什么场景该用哪个、参数怎么调、多机协同时哪里最容易出问题。先说一个反直觉的结论大部分实际项目里A*比Dijkstra用得多但CBS才是多机场景的真正门槛。很多人以为把A跑多遍就能解决多机问题结果一上线就发现机器人互相堵死。这不是A的问题是问题建模的维度变了。2. Dijkstra算法为什么它是最可靠的兜底方案2.1 核心逻辑从起点向外均匀扩散Dijkstra的本质是贪心加广度优先搜索。它从起点开始每次选出当前距离最小的节点然后更新它所有邻居的距离。这个过程像往水里扔石头波纹均匀向外扩散直到覆盖到终点。它的数学基础是最优子结构如果从起点到终点的最短路径经过节点X那么起点到X的路径也一定是最短的。这个性质保证了算法的正确性。用生活类比来说Dijkstra就像你在一个陌生城市找路每到一个路口就记录到该路口的最短距离然后继续探索没走过的路口直到找到目的地。它不关心方向只关心距离。2.2 为什么它慢但依然不可替代Dijkstra的时间复杂度是O((VE)logV)V是节点数E是边数。在栅格地图上如果地图是1000x1000那就是一百万个节点跑一次可能要几秒甚至更久。这也是为什么很多人一上来就用A*。但Dijkstra有一个A替代不了的优势它给出的是从起点到所有节点的最短距离。这意味着如果你需要频繁查询从起点到任意点的最短路径Dijkstra跑一次就够了后续查询都是O(1)的查表操作。而A每次查询都要重新跑。我在一个仓储项目里就遇到过这种情况调度系统需要实时计算从充电桩到任意货架的最短距离用来决定哪个机器人去哪个货架最划算。这时候用Dijkstra预计算一次全图距离表比每次用A*跑一遍要高效得多。2.3 实操中的参数与优化Dijkstra的代码实现核心是一个优先队列。Python里用heapqC里用priority_queue。关键参数是边的权重。在栅格地图上如果允许斜向移动斜边的权重应该是直边的1.414倍根号2而不是1。这个细节很多人会忽略导致路径长度计算不准。import heapq def dijkstra(graph, start): dist {node: float(inf) for node in graph} dist[start] 0 pq [(0, start)] while pq: d, u heapq.heappop(pq) if d dist[u]: continue for v, w in graph[u]: if dist[u] w dist[v]: dist[v] dist[u] w heapq.heappush(pq, (dist[v], v)) return dist注意如果图里有负权边Dijkstra会失效。路径规划场景里一般不会有负权但如果你把下坡省力建模成负权那就得换Bellman-Ford了。实测下来在100x100的栅格地图上Dijkstra跑一次大约需要几十毫秒对于实时性要求不高的预计算场景完全够用。但如果地图再大一个量级就必须考虑A*了。3. A*算法启发式函数才是它的灵魂3.1 从均匀扩散到有方向地探索A*在Dijkstra的基础上加了一个启发式函数h(n)用来估计从当前节点到终点的距离。每次选择节点时不再只看已走距离g(n)而是看f(n)g(n)h(n)。这样算法会优先探索看起来更接近终点的方向大大减少了无效搜索。启发式函数的设计是A*的核心。常见的h(n)有启发式函数公式适用场景是否可采纳曼哈顿距离|x1-x2||y1-y2|四方向移动栅格是欧几里得距离sqrt((x1-x2)^2(y1-y2)^2)任意方向移动是对角距离max(dx,dy)(sqrt(2)-1)*min(dx,dy)八方向移动栅格是切比雪夫距离max(|x1-x2|,|y1-y2|)八方向移动且代价相同是可采纳性是指h(n)永远不会高估实际距离。如果高估了A*可能找到的不是最短路径。这是很多人踩的坑为了让算法跑得更快把h(n)乘了一个大于1的系数结果路径变长了。3.2 权重系数速度与最优性的权衡实际项目中我们经常用加权A*即f(n)g(n)w*h(n)w1。这样搜索更有方向性速度更快但路径可能不是最优的。w越大越接近贪心最佳优先搜索。我在游戏AI项目里常用w1.2到1.5。玩家根本感觉不到路径长了百分之几但帧率提升很明显。具体调多少要看地图复杂度和性能预算。如果地图障碍物密集w可以大一点如果地图空旷w1就够了。3.3 代码实现中的三个关键细节import heapq def a_star(graph, start, goal, h): open_set [(h(start), start)] g_score {start: 0} came_from {} while open_set: _, current heapq.heappop(open_set) if current goal: path [] while current in came_from: path.append(current) current came_from[current] return path[::-1] for neighbor, cost in graph[current]: tentative_g g_score[current] cost if tentative_g g_score.get(neighbor, float(inf)): came_from[neighbor] current g_score[neighbor] tentative_g f tentative_g h(neighbor) heapq.heappush(open_set, (f, neighbor)) return None第一个细节是优先队列里可能存有同一个节点的多个条目。因为每次更新g值都会push一个新条目旧条目还在队列里。所以弹出节点时要检查当前g值是否比记录的更差如果是就跳过。上面的代码里用if d dist[u]做了这个检查。第二个细节是启发式函数必须和移动模型匹配。如果你的机器人只能上下左右走却用了欧几里得距离虽然可采纳但搜索效率会下降。因为欧几里得距离比曼哈顿距离小启发式不够紧算法会探索更多节点。第三个细节是地图表示。栅格地图用二维数组路网图用邻接表。如果地图很大考虑用跳点搜索JPS优化它能在对称路径上跳过大量节点。不过JPS实现复杂一般项目用标准A*就够了。提示A在动态环境里需要重新规划。如果障碍物是移动的每次环境变化都要重跑A。这时候可以用D* Lite它能在环境变化时增量更新路径比重跑快得多。4. CBS算法多智能体路径规划的真正解法4.1 为什么多机不能简单跑多次A*假设你有三个机器人起点和终点交叉。如果分别给每个机器人跑A*它们很可能选择同一条最短路径然后在中间撞上。更糟的是如果它们互相把对方当成静态障碍物可能陷入死锁A等B让路B等C让路C等A让路。多智能体路径规划MAPF的目标是找到一组无冲突的路径冲突包括顶点冲突两个智能体在同一时间到达同一节点边冲突两个智能体在同一时间交换位置相向而行跟随冲突一个智能体紧跟在另一个后面如果前者突然停下后者会撞上CBSConflict-Based Search的思路很巧妙先在低层给每个智能体独立规划路径然后在高层检测冲突针对冲突添加约束再重新规划。4.2 两层搜索的完整流程CBS分两层低层对每个智能体在考虑约束的情况下跑A*。约束形式是智能体i在时间t不能出现在节点v或智能体i在时间t不能从u走到v。高层维护一个约束树。每个节点包含一组约束和对应的路径集合。每次从优先队列里取出代价最小的节点检测冲突。如果没有冲突就找到了解。如果有冲突选择其中一个冲突生成两个子节点一个给智能体i添加约束另一个给智能体j添加约束。# 伪代码示意 def cbs(agents, map): root Node(constraints{}, paths{a: a_star(a, map) for a in agents}) open_list [root] while open_list: node open_list.pop_min_cost() conflict detect_conflict(node.paths) if not conflict: return node.paths agent_i, agent_j, loc, time conflict for agent in [agent_i, agent_j]: new_constraints node.constraints [(agent, loc, time)] new_paths dict(node.paths) new_paths[agent] a_star(agent, map, new_constraints) if new_paths[agent] is not None: open_list.append(Node(new_constraints, new_paths)) return None4.3 冲突检测与约束传播的实操细节冲突检测要遍历所有智能体的路径按时间步对齐。如果两个智能体在同一时间步出现在同一节点就是顶点冲突。如果智能体i在t时刻在u、t1时刻在v而智能体j在t时刻在v、t1时刻在u就是边冲突。约束传播时要注意添加约束后低层A*必须考虑时间维度。也就是说A*的状态空间从二维的(x,y)变成了三维的(x,y,t)。这会让搜索空间变大但CBS的高层剪枝能有效控制。我在一个多AGV调度项目里实测过10个智能体、50x50的地图CBS能在几百毫秒内找到解。但如果智能体数量超过20个或者地图有大量狭窄通道CBS的耗时可能飙升到几秒甚至超时。这时候需要用CBS的改进版比如ECBS增强CBS或MA-CBS元智能体CBS。4.4 CBS的局限与替代方案CBS的最大问题是最坏情况下指数级复杂度。当冲突很多时约束树会爆炸。实际项目中我们通常加一个时间限制超时就返回当前最优解或者降级到优先级规划给智能体排优先级依次规划后面的把前面的当动态障碍物。优先级规划实现简单但可能找不到解即使解存在。CBS保证完备性和最优性但慢。选择哪个取决于你的场景如果智能体数量少、地图简单CBS没问题如果数量多、实时性要求高优先级规划加局部避障可能更实用。5. 三个算法的选型对照与混合使用策略5.1 什么场景用什么算法场景推荐算法理由单智能体、需要全图距离Dijkstra一次计算多次查询单智能体、实时寻路A*速度快路径最优多智能体、数量少、要求最优CBS保证无冲突且最优多智能体、数量多、实时性高优先级规划局部避障速度快可能次优动态环境、障碍物移动D* Lite增量更新避免重跑5.2 混合使用的实际案例在一个仓储机器人项目里我们的方案是先用Dijkstra预计算所有充电桩到所有货架的距离表用于任务分配然后用A*给每个机器人规划初始路径最后用CBS的简化版只检测冲突不保证最优做多机协调。这样兼顾了速度和可用性。另一个技巧是分层规划全局用A*或CBS规划粗略路径局部用动态窗口法DWA或时间弹性带TEB做实时避障。全局规划负责大方向对局部规划负责不撞上突然出现的人或叉车。5.3 性能优化的几个实用手段地图预处理把栅格地图转成路网图减少节点数量。比如把连续的空闲区域合并成一个节点只在拐角处保留节点。启发式函数缓存如果终点固定可以预计算每个节点到终点的启发式距离避免重复计算。并行化CBS的低层A*可以并行跑每个智能体一个线程。高层冲突检测也可以并行。时间窗口多机规划时不需要规划到无穷远的时间。通常规划未来几十步就够了之后重新规划。注意并行化CBS时低层A*的约束是独立的但高层约束树是共享的。需要加锁保护约束树的读写否则会出现竞态条件。6. 踩坑记录那些文档里不会写的教训6.1 启发式函数写错导致路径绕远有一次在八方向栅格地图上我用了曼哈顿距离做启发式。结果A*找到的路径虽然是最短的但搜索效率极低因为曼哈顿距离严重高估了对角移动的距离。换成对角距离后搜索节点数减少了60%。启发式函数必须和移动模型严格匹配这是铁律。6.2 CBS约束添加顺序影响巨大CBS在分裂冲突时选择哪个冲突、给哪个智能体加约束会极大影响搜索效率。我试过随机选择结果同一个场景有时几十毫秒出解有时几秒都出不来。后来改成优先选择冲突最多的智能体加约束稳定性好了很多。这个策略叫最受约束智能体优先。6.3 时间步长设置不当导致假冲突CBS里时间步长是离散的。如果两个智能体实际不会撞但因为时间步长太粗被判定为冲突就会产生不必要的约束拖慢搜索。反过来时间步长太细状态空间爆炸。一般取机器人移动一个栅格所需的时间作为步长。6.4 动态障碍物处理A*和CBS都假设环境静态。如果环境里有移动的人或其他机器人需要定期重规划。重规划频率太高会浪费计算资源太低会撞上。我的经验是局部避障用反应式方法如DWA全局重规划每秒钟一次。这样既安全又高效。6.5 内存爆炸CBS的约束树在冲突多时会占用大量内存。我遇到过跑了几分钟后内存爆掉的情况。解决办法是限制约束树深度超过阈值就放弃当前分支或者用迭代加深的方式逐步放宽约束。7. 写在最后一些个人体会路径规划这个领域算法本身并不复杂难的是把算法和实际场景的约束对齐。Dijkstra、A*、CBS这三个算法分别对应了距离计算、单机寻路、多机协调三个层次。很多项目失败不是因为算法选错了而是因为没想清楚问题的层次。我个人的习惯是先用Dijkstra跑一遍全图看看距离分布是否合理再用A*验证单机路径最后用CBS做多机测试。如果CBS太慢就降级到优先级规划同时加局部避障兜底。这套流程在几个项目里都跑通了希望对你有参考价值。另外如果你在做多机规划强烈建议先把冲突检测和约束传播的逻辑写对再考虑优化。我见过太多人一上来就调参数结果发现是冲突检测漏了一种情况。基础不牢地动山摇。

Dijkstra、A*与CBS：多智能体路径规划算法选型与实战

相关推荐

汉诺塔移动次数统计：记忆化搜索与状态设计详解

Scrapy日志系统实战：配置、优化与常见问题排查

Ubuntu离线中文语音识别实战：从环境搭建到效果调优

更多资讯

sim-use 3分钟上手：observe-act-verify循环让AI验证自己写的移动App

智谱刚把 GLM-5.3 搬上 Amazon Bedrock，股价应声涨近 5%：国产大模型出海怎么突然就火了

C++手写CSV解析器：从状态机到流式处理实战

Pomotroid 土耳其语本地化实践：基于 Paraglide 的 8 语言架构与新增 locale 全流程

openJiuwen DeepSearch 研究规划提示模板（planner/user.md）深度解析：从 Jinja 渲染到计划生成的全链路实现

【宠粉赠书】分布式系统性能优化：方法与实践——用 TaoToken 统一 Key 打通压测与调优链路

今日更新

Susi AI API实战指南：susi_alexa_skill如何用Node.js调用chat.json获取智能回答

换新电脑了？KeyStats 恢复码数据找回完全指南，端到端加密统计一键重建

重建二叉树：由前序与中序遍历序列还原二叉树的原理与 Java 实现（YCBlogs 剑指 Offer 精讲）

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？