简介这套MATLAB源码实现了经典的牛耕式Boustrophedon栅格分区方法面向需要进行全覆盖路径规划、栅格地图划分或逐像素图像处理的算法学习者与开发者帮助解决二维空间中有序遍历与分区效率问题。资源包共9个文件包含6个.m脚本和3张.png示意图压缩后仅11KB结构轻量便于阅读与二次修改脚本覆盖主流程、代价计算、启发函数等核心模块图示则用于观察边界与角落处理效果。已有1751人学习下载说明该实现具备一定参考价值。通过两套可运行主程序和多个子函数可快速复现牛耕式路径生成与栅格遍历过程并在此基础上调整区域大小、起点位置和遍历规则适合作为课程设计或全覆盖算法研究的起步模板。 我第一次被 boustrophedon 这个词绕晕是在一个扫地机器人项目的方案评审上。同事说“栅格地图上直接做牛耕分区就行”我下意识以为要写什么高级的图搜索算法后来才明白他指的是让机器人像老黄牛耕地一样一行到头、掉头、挨着犁下一行。这个词源自古希腊语“牛转弯”放到路径规划里就是全覆盖路径规划中最基础也最经得起实战检验的一种策略。这项技术解决的问题很明确如何让一台机器人把已知区域不漏地走完同时尽量少走重复路线。扫地机器人、植保无人机、洗地车、光伏板清洁机器人底层几乎都离不开它。如果你手里的输入不是精确的几何多边形而是一张激光SLAM或者视觉重建出来的栅格地图那你大概率需要自己实现一次牛耕式分区。这篇文章我会把“栅格图上的牛耕式分区”从原理讲到实现细节再讲讲我实际调参时踩过的坑。1. 为什么叫“牛耕式”从黄牛犁地到栅格覆盖1.1 “直线走完再掉头”是覆盖效率的底线先直接说结论在很多覆盖任务里反复走平行直线看似很“笨”却是统计上最经济的基础运动方式。原因很简单——路径规划里机器人的代价通常分为两部分沿直线行走的代价和转弯代价。直线段上传感器稳定、位姿估计误差积累慢、能耗也相对可控而转弯阶段需要减速、转向、再加速时间成本往往是直线段的数倍。扫地机器人弓字形清扫本质就是每趟少转弯、多走直线把转弯次数压到理论下限。牛耕式轨迹还有一个统计层面的优势如果扫描线间距固定且机器人有效作业宽度稳定覆盖一条“垄”后只平移一个作业宽度那么相邻路径之间几乎不会出现间隙也不会叠加太多重复。这一点在没有精确传感器的情况下尤其重要因为你不需要闭环修正就能得到一条分布均匀的路径。1.2 为什么一定要“分区”如果只是在一个没有障碍物的矩形房间做牛耕扫描那确实不需要分区。但真实环境里总有桌子、墙垛、柜子横在扫描线中间。如果不做处理直接让机器人沿着扫描线走它会在障碍物面前停下要么掉头、要么绕行。掉头会漏掉障碍物后面的区域绕行则会打乱“一行接一行”的节奏导致后续扫描线错位甚至出现大面积漏覆盖。所以全覆盖规划的第一步往往不是画轨迹而是“把让扫描线无法一次穿过的区域切开切成若干个可以直接扫描的单元”。每个单元内部近似竖直或者近似凸机器人在单元内部做牛耕扫描时不需要为躲避障碍物额外改变运动方向。跨单元的移动则单独处理用“连接”的方式把单元串起来。几何方法里的梯形分解、牛耕分解就是干这个的栅格版实现的核心逻辑也一样只是把几何上的“关键点”换成了栅格上的“关键列”。1.3 栅格图为什么比几何图更好落纯粹从精度角度几何分解更漂亮提取多边形顶点、计算交线、合并单元结果是一条贴着实际边界的路径。但做工程的人都明白从激光SLAM地图里提取稳定可靠的几何多边形本身就是另一场战斗。地图噪声、墙体的轻微倾斜、动态物体的残留都会让顶点提取不稳定。而栅格地图本身就是一个标了自由/占据的离散网格把分区算法写成“统计列上连续自由区间”的循环比维护几何图结构简单得多对噪声也更鲁棒。当然栅格法牺牲了一点精度但绝大多数机器人的运动步长和传感器误差远大于栅格尺寸这点损失完全在可接受范围内。我在实际项目中基本都采用“先拿到占据栅格地图再做形态学处理然后直接栅格化分区”的路线跑起来省心得多。2. 栅格分区的基本逻辑关键列在哪里划分2.1 扫描线“穿墙而过”时的区间变化分区判据可以用一句话概括让一条扫描线沿地图从左往右移动观察它与自由空间交出的线段数量。数量发生变化的位置往往对应障碍物的“凸起”或“凹下”那里就是需要切开的地方。举个生活化的例子把房间想象成很多竖直的细条。没有柜子时每条竖条里“可站立区域”是一整段竖条移到柜子旁边时可站立区域被柜子截成两段分段数从1变成了2。这个变化说明地图的连通结构在这里发生突变如果还按原来的整体做一行扫到底机器人一定会被柜子挡住。因此在“1变2”的位置切开把地图拆成左右两个独立区域每个区域内再做牛耕扫描就能避开障碍物。2.2 栅格实现统计每一列的自由区间网格化之后这个判据实现起来非常直白。按列遍历地图对每一列做一次“连续自由区间”统计然后比较相邻列的区间数和区间端点位置。区间数量变化或者某个区间整体发生明显平移都可以视为关键列的候选。def free_intervals_in_column(grid, col): intervals [] rows grid.shape[0] r 0 while r rows: if grid[r, col] 0: # 0表示自由栅格 start r while r rows and grid[r, col] 0: r 1 intervals.append((start, r - 1)) else: r 1 return intervals def find_split_columns(grid): splits [] prev free_intervals_in_column(grid, 0) for col in range(1, grid.shape[1]): cur free_intervals_in_column(grid, col) if changed(prev, cur): splits.append(col) prev cur return splits这里的 changed 函数不只要比较区间数量还要考虑“同一区间端点出现剧烈平移”的情况。比如障碍物比较斜时某列自由区间的端点会连续好几列缓慢移动这种不算突变但如果端点一列之间跳了几十个栅格说明可能有凹角出现需要检查是否需要细分。2.3 分区的边界到底取哪一列确定关键列之后分割线不能直接压在障碍物所在的列上。比较稳妥的做法是把分割线放在关键列和前一列之间的空隙上。例如第 k 列自由区间数量比第 k-1 列多了一个说明障碍物在 k 列附近“长出来”分割线就放在第 k-1 列与第 k 列之间如果区间数量减少了说明障碍物接近结束同样把分割线放在 k-1 与 k 之间。这样左右两个子区域都不会包含被占据栅格后续扫进去更安全。用递归的方式可以继续对左右子区域重复这个过程直到每个子区域内任意一列的自由区间数量都不再变化。这本质上就是牛耕分解在栅格上的递归实现。需要注意递归时扫描方向可以保持同一方向也可以每层换一个方向后者对应更广义的 boustrophedon decomposition能进一步减少小碎块的产生。2.4 三种常见特殊边界第一障碍物贴着地图边界。此时自由区间数量虽然变化但被切掉的部分可能非常窄没必要生成一个独立单元可以设置最小宽度阈值过窄的区域直接和相邻区域合并。第二斜墙会带来锯齿状的关键列序列隔几列就“跳变”一次如果每次都切会把地图切成大量碎条。我在实践里一般要求“关键列连续出现至少两列”才真正切开能滤掉大部分斜墙造成的抖动。第三环形障碍物中间有空洞栅格图上会出现“自由-占据-自由-占据-自由”的结构简单区间计数无法处理这种多连通区域需要结合连通域标记把障碍物的内外边界都识别出来否则分区会失效。3. 单元生成之后往复轨迹与连接顺序怎么定3.1 单元内部的牛耕轨迹生成分区完成后每个单元可以看成一个近似竖直条带。接下来就是单元内部的牛耕轨迹了。把单元的左边界、右边界、顶部、底部提取出来按设定的扫描间距生成水平扫描线。每条扫描线从单元一侧边界走到另一侧下一行方向相反。扫描间距一般取机器人底盘有效作业宽度也就是毛刷、割幅或者喷幅的实际宽度而不是机器人本体宽度。def zigzag_cell(cell_left, cell_right, cell_top, cell_bottom, step): path [] y cell_top direction 1 while y cell_bottom: if direction 1: path.append((cell_left, y)) path.append((cell_right, y)) else: path.append((cell_right, y)) path.append((cell_left, y)) y step direction * -1 return path这里有个细节扫描方向不要固定为水平或竖直而应该选择“沿着单元长边”的方向。比如单元是一个竖直长条那就水平扫描如果是一个水平长条就竖直扫描。原因是长边方向走一趟更长转弯次数更少整体效率更高。如果单元内部还有局部凸起可以先把这部分剔除到相邻单元尽可能保证单元的近似矩形这样生成的牛耕线才整齐。3.2 单元之间的连接顺序不能乱排每个单元都有一条进入路径和一条离开路径。机器人覆盖完一个单元后要移动到下一个单元这一段“空驶路径”不产生覆盖收益但它会直接拉低整体效率。最简单的做法是按分区顺序依次访问但这往往不是最短路线因为分区顺序取决于扫描线的移动方向和物理位置关系不一定一致。真正落地时我会把每个单元看成一个节点单元之间的转移代价用两个单元入口点的欧氏距离近似然后做一次最近邻贪心排序从当前单元出发找最近的未访问单元作为下一个目标。对于几十个单元的场景贪心已经足够好如果单元数量上百可以用最小生成树或者2-opt做一轮改进。实测下来单靠一个最近邻排序空驶距离通常能减少15%以上代码量却只有十几行。3.3 一个最小示例演算拿一张很直观的地图举例地图中间靠上有一个大障碍物把地图切成了三个单元左单元A、右上单元B、右下单元C。A在最左B在右上C在右下整体呈“L”形。如果分区算法先切出A再往上切出B最后往下切出C按A→B→C的顺序覆盖机器人从B到C需要斜穿地图下方一段较长的空驶但如果改成A→C→B虽然覆盖单元的顺序变了C和A在上方共享一条边界连接距离短得多空驶里程能省掉大约四成。这说明单元本身怎么划分重要访问顺序同样重要。4. 实现牛耕式分区时最容易被忽略的参数与坑4.1 栅格分辨率不是越细越好栅格分辨率是整个算法最关键的参数之一。太粗窄通道会被直接抹掉关键列的跳变信息丢失分区结果完全失真太细整张地图的栅格数量爆炸算法变慢而且单个噪点就会变成一个“伪通道”产生大量碎单元。我的经验值是“机器人有效宽度的一半到三分之一”作为栅格边长。比如一台直径40cm的扫地机器人栅格尺寸取10cm到20cm比较合适。这个尺度既保留通道细节又不会把噪声放大。4.2 关键列检测的“假分裂”怎么压实际SLAM地图里总有噪点尤其在墙角附近传感器数据容易抖动栅格图上会冒出一个孤立的占据点。如果完全按区间数突变来切这里就会生成一个宽度才一两格的“假单元”路径规划进去根本转不开身还会增加大量无谓的掉头。我在做关键列检测时加了两个约束一是设定最小连续异常列数只出现一列的变化直接忽略二是先对栅格地图做一次形态学开运算去掉孤立噪点再做分区。这两个约束加完假分裂基本消失。仔细想原因也不复杂真实障碍物的边界变化通常是连续出现的而噪点只影响单列用连续列约束天然能把二者分开。4.3 覆盖率为什么总是达不到100%这是统计口径的问题。很多人直接按路径点画线数一下“路径穿过的栅格”除以“自由栅格”就算出覆盖率结果算出来很高实际跑起来却发现墙角、边缘根本没扫干净。原因是机器人本体有宽度轨迹是一条有宽度的带子而不是一条无宽度的线。正确的统计方式是把轨迹离散成密集点序列每个点按机器人半径做膨胀标记所有被膨胀圆覆盖的栅格再与自由栅格做交集。离散点的间距至少要小于栅格尺寸的一半否则会有漏标。做完这一步你会发现覆盖率很少能到100%能到95%以上已经是很不错的覆盖率剩下的往往是防撞膨胀区导致的物理不可达区域。4.4 转角处理与就地旋转空间栅格规划阶段很容易忽略真实底盘的转向半径。栅格图上看两个单元边界相距两格机器人实际转向、掉头需要的空间可能远大于这个距离。我曾在调试时遇到一个问题分区算法正常生成了一条贴着单元边界的转折线但小车到边缘后无法原地掉头因为边缘刚好是一堵墙没有留下转向余量。后来我在每个分区边界处向内部收缩一个机器人半径把转折点从物理边界上“拉”回一点才算真正跑通。这个处理看似损失了边缘一丁点覆盖面积换来的却是现场稳定性和设备安全性。5. 牛耕式分区之外的延伸排序、动态环境与工程心得5.1 用全局信息优化单元访问顺序前面提到过基于最近邻贪心的单元排序这里再补充一个更实用的变体不要只按单元入口的欧氏距离做贪心而要按“当前机器人所在位置到该单元入口的距离 该单元内部估计覆盖时间”共同排序。内部覆盖时间可以粗略用单元面积除以作业宽度得出。这样排序能避免一种尴尬情况——选了一个入口很近但面积很大的单元先做导致后面几个小单元之间的连接全部绕路。用面积加权之后整体空驶和转弯次数都能兼顾。5.2 环境局部变化时尽量复用原分区动态场景中地图里会临时出现椅子、箱子、行人。如果每次环境一变就重新全局分区机器人会不断改变覆盖策略看着很“聪明”实际效率很低甚至可能来回抖动。更工程的做法是只有当障碍物变化区域影响了某个单元的关键列时才把这个单元标记为失效仅对失效单元重新做一次牛耕分区和排序其余单元维持原有分区结果。这样既保证了覆盖又不让全局路径剧烈跳变。我试过在测试场地摆放临时路障用这种局部重规划方案机器人绕开路障后仍然能回到原来的牛耕线上继续干活整体覆盖率没有明显下降处理耗时也远低于全局重规划。5.3 做项目的一点心得牛耕式分区这套算法的价值不在于它多么“高级”而在于它用极少的计算量解决了一个非常清晰的问题先让地图结构变得适合扫描再按一种低转弯次数的模式把区域覆盖完。真正让工程落地变难的往往不是算法本身而是地图质量和设备约束。地图有脏点、栅格分辨率选错、转向空间不足这些问题都会让同一个算法出现天差地别的表现。先把地图预处理做干净把分辨率校准到和机器人尺寸匹配再回头调分区和排序你会发现牛耕式分区其实出奇地可靠。本文还有配套的精品资源点击获取