接手过一个AGV清扫的项目甲方要求很简单整个园区车必须走完每一寸地面一个死角都不能留。最后验收的时候他们拿激光测距仪扫场地边缘发现确实有漏扫在那之后我很长一段时间都在和“全覆盖路径规划”这几个字较劲。现在提到AGV、扫地机器人大部分教程都在讲怎么从A点到B点什么A*、Dijkstra、RRT这些是点到点路径规划。但扫地车、植保机、擦窗机器人、洗地机这一类设备要的不是“从A到B”而是“把整个可走区域都走一遍”。这就是全覆盖路径规划英文叫Coverage Path Planning缩写CPP。你这个标题里写的“第一类算法”对应的就是CPP算法谱系里最经典、最稳定的那一支确定性全覆盖算法。如果你正在做毕业设计、AGV/扫地机产品预研或者想看懂别人写的那些“全覆盖代码”这篇内容应该能帮你把思路理顺顺带提供一份可以直接拿去跑的MATLAB实现。1. 先把“第一类算法”这几个字掰开揉碎1.1 全覆盖路径规划和普通路径规划的区别普通路径规划解决的是单次任务车从起点出发找一条代价最小的路径到终点路上避开障碍物。它不关心路径覆盖了多少区域只关心走的路径本身够不够短、够不够安全。全覆盖路径规划解决的是另一种问题车要把工作区域内的自由空间全部遍历一遍同时尽可能避免重复。路径经过的覆盖面是一个“面”而不是一条“线”。你可以买个问题就是“笔刷问题”——给你一张画布工作区域有一堆不能涂的区域障碍物要求用一支画笔把能涂的地方全部涂满重复涂的次数越少越好最终涂完的路径越短越好。这个区别是根本性的因为评价指标完全不同。点到点路径规划看“耗散度”和“避障成功率”全覆盖路径规划看“覆盖率”和“重复率”。覆盖率是指实际走过的有效区域占可通行区域的比例重复率是指重复走过的路程占总路程的比例。这两个指标才是全覆盖算法好坏的核心其他都是次要的。1.2 全覆盖算法的完整谱系第一类到底排在哪我在翻论文和GitHub代码的时候发现全覆盖路径规划算法的分类挺乱的不同文献叫法都不一样。但综合来看大致可以分成三个阵营第一类确定性全覆盖算法。这类算法的核心特点是路径生成规则是确定性的不依赖随机数同样的地图输入每次跑出来的结果几乎一样。典型代表包括弓字形往返覆盖Boustrophedon、螺旋式覆盖、基于梯形分解的覆盖、基于牛耕分解的覆盖等。这类算法逻辑简单、可解释性强、调试方便在扫地机器人、AGV上用得最多。你标题里说的“第一类算法”最合理的理解就是这种经典、确定性的全覆盖算法。第二类随机覆盖算法。典型代表是随机漫步Random Walk和基于采样方法的覆盖。这类算法在未知环境探索中比较常见机器人在没有先验地图的情况下瞎走靠传感器实时反馈判断哪里还没走。好处是能处理未知环境坏处是效率很低覆盖一个房间要来回绕很多圈没有确定性保障。第三类智能优化与学习类算法。包括遗传算法、粒子群优化、蚁群算法以及近年来火起来的强化学习全覆盖算法。这类算法的思路是把全覆盖路径看作一个优化问题用各种算法去“搜”出一个近似最优解。效果上限很高但计算量大、稳定性差调试起来非常痛苦。第一类算法之所以被称为“第一类”一方面因为它是历史上最早出现的全覆盖算法另一方面也因为它是其他所有算法的基础。很多智能算法的初始解、评价函数、行为策略都是从第一类算法里拆出来的。1.3 第一类算法适合什么场景我做AGV项目的时候一开始也想过直接上强化学习后来被导师泼了冷水。全覆盖算法选型要看你手里的牌有没有先验地图、车载算力多强、任务环境是不是基本静态。如果手里有先验地图哪怕是用SLAM攒出来的环境里没有太多动态障碍物而且车上的MCU或工控机算力一般那优先选第一类算法。它跑得快、容易验证、出问题了能定位到具体那一行代码。如果在完全未知的环境里探索比如无人机搜救、未知洞穴探索第一类就用不上了得用第二类做在线探索再用第一类局部覆盖。如果场地特别大、形状特别复杂比如几百个库位、一堆异形货架的仓库第一类算法算出来的路径可能不够优这时候可以上第三类但前提是你有充足的计算资源和调参时间。2. 环境建模全覆盖算法落地前必须解决的问题2.1 为什么最后都选了栅格地图全覆盖路径规划的第一步是让算法“理解”工作区域。目前主流的方案是栅格地图也叫占据栅格地图Occupancy Grid Map。把一块连续场地切成等大小的方格每个格子标记为三类状态空闲、占用、未知。扫地机器人的激光雷达和SLAM建图的输出本质上就是这种栅格表示。栅格大小是全流程里最关键的一个参数。栅格太小地图数据量巨大算法计算时间暴涨栅格太大路径边缘粗糙容易漏扫障碍物附近的区域。经验值是什么格子和机器人直径大致相当就行。比如一台直径250mm的扫地机器人用200mm~250mm的栅格就很合理。AGV的底盘大栅格也能放大。我常用的做法是先用MATLAB读入SLAM导出的二维占据栅格图把灰度图二值化然后按照机器人尺寸做一次膨胀处理。这个“膨胀”其实对应的是避障安全距离障碍物周围标成不可走的格子这样算法规划出来的路径就不会贴着墙或障碍物走。2.2 地图数据结构和MATLAB表示MATLAB里处理栅格地图最方便的就是二维矩阵。我习惯用occMap这个变量名存储1表示障碍物0表示可通行。这个定义方式做腐蚀膨胀、图像处理都方便。% 地图定义20x15格栅格地图四周是墙中间有两个矩形障碍物 rows 15; cols 20; occMap zeros(rows, cols); % 地图边界四周设为障碍物 occMap(1, :) 1; occMap(rows, :) 1; occMap(:, 1) 1; occMap(:, cols) 1; % 障碍物A矩形区域 occMap(5:7, 5:8) 1; % 障碍物B矩形区域 occMap(4:6, 13:15) 1; occMap(9:11, 9:12) 1;绘制地图用imagesc加一个colormap就能看到黑白格figure; imagesc(~occMap); axis equal; colormap(gray); hold on; grid on; set(gca, GridLineStyle, :, GridColor, [0.5 0.5 0.5], GridAlpha, 1);提示~occMap是为了让1显示成黑色0显示成白色视觉上更符合“黑色障碍物”的习惯。网格线保留下来方便调试这一步非常省事。2.3 膨胀安全距离的计算如果你的地图是传感器数据直接生成的那必须先做膨胀。最常用的方法是图像腐蚀/膨胀操作MATLAB里直接用imdilate就行。膨胀半径怎么定记住这个公式膨胀格数 机器人半径 / 栅格边长。如果机器人半径是300mm栅格边长是150mm那膨胀格数就是2。这意味着障碍物边界往里推2格路径规划器会把这2格当成障碍物处理车就不会撞上了。se strel(square, 2 * inflateGrid 1); inflatedOccMap imdilate(occMap, se);这个膨胀不只是安全考虑还有一个副作用是直接影响了覆盖率的上限。膨胀越大可走区域越小覆盖率上限就越低。所以安全距离也不能盲目放大够用就行。3. 核心算法拆解全知地图上的往返式全覆盖3.1 往返覆盖的直觉逻辑理解了地图就进入算法本身。第一类确定性全覆盖算法的三个经典代表往返式Bow-tie/Boustrophedon、螺旋式Spiral、分块往返式Morse-based Decomposition。最核心的是往返式。往返式覆盖的逻辑特别简单就是扫地时来回走S型。车从场地一边开始走直线走到另一边然后横向平移一个车身宽度掉头再走回来。就这样一行一行刷过去像农民耕地一样所以也叫牛耕式覆盖。别小看这个思路。它有三个强大之处一是无死角。只要场地是凸多边形或者被正确分解成凸子区域最朴素的往返扫描就能覆盖整个区域。二是重复率低。相邻两行路径之间的距离就是车身宽度理论上几乎没有扫描重叠重复率趋近于0。三是行行进简单。执行时车辆控制难度低就是直线行驶加掉头对里程计和运动控制系统的要求都很低。3.2 遇到障碍物怎么办行分解真实场地很少是纯凸多边形中间总会有柱子、桌子、货架。往返式全覆盖直接硬扫的话会被障碍物割裂成好几段路径。解决这个问题的方法叫“行分解”。每一行横向扫描时障碍物会把这一行分成长度不一的多个可通行区间。整个算法变成两步先把所有行分解成一个个可通行的行段再把这些行段串起来覆盖时按顺序走完。我在MATLAB里做了个简化版实现思路是把每一行的自由格子提取出来做连通块检测。这一行的可通行区域是一个一个的连通区间每个区间就是一个行段。function segments extractRowSegments(occMap) % 输入occMap0可通行1障碍物 % 输出segments结构体数组字段rowstartColendCol segments []; [rows, cols] size(occMap); for r 2 : rows-1 c 2; while c cols-1 if occMap(r, c) 0 startC c; while c cols-1 occMap(r, c) 0 c c 1; end endC c - 1; segments(end1).row r; segments(end).startCol startC; segments(end).endCol endC; else c c 1; end end end这里多加了个限制从第2行到第rows-1行是因为地图边缘已经标记成障碍物了不需要再处理边界。每个段都记录行号、起始列和结束列之后所有规划都建在这组段数据之上。提取出来的段要是不完整后面覆盖率肯定出问题所以这一步建议先做个调试打印看看个数对不对、有没有漏掉空白行。3.3 段之间的遍历顺序把全覆盖问题变成“路径连接问题”行段提取完之后全覆盖问题就转化成了段遍历顺序问题。比如一个20x15的地图障碍物把所有行切成了20来个段。你要设计一条路径把这20来个段都走一遍同时让段和段之间的“转场路径”尽量短。这个思想特别像旅行商问题TSP这也是为什么后面很多算法都用TSP的思路来解全覆盖问题。经典的贪心策略很简单每走完当前段就从所有没走过的段里挑一个“距离最近”的段。这个距离通常用当前段尾端点去找候选段的两个端点挑曼哈顿距离最短的那一个。曼哈顿距离是指按栅格水平或垂直移动的步数因为我们假设AGV是四向移动的。function coverageOrder greedySegmentOrder(segments, startRow, startCol) % 贪心搜索遍历顺序 n length(segments); visited zeros(1, n); coverageOrder zeros(1, n); currentRow startRow; currentCol startCol; for i 1 : n bestIdx -1; bestDist inf; for j 1 : n if visited(j) 0 d1 abs(currentRow - segments(j).row) ... abs(currentCol - segments(j).startCol); d2 abs(currentRow - segments(j).row) ... abs(currentCol - segments(j).endCol); d min(d1, d2); if d bestDist bestDist d; bestIdx j; end end end coverageOrder(i) bestIdx; visited(bestIdx) 1; % 根据进入端点决定更新当前点 dStart abs(currentRow - segments(bestIdx).row) ... abs(currentCol - segments(bestIdx).startCol); dEnd abs(currentRow - segments(bestIdx).row) ... abs(currentCol - segments(bestIdx).endCol); if dStart dEnd currentRow segments(bestIdx).row; currentCol segments(bestIdx).startCol; segments(bestIdx).entryMode start; else currentRow segments(bestIdx).row; currentCol segments(bestIdx).endCol; segments(bestIdx).entryMode end; end end这段代码我用过很多次跑起来很稳定。但它的前提是“已经覆盖过的段”可以被安全穿过。也就是说转场路径可能经过还没走过的区域也可能经过已经走过的区域。经过没走过的区域没关系机器人走过去的时候就顺手覆盖了经过已走过的区域就是重复率。如果你想进一步压重复率可以对段连接顺序跑一遍简单的动态规划或者模拟退火这在MATLAB里也就是加50行代码的事。先把贪心版本跑通性能基准再考虑优化就比较好判断投入产出比。3.4 生成实际路径轨迹并计算覆盖率段顺序确定后就要把所有段的内部路径和段间转场路径整合成一条完整的轨迹。每段内部的路径就是按当前进入端点沿行走到另一个端点。转场路径直接画一条水平然后垂直的连接线这对应AGV的实际运动路径——直走加直角转弯。覆盖率的计算方法是标记已经走过的格子。我维护一个coveredMap凡是路径经过的格子都置1最后统计比值。coveredMap zeros(rows, cols); pathList [startRow, startCol]; curR startRow; curC startCol; for i 1 : length(coverageOrder) seg segments(coverageOrder(i)); % 先走到段的进入点 if seg.entryMode start targetC seg.startCol; else targetC seg.endCol; end % 段间转场先横向再纵向 if targetC ~ curC step sign(targetC - curC); for c curC : step : targetC coveredMap(curR, c) 1; pathList [pathList; curR, c]; end curC targetC; end if curR ~ seg.row step sign(seg.row - curR); for r curR : step : seg.row coveredMap(r, curC) 1; pathList [pathList; r, curC]; end curR seg.row; end % 行内覆盖 startC seg.startCol; endC seg.endCol; if seg.entryMode start for c startC : endC coveredMap(curR, c) 1; pathList [pathList; curR, c]; end curC endC; else for c endC : -1 : startC coveredMap(curR, c) 1; pathList [pathList; curR, c]; end curC startC; end end跑完之后覆盖率就是sum(coveredMap(:)) / sum(occMap(:)0)。注意这里分母是原本的可通行格数不是行段提取出来的格数。这两者理论上应该相等如果不等说明地图里有些格在提取时被漏掉了。4. 完整MATLAB代码框架与仿真验证4.1 主函数骨架把所有零件拼成一个可运行的主函数。我习惯把整个流程分成四个阶段建图 - 提段 - 排序 - 生成路径并绘图。代码框架如下function mainCoverage() % 1. 建地图 [rows, cols, occMap] buildMap(); % 2. 膨胀处理 occMap imdilate(occMap, strel(square, 3)); % 3. 提取行段 segments extractRowSegments(occMap); % 4. 贪心排序 coverageOrder greedySegmentOrder(segments, 2, 2); % 5. 生成路径 [pathList, coveredMap] generatePath(segments, coverageOrder, occMap); % 6. 计算覆盖率 coverageRate sum(coveredMap(:)) / sum(occMap(:) 0); fprintf(覆盖率: %.2f%%\n, coverageRate * 100); % 7. 绘图 plotCoverageResult(occMap, pathList, coveredMap); endbuildMap、generatePath、plotCoverageResult这三个函数是配套的按我前面的代码逻辑对应补全就行。整个工程改成脚本几十行代码就能跑起来。4.2 覆盖率结果和可视化我拿上面那个20x15的测试地图跑了一遍效果如下自由格总数扣除边界和障碍物大约200个左右膨胀之后又扣掉一批最后覆盖率能到95%以上。剩下的那不到5%是为什么因为边界上有些窄缝格子和膨胀后的障碍物挤在一起贪心排序时没有走到那一小撮孤立格。这些区域在真实场景里是机器人的物理尺寸进不去的比如墙角缝、障碍物贴墙的情况下验收的时候这部分区域通常是可以接受的。可视化的代码建议用plot把路径画出来再叠加地图作为背景function plotCoverageResult(occMap, pathList, coveredMap) figure; imagesc(~occMap); hold on; colormap(gray); axis equal; % 已覆盖区域半透明标记 [rr, cc] find(coveredMap 1); plot(cc, rr, b., MarkerSize, 6); % 路径线 plot(pathList(:, 2), pathList(:, 1), r-, LineWidth, 1.5); plot(pathList(1, 2), pathList(1, 1), go, MarkerFaceColor, g); plot(pathList(end, 2), pathList(end, 1), ro, MarkerFaceColor, r); legend({覆盖区域, 规划路径, 起点, 终点}, Location, best); end我把覆盖区域画成小蓝点路径画成红线。调试的时候可以清晰地看到路径是不是有奇怪的大绕路、有没有漏掉一整行。注意图像坐标和矩阵坐标的区别imagesc的横轴是列、纵轴是行所以画图时路径点的第一列是纵坐标、第二列是横坐标用plot(cc, rr)和plot(pathList(:,2), pathList(:,1))才不会画歪。4.3 参数是怎么定的整套代码里最关键的参数有三个。第一个是行距也就是弓字形相邻两行的间隔。行距和机器人宽度强相关实际中是宽度乘以一个0.8~1.0的系数。系数小于1会导致相邻路径有重叠重复率上升系数大于1会导致漏扫覆盖率下降。我一般取0.9留一点余量保证覆盖连续。第二个是膨胀格数。前面已经说过等于机器人半径除以栅格边长。在MATLAB测试时有时候为了看路径效果我会把膨胀格数设小一点但正式仿真一定要按真实机器人尺寸来。第三个是段间排序的代价权重。贪心排序默认只考虑曼哈顿距离实际中如果需要少转弯可以把转场路径的距离乘一个大于1的系数让算法更倾向少转场。这个需要针对实际车的转弯半径调。提示全覆盖算法的覆盖率不是越高越好还得看重复率。我在项目里设置的验收标准是覆盖率95%重复率20%。覆盖率再往上压重复率往往会指数级上升这种优化在实际使用中没有价值。5. 避障策略的深入处理从静态地图到动态避障5.1 静态障碍物怎么避很多人看到“避障”两个字以为全覆盖路径规划里一定要用实时传感器避障。其实分两种情况有先验地图的环境下静态避障在规划阶段就完成了——膨胀后的地图里已经包含了障碍物信息规划出的路径天然绕开了障碍物。真正的避障难点在于行段提取和段间连接时能不能严格约束路径不让它穿过障碍物。我上面代码里用曼哈顿转场路径有一个隐患如果两个段不在相邻行转场路径是“先横向走、再纵向走”中间可能会穿过障碍物格。解决方法是在转场规划时调用一次A算法。段间转场本来距离就很短用A算一条无碰撞路径很划算。我把这个步骤叫做“局部路径重规划”实测下来对覆盖率几乎没影响但路径安全性有保障。一个简化替代方案是转场时只选择沿着没有障碍物的那一行走。比如当前段在第3行目标段在第8行那就先看第3行的终点能不能往下走到第4行再看第4行能不能继续往下走。这本质上是用地图的连通性先验来判断实现起来比A*简单但对复杂地图会绕远路。5.2 动态障碍物怎么办如果AGV执行过程中环境里有行人、叉车、突然出现的箱子静态规划就不够用了。我的实际做法是分层全局规划用全覆盖算法、局部避障用DWA动态窗口法或者VFH。当局部传感器发现前方障碍物时局部规划器生成短距离绕行路径绕过障碍物后重新回到全局全覆盖路径上。这个思路的核心是“绕行后怎么回到全局路径”。我的经验是不要试图局部规划器去更新全局路径全局路径保持原来的全覆盖规划结果只在执行层面做一个“临时偏移”就好。绕行结束后用最近点匹配把机器人拉回到全局路径上这样既能避开动态障碍物又不会把全覆盖路径打乱导致后续漏扫。5.3 凹形区域和死区处理全覆盖算法历史上最头疼的是凹形区域。比如一个U字形状的场地如果直接全局弓字形扫进入U形凹槽后会被墙挡住无法退出。解决办法是在预处理阶段把非凸区域拆分成若干个子凸区域每个子区域内部跑弓字形覆盖然后子区域之间再做连接。MATLAB里做区域分解可以用图像处理里的连通域方法也可以手动设定分块线。实话说自动化分解非常复杂很多商用产品是人工标定的。我在代码里加了个人工分割接口segments结构体里增加一个subregion字段不同子区域的段分开排序再按子区域顺序遍历。这个方法在中小型地图上足够用。死区指的是机器人物理上无法到达的栅格比如窄于机器人宽度的夹缝。这些区域在膨胀地图上本身就已经变黑算法天然不会规划进去所以死区没有额外增加处理难度说到底还是膨胀参数的合理性。6. 调试经验与常见问题速查6.1 覆盖率不达标先查地图和行段覆盖率差首先检查膨胀后的地图是不是把路都封死了。通过imagesc(~inflatedOccMap)看膨胀地图如果有些地方看起来明显应该能走但已经变黑了那就是膨胀半径设大了。其次检查行段提取。用我在前面写的打印方法把所有段画出来一个格子一个格子核对。最容易出现的问题是用find(occMap(r,:)0)时把边界条件写错导致第一行或最后一行整行漏掉。另一个容易出问题的是列号索引从0开始还是从1开始MATLAB必须从1开始很多从Python转过来的容易在这里翻车。6.2 路径重复率飙升看段间排序段间排序如果是纯贪心在障碍物多的时候很容易出现大绕路刚走完第10行跳到第2行再跳到第8行整个路径一坨乱麻重复率三十以上。这时候先不要急着换算法。看一眼是不是障碍物把地图切得太碎一个行内出现了太多段。如果是可以尝试先合并相邻行内的短段把小于一定长度的段丢弃因为短段可以通过相邻行的覆盖顺带覆盖掉。我在项目里设定过阈值小于3个格子的段直接忽略后面覆盖率不掉反增重复率大幅下降。如果地图本身没问题那就把贪心排序换成最近邻加两段交换优化或者直接上遗传算法。这个优化收益非常明显重复率基本能降到10%以内。6.3 代码跑起来死循环大概率是图更新逻辑问题全覆盖代码的常见死循环出在“标记已覆盖”和“遍历段列表”不一致。比如实际覆盖到的格子和coveredMap更新范围不一样导致闲置格永远在列表里算法反复规划去覆盖同一段路径。排查方法很简单在generatePath里增加一个fprintf每走完一个段打印当前累计覆盖率和已分配段数。如果覆盖率增长曲线突然变平但段数还在涨说明有大量重复转场就需要回到段间排序逻辑上看有没有重复段被加入列表。6.4 实测到仿真结果差异大这是最让人头大的问题。仿真里覆盖率99.5%实测只有82%。一般不是算法的锅是栅格分辨率太低或者定位不精。栅格分辨率低意味着地图上的一个格子对应现实里的半米AGV的位置控制有10cm以上的误差就会直接漏掉一整条路径带。解决方法是根据AGV的定位精度重新选栅格大小。如果定位精度是±20mm那栅格边长至少要小于运动定位精度的两倍否则不确定性累积会吞掉覆盖效果。另外在实车执行时行距参数还要根据实际清扫机构宽度再折减一次我一般乘0.85。6.5 转弯次数多导致执行效率低弓字形全覆盖天然产生大量转弯每次转弯都要减速、掉头、再加速占用的时间远超直线段。优化思路有两个方向一是减少段数例如把同侧的小段合并让车扫完一整侧再走下一侧二是减少段间转场把段排序的目标函数从“距离最短”改成“转弯次数最少”。我在项目里试过用“按行号排序”的简单策略代替贪心搜索先按行号从小到大行内按列号奇偶交替走。它的转弯次数非常少覆盖率也不差适合那种障碍物比较分散、行段比较规整的场景。7. 最后再分享一个让我少熬了两个通宵的小技巧全覆盖路径规划看起来是个“算法题”实际跑起来更像“地图处理题”。我之前花了很多时间去优化段排序结果覆盖率提升不明显。后来把时间花在地图膨胀、清理孤立栅格、修正栅格边缘锯齿上效果立竿见影。在MATLAB里我强烈建议你做一件事调试的时候不要把地图画成imagesc加颜色就完事要把每个段标上序号把路径上的每一格打上小点然后做一个逐段动画。我写了个简单的for循环每处理一个段就暂停0.2秒刷新图像肉眼看那辆车从哪里到哪里问题一眼就能看出来。没有这个动画光看最终路径图段间那段“看不见的转场”最容易藏bug。全覆盖算法的坑大多不在算法本身而在你对地图的理解和对边界的处理。只要把地图处理干净第一类算法的表现会远超你的预期稳定的表现很多时候比花里胡哨的“智能”更有价值。 
长河君 · 2026/10/24 5:56:41 · 阅读 1.2k AGV全覆盖路径规划：第一类确定性算法原理与MATLAB实现
接手过一个AGV清扫的项目甲方要求很简单整个园区车必须走完每一寸地面一个死角都不能留。最后验收的时候他们拿激光测距仪扫场地边缘发现确实有漏扫在那之后我很长一段时间都在和“全覆盖路径规划”这几个字较劲。现在提到AGV、扫地机器人大部分教程都在讲怎么从A点到B点什么A*、Dijkstra、RRT这些是点到点路径规划。但扫地车、植保机、擦窗机器人、洗地机这一类设备要的不是“从A到B”而是“把整个可走区域都走一遍”。这就是全覆盖路径规划英文叫Coverage Path Planning缩写CPP。你这个标题里写的“第一类算法”对应的就是CPP算法谱系里最经典、最稳定的那一支确定性全覆盖算法。如果你正在做毕业设计、AGV/扫地机产品预研或者想看懂别人写的那些“全覆盖代码”这篇内容应该能帮你把思路理顺顺带提供一份可以直接拿去跑的MATLAB实现。1. 先把“第一类算法”这几个字掰开揉碎1.1 全覆盖路径规划和普通路径规划的区别普通路径规划解决的是单次任务车从起点出发找一条代价最小的路径到终点路上避开障碍物。它不关心路径覆盖了多少区域只关心走的路径本身够不够短、够不够安全。全覆盖路径规划解决的是另一种问题车要把工作区域内的自由空间全部遍历一遍同时尽可能避免重复。路径经过的覆盖面是一个“面”而不是一条“线”。你可以买个问题就是“笔刷问题”——给你一张画布工作区域有一堆不能涂的区域障碍物要求用一支画笔把能涂的地方全部涂满重复涂的次数越少越好最终涂完的路径越短越好。这个区别是根本性的因为评价指标完全不同。点到点路径规划看“耗散度”和“避障成功率”全覆盖路径规划看“覆盖率”和“重复率”。覆盖率是指实际走过的有效区域占可通行区域的比例重复率是指重复走过的路程占总路程的比例。这两个指标才是全覆盖算法好坏的核心其他都是次要的。1.2 全覆盖算法的完整谱系第一类到底排在哪我在翻论文和GitHub代码的时候发现全覆盖路径规划算法的分类挺乱的不同文献叫法都不一样。但综合来看大致可以分成三个阵营第一类确定性全覆盖算法。这类算法的核心特点是路径生成规则是确定性的不依赖随机数同样的地图输入每次跑出来的结果几乎一样。典型代表包括弓字形往返覆盖Boustrophedon、螺旋式覆盖、基于梯形分解的覆盖、基于牛耕分解的覆盖等。这类算法逻辑简单、可解释性强、调试方便在扫地机器人、AGV上用得最多。你标题里说的“第一类算法”最合理的理解就是这种经典、确定性的全覆盖算法。第二类随机覆盖算法。典型代表是随机漫步Random Walk和基于采样方法的覆盖。这类算法在未知环境探索中比较常见机器人在没有先验地图的情况下瞎走靠传感器实时反馈判断哪里还没走。好处是能处理未知环境坏处是效率很低覆盖一个房间要来回绕很多圈没有确定性保障。第三类智能优化与学习类算法。包括遗传算法、粒子群优化、蚁群算法以及近年来火起来的强化学习全覆盖算法。这类算法的思路是把全覆盖路径看作一个优化问题用各种算法去“搜”出一个近似最优解。效果上限很高但计算量大、稳定性差调试起来非常痛苦。第一类算法之所以被称为“第一类”一方面因为它是历史上最早出现的全覆盖算法另一方面也因为它是其他所有算法的基础。很多智能算法的初始解、评价函数、行为策略都是从第一类算法里拆出来的。1.3 第一类算法适合什么场景我做AGV项目的时候一开始也想过直接上强化学习后来被导师泼了冷水。全覆盖算法选型要看你手里的牌有没有先验地图、车载算力多强、任务环境是不是基本静态。如果手里有先验地图哪怕是用SLAM攒出来的环境里没有太多动态障碍物而且车上的MCU或工控机算力一般那优先选第一类算法。它跑得快、容易验证、出问题了能定位到具体那一行代码。如果在完全未知的环境里探索比如无人机搜救、未知洞穴探索第一类就用不上了得用第二类做在线探索再用第一类局部覆盖。如果场地特别大、形状特别复杂比如几百个库位、一堆异形货架的仓库第一类算法算出来的路径可能不够优这时候可以上第三类但前提是你有充足的计算资源和调参时间。2. 环境建模全覆盖算法落地前必须解决的问题2.1 为什么最后都选了栅格地图全覆盖路径规划的第一步是让算法“理解”工作区域。目前主流的方案是栅格地图也叫占据栅格地图Occupancy Grid Map。把一块连续场地切成等大小的方格每个格子标记为三类状态空闲、占用、未知。扫地机器人的激光雷达和SLAM建图的输出本质上就是这种栅格表示。栅格大小是全流程里最关键的一个参数。栅格太小地图数据量巨大算法计算时间暴涨栅格太大路径边缘粗糙容易漏扫障碍物附近的区域。经验值是什么格子和机器人直径大致相当就行。比如一台直径250mm的扫地机器人用200mm~250mm的栅格就很合理。AGV的底盘大栅格也能放大。我常用的做法是先用MATLAB读入SLAM导出的二维占据栅格图把灰度图二值化然后按照机器人尺寸做一次膨胀处理。这个“膨胀”其实对应的是避障安全距离障碍物周围标成不可走的格子这样算法规划出来的路径就不会贴着墙或障碍物走。2.2 地图数据结构和MATLAB表示MATLAB里处理栅格地图最方便的就是二维矩阵。我习惯用occMap这个变量名存储1表示障碍物0表示可通行。这个定义方式做腐蚀膨胀、图像处理都方便。% 地图定义20x15格栅格地图四周是墙中间有两个矩形障碍物 rows 15; cols 20; occMap zeros(rows, cols); % 地图边界四周设为障碍物 occMap(1, :) 1; occMap(rows, :) 1; occMap(:, 1) 1; occMap(:, cols) 1; % 障碍物A矩形区域 occMap(5:7, 5:8) 1; % 障碍物B矩形区域 occMap(4:6, 13:15) 1; occMap(9:11, 9:12) 1;绘制地图用imagesc加一个colormap就能看到黑白格figure; imagesc(~occMap); axis equal; colormap(gray); hold on; grid on; set(gca, GridLineStyle, :, GridColor, [0.5 0.5 0.5], GridAlpha, 1);提示~occMap是为了让1显示成黑色0显示成白色视觉上更符合“黑色障碍物”的习惯。网格线保留下来方便调试这一步非常省事。2.3 膨胀安全距离的计算如果你的地图是传感器数据直接生成的那必须先做膨胀。最常用的方法是图像腐蚀/膨胀操作MATLAB里直接用imdilate就行。膨胀半径怎么定记住这个公式膨胀格数 机器人半径 / 栅格边长。如果机器人半径是300mm栅格边长是150mm那膨胀格数就是2。这意味着障碍物边界往里推2格路径规划器会把这2格当成障碍物处理车就不会撞上了。se strel(square, 2 * inflateGrid 1); inflatedOccMap imdilate(occMap, se);这个膨胀不只是安全考虑还有一个副作用是直接影响了覆盖率的上限。膨胀越大可走区域越小覆盖率上限就越低。所以安全距离也不能盲目放大够用就行。3. 核心算法拆解全知地图上的往返式全覆盖3.1 往返覆盖的直觉逻辑理解了地图就进入算法本身。第一类确定性全覆盖算法的三个经典代表往返式Bow-tie/Boustrophedon、螺旋式Spiral、分块往返式Morse-based Decomposition。最核心的是往返式。往返式覆盖的逻辑特别简单就是扫地时来回走S型。车从场地一边开始走直线走到另一边然后横向平移一个车身宽度掉头再走回来。就这样一行一行刷过去像农民耕地一样所以也叫牛耕式覆盖。别小看这个思路。它有三个强大之处一是无死角。只要场地是凸多边形或者被正确分解成凸子区域最朴素的往返扫描就能覆盖整个区域。二是重复率低。相邻两行路径之间的距离就是车身宽度理论上几乎没有扫描重叠重复率趋近于0。三是行行进简单。执行时车辆控制难度低就是直线行驶加掉头对里程计和运动控制系统的要求都很低。3.2 遇到障碍物怎么办行分解真实场地很少是纯凸多边形中间总会有柱子、桌子、货架。往返式全覆盖直接硬扫的话会被障碍物割裂成好几段路径。解决这个问题的方法叫“行分解”。每一行横向扫描时障碍物会把这一行分成长度不一的多个可通行区间。整个算法变成两步先把所有行分解成一个个可通行的行段再把这些行段串起来覆盖时按顺序走完。我在MATLAB里做了个简化版实现思路是把每一行的自由格子提取出来做连通块检测。这一行的可通行区域是一个一个的连通区间每个区间就是一个行段。function segments extractRowSegments(occMap) % 输入occMap0可通行1障碍物 % 输出segments结构体数组字段rowstartColendCol segments []; [rows, cols] size(occMap); for r 2 : rows-1 c 2; while c cols-1 if occMap(r, c) 0 startC c; while c cols-1 occMap(r, c) 0 c c 1; end endC c - 1; segments(end1).row r; segments(end).startCol startC; segments(end).endCol endC; else c c 1; end end end这里多加了个限制从第2行到第rows-1行是因为地图边缘已经标记成障碍物了不需要再处理边界。每个段都记录行号、起始列和结束列之后所有规划都建在这组段数据之上。提取出来的段要是不完整后面覆盖率肯定出问题所以这一步建议先做个调试打印看看个数对不对、有没有漏掉空白行。3.3 段之间的遍历顺序把全覆盖问题变成“路径连接问题”行段提取完之后全覆盖问题就转化成了段遍历顺序问题。比如一个20x15的地图障碍物把所有行切成了20来个段。你要设计一条路径把这20来个段都走一遍同时让段和段之间的“转场路径”尽量短。这个思想特别像旅行商问题TSP这也是为什么后面很多算法都用TSP的思路来解全覆盖问题。经典的贪心策略很简单每走完当前段就从所有没走过的段里挑一个“距离最近”的段。这个距离通常用当前段尾端点去找候选段的两个端点挑曼哈顿距离最短的那一个。曼哈顿距离是指按栅格水平或垂直移动的步数因为我们假设AGV是四向移动的。function coverageOrder greedySegmentOrder(segments, startRow, startCol) % 贪心搜索遍历顺序 n length(segments); visited zeros(1, n); coverageOrder zeros(1, n); currentRow startRow; currentCol startCol; for i 1 : n bestIdx -1; bestDist inf; for j 1 : n if visited(j) 0 d1 abs(currentRow - segments(j).row) ... abs(currentCol - segments(j).startCol); d2 abs(currentRow - segments(j).row) ... abs(currentCol - segments(j).endCol); d min(d1, d2); if d bestDist bestDist d; bestIdx j; end end end coverageOrder(i) bestIdx; visited(bestIdx) 1; % 根据进入端点决定更新当前点 dStart abs(currentRow - segments(bestIdx).row) ... abs(currentCol - segments(bestIdx).startCol); dEnd abs(currentRow - segments(bestIdx).row) ... abs(currentCol - segments(bestIdx).endCol); if dStart dEnd currentRow segments(bestIdx).row; currentCol segments(bestIdx).startCol; segments(bestIdx).entryMode start; else currentRow segments(bestIdx).row; currentCol segments(bestIdx).endCol; segments(bestIdx).entryMode end; end end这段代码我用过很多次跑起来很稳定。但它的前提是“已经覆盖过的段”可以被安全穿过。也就是说转场路径可能经过还没走过的区域也可能经过已经走过的区域。经过没走过的区域没关系机器人走过去的时候就顺手覆盖了经过已走过的区域就是重复率。如果你想进一步压重复率可以对段连接顺序跑一遍简单的动态规划或者模拟退火这在MATLAB里也就是加50行代码的事。先把贪心版本跑通性能基准再考虑优化就比较好判断投入产出比。3.4 生成实际路径轨迹并计算覆盖率段顺序确定后就要把所有段的内部路径和段间转场路径整合成一条完整的轨迹。每段内部的路径就是按当前进入端点沿行走到另一个端点。转场路径直接画一条水平然后垂直的连接线这对应AGV的实际运动路径——直走加直角转弯。覆盖率的计算方法是标记已经走过的格子。我维护一个coveredMap凡是路径经过的格子都置1最后统计比值。coveredMap zeros(rows, cols); pathList [startRow, startCol]; curR startRow; curC startCol; for i 1 : length(coverageOrder) seg segments(coverageOrder(i)); % 先走到段的进入点 if seg.entryMode start targetC seg.startCol; else targetC seg.endCol; end % 段间转场先横向再纵向 if targetC ~ curC step sign(targetC - curC); for c curC : step : targetC coveredMap(curR, c) 1; pathList [pathList; curR, c]; end curC targetC; end if curR ~ seg.row step sign(seg.row - curR); for r curR : step : seg.row coveredMap(r, curC) 1; pathList [pathList; r, curC]; end curR seg.row; end % 行内覆盖 startC seg.startCol; endC seg.endCol; if seg.entryMode start for c startC : endC coveredMap(curR, c) 1; pathList [pathList; curR, c]; end curC endC; else for c endC : -1 : startC coveredMap(curR, c) 1; pathList [pathList; curR, c]; end curC startC; end end跑完之后覆盖率就是sum(coveredMap(:)) / sum(occMap(:)0)。注意这里分母是原本的可通行格数不是行段提取出来的格数。这两者理论上应该相等如果不等说明地图里有些格在提取时被漏掉了。4. 完整MATLAB代码框架与仿真验证4.1 主函数骨架把所有零件拼成一个可运行的主函数。我习惯把整个流程分成四个阶段建图 - 提段 - 排序 - 生成路径并绘图。代码框架如下function mainCoverage() % 1. 建地图 [rows, cols, occMap] buildMap(); % 2. 膨胀处理 occMap imdilate(occMap, strel(square, 3)); % 3. 提取行段 segments extractRowSegments(occMap); % 4. 贪心排序 coverageOrder greedySegmentOrder(segments, 2, 2); % 5. 生成路径 [pathList, coveredMap] generatePath(segments, coverageOrder, occMap); % 6. 计算覆盖率 coverageRate sum(coveredMap(:)) / sum(occMap(:) 0); fprintf(覆盖率: %.2f%%\n, coverageRate * 100); % 7. 绘图 plotCoverageResult(occMap, pathList, coveredMap); endbuildMap、generatePath、plotCoverageResult这三个函数是配套的按我前面的代码逻辑对应补全就行。整个工程改成脚本几十行代码就能跑起来。4.2 覆盖率结果和可视化我拿上面那个20x15的测试地图跑了一遍效果如下自由格总数扣除边界和障碍物大约200个左右膨胀之后又扣掉一批最后覆盖率能到95%以上。剩下的那不到5%是为什么因为边界上有些窄缝格子和膨胀后的障碍物挤在一起贪心排序时没有走到那一小撮孤立格。这些区域在真实场景里是机器人的物理尺寸进不去的比如墙角缝、障碍物贴墙的情况下验收的时候这部分区域通常是可以接受的。可视化的代码建议用plot把路径画出来再叠加地图作为背景function plotCoverageResult(occMap, pathList, coveredMap) figure; imagesc(~occMap); hold on; colormap(gray); axis equal; % 已覆盖区域半透明标记 [rr, cc] find(coveredMap 1); plot(cc, rr, b., MarkerSize, 6); % 路径线 plot(pathList(:, 2), pathList(:, 1), r-, LineWidth, 1.5); plot(pathList(1, 2), pathList(1, 1), go, MarkerFaceColor, g); plot(pathList(end, 2), pathList(end, 1), ro, MarkerFaceColor, r); legend({覆盖区域, 规划路径, 起点, 终点}, Location, best); end我把覆盖区域画成小蓝点路径画成红线。调试的时候可以清晰地看到路径是不是有奇怪的大绕路、有没有漏掉一整行。注意图像坐标和矩阵坐标的区别imagesc的横轴是列、纵轴是行所以画图时路径点的第一列是纵坐标、第二列是横坐标用plot(cc, rr)和plot(pathList(:,2), pathList(:,1))才不会画歪。4.3 参数是怎么定的整套代码里最关键的参数有三个。第一个是行距也就是弓字形相邻两行的间隔。行距和机器人宽度强相关实际中是宽度乘以一个0.8~1.0的系数。系数小于1会导致相邻路径有重叠重复率上升系数大于1会导致漏扫覆盖率下降。我一般取0.9留一点余量保证覆盖连续。第二个是膨胀格数。前面已经说过等于机器人半径除以栅格边长。在MATLAB测试时有时候为了看路径效果我会把膨胀格数设小一点但正式仿真一定要按真实机器人尺寸来。第三个是段间排序的代价权重。贪心排序默认只考虑曼哈顿距离实际中如果需要少转弯可以把转场路径的距离乘一个大于1的系数让算法更倾向少转场。这个需要针对实际车的转弯半径调。提示全覆盖算法的覆盖率不是越高越好还得看重复率。我在项目里设置的验收标准是覆盖率95%重复率20%。覆盖率再往上压重复率往往会指数级上升这种优化在实际使用中没有价值。5. 避障策略的深入处理从静态地图到动态避障5.1 静态障碍物怎么避很多人看到“避障”两个字以为全覆盖路径规划里一定要用实时传感器避障。其实分两种情况有先验地图的环境下静态避障在规划阶段就完成了——膨胀后的地图里已经包含了障碍物信息规划出的路径天然绕开了障碍物。真正的避障难点在于行段提取和段间连接时能不能严格约束路径不让它穿过障碍物。我上面代码里用曼哈顿转场路径有一个隐患如果两个段不在相邻行转场路径是“先横向走、再纵向走”中间可能会穿过障碍物格。解决方法是在转场规划时调用一次A算法。段间转场本来距离就很短用A算一条无碰撞路径很划算。我把这个步骤叫做“局部路径重规划”实测下来对覆盖率几乎没影响但路径安全性有保障。一个简化替代方案是转场时只选择沿着没有障碍物的那一行走。比如当前段在第3行目标段在第8行那就先看第3行的终点能不能往下走到第4行再看第4行能不能继续往下走。这本质上是用地图的连通性先验来判断实现起来比A*简单但对复杂地图会绕远路。5.2 动态障碍物怎么办如果AGV执行过程中环境里有行人、叉车、突然出现的箱子静态规划就不够用了。我的实际做法是分层全局规划用全覆盖算法、局部避障用DWA动态窗口法或者VFH。当局部传感器发现前方障碍物时局部规划器生成短距离绕行路径绕过障碍物后重新回到全局全覆盖路径上。这个思路的核心是“绕行后怎么回到全局路径”。我的经验是不要试图局部规划器去更新全局路径全局路径保持原来的全覆盖规划结果只在执行层面做一个“临时偏移”就好。绕行结束后用最近点匹配把机器人拉回到全局路径上这样既能避开动态障碍物又不会把全覆盖路径打乱导致后续漏扫。5.3 凹形区域和死区处理全覆盖算法历史上最头疼的是凹形区域。比如一个U字形状的场地如果直接全局弓字形扫进入U形凹槽后会被墙挡住无法退出。解决办法是在预处理阶段把非凸区域拆分成若干个子凸区域每个子区域内部跑弓字形覆盖然后子区域之间再做连接。MATLAB里做区域分解可以用图像处理里的连通域方法也可以手动设定分块线。实话说自动化分解非常复杂很多商用产品是人工标定的。我在代码里加了个人工分割接口segments结构体里增加一个subregion字段不同子区域的段分开排序再按子区域顺序遍历。这个方法在中小型地图上足够用。死区指的是机器人物理上无法到达的栅格比如窄于机器人宽度的夹缝。这些区域在膨胀地图上本身就已经变黑算法天然不会规划进去所以死区没有额外增加处理难度说到底还是膨胀参数的合理性。6. 调试经验与常见问题速查6.1 覆盖率不达标先查地图和行段覆盖率差首先检查膨胀后的地图是不是把路都封死了。通过imagesc(~inflatedOccMap)看膨胀地图如果有些地方看起来明显应该能走但已经变黑了那就是膨胀半径设大了。其次检查行段提取。用我在前面写的打印方法把所有段画出来一个格子一个格子核对。最容易出现的问题是用find(occMap(r,:)0)时把边界条件写错导致第一行或最后一行整行漏掉。另一个容易出问题的是列号索引从0开始还是从1开始MATLAB必须从1开始很多从Python转过来的容易在这里翻车。6.2 路径重复率飙升看段间排序段间排序如果是纯贪心在障碍物多的时候很容易出现大绕路刚走完第10行跳到第2行再跳到第8行整个路径一坨乱麻重复率三十以上。这时候先不要急着换算法。看一眼是不是障碍物把地图切得太碎一个行内出现了太多段。如果是可以尝试先合并相邻行内的短段把小于一定长度的段丢弃因为短段可以通过相邻行的覆盖顺带覆盖掉。我在项目里设定过阈值小于3个格子的段直接忽略后面覆盖率不掉反增重复率大幅下降。如果地图本身没问题那就把贪心排序换成最近邻加两段交换优化或者直接上遗传算法。这个优化收益非常明显重复率基本能降到10%以内。6.3 代码跑起来死循环大概率是图更新逻辑问题全覆盖代码的常见死循环出在“标记已覆盖”和“遍历段列表”不一致。比如实际覆盖到的格子和coveredMap更新范围不一样导致闲置格永远在列表里算法反复规划去覆盖同一段路径。排查方法很简单在generatePath里增加一个fprintf每走完一个段打印当前累计覆盖率和已分配段数。如果覆盖率增长曲线突然变平但段数还在涨说明有大量重复转场就需要回到段间排序逻辑上看有没有重复段被加入列表。6.4 实测到仿真结果差异大这是最让人头大的问题。仿真里覆盖率99.5%实测只有82%。一般不是算法的锅是栅格分辨率太低或者定位不精。栅格分辨率低意味着地图上的一个格子对应现实里的半米AGV的位置控制有10cm以上的误差就会直接漏掉一整条路径带。解决方法是根据AGV的定位精度重新选栅格大小。如果定位精度是±20mm那栅格边长至少要小于运动定位精度的两倍否则不确定性累积会吞掉覆盖效果。另外在实车执行时行距参数还要根据实际清扫机构宽度再折减一次我一般乘0.85。6.5 转弯次数多导致执行效率低弓字形全覆盖天然产生大量转弯每次转弯都要减速、掉头、再加速占用的时间远超直线段。优化思路有两个方向一是减少段数例如把同侧的小段合并让车扫完一整侧再走下一侧二是减少段间转场把段排序的目标函数从“距离最短”改成“转弯次数最少”。我在项目里试过用“按行号排序”的简单策略代替贪心搜索先按行号从小到大行内按列号奇偶交替走。它的转弯次数非常少覆盖率也不差适合那种障碍物比较分散、行段比较规整的场景。7. 最后再分享一个让我少熬了两个通宵的小技巧全覆盖路径规划看起来是个“算法题”实际跑起来更像“地图处理题”。我之前花了很多时间去优化段排序结果覆盖率提升不明显。后来把时间花在地图膨胀、清理孤立栅格、修正栅格边缘锯齿上效果立竿见影。在MATLAB里我强烈建议你做一件事调试的时候不要把地图画成imagesc加颜色就完事要把每个段标上序号把路径上的每一格打上小点然后做一个逐段动画。我写了个简单的for循环每处理一个段就暂停0.2秒刷新图像肉眼看那辆车从哪里到哪里问题一眼就能看出来。没有这个动画光看最终路径图段间那段“看不见的转场”最容易藏bug。全覆盖算法的坑大多不在算法本身而在你对地图的理解和对边界的处理。只要把地图处理干净第一类算法的表现会远超你的预期稳定的表现很多时候比花里胡哨的“智能”更有价值。