覆盖路径规划三大算法：牛耕、螺旋与图覆盖的实现与选型

简介：CPP.zip 是一份面向机器人学与自动化领域研究者的覆盖路径规划（Coverage Path Planning）完整实现包，针对如何让移动实体高效遍历整个工作区域、不重复不遗漏这一核心问题，适用于地面清洁、环境监测、搜索救援等典型任务场景。压缩包内共27个文件，以Matlab脚本为主干，包含核心算法函数、图像处理模块和交互界面，同时配有.mat格式的地图与仿真数据、.png与.fig格式的可视化图表、.txt格式的实验结果记录；整体大小仅218KB，结构紧凑，方便直接加载运行。资源实现了经典的Boustrophedon（牛耕式）覆盖策略，并附有多组不同尺寸的栅格地图样例，从环境建模、路径生成、碰撞规避到覆盖效果评估均给出了可执行参考。当前已有165人学习浏览。借助源码与数据，读者可以快速上手完整CPP流程，并根据实际需求修改参数或替换算法策略，是学习全覆盖路径规划问题的实用入门资料。

1. 覆盖路径规划到底解决什么问题：不是找路，而是把每条路都走完

如果你搜过 CPP、coverage planning、coverage problem、path planning 这几个词，十有八九是同一个需求：让机器人把一片区域完整走一遍，而不是从 A 点到 B 点。扫地机扫完整层地板，植保无人机飞完整个地块，巡检车查遍每个货架，这些都不是点对点导航能解决的。评价指标也从“快不快”变成了“覆盖了多少、重复走了多少、总共耗了多久”。只要有漏覆盖，任务就算失败。

这篇文章把这个覆盖问题拆开讲：三种常见算法族系、一份能直接改的离线栅格覆盖代码、在线覆盖的兜底思路，以及用覆盖率、重复率、转向代价三个指标验证效果。做移动机器人、无人机、扫地机的朋友，可以把它当作第一版覆盖规划器的工程笔记来读。

2. 三大算法族系：牛耕、螺旋与基于图的覆盖路径规划

覆盖路径规划的目标函数并不是单纯的“路径最短”，而是在覆盖完全的前提下让总成本最小。常见定义是：总成本 = 路径长度 + 重复覆盖惩罚 + 转向次数惩罚。三种算法族系都是在不同约束下逼近这个目标。搞清它们各自擅长什么，能帮你避免一上来就写一个又复杂又跑不通的实现。

2.1 牛耕法：最经济也最容易上手的起点

牛耕法（Boustrophedon）的思路像插秧：把区域按行切分成条带，沿条带弓字形往返。它最大的优点是实现简单，只要给定边界，几乎不需要启发式设计。对矩形或简单凸区域，牛耕法的重复率很低；对复杂区域，需要先做区域分解，把凹多边形切成多个凸子区域，每个子区域各自牛耕，再用过渡路径连接。

实际落地时，很多人会忽略条带的行进方向。把行进方向选在区域内最长边方向，能减少条带数量；选在短边方向，转向更频繁，总耗时更高。我有一个习惯：在做全局覆盖前，先把区域旋转一遍，找让条带数量最少的方向。这一步在覆盖率上差别不大，但能明显降低总路径长度。

对室内结构化场景，牛耕法是首选。这类环境墙壁基本横平竖直，障碍物多为矩形，分解出来的子区域几乎是凸多边形，牛耕法的重复覆盖可以控制在 5% 以内。我一般会先做连通区分解，再对每个连通区分别调用牛耕，而不是把整张地图当成一个区域处理。连通区的判断用 Flood Fill 就能搞定，几十行代码的事。

2.2 螺旋路径：从外圈往里收的贴边策略

螺旋路径是从边界开始，沿着障碍物轮廓一圈一圈向内收缩。优点是贴边效果好，很适合墙面清洗、外墙喷涂这类需要贴着边界作业的场景。缺点是路径形状很依赖边界是否规整，一旦遇到凹口或固定障碍，就要做“绕障断开再续”的处理，写起来比牛耕法啰嗦。

生成外螺旋的常见做法是：先对外部边界做等距偏置，得到一条向内收缩的环；然后对内部障碍物边界做等距偏置，得到一条向外扩张的环；两条环相互剪裁，连接成一条连续路径。这个偏置距离通常取机器人覆盖宽度的 0.8 倍，这里不能用 1 倍。因为还要留出传感器误差、惯性滑移和转向推进的余量，直接用满覆盖宽度会让相邻两圈之间出现漏覆盖条带。

在工程选型上，我会把螺旋路径只留给“边界相对规整、长宽比不大、内部没有太多散落障碍”的环境。如果你面对的是多房间楼层，或者一堆柱子密集排列的仓库，螺旋路径会绕出大量短路跳变，路径点之间反复切换，效率反而不如牛耕。它真正出彩的地方是单一大空间和贴边属性强的任务。

2.3 基于图的覆盖：把覆盖问题转换成路径规划问题

如果把区域离散成栅格，覆盖问题就变成“如何让一条路径访问所有自由栅格”。这种表述天然适合图论：每个自由栅格是顶点，相邻栅格连一条边，然后找一条能覆盖全部顶点的路径。最理想的是哈密顿路径，但它在非平凡地图上是 NP-hard 的，几十个栅格还能枚举，几千个栅格就完全不可行了。

工程上退一步的做法是 MST-Coverage：对自由栅格图求最小生成树，然后从树根出发对树做深度优先遍历。由于树边在 DFS 中会被走两次，这条路径的重复覆盖会明显偏高，但换来的是对任意复杂障碍环境的通用性。牛耕法和螺旋路径遇到一团乱麻一样的障碍布局时往往要写一堆特判，图覆盖方法反而不需要，只要图是连通的，它就能给出一条完整路径。

这个方向还有一个衍生分支：多机器人覆盖。把栅格图切分成多个连通子图，让每台机器人负责一个子图，本质上是在求解不平衡任务划分。你在论文里看到带 “multi-agent coverage” 的标题，多半就是这一类。这类方法的路径通常不是最短，但它的稳定性是前两种算法比不了的。选型建议是：地图形态规整用牛耕，贴边任务用螺旋，障碍复杂或者要做多机协作时直接上基于图覆盖。

这里补一个对比表，方便你判断手上的场景适合哪一族系：

选型时还有一个很容易踩的误区：以为“覆盖率越高越好”。实际上，把覆盖率从 98% 推到 99% 往往要付出巨大的重复覆盖和转向代价，对扫地这类任务完全不值。工程上更常见的指标是“覆盖率达标 + 总耗时最小”，而不是无限追求最后一个栅格。

3. 从栅格地图到可执行路径：牛耕覆盖的完整实现与参数设置

牛耕法听起来简单，写出来的代码能不能直接用又是另一回事。这一章给出一份可以直接改着跑的 Python 实现，并把环境建模和四个核心参数说清楚。这里默认你已经有一张二维栅格地图，0 代表自由栅格，1 代表障碍物。

3.1 环境建模：栅格地图与四邻/八邻的取舍

先确定地图坐标系。我在代码里用(row, col)表示栅格坐标，因为按行扫描时，行号正好对应扫描次序。栅格尺寸取决于机器人覆盖宽度和定位精度，一般取覆盖半径的 1/3 到 1/2。取太小会让路径点数量爆炸，规划耗时变长；取太大会漏覆盖，尤其是贴障碍物边缘时，半个栅格的偏差都可能造成漏带。

邻接关系上，做全覆盖时我默认用四邻（上下左右）。八邻会让路径斜着穿过窄通道，例如两个障碍物之间刚好只有一个栅格宽时，八邻会认为斜对角也能走，但实际机器人根本转不过去。只有在农机、无人机这类不受转向限制的场景，我才会改用八邻。

另一个容易忽略的点是障碍物膨胀。规划前要把机器人半径叠加到障碍物上，否则路径会贴着墙走，在真机上撞墙。膨胀量一般取车体半径的 1.1 倍，留 10% 的余量。但要注意：外墙边界不要一起膨胀。边界是需要贴近作业的，膨胀后的路径永远离墙有一段距离，导致墙根漏覆盖。正确做法是把外墙和内部障碍物分开处理：内部障碍物做碰撞膨胀，外墙只在规划时允许路径走到离墙约半个车体宽度的位置。

3.2 按行扫描：一份可以直接改的 Python 实现

下面的代码输入一张栅格地图，输出按牛耕法生成的路径点列表。它先把每一行的自由栅格切成一个个连续区间，再按行往返扫描，遇到障碍物断开的区间也能正确处理。

import numpy as np def row_sweep_coverage(grid, start_row=0): """ 栅格地图牛耕覆盖，输出路径点列表（row, col） grid: 0 为自由栅格，>=1 为障碍栅格 """ rows, cols = grid.shape path = [] # 1. 提取每一行的自由区间，障碍物会把一行切开成多段 row_intervals = [] for r in range(rows): intervals = [] c = 0 while c < cols: if grid[r, c] == 0: start_c = c while c < cols and grid[r, c] == 0: c += 1 intervals.append((start_c, c - 1)) else: c += 1 row_intervals.append(intervals) direction = 1 # 1 表示向右扫描，-1 表示向左扫描 for r in range(start_row, rows): intervals = row_intervals[r] if not intervals: continue # 2. 按当前行进方向排序区间，避免在同一行内来回跳 if direction == 1: intervals.sort(key=lambda x: x[0]) else: intervals.sort(key=lambda x: -x[0]) # 3. 把区间展开成栅格点 for a, b in intervals: if direction == 1: seg = [(r, c) for c in range(a, b + 1)] else: seg = [(r, c) for c in range(b, a - 1, -1)] path.extend(seg) direction *= -1 # 4. 行尾换向，形成弓字形 return np.array(path)

这段代码的核心逻辑分三步：先扫描出每行的自由栅格区间，再按当前扫描方向排列这些区间，最后展开成离散点。其中direction变量负责在行与行之间切换方向，让路径呈现弓字形。如果一个区间被障碍物从中间断开，代码会把它拆成两个独立区间，避免路径直接从障碍物上穿过去。

参数方面，start_row可以指定从第几行开始扫描，适合把起始点放在区域长边端点旁边。grid的值只区分 0 和非 0，所以负值、未知栅格或不同障碍物等级都会被统一当作障碍物处理。如果你想把未知栅格和障碍物区别对待，在生成grid时把它们标成不同值，然后在区间提取时单独过滤。

3.3 四个必调参数：栅格尺寸、行间距、起始点与膨胀半径

牛耕法写出来后，真正影响效果的往往是参数，而不是算法本身。我总结出四个必调参数，按影响程度排序如下。

栅格尺寸是第一步。它决定地图离散化的精度，也决定路径点的密度。建议取覆盖宽度的 1/3 到 1/2。以一台覆盖宽度 60cm 的扫地机为例，栅格取 20cm 到 30cm 比较合适。小于这个范围，路径点数量会翻倍，但覆盖率提升有限；大于这个范围，窄通道会被直接抹掉。

行间距是最容易出问题的参数。很多人以为行间距等于覆盖宽度，结果实际跑起来相邻两行之间总有一条漏覆盖带。原因很简单，机器人沿直线走时会有横向漂移，转向入位时也有误差。我一般把行间距设为覆盖宽度的 0.8 倍，这样两行之间会有 20% 的重叠区，用来吸收定位和运动误差。无人机的取值可以放宽到 0.9 倍，因为飞行器没有地面轮式机器人的转向扰动。

起始点选择会影响整体路径的整洁度。常见的做法是从区域最外侧长边的端点开始，这样第一行就能覆盖整个长边，后续换向次数最少。反过来，如果从一个短边开始，路径会切成更多行，转向次数明显增加。这个差异在小区域里看不出来，在边长几十米的大区域里很可观。

最后一个参数是膨胀半径。它由车体尺寸决定，而不是由算法决定。需要注意的是，膨胀后的地图一定要在可视化界面上检查一遍，尤其要看狭窄通道是否被过度膨胀导致地图“堵死”。膨胀半径设得过大，会让原本可以通过的通道变成不可达区域，覆盖率就会永久性损失；设得过小，路径会离障碍物太近，真机上容易剐蹭。

4. 覆盖规划最容易翻车的五个场景：排查与避坑

覆盖规划的坑很难在仿真阶段暴露出来，多数要等真机跑起来才明显。以下五条是我在实际调试中反复遇到的场景，每条按现象、原因、解决的顺序说清楚，方便你直接对照排查。

4.1 覆盖率停在 98%，剩下的栅格永远扫不到

现象：覆盖率曲线到 98% 之后就不再上涨，路径反复在地图某个角落绕圈，但那一小片区域就是进不去。

原因：狭窄通道或凹形区域里的孤立栅格，在按行扫描时被结构性漏掉了。比如一条宽度只有一个栅格的走廊，牛耕法的行间距远大于走廊宽度，路径只会从走廊口经过，不会真正走进去。

解决：把连通区分解和覆盖规划拆开。先用 BFS 或 Flood Fill 标出所有自由栅格的连通分量，对每个连通分量单独做一次牛耕。如果某个连通分量自身就是一根窄带，就对该分量改用按列扫描，或者直接用下一章的 DFS 方案。这样能保证每个连通区都被分配了路径，而不是被大区域的扫行带过。

4.2 覆盖率足够，但重复率高达 40%

现象：仿真里看起来全走完了，一统计却发现很多栅格被覆盖了两次甚至三次。

原因：行间距设置过小，或者行进方向频繁切换导致重叠区变大。还有一个隐蔽原因是代码里没有处理区间之间的重复点，比如相邻两行的区间头尾重合。

解决：先把行间距调到覆盖宽度的 0.8 倍，再看重复率是否降下来。如果还高，把路径点画成覆盖热力图，给每个栅格累计覆盖次数，重复区域一眼就能看出来。检查时注意路径点本身是否去重：相邻行首尾相接时，最后一个点和下一行第一个点不要重复写入路径列表。

4.3 仿真时间合理，真机时间多出 35%

现象：路径总长度几乎一样，但真机执行时间比仿真预估多出一大截。

原因：转向次数太多。轮式机器人转弯时要减速、原地旋转再加速，一个 90 度转向的耗时大约等于直行 0.3 到 0.5 米。一条路径即使总长度短，如果充满频繁转向，实际耗时反而更长。

解决：在路径评价函数里加入转向惩罚。常见做法是每次转向按 15 个栅格的等价长度计入总成本。这样比较不同覆盖策略时，不会只看路径长度。真机上如果电机允许，可以设定最小转弯半径来代替原地旋转，也能显著降低转向耗时。

4.4 边缘永远漏一条带：贴墙不足

现象：机器人贴着墙走，但墙根始终有一圈没覆盖到，宽度大约等于半个车体。

原因：代价地图的障碍物膨胀层把外墙边界一起标记成了禁止进入区域。路径生成时默认所有膨胀栅格都不能走，路径自然就不敢靠近墙根。

解决：把障碍物碰撞膨胀和边界靠近补偿分开处理。内部障碍物必须做膨胀，外墙边界则不参与膨胀，只允许路径到达离墙约半个车体宽度的位置。实现时可以用两层地图：一层给碰撞检测，一层给覆盖评价。路径规划用碰撞层，但评价覆盖率时用包含边界补偿的评价层。

4.5 地图一更新，规划器直接死循环

现象：测试时往地图里加入一个新障碍物，规划器陷入局部反复横跳，或者在某个点来回走停不下来。

原因：在线地图更新后，已经规划好的路径点变成了不可达位置，但覆盖评价里仍然把这些点当作“还需覆盖”的目标。规划器试图走到一个已经被障碍占用的栅格，自然怎么走都走不到。

解决：覆盖规划器要能区分“已覆盖”和“已失效”。每次地图更新后，先删除落在新增障碍物上的路径点，再用局部重规划填补留下的空洞，不要整张地图重新规划。如果空洞面积很小，可以直接忽略，待下次任务再覆盖；如果面积大，就在空洞边界上选择一个入口点做局部牛耕，这样能避免全局重规划引起的路径大乱。

5. 没有全局地图时的兜底方案：在线 DFS 覆盖与参数收敛技巧

不是所有场景都有现成的高精度全局地图。厂房改造、野外勘察、灾后搜救这类环境，地图是边探索边建立的。此时就要用在线覆盖策略。这一章给出一个可运行的 DFS 覆盖模拟代码，并解释三个收敛参数怎么设置。

5.1 在线覆盖与离线覆盖的本质区别

离线覆盖假设已知整张地图，一次性规划出完整路径；在线覆盖只有局部传感器信息，机器人必须一边探索一边决定下一步往哪走。在线最大难点是：你永远不知道边界后面是什么，只能靠已经走过的区域推测还有没有未覆盖的邻居。常见做法是贪心加回溯：优先往未走过的方向走，走投无路时就沿着来路回退。

在线 DFS 的成功率不取决于算法本身多花哨，而取决于传感器的探测距离和地图更新的及时性。一个只看到三米外的扫地机，和一个能看到十米外的扫地机，即使用同一个覆盖算法，最终路径质量差别非常大。工程上还有一种常见做法：先开着机器人用在线覆盖快速跑一遍，拿到粗略地图后，再用离线的牛耕规划重跑一遍，进行补洞。这种做法比一上来就用离线规划安全得多，也比完全依赖在线覆盖高效。

5.2 一个可直接跑的 DFS 覆盖模拟器

下面这段代码模拟一个只知道局部地图的机器人。get_local_grid返回以当前位置为中心的局部占用信息，move_to负责执行位移。代码里用栈记录走过的路径，没有未访问邻居时就回溯到栈里的上一个节点。

def dfs_cover(get_local_grid, move_to, max_steps=3000): visited = set() current = (0, 0) visited.add(current) stack = [current] steps = 0 while stack and steps < max_steps: # 1. 读取以当前栅格为中心的局部地图 local = get_local_grid(current) nbrs = [] for drow, dcol in [(-1, 0), (1, 0), (0, -1), (0, 1)]: nxt = (current[0] + drow, current[1] + dcol) dx = nxt[0] - current[0] dy = nxt[1] - current[1] if local.get((dx, dy), 0) == 0 and nxt not in visited: nbrs.append(nxt) # 2. 有未访问邻居就走最近的一个，否则回溯到栈中上一节点 if nbrs: nxt = nbrs[0] move_to(nxt) visited.add(nxt) stack.append(nxt) current = nxt else: if len(stack) >= 2: back = stack[-2] else: break move_to(back) current = back stack.pop() steps += 1 return visited

这段代码的关键点有两个。第一，邻居只取四邻，理由和离线规划一样，避免窄通道被斜穿。第二，回溯时必须回到栈里的上一个节点，而不是任意已覆盖节点。如果回溯到任意节点，路径会在地图上跳变，实机根本无法执行。虽然这样会增加总路径长度，但保证执行的可行性。

max_steps是保护参数，防止机器人陷入死循环时无限空转。在真机上，我会把它设为“估计自由栅格数 × 3”的量级。这个值太小会导致覆盖中途停止，太大则失去了保护意义。get_local_grid的返回结构要设计成以当前栅格为原点的相对坐标字典，键是(dx, dy)，值是 0 表示可通行，这样代码可以复用不同传感器模型。

5.3 收敛参数：探测距离、回溯阈值和边界记忆

在线覆盖效果好不好，主要看三个参数。

探测距离决定机器人“看”多远。在仿真里把它调大一倍，相当于给机器人装了更好的传感器，路径的连贯性会明显提升。真机上如果探测距离很短，DFS 很容易陷入频繁回溯，路径变成锯齿状。这时建议提高“走向优先级”，让机器人优先直行而不是左右摇摆。

回溯阈值是控制放弃路径的标准。在上述代码里，只要没有未访问邻居就立即回溯，这在某些环境中过于保守。常见改进是允许机器人继续多走几步，看看是否还能进入新区域，超过阈值再往回撤。这个值不宜太大，否则机器人会在死胡同尽头反复原地试探。

边界记忆用于判断“是否绕回起点”。简单实现是把走过的边界栅格坐标存下来，当地图上所有未访问邻居都不可达时，说明覆盖已完成。真机上还要加一道安全护栏：连续若干步没有新增覆盖栅格，就自动停车报错。这能避免算法 bug 导致机器人原地打转，白白消耗电池和电机。

6. 验证你的覆盖规划器：覆盖率、重复率与转向代价三个量化技巧

覆盖规划器的输出不是看一眼路径图就完了，要量化。三个指标最实用：覆盖率、重复率、转向代价。它们分别对应任务完成度、效率浪费和执行耗时，缺一不可。

6.1 覆盖率：把“走过”变成“覆盖过”

覆盖率的基础公式是：覆盖率 = 被覆盖到的自由栅格数 / 自由栅格总数。但要注意，路径点是点，覆盖是面。一个路径点经过某个栅格，并不意味着这个栅格被完全覆盖。正确做法是把路径点按覆盖宽度膨胀成圆盘，再把圆盘覆盖到的栅格计为“已覆盖”。只统计路径点本身所在的栅格，会出现虚高结果，仿真里 99%，真机一跑只有 85%。

可视化时建议直接画覆盖热力图：已覆盖和未覆盖分色显示，漏覆盖区域一定会以小块或细条的形式暴露出来。这个热力图比任何数值都有说服力。

6.2 重复率：用计数矩阵量化

每个自由栅格维护一个计数器，路径每经过一次就加一。最终统计计数器大于 1 的栅格数占所有被覆盖栅格数的比例，就是重复率。

重复率低于 5%，说明规划质量很好；超过 20%，基本可以判断是行间距或区间排序出了问题。这一步也能用来对比不同算法的表现：同样的地图，牛耕和螺旋谁更合适，跑一两张热力图对比就清楚了。

6.3 转向代价：把耗时拍进仿真

仿真里只比路径长度是不公平的，因为转向在真机上的成本远高于直行。我会在仿真里给每个 90 度转弯加上等价直行步数，通常是 15 个栅格，然后比较“总步数 + 转向惩罚”的综合成本。之前我在某个模拟项目里做对比实验时，光加上这项惩罚，两个算法的优劣排序就直接翻转过来了。

我的习惯是：每次调完参数，先输出三张图——覆盖热力图、重复热力图、转向热力图，肉眼扫一遍再上真机。第一版覆盖规划器我只盯着覆盖率看，真机一跑才发现原地转向太多，电池耗完了覆盖率才到 70%。从那以后，我再也没有只凭一个数字判断覆盖质量。希望帮到你。

本文还有配套的精品资源，点击获取