一、为什么不用先验地图
分叉在哪
2025 年那篇 CPP 综述把这条当作一级划分，并且把「在线 / 离线」和「未知 / 已知」当成同一件事：
Offline planning 指机器人在已知环境中工作，所有环境数据事先给定。
空间覆盖
┌───────────────┴───────────────┐
有先验地图 无先验地图
任务 = 纯路径规划 任务 = 建图 + 覆盖
可一次算出完整路径 只能边走边决定
感知只用于避障 感知同时要建图
BCD / 螺旋 / TSP ICML 2024
三条依据
① 已知地图下，学习方法没有立足点
ICML 2024 自己承认：和离线 BCD 比，他们到 90% / 99% 覆盖分别慢 35% 和 51%。 他们的说法是「BCD 是离线方法且不解决建图问题，我们不指望超过它， 只是拿它看自己离好解有多远」。
离线经典方法在已知地图上仍然是上界。
② 已知地图下，我们的差异有两处失效
| 差异 | 已知地图下还剩多少 |
|---|---|
| RGB 感知 | 障碍都在图上，感知只剩处理动态障碍 → 价值大减 |
| 预训练骨干 | 没什么需要「理解」的 → 价值大减 |
| 候选 + 几何打分 | 仍然有效 |
③ 领域分工本来就是这样
那篇综述的一级划分里，已知地图那支是 BCD / 螺旋 / TSP 几十年的成熟领地； 学习方法集中在未知那支。
代价
量产清扫机器人是「先建图，再用图清扫」，已知地图更贴近它们的日常工作方式。
适用范围因此要划清楚：未知地图设定对应首次进入、环境发生变化、或无法预先建图的场景； 已知地图下的覆盖是另一个成熟的问题，不在本文范围内。
二、无先验地图的覆盖清扫：先例分析
无先验地图的覆盖清扫不是新问题。先例分三块，学术上还分成互不往来的两支。
先验知道什么：三档，不是两档
「在线」不等于「什么都不知道」。核过原文之后，这批算法要分三档：
① 全知 边界已知 + 障碍已知 离线 STC 2001 · BCD · F2C
② 半知 边界给定 + 障碍未知 在线 ε* / ε*+
③ 全未知 边界未知 + 障碍未知 在线 Spiral-STC 2002 · C* 2026
本文要的是第 ③ 档。 ICML 2024 用自我中心多尺度地图 + frontier，不需要全局范围，属第 ③ 档； 具身探索（Habitat）同属第 ③ 档。
依据
STC 2001 是离线的：
This earlier version is off-line, where the robot has perfect a priori knowledge of its environment
在线版是另一篇，Spiral-STC（ICRA 2002），针对 unknown terrain graph。这两篇常被混为一谈。
ε* 是第 ② 档。ε*+ 论文里这两句放在一起看：
a hierarchical multiscale tiling (MST) is constructed on the search area A
The states of all the cells are initialized with state U as the search area is assumed to be a priori unknown
「a priori unknown」指的是格子的状态未知。要铺 tiling 就得先知道 A 的范围， 所以区域边界是给定的。（这一句是把两处并起来的推断，不是论文原话。）
C* 是第 ③ 档，问题定义里写死了：
Let 𝒜⊂ℝ² be the unknown area populated by obstacles of arbitrary shapes
经典 CPP 一览
| 年 | 方法 | 作者 | 先验知道什么 | 核过 |
|---|---|---|---|---|
| 2000 | 在线单元分解（Morse） | Acar & Choset | 未知，传感器增量构建 | 题名 |
| 2001 | STC 生成树覆盖 | Gabriely & Rimon | ① 全知（离线） | ✅ |
| 2002 | Spiral-STC | Gabriely & Rimon | ③ 未知栅格图 | ✅ |
| 2003 | FS-STC | — | ? | ✗ |
| 2005 | BSA 回溯螺旋 | Gonzalez et al. | ? | ✗ |
| 2007 | Brick-and-Mortar | Ferranti et al. | ? | ✗ |
| 2008 | NNCPP | Luo & Yang | ? | ✗ |
| 2013 | BA* 牛耕 + A* 回溯 | Viet et al. | ? | ✗ |
| 2018 | ε* | Song & Gupta | ② 区域给定 | ✅ |
| 2019 | PPCPP 捕食者-猎物 | Hassan & Liu | ? | ✗ |
| 2025 | CAP | — | ? | ✗ |
| 2026 | C* | — | ③ 区域也未知 | ✅ |
标 ✗ 的六个只按 C* 相关工作的说法统称「online」，没有逐篇核过属于 ② 还是 ③。
共同点：全部假定测距传感器。 C* 的原话是机器人配备 「量程 r_d 的测距与建图传感器（如激光和超声）」。
2008 年那个 NNCPP 是生物启发式神经网络，不是深度学习。
学习类 CPP
Tetromino 清洁机器人 CCPP-RL、2022 年 IEEE 的 Adaptive CPP with DRL、2024 年的 DDQN + PER 室内盲区、2025 年 3 月的 TD3 preprint，以及 ICML 2024。
输入是占据栅格或激光测距向量，网络从零训。
具身探索
| 年 | 工作 | 内容 |
|---|---|---|
| 2020 | Active Neural SLAM（ICLR） | RGB 输入，边建图边探索，奖励即 area coverage |
| 2020 | Occupancy Anticipation（ECCV） | 从 RGB-D 预测视野之外的占据，Habitat PointNav 2020 冠军 |
| 2025 | NextBestPath | 未知环境的高效三维建图 |
商业
现代激光扫地机首次清扫即边扫边建图（SLAM + LDS）。无先验地图的覆盖清扫在商业上 是每台机器的第一次运行。部分机型另外提供先快速建图、再清扫的 mapping run 模式。
三支的位置
| 感知 | 要求机器人本体压过每一点 | |
|---|---|---|
| 经典在线 CPP（STC / BSA / ε* / C*） | 测距 | ✅ |
| 学习类 CPP（DQN / TD3 / ICML 2024） | 栅格 / 激光向量 | ✅ |
| 具身探索（ANS / OccAnt） | RGB | ❌ 看到就算 |
| 本文 | RGB | ✅ |
具身探索与学习类 CPP 的差别
两支都在学，但评价体系不同。
| 具身探索 | 学习类 CPP | |
|---|---|---|
| 覆盖算什么 | 看到就算 | 本体压过才算 |
| 输入 | RGB / RGB-D 第一人称图像 | 占据栅格、激光测距向量 |
| 机器人 | 基本是点，无体积 | 有 footprint（清扫宽度） |
| 动作 | 离散（前进 0.25 m / 左右转 30°） | 连续速度量，常带非完整约束 |
| 仿真 | Habitat / Gibson / MP3D，真实房屋三维扫描 | 自己写的 2D 栅格世界 |
| 指标 | explored area (m²)、地图精度、下游 PointNav 成功率 | 覆盖率、路径长度、重复率、T90 / T99 |
| 结构 | 模块化：建图 → 选长期目标 → 走过去 | 多为端到端单策略 |
| 社区 | CVPR / ICCV / ICLR | ICRA / IROS / RA-L |
三条实质差别：
① 有没有体积。 具身探索的机器人基本是个点，路径宽度不存在， 「重叠率」「转弯代价」「漏一条 8 cm 的缝」这些概念在那边不出现。
② 能不能靠预测抄近路。 Occupancy Anticipation 的做法是预测视野之外的占据， 看不到也能标进地图。清扫这边预测再准也得开过去。
③ 端到端还是模块化。 ANS 是三段式，学习类 CPP 多是一张网直接出动作。
空白
上面那张表的右上格是空的：RGB 感知 + 要求本体压过每一点。
2025 年那篇 28 页的 CPP 综述里，camera 出现 2 次，
transformer / foundation model / pretrain / DINO / RGB 命中数为 0。
CPP 这一支不引具身那一支的工作。
本文的位置是把具身探索的感知栈接到 CPP 的任务定义上。
参考
- Jayalakshmi, Nair & Sathish. A Comprehensive Survey on Coverage Path Planning for Mobile Robots in Dynamic Environments. IEEE Access 13:60158–60185, 2025
- Jonnarth, Zhao & Felsberg. Learning Coverage Paths in Unknown Environments with Deep RL. ICML 2024
- Gabriely & Rimon. Spanning-tree based coverage of continuous areas by a mobile robot. Ann. Math. AI, 2001（离线）
- Gabriely & Rimon. Spiral-STC: An On-Line Coverage Algorithm of Grid Environments by a Mobile Robot. ICRA 2002
- Acar & Choset. Sensor-based coverage of unknown environments: Incremental construction of Morse decompositions. IJRR 2002
- Gonzalez et al. BSA: A Complete Coverage Algorithm. ICRA 2005 · Viet et al. BA*. 2013
- Song & Gupta. ε*: An Online Coverage Path Planning Algorithm. T-RO 2018 · Shen et al. ε*+. arXiv:2008.13041, 2020
- C*: A Coverage Path Planning Algorithm for Unknown Environments using Rapidly Covering Graphs. T-RO 2026, arXiv:2505.13782
- Chaplot et al. Learning to Explore using Active Neural SLAM. ICLR 2020, arXiv:2004.05155
- Ramakrishnan et al. Occupancy Anticipation for Efficient Exploration and Navigation. ECCV 2020, arXiv:2008.09285