覆盖式路径规划调研

覆盖式路径规划（CPP）要走遍一片区域而不是从 A 点到 B 点，评价标准也完全不同。本文 按「区域怎么被切开」这条轴梳理 CPP 的算法体系，回顾四篇综述二十年的关注点迁移， 并给出六个主流开源实现的实测对比。

一、问题定义

1.1 覆盖与点到点的区别

全局路径规划回答「怎么从 A 走到 B」，覆盖式路径规划（Coverage Path Planning, CPP） 回答的是「怎么走遍这片区域的每一个可达位置」。扫地机器人、割草机、农业植保、 消杀、巡检安防都属于后者。

这个差别不只是目标不同，评价体系是另一套：

指标 含义 点到点规划里有没有
覆盖率 区域内被传感器视场（或机体）扫过的比例 无
重复率 路径中重叠部分占比，越低越好 无
路径长度 / 时间 完成覆盖的总代价 有
转弯次数与累计转角 转弯要减速、停车、原地旋转，是实际耗时的大头 弱
重访间隔 周期性巡检中同一位置两次被访问的时间差 无

转弯代价是最容易被低估的一项。 Bormann 等人在 550 多张真实户型图上做的对比里， 神经网络法的覆盖率不差，但路径最长、累计转角最大、主观观感最差；而 Boustrophedon 分解转弯最少。在实机上，几十次多余的原地旋转带来的时间损失，往往超过路径长度 差异本身——因为非完整约束底盘的原地转向速度远低于直行。

1.2 复杂度

CPP 与覆盖旅行商问题和割草机问题同源，均为 NP-hard。这决定了：

  • 精确最优解只在很小规模下可求
  • 实用算法基本是「先用几何把问题拆小，再在小规模上做组合优化」
  • 「完备性」（只要存在完全覆盖的路径就一定能找到）和「最优性」要分开谈， 绝大多数工程算法只保证前者

Galceran 与 Carreras 在 2013 年的综述里总结了 CPP 的六条理想准则： 完整性、高效性、连续性、避障、轨迹简单性、最优性。没有算法能同时满足全部六条， 选型本质上是在这六条之间取舍。

二、算法体系：按「区域怎么被切开」看

CPP 的算法名目繁多，但真正的分野只有一个问题：要不要先把区域切开，以及怎么切。

flowchart TD
    A["目标区域 + 障碍"] --> B{"要不要先切开？"}
    B -->|"不切"| C["栅格遍历<br/>Wavefront / Spiral-STC / BSA"]
    B -->|"几何切"| D["单元分解<br/>梯形 / Boustrophedon / Morse"]
    B -->|"语义切"| E["房间分割<br/>Voronoi / 形态学"]
    B -->|"不切，学策略"| F["DRL<br/>DQN / PPO / A3C"]
    D --> G["cell 内弓字形往复"]
    E --> G
    G --> H{"cell 间顺序怎么定？"}
    H -->|"邻接图穷举"| I["走一遍就完"]
    H -->|"组合优化"| J["TSP / GTSP<br/>近年主流"]
    C --> K["路径后处理<br/>Clothoid 平滑"]
    I --> K
    J --> K

2.1 不切：直接在栅格上走

把地图栅格化，直接设计一条遍历所有自由栅格的规则。

方法 原理 特点
Wavefront / 距离变换 从目标点做波前扩散，按梯度遍历 简单直观，适合规则区域
Spiral-STC 划分为 2D×2D 大单元，构建生成树后沿树螺旋覆盖 保证完全覆盖且重复率极低，需预知全局地图
BSA（回溯螺旋） 螺旋覆盖 + 回溯机制处理死角 可处理更复杂地图
神经网络法 Hopfield / 竞争型网络的能量最小化 可应对动态障碍，但路径长、转弯多

生成树覆盖（STC）系列的价值在于重复率：因为沿树走，理论上每个大单元只经过一次。 代价是把地图按 2D×2D 粗化，分辨率损失在窄通道场景会致命。

2.2 几何切：单元分解

把自由空间切成若干互不重叠的简单子区域（cell），并集恰好等于自由空间， 每个 cell 内部无障碍，可用简单的弓字形往复走完。

  • 梯形分解：在每个障碍物顶点做垂直线，产生大量细碎 cell。实现最简单，但 cell 多、路径长。
  • Boustrophedon（牛耕式）分解：只在「连通性发生变化」的临界点处划分， cell 数量通常约为梯形分解的一半，覆盖路径显著更短。这是室内覆盖最成熟的方法。
  • Morse 分解：Boustrophedon 的推广，基于 Morse 函数的临界点划分， 可处理非多边形障碍，且临界点可以在线检测，理论更完备但实现复杂。

Boustrophedon 的失效场景要记住：在杂乱环境中，障碍物顶点密集会导致 cell 被切得 极碎，每个 cell 只够走一两趟，cell 间转移的代价反而主导了总路径。这时候它退化得 比栅格法还差，Bormann 等人建议与局部能量法互补使用。

2.3 切完之后：遍历顺序才是近年的主战场

分解完成后还剩一个问题：这些 cell 按什么顺序走。早期做法是在邻接图上找一条 穷举遍历路径，走通即可，不追求最优。近年的主流是把它建模成组合优化问题：

  • Grid-based TSP：把栅格中心当节点求解 TSP。路径质量高，但计算开销随区域 急剧上升——Bormann 等人的实验里，优化类方法平均 41.6 秒一个房间，最坏超过 30 分钟， 而启发式方法都在 4 秒以内。
  • 广义旅行商问题（GTSP）：把 BCD 分解后的每个 cell 视为一个「点集」（该 cell 有多个可能的进入/离开点），求解 GTSP 得到最优 cell 遍历序列。 Bähnemann 等人的工作把这条路线做扎实了，是目前多边形覆盖里效果最好的组合优化方案。

一条负面结果值得记：Manzini 与 Murphy 尝试把 BCD 路径参数化成可微形式， 用梯度下降优化扫描方向和间距，结论是搜索空间高度非凸、梯度方法效果有限。 这条路暂时走不通，组合优化仍是当前的正解。

2.4 语义切：先分房间再覆盖

室内场景还有第三条路：不按几何临界点切，按语义切成房间，再逐个房间覆盖， 最后用 TSP 优化房间访问顺序。Fraunhofer IPA 的工具链就是这个结构—— 房间分割、房间内覆盖、多房间访问顺序三个模块分离。

好处是分解结果符合人的直觉（一个房间一次走完，不会来回横跨）， 并且天然支持「跳过某些房间」这类业务需求。

2.5 不切，学一个策略出来

深度强化学习路线把覆盖建模成 MDP，直接学一个从状态到动作的策略：DQN 处理大状态空间、 PPO 用于工业喷涂、A3C/DDPG 处理连续控制。卖点是不需要显式建模几何约束。

但工程落地要清醒：训练成本高、可解释性差、对地图变化的泛化未经充分验证。 在静态已知地图这个前提下，几何方法的确定性和可调试性目前仍明显占优。 DRL 真正有价值的场景是未知或动态环境——那里几何方法本身也不成立。

2.6 路径后处理：平滑

上面所有方法产出的都是折线路径，弓字形的直角转弯对非完整约束底盘尤其难跟踪 （要减速、停车、原地旋转、再起步）。

Šelek 等人的做法是用 clothoid（回旋曲线） 替换转弯段。clothoid 的曲率随弧长 线性变化，这正好匹配「方向盘匀速转动」或「差速底盘角速度线性变化」的物理过程， 使机器人能以时间最优的方式通过转弯，不必在转弯点停车旋转。他们在 Pioneer 3DX 上实测降低了覆盖时间、路径长度和重叠面积。

注意他们平滑的对象是生成树覆盖（RSTC）路径，不是弓字形路径——不过思路可迁移。

三、四篇综述，二十年的关注点迁移

维度 2013 Galceran 2018 Bormann 2019 Almadhoun 2025 Jayalakshmi
研究对象 单机 2D/3D 室内房间级 多机 3D 重建 动态环境多机
方法重心 几何分解 实验对比 分布式协调 强化学习 / 预测
独特贡献 建立分类体系 开源实现 + 550 张户型图数据集 视点-路径-重建流程 学习类方法梳理
环境假设 以静态为主 静态 静态 + 部分动态 动态为核心

共同底座：Boustrophedon、STC、栅格法在四篇综述中被反复引用，是 CPP 的基石。

另有一篇 2021 年 IEEE Access 的综述（A Comprehensive Review of Coverage Path Planning in Robotics Using Classical and Heuristic Algorithms）被引已超过 340 次， 按经典法与启发式法两分，可作为 2013 与 2025 之间的补充参照。

一个从引文数据里读出来的观察

顺着 Galceran 2013 的被引展开会发现一个明显的现象：2021 年以后引用它的高被引论文， 绝大多数是无人机、农业和海事搜救——多机 UAV 覆盖、精准农业路径规划、 水面搜救覆盖占据了前列，室内地面机器人的 CPP 几乎看不到高被引新作。

我的解读是：室内地面 CPP 在学术上被认为基本解决了。剩下的困难是工程性的 （算力、跟踪精度、动态障碍、长期运行）。

四、开源实现

以下数据为 2026-08-29 通过 GitHub API 实测，非转述。

项目 算法 Star 许可证 最后推送 输入 生态
Fields2Cover BCD / 梯形等多种 880 BSD-3-Clause 2026-08 多边形（含孔洞） 独立库，面向农业
nobleo/full_coverage_path_planner BSA 螺旋 671 Apache-2.0 2025-05 costmap ROS 1 / MBF 插件
ethz-asl/polygon_coverage_planning BCD + GTSP 655 GPL-3.0 2023-11（已停更） 多边形（含孔洞） ROS 1
ipa320/ipa_coverage_planning 8 种可选 359 见下方注意 2025-11 OccupancyGrid ROS 1
Greenzie/boustrophedon_planner BCD 314 LGPL-3.0 2024-05 多边形 ROS 1，ActionLib
open-navigation/opennav_coverage Fields2Cover 封装 314 Apache-2.0 2026-08 多边形 ROS 2 / Nav2

选型的几个维度

抛开具体项目，选型时真正会卡住的是这几点：

  1. 输入形式：接受多边形，还是只接受 OccupancyGrid / costmap？ 如果业务是「用户圈一片区域」，前者省掉一整套地图裁剪逻辑。
  2. 孔洞支持：区域内部有柱子、固定设备时，规划器能不能直接处理带孔多边形。 不支持的话要么预处理拆分，要么靠代价地图兜底。
  3. 许可证：见上。这一条决定能不能用，应该第一个查而不是最后一个查。
  4. 输出形式：多数项目输出的是航点序列（PoseArray / Pose2D[]）， 需要自己写一个节点逐点下发给导航栈，这部分工作量在选型时容易被漏算。
  5. ROS 版本：ROS 1 生态里可选项多但多数已停更；ROS 2 侧目前主要是 Nav2 官方的 opennav_coverage 一条路。
  6. 覆盖语义：是机体覆盖（清扫、消杀，要求实体走过）还是 传感器视场覆盖（巡检、监控，扫到即可）。两者的行距计算完全不同， 后者的行距由 FOV 决定，通常远大于机体宽度。

五、几个值得注意的方向

转弯最小化被单独立题了。 有工作专门研究非凸环境的最优分区以最小化转弯次数 （RA-L 2022），而不是最小化路径长度。这与 1.1 节的观察一致——转弯才是实际耗时的大头。

巡检场景带来了新指标。 CPP 的传统目标是「走完」，而周期性巡检关心的是 「多久回来一次」。Kachavarapu 等人的 FaRe-CPP 面向巡逻机器人，用长距离传感器 信息生成覆盖航点并做随机搜索优化，报告路径长度减少 21%–40%、重访时间减少 33%–45%。 这是一个和覆盖率正交的优化目标，传统 CPP 方法并不直接优化它。

多机从启发式转向了组合优化与学习。 近年有把大规模多机 CPP 做成局部搜索的工作 （AAAI 2024），也有用混合整数规划求时间最优多机覆盖的（RA-L 2023）。 学习类的代表是 MARVEL（ICRA 2025），用图注意力网络处理受限视场下的多机协同—— 注意它解决的是探索（exploration）问题而非覆盖（coverage），两者目标不同， 不要混为一谈。

可重构机器人是个冷门但有趣的分支。 有一类工作研究能改变自身形状的瓦片式机器人 如何覆盖——形状可变意味着覆盖宽度不再是常数，这让传统的等行距假设失效。

六、我的判断

如果场景是室内静态已知地图 + 多边形圈定区域，BCD 加上 GTSP 优化遍历顺序仍是 当前最优实践，DRL 方法的工程成熟度还不足以替代它。这个结论在过去几年基本没变， 也印证了第三节那个「室内地面 CPP 已经成熟」的观察。

但真正决定项目成败的往往不是算法选择，而是三件更琐碎的事：

  1. 航点下发与跟踪——几乎所有开源项目都只到「输出一串航点」为止， 从航点到实际平滑行驶之间的工程量，比算法本身大
  2. 转弯的实际代价——纸面上的路径长度对比，可能和实机耗时排序完全不同

最值得投入的优化方向，我认为是路径后处理而非路径生成：用 clothoid 之类的 曲率连续曲线替换直角转弯，收益直接体现在耗时和跟踪稳定性上，且不依赖于换算法， 对现有系统是增量改进。

七、参考

综述

  • Galceran, E., & Carreras, M. (2013). A survey on coverage path planning for robotics. Robotics and Autonomous Systems, 61(12), 1258–1276. DOI: 10.1016/j.robot.2013.09.004
  • Bormann, R., Jordan, F., Hampp, J., & Haegele, M. (2018). Indoor coverage path planning: Survey, implementation, analysis. ICRA 2018. ｜💻 ipa_coverage_planning
  • Almadhoun, R., Taha, T., Seneviratne, L., & Zweiri, Y. (2019). A survey on multi-robot coverage path planning for model reconstruction and mapping. SN Applied Sciences, 1(8), 847. DOI: 10.1007/s42452-019-0872-y
  • Jayalakshmi, K. P., Nair, V. G., & Sathish, D. (2025). A comprehensive survey on coverage path planning for mobile robots in dynamic environments. IEEE Access, 13. DOI: 10.1109/ACCESS.2025.3556446
  • Tan, C. S., et al. (2021). A comprehensive review of coverage path planning in robotics using classical and heuristic algorithms. IEEE Access, 9. DOI: 10.1109/ACCESS.2021.3108177

方法

  • Choset, H., & Pignon, P. (1998). Coverage path planning: The boustrophedon cellular decomposition. Field and Service Robotics. DOI: 10.1007/978-1-4471-1273-0_32
  • Bähnemann, R., Lawrance, N., Chung, J. J., et al. (2021). Revisiting boustrophedon coverage path planning as a generalized traveling salesman problem. Springer Proceedings in Advanced Robotics（FSR 2019）. DOI: 10.1007/978-981-15-9460-1_20 ｜💻 polygon_coverage_planning
  • Manzini, T., & Murphy, R. (2023). Differentiable boustrophedon paths that enable optimization via gradient descent. arXiv:2309.09882
  • Šelek, A., Seder, M., Brezak, M., & Petrović, I. (2022). Smooth complete coverage trajectory planning algorithm for a nonholonomic robot. Sensors, 22(23), 9269. DOI: 10.3390/s22239269
  • Kachavarapu, S., Doernbach, T., & Gerndt, R. (2025). Fast-revisit coverage path planning for autonomous mobile patrol robots using long-range sensor information. arXiv:2501.07343
  • Karakaya, S., & Konyar, M. Z. (2025). Hybrid boustrophedon and direction-biased region transitions for mobile robot coverage path planning. Applied Sciences, 15(23), 12666. DOI: 10.3390/app152312666
  • Ni, J., Gu, Y., & Tang, G. (2024). Cooperative coverage path planning for multi-mobile robots based on improved K-means clustering and deep reinforcement learning. Electronics, 13(5), 944. DOI: 10.3390/electronics13050944
  • MARVEL: Multi-agent reinforcement learning for constrained field-of-view multi-robot exploration in large-scale environments. ICRA 2025. arXiv:2502.20217 ｜💻 marmotlab/MARVEL

开源实现（Star 数与许可证为 2026-08-29 实测）

项目 许可证 说明
Fields2Cover BSD-3-Clause 农业方向，模块化，最活跃
nobleo/full_coverage_path_planner Apache-2.0 BSA 螺旋，MBF 插件
ethz-asl/polygon_coverage_planning GPL-3.0 BCD+GTSP，已停更
ipa320/ipa_coverage_planning LGPL，商用需授权 8 种算法，含 FOV 模式
Greenzie/boustrophedon_planner LGPL-3.0 接受多边形输入，代码简洁
open-navigation/opennav_coverage Apache-2.0 ROS 2 / Nav2 生态
机器人学 > 导航规划
#覆盖式路径规划 #单元分解 #巡检 #开源实现 #调研
覆盖式路径规划调研
https://ethanyliang.github.io/2026/08/29/覆盖式路径规划调研/
作者
EthanYLiang
发布于
2026年8月29日
更新于
2026年9月2日
许可协议