2026/9/16 15:45:45
FEATURED · 精选文章 
简介面向多AGV物流分拣场景的CBS算法路径规划仿真系统源于本科毕业设计已在实测中运行通过并开源分享。系统基于Conflict-Based Search架构实现多智能体路径搜索与冲突消解可自定义地图、起点终点及障碍物并输出无冲突路径适合计算机、人工智能、自动化等专业学生参考毕设、课程设计或项目立项。压缩包共34个文件以21个JavaScript的算法与交互代码为主包含AStar、CBS、Agent、Environment等核心模块及p5.js渲染库另含Python脚本、CSS样式、Word开发说明手册、图片与字体资源整体大小10.77MB目录清晰便于按需查阅。目前已有237人学习/下载。资源提供完整源码、项目开发说明与可直接运行的演示程序代码测试通过且逻辑基本无bug既可直接用作毕业设计成果也可在此基础上扩展功能或改造为其他多机器人调度仿真场景。1. 多AGV调度为什么必须上CBS在电商仓库里几十台AGV同时在地图里跑单机A*规划出的路径合在一起经常在路口撞上。如果只让一台车停下可能引发连锁死锁。CBSConflict-Based Search基于冲突的搜索把多机路径规划拆成两层低层只负责单机最短路径高层专门处理冲突。它是目前求解带约束多AGV路径规划最常用的框架之一。这套基于CBS算法多AGV路径规划仿真系统用JavaScript实现了完整的CBS流程带p5.js可视化界面、地图预处理脚本和调试工具适合拿来研究算法也适合直接改造成课程设计或毕业设计的演示基础。接下来我会从算法原理、工程实现、调参上手三个层面拆解它。2. CBS算法核心低层A*与高层约束树的分层消解多AGV路径规划的本质是在时间和空间两个维度上保证agent不相撞。如果把问题直接建模成一个大的搜索空间状态会随agent数量指数爆炸。CBS的聪明之处是把问题分解成两个搜索层级低层是普通A*高层是一棵约束树。每个节点代表一组时间-空间约束低层在这些约束下为每个agent单独找路高层则负责发现约束树节点内部路径之间的冲突再把冲突转换为新约束继续扩展。项目里AStar.js和AStar_v2.js是低层实现CBS.js和CBS_v2.js是高层实现文件划分本身就是算法设计的一种体现。2.1 低层A*单机路径代价计算与启发函数设计低层A的作用是在给定的约束集合下为单个agent从起点搜索到终点的最优路径。标准A用g值记录从起点到当前格子的累计代价用h值估计从当前格子到终点的最小代价fgh每次从open表里取f最小的节点扩展。多AGV场景下路径代价不能只看路程长度还要看agent是否会为了躲避冲突而绕路或等待。项目里的AStar_v2.js可能就是在基础AStar.js上扩展了时间维度让搜索状态从(x,y)变成(x,y,t)这样高层约束才能生效。// 低层A*的核心搜索逻辑工程简化版实际需要closed表 function aStar(grid, start, goal, constraints) { const open new PriorityQueue((a, b) a.f - b.f); const startNode { x: start.x, y: start.y, g: 0, h: heuristic(start, goal), parent: null }; open.push(startNode); while (!open.isEmpty()) { const cur open.pop(); if (cur.x goal.x cur.y goal.y) return reconstruct(cur); for (const dir of DIRS) { const nx cur.x dir[0], ny cur.y dir[1]; if (!inside(grid, nx, ny) || !grid[ny][nx].walkable) continue; const t depth(cur) 1; if (isForbidden(constraints, cur.agentId, nx, ny, t)) continue; const g cur.g stepCost(cur, dir); open.push({ x: nx, y: ny, g, h: heuristic({x: nx, y: ny}, goal), parent: cur }); } } return null; }代码里有几个点值得重点看。isForbidden检查的是时空约束比如高层约束树里有一条{agentId: 0, x: 2, y: 2, t: 4}那么低层搜索在时间步4就不能进入格子(2,2)。stepCost返回单步移动代价如果开了等待选项还可以返回原地等待的代价。如果不希望agent转弯可以在这里增加转弯惩罚系数让搜索倾向直线路径。启发函数h的选择直接决定搜索效率下面是我常用的配置表运动模型单步代价启发式适用场景四方向水平/垂直1曼哈顿距离直角转向的AGV八方向直线1对角1.4对角距离全向移动底盘带转弯惩罚直线1转弯0.5曼哈顿最小转弯数叉车式AGV项目的地图坐标通过Cell.js维护四方向和八方向的区别就在DIRS数组长度。由于CBS低层会被反复调用很多次我建议把启发函数设为可配置项避免每次改动都重写AStar.js。项目里的BasicConfigs.js里如果没暴露这个参数你可以自己加一个directionMode字段后续做实验对比时很有用。2.2 高层约束树冲突检测与约束添加高层约束树的搜索节点是一个“约束集合”加上一组“路径解”。初始节点不含任何约束每个agent直接走最短路径。接下来检测agent之间的冲突常见的冲突有顶点冲突和边冲突。顶点冲突是同一时间两个agent在同一格边冲突是两个agent在同一时间步交换位置比如A从(1,1)移到(2,1)B从(2,1)移到(1,1)。如果检测到冲突就针对冲突涉及的两个agent分别生成一个子节点每个子节点给其中一个agent增加一个“禁止在某个时间到达某个位置”的约束然后重新调用低层A*求解。// 约束树节点结构与冲突检测入口 class CTNode { constructor() { this.constraints []; // 每个约束形如 { agentId, x, y, t, type } this.solution {}; // agentId - path 数组 this.cost 0; // 所有agent路径长度总和 } findFirstConflict() { for (let i 0; i agentIds.length; i) { for (let j i 1; j agentIds.length; j) { const conflict detectConflict(this.solution[i], this.solution[j]); if (conflict) return conflict; } } return null; } }这里的关键是冲突选择策略。CBS的解质量取决于每次迭代选择哪个冲突去分裂。经验做法是选择时间最早的冲突因为越早的冲突越可能影响后续路径的结构。另一个做法是优先选择两个agent路径交点附近的冲突这样分支更均衡。项目里CBS.js如果没有显式配置默认应该就是按时间顺序扫描的。约束树生成子节点后全部放进优先队列按cost升序排列。这里cost是所有agent路径长度之和因此CBS天然是最优算法——它本质上是在隐式枚举所有约束组合然后用低层A*快速求出每种组合的最优路径。需要注意的是约束树节点数在最坏情况下会指数增长所以工程实现里要加迭代上限。我在做毕业设计时设的是500地图稍大一点也能在几秒内完成。2.3 从AStar.js到CBS.js的协作看源码时我习惯先找调用点。在这套系统里sketch.js是主入口它初始化Environment创建Agent列表然后调用CBS.js的solve方法。solve方法内部会创建初始CTNode对每个agent调用AStar_v2.js或者AStar.js取决于BasicConfigs.js里的配置。当CBS求解结束后返回一组无冲突路径sketch.js再把路径交给每个Agent实例去逐帧渲染。我猜测CBS_v2.js是在CBS.js基础上做了两个改进一是把低层搜索结果缓存起来避免同一个约束组合被重复求解二是改用更高效的冲突选择函数比如基于“关键冲突”的排序。这些优化点对学习算法很有参考意义因为实际系统的性能瓶颈往往不在单个A*上而在约束树的反复求解次数。如果你也想重写一版保留这两个优化就够了。3. 仿真系统的模块化实现Environment、Agent与地图进程从index.html的脚本加载顺序可以看出系统分了三层libraries下的p5.js、jquery、lodash是基础库Environment.js、Agent.js、Cell.js是仿真对象CBS.js、AStar.js是算法层。这种分层让算法不需要关心渲染细节仿真对象也不需要关心约束树怎么展开。我在后面会按文件拆开讲方便你在IDE里对照代码看。3.1 Environment.js与Cell.js栅格地图的数据结构Environment是整个地图的总容器它维护rows和cols两个整数内部用一个二维数组存储Cell对象。Cell代表栅格地图里的一个格子除了保存walkable状态外还应该持有这个格子最近一次被哪个agent占用、在哪一个时间步被占用的信息。这样在渲染历史轨迹时可以直接从Cell中读取轨迹点不用额外维护一份路径数据。// Cell.js 的状态字段设计 class Cell { constructor(x, y) { this.x x; this.y y; this.walkable true; this.occupiedBy null; this.reservedTime -1; } }我在做仿真时还会给Cell增加一个costMultiplier字段用来模拟不同地面的摩擦系数比如一些区域AGV需要减速低层A*搜索时会把该格子的代价设为普通格子的1.5倍。这个改动很小但对路径规划的“经济性”影响很直观。Environment.js对外提供isWalkable(x, y)方法内部会先判断坐标是否越界再检查Cell.walkable。常见错误是忘记检查边界导致数组索引越界p5.js的console会报undefined错误。3.2 Agent.js状态推进与速度模型Agent类描述一个可移动的AGV实体包含起点start、终点end、当前坐标、求解出来的路径path和当前进度step。在CBS求解完成后Agent按照path逐格前进。因为CBS返回的路径是离散的格子序列Agent需要把离散序列平滑成连续动画否则小车会一跳一跳地移动。项目里Agent.js的做法大概是用当前坐标和目标格子的差值乘以一个速度因子速度因子越大动画越快但不影响算法层的时间步概念。update(dt) { if (!this.path || this.step this.path.length) return; const target this.path[this.step]; const dx target.x - this.x; const dy target.y - this.y; const dist Math.hypot(dx, dy) || 0.001; const move this.maxSpeed * dt; if (dist move) { this.x target.x; this.y target.y; this.step; } else { this.x dx / dist * move; this.y dy / dist * move; } }这段代码里maxSpeed的单位是格/秒dt是上一帧到这一帧的秒数。如果把maxSpeed设得很大动画看起来瞬间移动无法观察避让过程设得太小又觉得小车爬行。我的经验是设为2左右配合20x20的地图视觉节奏刚好。注意算法层的路径长度和动画层的速度没有直接关系一个时间步可以让小车移动一格也可以拆分成多帧插值只要最终到达时间一致即可。3.3 map_process/main.py批量地图的预处理与验证map_process目录下的main.py承担了地图生成和验证工作。在纯前端环境里如果每次手动在地图上点障碍物再测试CBS效率很低。所以一般会写一个Python脚本用随机方式生成带障碍物的地图并对每个agent的起点终点做连通性校验然后把地图数据导出成JSON文件前端通过configs.js加载。python map_process/main.py --rows 20 --cols 20 --obstacle 0.15 --agents 4 --output maps.json命令里的--obstacle 0.15表示15%的格子随机变成障碍物。脚本生成后会做一遍预检查如果某个agent的起点终点不在同一个连通分量里就直接跳过这个场景并打印警告。这样能避免在浏览器里跑CBS时莫名返回无解。我在实际使用中会让脚本同时生成多张地图并把每个场景的agent平均数量和障碍物比例保存到JSON里方便做算法性能对比。这里贴一张简化后的模块分工表方便你对照文件看文件职责主要对外接口Cell.js格子状态setOccupied, isWalkableEnvironment.js地图容器isWalkable, addObstacle, getRandomFreeCellAgent.js小车实体setPath, update, getPositionCBS.js高层冲突搜索solve, getCostAStar.js低层单机搜索findPath(start, goal, constraints)模块之间没有循环依赖Environment不依赖AgentAgent也不依赖CBS这让单元测试变得很容易。如果你想扩展比如增加一个Vehicle类型只需要继承Agent并重写update方法CBS求解逻辑完全不需要动。4. 实操从下载到跑通一个双AGV避让场景代码拿到手先别急着改把默认演示跑起来再看效果。这个系统是纯前端项目需要一个HTTP服务承载因为浏览器不允许file协议下用fetch加载本地JSON。虽然直接双击index.html也能显示页面但一旦涉及地图文件读取就会出现跨域报错。我在本地项目里习惯用Python起服务也支持npx serve。4.1 配置文件解析BasicConfigs.js与configs.js的调参点BasicConfigs.js保存算法运行配置configs.js保存当前演示场景的地图配置。两者的作用域不同前者影响CBS求解策略后者只定义一次测试用例。下面是一个典型的BasicConfigs.js内容const BasicConfigs { rows: 20, cols: 30, lowLevelVersion: astar_v2, // 使用AStar_v2.js或者改用astar highLevelVersion: cbs_v2, // 使用CBS_v2.js或者改用cbs allowWait: true, // 允许agent原地等待 maxIterations: 500, // 约束树最大扩展节点数 heuristic: manhattan, // 低层启发函数 conflictSelection: earliest // 冲突选择earliest / random };参数调优建议我放在下面的表里参数作用我的建议maxIterations约束树最大节点数小地图200大地图800allowWait是否允许原地等待出现死锁时打开heuristic低层启发函数四方向用manhattanconflictSelection冲突选择策略优先earliestallowWait打开后低层A*允许agent在某个时间步原地等待状态会从(x,y,t)扩展到(x,y,t1)搜索空间变大但更容易找到可行解。如果你的仓库模拟不允许AGV停在路中间就把这个参数设为false然后观察CBS是否还能消解冲突。maxIterations设得太小会提前退出返回无解但这个“无解”是不准确的设太大复杂场景可能要等几十秒。建议用二分法在当前地图规模下找到合理值。4.2 用本地HTTP服务跑通演示程序在项目根目录执行python -m http.server 8080打开浏览器访问http://localhost:8080。如果看到p5.js画布上出现几个不同颜色的小车从起点移动到终点说明系统正常。页面里一般会有一个调试面板显示当前CBS约束树迭代次数、总路径代价和每个agent的路径长度。这些日志可以直接辅助判断参数是否生效。提示如果打开页面后只有背景没有小车按下F12看控制台。常见问题是images目录下的png加载失败或者configs.js里agent的start/end超出地图边界。p5.js对这类错误往往只报一行ReferenceError非js从业者容易忽略。渲染正常后尝试在configs.js里修改agents数组的起点终点把某个agent的end改到障碍物上再刷新页面。你会看到CBS返回null或抛错这是正常的——低层A*找不到路径时整个约束树都无法构建。这个验证方法可以帮助你检查地图数据是否合法。4.3 手动构造一个双AGV交叉冲突场景为了直观看到CBS怎么避免碰撞我建议你临时改配置做一次5x5小地图的实验。设两个agent一个从左上角到右下角一个从左下角到右上角它们的曼哈顿最优路径必然在中心区域交叉。具体改动如下// configs.js 中的agents定义 agents: [ { start: { x: 1, y: 1 }, end: { x: 3, y: 3 }, color: #ff5722 }, { start: { x: 3, y: 1 }, end: { x: 1, y: 3 }, color: #2196f3 } ]刷新后你会看到CBS求解结束时两个agent依次通过中心点而不是同时到达。如果你打开调试日志还能看到第一次冲突检测报告的位置和时间戳。如果你想看边冲突可以让两个agent在一条2格长的通道里相向而行CBS同样会消解这个冲突只是约束类型会变成边约束。这个小实验是检验一个CBS实现是否完整的有效手段。5. 扩展与验证把CBS接到真实AGV调度系统的三个技巧当系统能稳定跑通后剩下的工作就是验证正确性和做性能优化。这三个技巧是实际工程中最常用的。5.1 用时间窗校验消解结果CBS返回的路径在动画里看着没有相撞但最好用脚本再验证一遍。我将每个agent的路径展开成时间窗列表例如agent 0在时间5位于(1,2)此时如果有另一个agent也在(1,2)就是冲突。用Python写一个checker遍历所有路径的每一时间步把所有agent映射到一个字典里键是(t,x,y)值是该时间点的agentId遇到相同键就报错。这个校验必须在修改任何调参代码后重跑防止引入回归。5.2 用JPS替换低层A*提速当CBS迭代到几百个节点时每个节点都要调用低层搜索低层A如果在50x50地图上跑耗时就变得明显。一个成熟的优化手段是把低层搜索替换成JPS。JPS在预处理阶段标注跳跃点和关键方向在线搜索阶段跳过大量无意义节点在开放地图上速度是A的数倍。这套项目里AStar_v2.js就是低层算法的替身你只要保证对外接口findPath(start, goal, constraints)不变内部换成JPS实现CBS完全不用改。5.3 动态障碍物与重规划策略真实仓库里会有临时障碍物比如人工堆放的货箱或者其他设备。CBS本身是离线算法但可以通过周期性重规划来适应动态变化。每次重规划前先更新Environment里的障碍物状态再对尚未到达终点的agent重新调用CBS。为了让重规划不打断正在执行的agent我会把已经到达或路径不受影响的agent标记为固定只对受影响Agent重新求解求解时以当前坐标为起点原终点不变。重规划期间我会把受影响agent的上一次约束集清空只保留起点终点和当前时刻这样CBS能在一个干净的子问题上重新求解而不用背负历史约束包袱。本文还有配套的精品资源点击获取
CBS算法多AGV路径规划仿真系统：原理、实现与调参
简介面向多AGV物流分拣场景的CBS算法路径规划仿真系统源于本科毕业设计已在实测中运行通过并开源分享。系统基于Conflict-Based Search架构实现多智能体路径搜索与冲突消解可自定义地图、起点终点及障碍物并输出无冲突路径适合计算机、人工智能、自动化等专业学生参考毕设、课程设计或项目立项。压缩包共34个文件以21个JavaScript的算法与交互代码为主包含AStar、CBS、Agent、Environment等核心模块及p5.js渲染库另含Python脚本、CSS样式、Word开发说明手册、图片与字体资源整体大小10.77MB目录清晰便于按需查阅。目前已有237人学习/下载。资源提供完整源码、项目开发说明与可直接运行的演示程序代码测试通过且逻辑基本无bug既可直接用作毕业设计成果也可在此基础上扩展功能或改造为其他多机器人调度仿真场景。1. 多AGV调度为什么必须上CBS在电商仓库里几十台AGV同时在地图里跑单机A*规划出的路径合在一起经常在路口撞上。如果只让一台车停下可能引发连锁死锁。CBSConflict-Based Search基于冲突的搜索把多机路径规划拆成两层低层只负责单机最短路径高层专门处理冲突。它是目前求解带约束多AGV路径规划最常用的框架之一。这套基于CBS算法多AGV路径规划仿真系统用JavaScript实现了完整的CBS流程带p5.js可视化界面、地图预处理脚本和调试工具适合拿来研究算法也适合直接改造成课程设计或毕业设计的演示基础。接下来我会从算法原理、工程实现、调参上手三个层面拆解它。2. CBS算法核心低层A*与高层约束树的分层消解多AGV路径规划的本质是在时间和空间两个维度上保证agent不相撞。如果把问题直接建模成一个大的搜索空间状态会随agent数量指数爆炸。CBS的聪明之处是把问题分解成两个搜索层级低层是普通A*高层是一棵约束树。每个节点代表一组时间-空间约束低层在这些约束下为每个agent单独找路高层则负责发现约束树节点内部路径之间的冲突再把冲突转换为新约束继续扩展。项目里AStar.js和AStar_v2.js是低层实现CBS.js和CBS_v2.js是高层实现文件划分本身就是算法设计的一种体现。2.1 低层A*单机路径代价计算与启发函数设计低层A的作用是在给定的约束集合下为单个agent从起点搜索到终点的最优路径。标准A用g值记录从起点到当前格子的累计代价用h值估计从当前格子到终点的最小代价fgh每次从open表里取f最小的节点扩展。多AGV场景下路径代价不能只看路程长度还要看agent是否会为了躲避冲突而绕路或等待。项目里的AStar_v2.js可能就是在基础AStar.js上扩展了时间维度让搜索状态从(x,y)变成(x,y,t)这样高层约束才能生效。// 低层A*的核心搜索逻辑工程简化版实际需要closed表 function aStar(grid, start, goal, constraints) { const open new PriorityQueue((a, b) a.f - b.f); const startNode { x: start.x, y: start.y, g: 0, h: heuristic(start, goal), parent: null }; open.push(startNode); while (!open.isEmpty()) { const cur open.pop(); if (cur.x goal.x cur.y goal.y) return reconstruct(cur); for (const dir of DIRS) { const nx cur.x dir[0], ny cur.y dir[1]; if (!inside(grid, nx, ny) || !grid[ny][nx].walkable) continue; const t depth(cur) 1; if (isForbidden(constraints, cur.agentId, nx, ny, t)) continue; const g cur.g stepCost(cur, dir); open.push({ x: nx, y: ny, g, h: heuristic({x: nx, y: ny}, goal), parent: cur }); } } return null; }代码里有几个点值得重点看。isForbidden检查的是时空约束比如高层约束树里有一条{agentId: 0, x: 2, y: 2, t: 4}那么低层搜索在时间步4就不能进入格子(2,2)。stepCost返回单步移动代价如果开了等待选项还可以返回原地等待的代价。如果不希望agent转弯可以在这里增加转弯惩罚系数让搜索倾向直线路径。启发函数h的选择直接决定搜索效率下面是我常用的配置表运动模型单步代价启发式适用场景四方向水平/垂直1曼哈顿距离直角转向的AGV八方向直线1对角1.4对角距离全向移动底盘带转弯惩罚直线1转弯0.5曼哈顿最小转弯数叉车式AGV项目的地图坐标通过Cell.js维护四方向和八方向的区别就在DIRS数组长度。由于CBS低层会被反复调用很多次我建议把启发函数设为可配置项避免每次改动都重写AStar.js。项目里的BasicConfigs.js里如果没暴露这个参数你可以自己加一个directionMode字段后续做实验对比时很有用。2.2 高层约束树冲突检测与约束添加高层约束树的搜索节点是一个“约束集合”加上一组“路径解”。初始节点不含任何约束每个agent直接走最短路径。接下来检测agent之间的冲突常见的冲突有顶点冲突和边冲突。顶点冲突是同一时间两个agent在同一格边冲突是两个agent在同一时间步交换位置比如A从(1,1)移到(2,1)B从(2,1)移到(1,1)。如果检测到冲突就针对冲突涉及的两个agent分别生成一个子节点每个子节点给其中一个agent增加一个“禁止在某个时间到达某个位置”的约束然后重新调用低层A*求解。// 约束树节点结构与冲突检测入口 class CTNode { constructor() { this.constraints []; // 每个约束形如 { agentId, x, y, t, type } this.solution {}; // agentId - path 数组 this.cost 0; // 所有agent路径长度总和 } findFirstConflict() { for (let i 0; i agentIds.length; i) { for (let j i 1; j agentIds.length; j) { const conflict detectConflict(this.solution[i], this.solution[j]); if (conflict) return conflict; } } return null; } }这里的关键是冲突选择策略。CBS的解质量取决于每次迭代选择哪个冲突去分裂。经验做法是选择时间最早的冲突因为越早的冲突越可能影响后续路径的结构。另一个做法是优先选择两个agent路径交点附近的冲突这样分支更均衡。项目里CBS.js如果没有显式配置默认应该就是按时间顺序扫描的。约束树生成子节点后全部放进优先队列按cost升序排列。这里cost是所有agent路径长度之和因此CBS天然是最优算法——它本质上是在隐式枚举所有约束组合然后用低层A*快速求出每种组合的最优路径。需要注意的是约束树节点数在最坏情况下会指数增长所以工程实现里要加迭代上限。我在做毕业设计时设的是500地图稍大一点也能在几秒内完成。2.3 从AStar.js到CBS.js的协作看源码时我习惯先找调用点。在这套系统里sketch.js是主入口它初始化Environment创建Agent列表然后调用CBS.js的solve方法。solve方法内部会创建初始CTNode对每个agent调用AStar_v2.js或者AStar.js取决于BasicConfigs.js里的配置。当CBS求解结束后返回一组无冲突路径sketch.js再把路径交给每个Agent实例去逐帧渲染。我猜测CBS_v2.js是在CBS.js基础上做了两个改进一是把低层搜索结果缓存起来避免同一个约束组合被重复求解二是改用更高效的冲突选择函数比如基于“关键冲突”的排序。这些优化点对学习算法很有参考意义因为实际系统的性能瓶颈往往不在单个A*上而在约束树的反复求解次数。如果你也想重写一版保留这两个优化就够了。3. 仿真系统的模块化实现Environment、Agent与地图进程从index.html的脚本加载顺序可以看出系统分了三层libraries下的p5.js、jquery、lodash是基础库Environment.js、Agent.js、Cell.js是仿真对象CBS.js、AStar.js是算法层。这种分层让算法不需要关心渲染细节仿真对象也不需要关心约束树怎么展开。我在后面会按文件拆开讲方便你在IDE里对照代码看。3.1 Environment.js与Cell.js栅格地图的数据结构Environment是整个地图的总容器它维护rows和cols两个整数内部用一个二维数组存储Cell对象。Cell代表栅格地图里的一个格子除了保存walkable状态外还应该持有这个格子最近一次被哪个agent占用、在哪一个时间步被占用的信息。这样在渲染历史轨迹时可以直接从Cell中读取轨迹点不用额外维护一份路径数据。// Cell.js 的状态字段设计 class Cell { constructor(x, y) { this.x x; this.y y; this.walkable true; this.occupiedBy null; this.reservedTime -1; } }我在做仿真时还会给Cell增加一个costMultiplier字段用来模拟不同地面的摩擦系数比如一些区域AGV需要减速低层A*搜索时会把该格子的代价设为普通格子的1.5倍。这个改动很小但对路径规划的“经济性”影响很直观。Environment.js对外提供isWalkable(x, y)方法内部会先判断坐标是否越界再检查Cell.walkable。常见错误是忘记检查边界导致数组索引越界p5.js的console会报undefined错误。3.2 Agent.js状态推进与速度模型Agent类描述一个可移动的AGV实体包含起点start、终点end、当前坐标、求解出来的路径path和当前进度step。在CBS求解完成后Agent按照path逐格前进。因为CBS返回的路径是离散的格子序列Agent需要把离散序列平滑成连续动画否则小车会一跳一跳地移动。项目里Agent.js的做法大概是用当前坐标和目标格子的差值乘以一个速度因子速度因子越大动画越快但不影响算法层的时间步概念。update(dt) { if (!this.path || this.step this.path.length) return; const target this.path[this.step]; const dx target.x - this.x; const dy target.y - this.y; const dist Math.hypot(dx, dy) || 0.001; const move this.maxSpeed * dt; if (dist move) { this.x target.x; this.y target.y; this.step; } else { this.x dx / dist * move; this.y dy / dist * move; } }这段代码里maxSpeed的单位是格/秒dt是上一帧到这一帧的秒数。如果把maxSpeed设得很大动画看起来瞬间移动无法观察避让过程设得太小又觉得小车爬行。我的经验是设为2左右配合20x20的地图视觉节奏刚好。注意算法层的路径长度和动画层的速度没有直接关系一个时间步可以让小车移动一格也可以拆分成多帧插值只要最终到达时间一致即可。3.3 map_process/main.py批量地图的预处理与验证map_process目录下的main.py承担了地图生成和验证工作。在纯前端环境里如果每次手动在地图上点障碍物再测试CBS效率很低。所以一般会写一个Python脚本用随机方式生成带障碍物的地图并对每个agent的起点终点做连通性校验然后把地图数据导出成JSON文件前端通过configs.js加载。python map_process/main.py --rows 20 --cols 20 --obstacle 0.15 --agents 4 --output maps.json命令里的--obstacle 0.15表示15%的格子随机变成障碍物。脚本生成后会做一遍预检查如果某个agent的起点终点不在同一个连通分量里就直接跳过这个场景并打印警告。这样能避免在浏览器里跑CBS时莫名返回无解。我在实际使用中会让脚本同时生成多张地图并把每个场景的agent平均数量和障碍物比例保存到JSON里方便做算法性能对比。这里贴一张简化后的模块分工表方便你对照文件看文件职责主要对外接口Cell.js格子状态setOccupied, isWalkableEnvironment.js地图容器isWalkable, addObstacle, getRandomFreeCellAgent.js小车实体setPath, update, getPositionCBS.js高层冲突搜索solve, getCostAStar.js低层单机搜索findPath(start, goal, constraints)模块之间没有循环依赖Environment不依赖AgentAgent也不依赖CBS这让单元测试变得很容易。如果你想扩展比如增加一个Vehicle类型只需要继承Agent并重写update方法CBS求解逻辑完全不需要动。4. 实操从下载到跑通一个双AGV避让场景代码拿到手先别急着改把默认演示跑起来再看效果。这个系统是纯前端项目需要一个HTTP服务承载因为浏览器不允许file协议下用fetch加载本地JSON。虽然直接双击index.html也能显示页面但一旦涉及地图文件读取就会出现跨域报错。我在本地项目里习惯用Python起服务也支持npx serve。4.1 配置文件解析BasicConfigs.js与configs.js的调参点BasicConfigs.js保存算法运行配置configs.js保存当前演示场景的地图配置。两者的作用域不同前者影响CBS求解策略后者只定义一次测试用例。下面是一个典型的BasicConfigs.js内容const BasicConfigs { rows: 20, cols: 30, lowLevelVersion: astar_v2, // 使用AStar_v2.js或者改用astar highLevelVersion: cbs_v2, // 使用CBS_v2.js或者改用cbs allowWait: true, // 允许agent原地等待 maxIterations: 500, // 约束树最大扩展节点数 heuristic: manhattan, // 低层启发函数 conflictSelection: earliest // 冲突选择earliest / random };参数调优建议我放在下面的表里参数作用我的建议maxIterations约束树最大节点数小地图200大地图800allowWait是否允许原地等待出现死锁时打开heuristic低层启发函数四方向用manhattanconflictSelection冲突选择策略优先earliestallowWait打开后低层A*允许agent在某个时间步原地等待状态会从(x,y,t)扩展到(x,y,t1)搜索空间变大但更容易找到可行解。如果你的仓库模拟不允许AGV停在路中间就把这个参数设为false然后观察CBS是否还能消解冲突。maxIterations设得太小会提前退出返回无解但这个“无解”是不准确的设太大复杂场景可能要等几十秒。建议用二分法在当前地图规模下找到合理值。4.2 用本地HTTP服务跑通演示程序在项目根目录执行python -m http.server 8080打开浏览器访问http://localhost:8080。如果看到p5.js画布上出现几个不同颜色的小车从起点移动到终点说明系统正常。页面里一般会有一个调试面板显示当前CBS约束树迭代次数、总路径代价和每个agent的路径长度。这些日志可以直接辅助判断参数是否生效。提示如果打开页面后只有背景没有小车按下F12看控制台。常见问题是images目录下的png加载失败或者configs.js里agent的start/end超出地图边界。p5.js对这类错误往往只报一行ReferenceError非js从业者容易忽略。渲染正常后尝试在configs.js里修改agents数组的起点终点把某个agent的end改到障碍物上再刷新页面。你会看到CBS返回null或抛错这是正常的——低层A*找不到路径时整个约束树都无法构建。这个验证方法可以帮助你检查地图数据是否合法。4.3 手动构造一个双AGV交叉冲突场景为了直观看到CBS怎么避免碰撞我建议你临时改配置做一次5x5小地图的实验。设两个agent一个从左上角到右下角一个从左下角到右上角它们的曼哈顿最优路径必然在中心区域交叉。具体改动如下// configs.js 中的agents定义 agents: [ { start: { x: 1, y: 1 }, end: { x: 3, y: 3 }, color: #ff5722 }, { start: { x: 3, y: 1 }, end: { x: 1, y: 3 }, color: #2196f3 } ]刷新后你会看到CBS求解结束时两个agent依次通过中心点而不是同时到达。如果你打开调试日志还能看到第一次冲突检测报告的位置和时间戳。如果你想看边冲突可以让两个agent在一条2格长的通道里相向而行CBS同样会消解这个冲突只是约束类型会变成边约束。这个小实验是检验一个CBS实现是否完整的有效手段。5. 扩展与验证把CBS接到真实AGV调度系统的三个技巧当系统能稳定跑通后剩下的工作就是验证正确性和做性能优化。这三个技巧是实际工程中最常用的。5.1 用时间窗校验消解结果CBS返回的路径在动画里看着没有相撞但最好用脚本再验证一遍。我将每个agent的路径展开成时间窗列表例如agent 0在时间5位于(1,2)此时如果有另一个agent也在(1,2)就是冲突。用Python写一个checker遍历所有路径的每一时间步把所有agent映射到一个字典里键是(t,x,y)值是该时间点的agentId遇到相同键就报错。这个校验必须在修改任何调参代码后重跑防止引入回归。5.2 用JPS替换低层A*提速当CBS迭代到几百个节点时每个节点都要调用低层搜索低层A如果在50x50地图上跑耗时就变得明显。一个成熟的优化手段是把低层搜索替换成JPS。JPS在预处理阶段标注跳跃点和关键方向在线搜索阶段跳过大量无意义节点在开放地图上速度是A的数倍。这套项目里AStar_v2.js就是低层算法的替身你只要保证对外接口findPath(start, goal, constraints)不变内部换成JPS实现CBS完全不用改。5.3 动态障碍物与重规划策略真实仓库里会有临时障碍物比如人工堆放的货箱或者其他设备。CBS本身是离线算法但可以通过周期性重规划来适应动态变化。每次重规划前先更新Environment里的障碍物状态再对尚未到达终点的agent重新调用CBS。为了让重规划不打断正在执行的agent我会把已经到达或路径不受影响的agent标记为固定只对受影响Agent重新求解求解时以当前坐标为起点原终点不变。重规划期间我会把受影响agent的上一次约束集清空只保留起点终点和当前时刻这样CBS能在一个干净的子问题上重新求解而不用背负历史约束包袱。本文还有配套的精品资源点击获取 
