精读笔记

Problem Setting

《C*: A Coverage Path Planning Algorithm for Unknown Environments Using Rapidly Covering Graphs》（IEEE Transactions on Robotics / 2026）处理的是未知环境中的在线 CPP：机器人不知道完整地图，只能在运动过程中通过传感器增量发现环境，同时要形成一条覆盖整个自由空间的轨迹。这里的关键矛盾是：覆盖任务希望轨迹具有全局结构，例如整齐的 back-and-forth 扫掠以减少转弯和重叠；但未知环境只允许局部观测，局部贪心很容易被障碍拓扑诱导到死角或留下孤立未覆盖区域。以前很多方法卡在表示和决策不匹配：grid 表示足够细，但每步决策常是局部 cell 级别；spanning-tree/spiral/backtracking 能保证覆盖，却常以不必要的回退、螺旋转弯或后处理补洞为代价。C* 试图解决的不是一般意义的全局最优 CPP，而是在在线未知场景中构造一种足够轻量、足够拓扑感知、又能诱导规则扫掠轨迹的中间表示。

Motivation

作者看到的缺口很明确：在线 CPP 需要一个比局部网格邻域更“长视”的状态表示，但又不能像全局优化那样依赖完整地图。已有路线要么随机/局部导致重复覆盖高，要么系统性模式在复杂障碍下会形成 coverage holes，要么死角逃逸依赖搜索完整 grid，计算和轨迹质量都不理想。C* 的出发点是：覆盖问题中真正需要被记住的不是所有 free cells，而是与扫掠推进、边界闭合、障碍绕行和未探索 frontier 有关的少量结构点。如果能在线维护这个稀疏骨架，就可以把未知环境下的覆盖从密集栅格搜索转成图上的状态推进。核心观察是 coverage holes 的代价通常来自“发现得太晚”：当一个局部未覆盖区域已经被已覆盖轨迹和障碍包围后，再从远处回去补，会显著增加 overlap 和 trajectory length。因此作者把 hole prevention 放到在线决策时刻，而不是作为事后回溯。

Core Idea

论文真正核心的思想是 Rapidly Covering Graph：不是对环境做完整离散化，而是增量构建一个覆盖任务所需的 sparse, planar, connected, minimum-sufficient graph。节点来自 frontier samples，边对应潜在可通行覆盖段。这个图的角色介于 occupancy grid 和 topological roadmap 之间：它不是 purely geometric roadmap，也不是 uniform coverage grid，而是被 back-and-forth 覆盖模式强约束过的任务图。

本质区别在于信息流被重组了。传统 grid-based online CPP 通常是“地图更新 → 当前邻域选 cell → 必要时回溯”；C* 是“地图更新 → frontier/lap 采样 → RCG 稀疏化 → 图状态驱动下一 waypoint”。这带来两个 inductive bias：一是 coverage trajectory 默认沿固定方向形成 boustrophedon 模式，减少无意义转弯；二是只在 frontier/障碍/边界附近保留节点，把复杂几何压缩成 coverage-relevant topology。理论上它有效，是因为覆盖半径和 lap 间距保证相邻 laps 间区域被覆盖，RCG 连通性保证所有 lap/边界结构可达，dead-end escape 保证不会因局部封闭而终止。

Method

C* 的关键机制可以压缩为四个，而不是按论文模块流水账理解。

第一，progressive frontier sampling 解决的是未知环境下“何时在哪里扩展表示”的问题。它只在新发现且未采样的 sampling front 上生成 frontier samples，并沿期望扫掠方向布置 laps。这一步的核心变化是把 uniform grid 的全域离散变成 coverage-frontier-driven 的非均匀采样，降低表示规模，同时保留对未知边界和障碍边界的敏感性。

第二，RCG pruning 解决的是“稀疏化之后是否还足够覆盖”的问题。essential nodes/edges 的定义围绕三类信息：未知区域连接、lap 端点覆盖、跨 lap 转移。它牺牲了很多几何细节，但保留了覆盖推进所需的拓扑连通和边界贴合。这里的有效性依赖一个强假设：覆盖轨迹主要可以被 lap structure 表达。

第三，goal selection 解决的是“如何从稀疏图生成低转弯轨迹”的问题。固定优先级邻居选择看起来简单，但它强行把搜索策略投影到 back-and-forth 模式上。它不是在每一步优化 CT，而是用结构化策略避免局部策略产生的 zig-zag 和 spiral。

第四，retreat node 与 coverage-hole TSP 分别解决两个失败模式：前者处理无 open neighbor 的死角，用 A* 找最近可继续覆盖的开放节点；后者在局部未覆盖区域即将变成孤岛时，用小规模 TSP 先清掉。TSP 在这里不是全局优化器，而是局部异常区域的修补器。

Key Insight / Why It Works

这篇论文最有效的部分不是 TSP，也不是 A* dead-end escape，而是 RCG 这个任务特化表示。它把在线覆盖的状态空间从 dense grid 降到 sparse frontier graph，同时引入强烈的 boustrophedon inductive bias。多数性能增益应来自两个来源：一是 representation sparsification 让 waypoint 更非局部，减少迭代和局部抖动；二是 hole prevention 避免了后期长距离补洞带来的 overlap。换言之，C* 的优势更像是 better inductive bias + memory reuse，而不是更强的通用规划优化。

所谓 near optimal 需要谨慎看。C* 接近全图 TSP path length 的实验很有说服力，但不应理解为算法具有全局最优性。全图 TSP 是 offline 已知地图下的强基线，C* 是在线规则策略；两者接近可能说明在测试场景中 back-and-forth + 局部补洞已经接近几何覆盖下界，也可能说明场景结构偏向这类规则扫掠。文中未充分说明不同 sweep direction、障碍密度、窄通道比例和非矩形拓扑对 near-optimality 的影响。

coverage-hole prevention 是实质贡献，但它更像 localized test-time compute：当全局规则模式遇到局部拓扑异常时，临时把异常区域转成小规模 TSP。这个设计很实用，因为 coverage holes 通常规模小，TSP 成本可控；但它并没有解决全局 coverage ordering，只是避免一种常见坏局部结构。dead-end escape 则相对常规，主要是把回退目标限制在 retreat nodes 上，减少搜索和避免破坏轨迹结构。

完整性证明的核心依赖是 resolution-level 几何覆盖：若 lap spacing w 不超过覆盖直径，且 RCG 最终能沿所有 frontier 扩展，那么相邻 laps 间区域被覆盖。这里的 complete coverage 不是连续几何意义下无条件保证，而是对采样分辨率、传感覆盖、地图精度和自由空间连通性的组合保证。文中对噪声做了实验，但理论上对 noisy SLAM、障碍误检、定位漂移导致的 graph inconsistency 支撑不足。

Relation To Prior Work

C* 最接近的技术谱系是 online systematic CPP，尤其是 boustrophedon/back-and-forth、STC/BSA/BA*、grid backtracking 和 frontier-based exploration 的混合体。它不是从零发明一种覆盖范式，而是把几个已有思想重组到一个更合适的表示中：frontier sampling 来自探索，lap-based sweep 来自 boustrophedon，dead-end escape 来自 graph search/backtracking，局部 TSP 来自 known-region coverage optimization。

真正不同点是表示层。STC/FS-STC 以 grid/spanning tree 为主，保证性强但轨迹形态和分辨率受限；BSA/BM/BA* 在局部邻域做规则推进，回退成本高；NNCPP/势场类方法用场传播解决吸引未覆盖区域，但轨迹可能不规整且解释性弱。C* 用 RCG 把“覆盖所需的拓扑边界”显式化，因此能同时获得规则扫掠和较低搜索成本。实质创新是 minimum-sufficient graph for coverage 这个中间抽象，以及把 coverage-hole detection 接到局部 TSP 修复上。看似新的部分中，A* 回退、TSP 求局部路径、back-and-forth 扫掠本身都不是新思想；新的是它们被 RCG 统一组织后形成了稳定的信息流。

Dataset / Evaluation

评估设计总体能支撑工程有效性。仿真包含多个 50m × 50m 随机复杂障碍场景，并与七个在线 CPP baseline 比较 CT、NT、TL、OR；还有传感噪声扰动、真实机器人实验，以及 energy-constrained 和 multirobot 扩展。真实实验尤其重要，因为该类方法很容易在完美仿真地图中表现好、在真实定位和障碍 buffer 下退化。论文展示了 onboard 实时运行和实际 dead-end/hole handling，这是强证据。

但 evaluation 仍有明显边界。第一，场景主要是二维静态、障碍固定、覆盖半径和采样分辨率匹配的 setting；它没有验证动态障碍、强定位漂移、复杂非欧式约束或大尺度地图下的长期一致性。第二，比较基线多为 grid/rule-based CPP，缺少更强的 modern sampling-based/global replanning hybrid 或学习型 policy 在相同设置下的对照。第三，与 optimal TSP 的比较容易被误读：它验证 path length 接近某个 offline surrogate，不等于在线策略全局最优。第四，多机器人实验主要验证了 centralized partitioned deployment 下的可用性，不足以支持去中心化协同或高机器人数量 scalability claim。

Limitation

C* 的上限由它的 inductive bias 决定。它假设 back-and-forth 是大多数场景的好模式，因此在长条、房间、岛屿类二维环境中会很好；但在高度碎片化、窄通道密集、覆盖代价各向异性、转弯半径显著、或 sweep direction 选择不佳的环境中，固定 lap structure 可能变成限制。文中未充分说明 sweep direction 如何自适应选择，方向错误时可能导致过多跨 lap 转移和局部 TSP 修补。

完整覆盖保证是 resolution completeness，不是传感/建图不确定性下的严格保证。RCG pruning 假设 essential criteria 足以保留所有必要覆盖结构，但在 noisy map 或边界拓扑频繁变化时，错误 pruning 可能造成不可见的覆盖缺口。文中对噪声的实验较温和，不能完全说明真实 SLAM drift 下 RCG 的一致性问题。

coverage hole detection 依赖对“已发现但未覆盖、且不邻接未知”的判断，这在在线未知环境中很脆弱：如果未知区域被误判为障碍或已知边界，可能过早把区域当 hole；如果边界感知不完整，可能漏检。TSP 子问题规模通常小是经验性假设；在复杂障碍造成大面积局部孤岛时，TSP 计算和轨迹质量都会受影响。

energy-constrained 和 multirobot 扩展更像 engineering demonstration。energy 版本只是把节点推进前加 retreat feasibility check；multirobot 版本依赖 centralized server、统一 RCG 和简单空间 partition，真正的任务分配、冲突避免、通信延迟、失败恢复都不在核心算法内。因此这些扩展说明 C* 表示可复用，但不构成相应问题的完整解法。

性能增益归因也并非完全清晰。更低 OR/TL/NT 可能来自 RCG，也可能很大程度来自固定 back-and-forth 轨迹和 proactive hole repair；缺少 ablation，例如无 pruning、无 TSP hole prevention、dense grid with same sweep policy、不同 sampling resolution 的系统比较。没有这些实验，很难精确判断 RCG 本身贡献了多少。

Takeaway

1. 对在线 CPP 来说，关键不一定是更复杂的优化器，而是任务特化的中间表示：只保留 coverage-relevant topology，可以同时提升实时性和轨迹质量。
2. Proactive repair 比 post-hoc backtracking 更重要。
coverage holes 一旦形成，后续代价通常是非局部的；在局部拓扑刚闭合时处理，能显著降低 overlap。
3. C* 的可迁移 insight 是“global regular pattern + local exception solver”：用强规则模式覆盖大部分空间，用局部优化处理障碍诱发的异常。

一句话总结

C* 是一类从 dense grid 在线覆盖转向 sparse task graph 覆盖的系统性 CPP 方法，真正贡献在于用 RCG 这个强 inductive-bias 表示把规则扫掠、死角逃逸和局部补洞统一起来，而不是提供一般意义的全局最优规划。