PythonRobotics 覆盖路径规划（CPP）算法实战指南：网格扫描、螺旋生成树与波前覆盖
【免费下载链接】PythonRoboticsPython sample codes and textbook for robotics algorithms.项目地址: https://gitcode.com/GitHub_Trending/py/PythonRobotics
导读
覆盖路径规划（Coverage Path Planning, CPP）的目标是让机器人在不遗漏、不重复的前提下遍历工作区域内所有可通行空间，是清扫机器人、割草机、农业植保、船舶航道检测等应用的核心算法模块。本文以 PythonRobotics 仓库中的 coverage_path 文档 为主线，深入讲解其中收录的三种 2D 网格化覆盖规划算法——Grid based sweep（网格扫描）、Spiral Spanning Tree（螺旋生成树，Spiral-STC）与Wavefront（波前/距离变换）的原理、源码实现与运行方式。读完后你将理解三种算法的适用场景差异，并能在本仓库中直接运行对应的仿真与测试代码。
三种算法一览：同一目标，三种策略
覆盖路径规划问题天然存在多种求解思路。本仓库在PathPlanning目录下提供了三个独立模块，分别对应三种代表性方法：
| 算法 | 模块路径 | 核心思想 | 输入形式 |
|---|---|---|---|
| Grid based sweep | PathPlanning/GridBasedSweepCPP | 沿固定方向逐行“扫地”式扫描，遇障自动换行 | 多边形顶点坐标(ox, oy)+ 栅格分辨率 |
| Spiral Spanning Tree（Spiral-STC） | PathPlanning/SpiralSpanningTreeCPP | 基于生成树的在线螺旋覆盖，机器人沿树边做“环形回旋”遍历 | 偶数尺寸的二值 PNG 地图 + 起始节点 |
| Wavefront（波前/距离变换） | PathPlanning/WavefrontCPP | 在距离变换场/路径变换场上做最陡下降，得到全覆盖路径 | 二值 PNG 地图 + 起点 + 终点 |
三种方法覆盖了 CPP 领域的三种典型范式：确定性逐行扫描（实现简单、工程常用）、基于生成树的螺旋遍历（在线规划、单次遍历近似最优）、基于势场/距离变换的最陡下降（可显式控制终点与障碍距离）。下文分别展开其原理、源码结构与运行方式。
Grid based sweep：逐行扫描式全覆盖
算法流程与源码结构
Grid based sweep 的入口是planning()函数，位于 grid_based_sweep_coverage_path_planner.py，完整流程分为四步：
- 确定扫描方向与起点：
find_sweep_direction_and_start_position()遍历多边形各边，找出最长的一条边作为扫描主方向，并以其一端作为起点； - 坐标变换：
convert_grid_coordinate()将全局坐标旋转到扫描坐标系，使扫描问题简化为沿栅格轴行进；规划完成后再由convert_global_coordinate()逆变换回全局坐标； - 栅格化建图：
setup_grid_map()基于多边形包围盒与分辨率创建GridMap（复用 Mapping/grid_map_lib/grid_map_lib.py 中的通用栅格地图类），将多边形外部标记为占用栅格，并调用expand_grid()对障碍做一格膨胀，避免规划路径贴边； - 扫描搜索：
sweep_path_search()驱动SweepSearcher从起点开始，逐格移动直至覆盖全部自由栅格，返回路径点序列(px, py)。
核心调度逻辑在SweepSearcher类中（grid_based_sweep_coverage_path_planner.py），它用两个IntEnum描述机器人的运动状态：
SweepDirection：UP = 1/DOWN = -1，表示整体扫描（换行）方向；MovingDirection：RIGHT = 1/LEFT = -1，表示当前行内的行进方向。
move_target_grid()是单步决策函数：优先沿当前moving_direction前进；若前方栅格被占用，则通过find_safe_turning_grid()在“转向窗口”turing_window（包含前、斜前、侧、斜后共 4 个候选栅格）中寻找安全换行点；若整行都已覆盖，则回退一格并调用swap_moving_direction()反转行进方向，形成经典的“蛇形（boustrophedon）”扫描路径。is_search_done()通过检查目标边缘行是否全部被占用来判断覆盖是否完成。
参数说明与运行示例
planning()的完整签名如下：
def planning(ox, oy, resolution, moving_direction=SweepSearcher.MovingDirection.RIGHT, sweeping_direction=SweepSearcher.SweepDirection.UP): ... return rx, ry # 全局坐标系下的覆盖路径点ox, oy：工作区域多边形顶点的 x、y 坐标列表（浮点数，单位米）；resolution：栅格分辨率（米/格），直接决定覆盖精度与路径长度，越小路径越精细、计算量越大；moving_direction：行内行进方向，取RIGHT或LEFT；sweeping_direction：换行扫描方向，取UP或DOWN。
模块自带的main()（grid_based_sweep_coverage_path_planner.py）内置了三组多边形示例，例如第一组不规则凸多边形使用resolution = 5.0，第二组矩形区域使用resolution = 1.3。直接运行：
python PathPlanning/GridBasedSweepCPP/grid_based_sweep_coverage_path_planner.py即可看到红色覆盖路径沿多边形内部逐行推进的动画（窗口内按Esc可随时终止仿真）。关闭动画只需将模块顶部的do_animation置为False。
测试用例 test_grid_based_sweep_coverage_path_planner.py 对三组多边形分别验证了RIGHT/LEFT × UP/DOWN四种方向组合，断言生成的路径点数len(px) >= 5，保证算法在任意方向组合下都能正常出解。
Spiral Spanning Tree（Spiral-STC）：基于生成树的螺旋覆盖
算法原理：2×2 单元格合并与深度优先生成树
Spiral-STC 算法出自 Gabriely 等人的论文Spiral-STC: An On-Line Coverage Algorithm of Grid Environments by a Mobile Robot，其核心思想是：把地图按2×2的尺寸合并成“超格（merged cell）”，每个超格内的 4 个子格是否可通行决定了该超格是否可达；然后在超格级别构造一棵深度优先生成树，机器人沿树的每条边绕行一圈，即可在不重复经过任何子格的前提下覆盖整个自由区域。
本仓库的实现类为SpiralSpanningTreeCoveragePlanner，位于 spiral_spanning_tree_coverage_path_planner.py，规划入口是plan()方法。其关键设计点包括：
- 偶数尺寸约束：由于要做 2×2 合并，构造器要求输入地图的宽、高均为偶数，否则直接
sys.exit()报错退出； - 节点合法性判定：
is_valid_node()要求某超格的 4 个子格全部为自由格才算可达； - 逆时针邻居搜索：
perform_spanning_tree_coverage()按[[1,0],[0,1],[-1,0],[0,-1]]的逆时针顺序递归扩展生成树，无未访问邻居时回溯； - 往返路径处理：
plan()将生成树的边序列edge翻译为机器人的实际移动序列path，其中对“往返（round-trip）”、“相邻节点移动”和“非相邻节点（间距 2）”分别通过get_round_trip_path()、move()与get_intermediate_node()特殊处理，确保路径在子格粒度上连续； - 子格坐标映射：
get_sub_node()将超格节点映射回 2×2 子格的四个方位（SE/SW/NE/NW），这是“沿树边绕行”几何实现的基础。
运行方式与输入地图
模块的main()（spiral_spanning_tree_coverage_path_planner.py）默认读取 map/test_2.png（48×40 像素的十字形障碍地图），以start = (10, 0)为起点：
python PathPlanning/SpiralSpanningTreeCPP/spiral_spanning_tree_coverage_path_planner.py运行时窗口会同时展示灰色障碍地图、青色生成树边、紫色起点与黑色覆盖轨迹。同目录下还提供了 test.png（44×44）与 test_3.png（48×32）两张备选地图，可用于不同障碍形态的验证。
测试用例 test_spiral_spanning_tree_coverage_path_planner.py 对三张地图分别以(0,0)、(10,0)等不同起点运行规划，并断言生成树覆盖的超格节点数等于自由子格数除以 4（len(covered_nodes) == num_free / 4），从测试层面证明了“完整覆盖”这一核心性质。
Wavefront（波前/距离变换）覆盖路径
算法原理：距离变换场上的最陡下降
Wavefront 覆盖规划器实现了 Zelinsky 等人的论文Planning Paths of Complete Coverage of an Unstructured Environment by a Mobile Robot中的方法，位于 wavefront_coverage_path_planner.py。该方法的独特之处在于它显式给定了一个终点（goal），规划出的覆盖路径以终点收束，非常适合需要“扫完自动归位”的应用。
整个流程分两步：
- 构造变换场：
transform()以终点为源点，用类似动态规划的 BFS 遍历（8 邻域）计算每个自由栅格的代价，得到一张“变换矩阵”transform_matrix； - 最陡下降寻路：
wavefront()从起点出发，每一步都走向当前邻域中变换值最大且未被访问的栅格（代码中为transform_matrix[ni][nj] > max_T），一路“爬坡”到终点，从而遍历所有自由栅格。
transform()支持两种变换类型（transform_type参数）与两种距离度量（distance_type参数），组合出多种行为：
| 参数 | 取值 | 含义 |
|---|---|---|
distance_type | 'chessboard' | 8 邻域代价均为 1 的棋盘距离 |
distance_type | 'eculidean' | 对角邻域代价为sqrt(2)的欧氏距离（注意源码中此拼写为'eculidean'，使用时需保持一致） |
transform_type | 'distance' | 纯距离变换，等价于经典 Wavefront 距离场 |
transform_type | 'path' | 路径变换（Path Transform），额外叠加障碍距离项alpha * eT，其中eT由scipy.ndimage.distance_transform_cdt计算，alpha（默认 0.01）控制路径远离障碍的程度 |
alpha是路径变换的核心调参项：alpha = 0时退化为纯距离变换；alpha越大，覆盖路径越倾向于贴近障碍边缘（因为障碍近旁栅格的变换值被抬高，最陡下降更偏好经过它们），但过大会导致路径过度贴边。模块自带的main()（wavefront_coverage_path_planner.py）对同一张地图分别用距离变换与路径变换（alpha=0.01）各规划一次，便于对比两种变换场的差异。
运行方式与输入地图
默认读取 map/test.png（44×44），起点(43, 0)、终点(0, 0)。注意源码先执行img = 1 - img反转像素值，即地图中白色视为障碍、黑色视为自由空间：
python PathPlanning/WavefrontCPP/wavefront_coverage_path_planner.py窗口内将依次演示距离变换波前与路径变换波前两条红色覆盖路径。同目录的 test_2.png 与 test_3.png 可用于更多障碍形态测试（对应的起点/终点可参考 test_wavefront_coverage_path_planner.py 中的设置）。
测试用例 test_wavefront_coverage_path_planner.py 对三张地图分别验证了距离变换与路径变换两种模式，并断言len(DT_path) == num_free——即覆盖路径点数量必须等于自由栅格总数，从测试层面直接印证了“全覆盖、不遗漏”的正确性。
三种算法的选型对比与实践建议
综合上述源码分析，可以从以下几个维度对三种算法进行选型：
- 输入形式：Grid based sweep 接受任意多边形顶点（适合由测绘得到的封闭工作区域）；Spiral-STC 与 Wavefront 接受二值栅格/图片地图（适合已有占据栅格图的场景），其中 Spiral-STC 额外要求地图宽高为偶数；
- 终点约束：Wavefront 必须指定终点，可自然生成“覆盖结束后归位”的路径；Grid based sweep 与 Spiral-STC 不显式控制终点；
- 覆盖保证：三者的测试均验证了完整覆盖性质——Grid based sweep 的测试覆盖四种方向组合，Spiral-STC 断言超格覆盖数等于自由区 1/4，Wavefront 断言路径点数等于自由栅格总数；
- 在线/离线特性：Spiral-STC 源自在线覆盖算法，其生成树框架天然支持边探索边覆盖的在线场景；Grid based sweep 与 Wavefront 为离线规划；
- 障碍距离控制：Wavefront 的路径变换通过
alpha显式调节覆盖路径与障碍的贴近程度，是三者中可调性最强的。
工程实践建议：对简单规则区域（矩形、凸多边形），Grid based sweep 实现成本最低、行为最可预测；对存在复杂障碍且要求单次遍历不重复的区域，Spiral-STC 的生成树方案理论保证更强；对需要终点归位或希望控制贴边程度的场景，优先选用 Wavefront 路径变换并配合合适的alpha值。
延伸阅读与验证途径
- 三种算法的完整实现分别位于 GridBasedSweepCPP、SpiralSpanningTreeCPP、WavefrontCPP；
- 网格扫描算法依赖的栅格地图基础设施（
GridMap、FloatGrid、障碍膨胀expand_grid）见 grid_map_lib.py； - 三个模块的测试用例 test_grid_based_sweep_coverage_path_planner.py、test_spiral_spanning_tree_coverage_path_planner.py、test_wavefront_coverage_path_planner.py 提供了可直接参考的调用参数组合；
- 仓库还收录了其他覆盖/区域规划相关实现，如基于网格扫描的 grid_based_sweep_coverage_path_planner.py 之外，还可对比 PathPlanning 目录下其他路径规划算法理解“点到点规划”与“覆盖规划”的差异。
运行环境方面，本仓库的依赖清单见 requirements/requirements.txt，主要依赖numpy、matplotlib、scipy（Wavefront 模块的距离变换用到scipy.ndimage）等。克隆仓库后安装依赖，即可逐一运行上述三个模块的main()与对应测试，直观对比三种覆盖路径规划算法的行为差异。
【免费下载链接】PythonRoboticsPython sample codes and textbook for robotics algorithms.项目地址: https://gitcode.com/GitHub_Trending/py/PythonRobotics
创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
