D7 感知引导规划与自主探索——从前沿概念到覆盖路径引导¶

性质：算法工程教学 | 难度跨度：⭐⭐ ~ ⭐⭐⭐⭐ | 预计精读：20-28 小时

一句话定位：从 1997 年 Yamauchi 的贪婪前沿到 2024 年 FALCON 的覆盖路径引导，本章完整讲透无人机自主探索的三代范式演进——为什么前沿是探索的自然语言、怎样用运筹学把"去哪里"变成可解的 TSP/ATSP、以及 yaw 为什么是四旋翼独有的"免费"感知自由度。

前置自测¶

开始前先回答下面 5 个问题。答不出 2 题以上，建议先回前置章节补齐——D7 的每一层规划都建立在这些基础之上，欠了账会在第二节就卡住。

ESDF（Euclidean Signed Distance Field）的核心性质是什么？ 给定空间中任意一点 $\mathbf{p}$，ESDF 返回什么值？这个值在碰撞检测和梯度规划中分别怎么用？（答不出 → 回 D6 环境表示，§D6.2）
四旋翼的微分平坦输出是什么？ 平坦输出 $\sigma = (x, y, z, \psi)^\top$ 中，yaw 角 $\psi$ 对位置跟踪有影响吗？为什么？（答不出 → 回 D1 微分平坦，§D1.1；或本章 §D7.8 会详细展开）
B 样条曲线的局部支撑性（Local Support）意味着什么？ 修改一个控制点，曲线的哪些段会受影响？这对在线重规划有什么工程价值？（答不出 → 回 D4 B 样条轨迹优化，§D4.1）
TSP（旅行商问题）为什么是 NP-hard 的？ 对于 50 个节点的 TSP，精确求解和启发式求解的时间量级分别是多少？在线探索为什么可以接受非精确解？（答不出 → 回 Part 0 算法复杂度基础，或阅读本章 §D7.14 数学补充）
OctoMap 的体素状态有哪三种？ 概率占据模型中，$P(\text{occupied}) \approx 0.5$ 意味着什么？为什么这个状态对探索问题至关重要？（答不出 → 回 D6 环境表示，§D6.1）

参考答案要点（先自己答，再对照）：

ESDF 返回点 $\mathbf{p}$ 到最近障碍物表面的带符号距离。正值在自由空间（距障碍物越远值越大），负值在障碍物内部。碰撞检测中，$\text{ESDF}(\mathbf{p}) > d_{\text{safe}}$ 保证安全；梯度规划中，$\nabla \text{ESDF}$ 直接提供远离障碍物的梯度方向，可用于构造斥力势场。
平坦输出 $\sigma = (x, y, z, \psi)^\top$。yaw 角 $\psi$ 对位置跟踪**没有影响**。原因：推力方向由 $(\ddot{x}, \ddot{y}, \ddot{z} + g)$ 决定，推力大小 $f = m\|\mathbf{a} + g\mathbf{e}_3\|$ 均与 $\psi$ 无关。yaw 只决定绕推力方向的旋转，因此是"免费"的感知自由度。
局部支撑性：$k$ 阶 B 样条中，第 $i$ 个控制点仅影响 $k$ 个相邻曲线段。工程价值：在线重规划时只需修改局部控制点，不影响远处已执行的轨迹段，这使增量优化在计算上可行。
TSP 是 NP-hard 的，因为可以将哈密顿回路问题多项式归约到 TSP。50 个节点精确求解需要 $O(n^2 \cdot 2^n)$（Held-Karp 动态规划）$\approx 50^2 \times 2^{50} \approx 2.8 \times 10^{18}$ 次运算，不可行；启发式（LKH）仅需毫秒级。在线探索中地图每秒更新，当前的"最优"序列下一秒可能失效，因此快速近似远比慢速精确更有实际价值。
三种状态：occupied（$P > 0.5$）、free（$P < 0.5$）、unknown（$P \approx 0.5$，未被任何射线穿越）。unknown 状态对探索至关重要——前沿（Frontier）的定义就是 free 与 unknown 的边界，它标记了"已知世界的边缘"，是探索算法的基本驱动力。

本章目标¶

学完本章后，你应该能够：

**形式化定义**自主探索问题——从输入（未知环境、传感器模型）到目标（最小时间覆盖），并理解其 NP-hard 本质
**解释**探索范式的三代演进——贪婪 NBV（nbvplanner）→ 分层 TSP/ATSP（FUEL/TARE）→ 覆盖路径引导（FALCON），每代解决了前代的什么缺陷
深入理解 FUEL 的核心贡献——前沿信息结构（FIS）的增量维护机制，以及三层分层规划的完整流程
对比分析 TARE 的双分辨率原则与 FUEL 的单分辨率方案——在何种场景下各自占优
理解 RACER 的去中心化多机协同——在线分层栅格、成对竞价、CVRP 建模的完整链路
论证 yaw 作为一等决策变量的物理基础——从微分平坦的数学性质出发，而非凭直觉
追踪 FUEL 或 TARE 代码中一次完整的探索决策过程——从传感器数据到轨迹输出

本章知识导航¶

本章的知识结构是一棵以"如何让无人机自主探索未知环境"为根的树。树干是三个递进的核心问题，树枝是每个问题的技术细节和工程实现。

什么是探索？怎么形式化？(§D7.1)
    │
    ▼
怎么量化"一个视点的价值"？(§D7.2 信息增益 + NBV)
    │
    ├─→ nbvplanner: RRT + 射线投射 (§D7.2)
    │     │
    │     └─→ 局限: 贪婪短视 → 需要全局序列
    │
    ▼
怎么规划全局探索序列？(§D7.3-D7.4 FUEL/TARE)
    │
    ├─→ FUEL: 增量 FIS + LKH ATSP + DAG 局部 (§D7.3)
    │
    ├─→ TARE: 双分辨率 TSP + OR-Tools (§D7.4)
    │     │
    │     └─→ 局限: 前沿选择仍有往返 → 需要覆盖引导
    │
    ├─→ FALCON: 全局覆盖路径引导 (§D7.6)
    │
    ├─→ FC-Planner: 骨架引导覆盖 (§D7.7)
    │
    ▼
多机怎么协同？(§D7.5 RACER / §D7.9 MUI-TARE)
    │
    ├─→ RACER: 去中心化 + CVRP + 成对竞价 (§D7.5)
    │
    └─→ MUI-TARE: 未知初始位姿 + AutoMerge (§D7.9)

正交维度: 传感器朝向怎么优化？(§D7.8 感知引导)
    │
    ├─→ RAPTOR: yaw 图搜索 (§D7.8)
    │
    ├─→ PAMPC: 位置-yaw 联合 NMPC (§D7.8)
    │
    └─→ VIO 可观性约束 (§D7.8)

系统集成与工程实践 (§D7.10-D7.11)

小节	主题	难度	一句话
§D7.1	探索问题形式化与历史演进	⭐⭐	前沿 = 已知与未知的边界
§D7.2	信息增益与 NBV 范式	⭐⭐	射线投射量化视点价值，nbvplanner 建立范式
§D7.3	FUEL 的增量前沿信息结构	⭐⭐⭐	增量 FIS + LKH ATSP + DAG Dijkstra + B 样条
§D7.4	TARE 的双分辨率原则	⭐⭐⭐	近处精细 TSP + 远处粗糙 TSP + OR-Tools
§D7.5	RACER 去中心化多机协同	⭐⭐⭐	在线 hgrid + 成对竞价 + CVRP → LKH-3
§D7.6	FALCON 覆盖路径引导	⭐⭐⭐	全局覆盖路径持久引导局部前沿
§D7.7	FC-Planner 骨架引导覆盖	⭐⭐⭐	ROSA 旋转对称轴 → 子空间分解 → ATSP
§D7.8	感知引导——yaw 作为一等公民	⭐⭐⭐	微分平坦 → yaw 免费 → 图搜索/NMPC
§D7.9	多机通讯与任务分配	⭐⭐⭐⭐	运筹学建模 TSP/CVRP/MD-VRP
§D7.10	感知-规划一体化架构	⭐⭐⭐⭐	四层耦合：分离 → 弱 → 中 → 强
§D7.11	传感器模型与环境表示	⭐⭐	深度相机 vs LiDAR；OctoMap vs voxblox
§D7.12	前沿工作与开放问题	⭐⭐⭐⭐	3DGS 主动感知、LLM 引导探索

两条阅读线：

理论线（理解算法本质）：§D7.1 → §D7.2 → §D7.3 → §D7.4 → §D7.6 → §D7.8 → §D7.9，重点是数学建模和范式对比
工程线（会用就行）：§D7.1 → §D7.3 → §D7.5 → §D7.11 → §D7.13，重点是代码结构和系统集成

无论哪条线，§D7.1 和 §D7.2 都是必读——它们是所有后续内容的地基。

前置知识桥接¶

回顾 D6（环境表示）：D6 建立了无人机感知环境的两种核心数据结构——TSDF（截断带符号距离场）用于表面重建，ESDF（欧几里得带符号距离场）用于规划。ESDF 的核心性质是：对空间中任意一点 $\mathbf{p}$，$\text{ESDF}(\mathbf{p})$ 返回到最近障碍物表面的带符号距离。在本章中，ESDF 会被用于三个地方：（1）前沿检测——free 体素（$\text{ESDF} > 0$）与 unknown 体素的边界就是前沿；（2）碰撞检测——候选视点必须满足 $\text{ESDF}(\mathbf{p}) > d_{\text{safe}}$；（3）路径规划——A* 搜索在 ESDF 栅格上进行。

回顾 D4（B 样条轨迹优化）：D4 讲了 B 样条的数学基础和优化方法。FUEL 和 RACER 的轨迹后端都是最小时 B 样条——用 NLopt 优化控制点，代价函数包含平滑性、碰撞惩罚、动力学约束和总时间。B 样条的局部支撑性在这里至关重要：探索中轨迹需要频繁重规划（地图更新 → 新前沿 → 新目标），局部修改已有轨迹比从头重算效率高得多。

回顾 D5（MINCO/安全走廊）：FALCON 和 RACER 的最新版本使用 MINCO 轨迹表示。MINCO 将轨迹参数化为端点导数，约束通过安全走廊自然满足。如果你在 D5 学的 MINCO 公式化，在 FALCON 的轨迹层会直接用上。

前向预告：本章聚焦"去哪里"（探索策略）和"看哪里"（yaw 规划），假设底层的轨迹优化和控制已经解决。后续章节的 D8 将讨论更高层的任务规划（多任务调度、任务分解），可以视为探索策略的上层抽象。现在只需要知道：探索是无人机自主系统中"策略层"的核心问题，它的输入是地图和传感器模型，输出是视点序列和轨迹。

科研发展脉络¶

在钻进具体方法前，先把这条研究线的来龙去脉理清——知道每个方法"从哪来、解决了前人什么痛点、又留下什么给后人"，比孤立地记名字有用得多。

年份	论文	Venue	核心贡献
1997	Yamauchi, "A Frontier-based Approach for Autonomous Exploration"	CIRA	前沿概念鼻祖：已知空间与未知空间的边界 → 贪婪最近前沿
2016	Bircher 等 (ETH ASL), "Receding Horizon NBV Planner for 3D Exploration"	ICRA / AR 2018	nbvplanner：RRT + 视锥射线投射信息增益；OctoMap 后端
2020	Schmid 等 (ETH ASL), "An Efficient Sampling-Based Method for Online Informative Path Planning"	RA-L	mav_active_3d_planning：持久化 RRT* + voxblox；虚函数插件架构——学术代码中最干净的 Factory/Strategy 设计
2021	Cao, Zhu, Choset, Zhang (CMU), "TARE: A Hierarchical Framework for Efficiently Exploring Complex 3D Environments"	RSS Best Paper + Best System Paper	双分辨率：局部精细 TSP + 全局粗糙 TSP；OR-Tools；Science Robotics 2023 扩展；DARPA SubT 实战
2021	Zhou, Zhang, Chen, Shen (HKUST), "FUEL: Fast UAV Exploration Using Incremental Frontier Structure and Hierarchical Planning"	RA-L	增量前沿信息结构（FIS）：PCA 包围盒 + 候选视点 + A* 代价缓存；LKH ATSP 全局序列
2021	Zhou, Pan, Gao, Shen (HKUST), "RAPTOR: Robust and Perception-aware Trajectory Replanning"	TRO	yaw 图搜索：离散 yaw 采样 + 信息增益 + yaw 率平滑；拓扑路径引导
2023	Zhou, Xu, Shen (SYSU STAR), "RACER: Rapid Collaborative Exploration With a Decentralized Multi-UAV System"	TRO Best Paper	去中心化多机：在线分层栅格 + CVRP + LKH-3；异步成对协商
2024	Feng 等 (HKUST), "FC-Planner: A Skeleton-guided Planning Framework for Fast Aerial Coverage"	ICRA Best UAV Paper Finalist	骨架引导覆盖：ROSA 旋转对称轴 → 子空间分解 → Set-Cover 视点 → ATSP
2024	Zhang, Chen 等 (HKUST), "FALCON: Fast Autonomous Aerial Exploration Using Coverage Path Guidance"	TRO	覆盖路径引导 > 前沿选择：全局覆盖路径持久引导局部前沿访问；EPEE 基准

关键实验室脉络：UPenn KumarRobotics → MIT ACL → ETH ASL（nbvplanner/mav_active_3d_planning）→ CMU RI（TARE/MUI-TARE，DARPA SubT 实战验证）→ HKUST（FUEL/RAPTOR/RACER/FALCON，从单机到多机的完整方案）→ SYSU STAR（RACER 去中心化）。

本质洞察：纵观整条研究线，有一条清晰的主线：探索决策从"贪婪单步"走向"全局序列"，再走向"持久覆盖路径"。每一步都在扩大规划时域——nbvplanner 只看一步，FUEL 看全部前沿但每次重算，FALCON 维持一条跨越整个未探索空间的持久路径。规划时域越长，移动效率越高，但计算负担也越重——这正是推动三代方法演进的核心张力。

如果跳过本章会怎样¶

跳过 D7，你会卡在两个具体的地方。

场景一："探索太慢，效率不到理论值的 1/3。" 你让四旋翼在一个 $50 \times 50 \times 3$ m 的室内环境中自主建图。你用最朴素的策略——每帧检测所有前沿体素，选最近的前沿飞过去。结果：无人机在相邻房间之间来回往返（ping-pong effect），反复穿越已建图区域，200 秒只覆盖了 60%。而 FUEL 用 LKH 求解 ATSP 全局序列 + DAG 局部视点精修，同样的场景只需 80 秒就覆盖 95%。根本原因是你没有全局序列优化——贪婪最近前沿在"视野边缘刚发现新前沿"时会立刻切换目标，导致已规划的路径被频繁打断。

场景二："无人机撞墙了，因为飞进了白墙区域 VIO 丢了。" 你的探索系统只优化"去哪里"，yaw 跟随速度方向。飞行中无人机转弯进入一段白墙走廊——深度相机看到的全是无纹理白墙，VIO 特征点骤降到 5 个以下，状态估计发散，位置跳变 2 米，撞上墙壁。没有 D7 的 yaw 规划（RAPTOR 的图搜索或 PAMPC 的感知代价），你不知道如何在规划层面约束传感器朝向，让相机始终看到足够的纹理特征。

预计阅读时间¶

模式	时长	适合
精读	20-28 小时	第一次系统学无人机探索：逐节读动机 → 算法 → 代码走读，做完每节练习。建议分 7-8 次，每次 3 小时。
速读	5-7 小时	有探索基础、想建立全局图景：读每节的"动机"和关键算法流程、§D7.3 FUEL 和 §D7.8 yaw 规划，跳过代码细节。
速查	30-60 分钟	已学过、回来查特定算法：直接定位到对应小节，看算法流程图 + 参数表 + API 速查。

D7.1 探索问题的形式化定义与历史演进 ⭐⭐¶

动机——无人机为什么需要"自己决定去哪里"¶

想象你是一个消防员，接到报警后进入一栋完全黑暗、布局未知的建筑。你只有一个手电筒（视野有限），需要尽快搜索所有房间寻找被困人员。你怎么做？

你不会站在门口随机选一个方向走——你会系统地扫描周围，发现哪个方向有未检查的空间，优先去那个方向，同时在脑中记住"哪些地方还没去过"。这正是自主探索的本质：在信息不完全的情况下，实时决策"下一步去哪里"，使得累积的信息收益最大化。

对无人机而言，这个问题更具挑战性。消防员可以慢慢走、随时停下来思考；无人机以 2 m/s 的速度飞行，每秒需要做出新的决策，而且电池只有 15 分钟。如果决策效率低——比如在两个房间之间来回飞——宝贵的电量就浪费在无信息增益的移动上。

读到这里你可能会问："为什么不先用一个传感器（比如 LiDAR）全局扫一遍得到粗略地图，再规划路径？"答案是：对于很多应用场景（搜救、未知建筑巡检、行星表面探测），根本没有"先看一遍"的机会——环境是完全先验未知的。即使有粗略先验，真实环境的细节（门是否打开、走廊是否被堵）只有飞进去才知道。因此探索系统必须在"边飞边建图"的过程中做出决策。

形式化定义 ⭐⭐¶

自主探索（Autonomous Exploration）是机器人学中的一个基本问题。下面给出严格的形式化定义，然后逐项解释每个符号的含义和设计动机。

给定:
  W ⊂ ℝ³           — 有界工作空间（先验未知）
  q₀ ∈ SE(3)       — 机器人初始位姿（位置 + 姿态）
  S: SE(3) → 2^W    — 传感器模型（位姿 → 可观测区域的映射）
  M_t: W → {free, occupied, unknown}  — 时刻 t 的地图状态

目标:
  找到轨迹 τ: [0,T] → SE(3)，使得:
    min T                                      ← 最小化探索总时间
    s.t. |{w ∈ W : M_T(w) = unknown}| → 0     ← 未知体积趋近于零
         τ(t) ∈ C_free(M_t)  ∀t               ← 轨迹始终无碰撞
         ‖a(t)‖ ≤ a_max, ‖v(t)‖ ≤ v_max      ← 动力学约束

为什么这个问题如此困难？ 这个看似简单的定义隐藏了四个根本性困难：

困难	本质原因	后果
信息不完全	地图 $M_t$ 随探索逐渐揭示，$t$ 时刻无法知道 $t+1$ 时刻的地图	不可能做全局最优规划，只能做在线滚动决策
NP-hard 子问题	即使知道所有前沿/视点的位置，最优访问顺序是 TSP/ATSP	精确求解不可行，必须用启发式近似
在线实时性	无人机以 2 m/s 飞行，必须在飞行中（毫秒级）做出决策	计算预算极其有限，不能离线跑优化器
感知-规划耦合	传感器朝向（yaw）影响观测范围，进而影响地图更新	规划必须同时决定"去哪里"和"看哪里"

本质洞察：探索问题本质上是一个**序贯决策问题**——每一步的决策影响未来的信息状态，而未来的信息状态又影响后续决策的质量。这与强化学习的 MDP 框架高度相似。但与 MDP 不同的是，探索的状态空间（$M_t$ 的所有可能地图配置）是天文数字级别的——一个 $50 \times 50 \times 3$ m、分辨率 0.1 m 的体素栅格有 $7.5 \times 10^6$ 个体素，每个有 3 种状态，总共 $3^{7.5 \times 10^6}$ 种可能的地图配置。因此所有实际可行的方法都在做某种形式的近似——这正是三代范式演进的驱动力。

从 2D 到 3D：Yamauchi 前沿方法的开创性工作 ⭐⭐¶

1997 年，Brian Yamauchi 在 CIRA 会议上发表了开创性的论文 "A Frontier-based Approach for Autonomous Exploration"，首次提出了**前沿（Frontier）**的概念。这个概念的深远影响怎么强调都不过分——此后 27 年的所有探索工作都可以视为对前沿概念的扩展和改进。

前沿：已知自由空间与未知空间之间的边界单元。

前沿概念的天才之处在于它的**简洁性**：它把"去哪里探索"这个看似无穷选项的问题压缩为"去哪个前沿"这个有限选项的问题。任何真正的新信息只能在前沿处获得——已知区域已经建图（无新信息），被障碍物包围的区域不可达（无法获取信息），只有前沿处的观测既可达又有信息增益。

┌────────────────────────────────────────────────────┐
│                                                    │
│   ██████████  occupied (障碍物)                     │
│   ░░░░░░░░░░  unknown (未探索)                     │
│   ··········  free (已知自由)                       │
│   ▓▓▓▓▓▓▓▓▓▓  FRONTIER (前沿 = free ∩ 邻接 unknown)│
│                                                    │
│   ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░   │
│   ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░   │
│   ░░░░░░░░░░▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓░░░░░░░░░░░░░   │
│   ░░░░░░░░░░▓····················▓░░░░░░░░░░░░░   │
│   ░░░░░░░░░░▓····················▓░░░░░░░░░░░░░   │
│   ░░░░░░████▓····· R ············▓████░░░░░░░░░   │
│   ░░░░░░████▓····················▓████░░░░░░░░░   │
│   ░░░░░░░░░░▓····················▓░░░░░░░░░░░░░   │
│   ░░░░░░░░░░▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓░░░░░░░░░░░░░   │
│   ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░   │
│   ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░   │
│                                                    │
└────────────────────────────────────────────────────┘
        R = 机器人当前位置

**Yamauchi 的贪婪策略**非常简单：检测所有前沿 → 聚类 → 选最近的簇 → 导航过去 → 更新地图 → 重复。

# Yamauchi 贪婪前沿探索（1997 原始算法伪代码）
def yamauchi_exploration():
    while frontiers_exist(map):
        frontiers = detect_frontiers(map)          # 扫描所有 free-unknown 边界
        clusters  = cluster_frontiers(frontiers)   # 连通分量聚类
        target    = nearest_cluster(robot_pos, clusters)  # 贪婪选最近
        path      = plan_path(robot_pos, target.centroid)  # A* 或 Dijkstra
        execute(path)
        update_map(sensor_data)

如果不用前沿概念会怎样？ 在 Yamauchi 之前，探索方法主要是"随机行走"或"信息论方法"（在整个空间上计算信息熵梯度）。随机行走效率极低——在一个有 10 个房间的环境中，随机行走可能反复在同一个房间打转。信息论方法虽然有理论保证，但计算复杂度极高——需要对整个空间的每个体素计算信息熵变化。前沿概念的引入将搜索空间从"整个环境"压缩到"前沿边界"——前沿体素通常只占总体素数的不到 1%，这是效率飞跃的根本原因。

原始实验平台：Nomad 200 移动机器人，配备激光雷达、16 个超声波传感器和 16 个红外传感器。注意这是 2D 地面机器人，Yamauchi 的原始算法只处理 2D 栅格地图。

从 2D 到 3D 的扩展：将前沿概念扩展到 3D 面临几个关键挑战：

3D 前沿体素的定义:
  v 是前沿体素 ⟺ M(v) = free ∧ ∃v' ∈ N₂₆(v) : M(v') = unknown

其中 N₂₆(v) 是 v 的 26-连通邻域（3×3×3 立方体去中心）

与 2D 相比，3D 前沿的体素数量大幅增加（从线段变为曲面），前沿聚类从 2D 连通分量变为 3D 连通分量，信息增益计算从 2D 扇形扫描变为 3D 视锥射线投射。这些变化使得"全图扫描前沿 + 全量射线投射"在大场景下变得不可行——正是这个计算瓶颈驱动了后续所有工作。

局限性分析（这些局限直接催生了三代后续方法）：

局限	根本原因	直接后果	后续谁解决
来回往返（ping-pong）	贪婪最近策略无全局视野	在相邻前沿间反复切换	FUEL 的 ATSP 全局序列
大前沿小前沿同等对待	没有信息增益加权	浪费时间在小缝隙前沿上	nbvplanner 的射线投射增益
没有传感器朝向优化	yaw 跟随速度方向	可能错过侧方的大片未知区域	RAPTOR 的 yaw 图搜索
3D 全量扫描太慢	$O(N_{\text{total}})$ 复杂度	大场景下帧率骤降	FUEL 的增量 FIS

探索范式的三代演进 ⭐⭐¶

纵观 1997-2024 年的发展，探索方法可以分为三代，每一代解决了前代的核心瓶颈：

第一代：贪婪 NBV（1997-2019）
├── Yamauchi 贪婪前沿（1997）          — 最近前沿，无信息增益
├── nbvplanner（Bircher 2016）        — RRT + 射线投射信息增益
├── GBP（Dang 2019, SubT）            — 图搜索 + 局部/全局增益
└── mav_active_3d_planning（2020）    — 插件化 RRT* + 可定制增益

    ↓ 解决了"看哪里有价值"，但仍是一步一贪婪
    ↓ 瓶颈: 没有全局序列 → 来回往返

第二代：分层 TSP/ATSP（2020-2023）
├── FUEL（Zhou 2021）                 — 增量 FIS + LKH ATSP + DAG 局部
├── TARE（Cao 2021）                  — 双分辨率 TSP + OR-Tools
├── RACER（Zhou 2023）                — 多机 CVRP + LKH-3 + 成对竞价
└── MUI-TARE（Yan 2023）              — 多机 MD-VRP + AutoMerge

    ↓ 解决了"访问所有前沿的最优顺序"
    ↓ 瓶颈: 前沿随时变化 → 序列频繁重算 → 来回往返仍存在

第三代：覆盖路径引导（2024-）
├── FALCON（Zhang 2024）              — 全局覆盖路径持久引导局部前沿
├── FC-Planner（Feng 2024）           — 骨架引导子空间分解 + ATSP
└── SOAR（2025）                      — 异构编队（探索者 + 摄影师）

    ↓ 解决了"全局覆盖路径的持久性"
    ↓ 前沿变化只影响局部，全局方向不变

正交维度：感知约束规划
├── RAPTOR（Zhou 2021）               — yaw 图搜索 + 信息增益
├── PAMPC（Falanga 2018）             — yaw 直接入 NMPC
└── VIO 可观性约束（2025-2026）        — 特征共视 + Fisher 信息

本质洞察：三代范式的演进本质上是**规划时域的扩展**。第一代只看当前一步（$O(1)$ 时域），第二代看全部当前前沿（$O(N_{\text{frontier}})$ 时域但每帧重算），第三代维持跨越整个未探索空间的持久覆盖路径（$O(|\mathcal{W}|)$ 时域但增量更新）。规划时域越长，移动效率越高——但只有当更新机制足够高效（增量而非全量）时，长时域才不会成为计算瓶颈。

⚠️ 常见陷阱¶

概念误区 1：前沿 = 障碍物边界

错误做法：将前沿理解为"free 与 occupied 的边界"
现象：探索算法总是贴着墙飞，从不进入开放区域
根本原因：前沿是 free 与 unknown 的边界，不是 free 与 occupied 的边界。free-occupied 边界是障碍物表面，去那里没有新信息；free-unknown 边界才是"已知世界的边缘"，那里有新信息
正确做法：v 是前沿 ⟺ M(v) = free ∧ ∃v' ∈ N(v) : M(v') = unknown

编程陷阱 2：前沿检测使用全图扫描

错误做法：每帧遍历所有 $N_{\text{total}}$ 个体素检查是否为前沿
现象：在 $50 \times 50 \times 3$ m 场景下（$7.5 \times 10^6$ 个体素），前沿检测耗时 50 ms，吃掉了整个规划的计算预算
根本原因：绝大多数体素的状态在两帧之间没有变化。全图扫描做了大量无用功
正确做法：只在地图更新区域（update bounding box）内做增量检测（FUEL 的核心思想）

思维陷阱 3：前沿越多，探索越高效

错误理解：前沿数量多说明有很多"选择"，应该更高效
现象：大场景下前沿簇数达到 100+，ATSP 求解变慢，整体效率反而下降
根本原因：前沿多意味着决策空间大（TSP 节点多），但不意味着每个前沿都值得专门飞一趟。很多小前沿（如墙角缝隙）的信息增益远不如移动代价
正确做法：过滤小前沿簇（cells < min_cluster_size），并用信息增益加权而非简单计数

练习¶

练习 D7.1.1 ⭐⭐：给定一个 $20 \times 20$ 的 2D 栅格地图（0 = free, 1 = occupied, 2 = unknown），手写 Python 代码实现：（1）前沿检测（4-邻域）；（2）前沿聚类（BFS 连通分量）；（3）贪婪最近前沿选择。不使用任何第三方库。预期代码量 ~80 行。

练习 D7.1.2 ⭐⭐：分析 Yamauchi 贪婪前沿策略在以下环境中的行为（画出机器人路径）：一条 $20 \times 3$ m 的长走廊，中间有一个 $T$ 形分叉。从 $T$ 的底部出发。贪婪策略会先探索哪个方向？在分叉处会发生什么？画出时间-覆盖体积曲线，并与"理想策略"（先完整探索一侧再探索另一侧）对比。

D7.2 信息增益与 Next-Best-View 范式 ⭐⭐¶

动机——"最近"不等于"最有价值"¶

Yamauchi 的贪婪最近前沿策略有一个根本缺陷：它只考虑距离，不考虑信息量。想象两个前沿——前沿 A 距离 3 m，只有 5 个前沿体素（一个小缝隙）；前沿 B 距离 8 m，有 500 个前沿体素（一扇开着的门后面是一整个房间）。贪婪最近策略会选 A，但显然 B 才是更好的选择。

如果不量化信息增益会怎样？ 机器人会花大量时间去探索小缝隙和墙角，而忽视大片未知区域。在实际实验中，这种行为表现为：探索初期（大片未知区域）效率还可以，但探索后期（只剩小缝隙）效率骤降——因为机器人需要逐一访问每个小缝隙，每次飞行只获得极少新信息。

这就引出了第一代探索方法的核心改进：量化每个候选视点的信息增益，在距离与增益之间做权衡。

信息增益的数学定义 ⭐⭐¶

信息增益量化了从某个视点 $\mathbf{v}$ 出发的观测能获得多少新信息。最基本的定义是体积信息增益（Volumetric Information Gain）：

\[ \text{IG}(\mathbf{v}) = |\{w \in S(\mathbf{v}) : M(w) = \text{unknown}\}| \]

其中 $\mathbf{v} \in SE(3)$ 是候选视点（位置 + 朝向），$S(\mathbf{v}) \subseteq \mathcal{W}$ 是从 $\mathbf{v}$ 出发的传感器视锥覆盖的空间。简单来说：信息增益 = 视锥内未知体素的数量。

这个定义虽然简单，但已经足够驱动有效的探索行为。更精细的变体包括：

增益度量	公式	适用场景	代表系统
加权体积增益	$\text{IG}_w = \sum_{w \in S(\mathbf{v})} \frac{1}{\\|\mathbf{w}-\mathbf{v}\\|^2} \cdot \mathbb{1}[M(w) = \text{unknown}]$	重视近处体素	nbvplanner
熵减少	$\text{IG}_H = H(M) - H(M	z_\mathbf{v}) = \sum_{w} [H(P(w)) - H(P(w	z_\mathbf{v}))]$
表面前沿增益	$\text{IG}_{\text{surf}} =	{w \in S(\mathbf{v}) : w \in \partial(\text{free} \cap \text{unknown}) \wedge w \text{ 靠近表面}}	$

读到这里你可能会问："熵减少和体积增益有什么区别？"关键区别在于：体积增益把所有 unknown 体素同等对待，而熵减少还考虑了体素的**不确定程度**——一个 $P(\text{occupied}) = 0.5$ 的体素（完全不确定）比一个 $P(\text{occupied}) = 0.45$ 的体素（略微倾向 free）有更高的熵。在实践中，体积增益因为计算简单而被广泛使用，熵减少在理论上更优但计算更贵。

射线投射计算信息增益 ⭐⭐¶

信息增益的计算核心是**射线投射（Ray Casting）**——模拟传感器的观测过程。对于相机传感器，射线在视锥内均匀采样，每条射线沿视线方向步进，统计遇到的未知体素数。

def compute_gain(viewpoint, map, sensor_model):
    """
    viewpoint: (位置 p, 朝向 R) ∈ SE(3)
    map: OctoMap/voxblox 体素地图
    sensor_model: 相机/LiDAR 参数（FOV, 范围, 分辨率）
    """
    gain = 0

    # 对视锥中的每条射线
    for ray in sensor_model.generate_rays(viewpoint):
        # 沿射线步进（DDA 算法或 Bresenham 3D）
        t = 0
        while t < sensor_model.max_range:
            voxel = map.get_voxel(ray.origin + t * ray.direction)

            if voxel.state == OCCUPIED:
                break              # 射线被遮挡，停止
            elif voxel.state == UNKNOWN:
                gain += 1          # 发现未知体素
                break              # 一般实现遇到第一个 unknown 就停止
            # else: FREE，继续步进

            t += map.resolution

    return gain

计算开销分析：射线投射是探索中最耗时的操作之一。nbvplanner 对每个 RRT 节点做约 768 条射线（$32 \times 24$）的投射，每条射线步进约 100 步，每个节点约 76,800 次体素查询。当 RRT 有 1000 个节点时，总共需要约 7680 万次查询——这解释了为什么 nbvplanner 在大场景下变慢。

优化手段：

优化策略	做法	加速比	代价
稀疏射线采样	减少射线数（$16 \times 12 = 192$ 条）	4x	精度降低
自适应步长	在 ESDF 中按距离场步进（sphere tracing）	3-10x	需要 ESDF
增量更新	只对地图变化区域重新计算	10-100x	实现复杂
GPU 加速	并行射线投射（OctoMap-RT）	41x	需要 GPU
近似估计	用前沿体素数近似信息增益	100x+	精度最低

nbvplanner——经典 NBV 方法的代表 ⭐⭐¶

nbvplanner（Bircher 等, ETH ASL, ICRA 2016） 建立了"RRT + 信息增益 + 滚动时域"的范式，是第一代探索方法的标杆。

为什么用 RRT 而不是均匀采样视点？ 均匀采样在 3D 空间中效率极低——$50 \times 50 \times 3$ m 空间按 1 m 间隔采样就有 7500 个视点，每个都要做射线投射。RRT 的优势在于：（1）采样密度自适应——自由空间大的地方 RRT 自然探索更多；（2）天然形成树结构——回溯到根节点的路径就是一条可行轨迹；（3）增量构建——可以随时中断返回当前最佳。

算法流程：

nbvplanner 主循环:

while not exploration_complete:
    # 1. 在当前位置的局部空间中生长 RRT
    tree = RRT()
    tree.root = current_pose

    for i in range(N_samples):                  # 典型 N_samples = 2000
        q_rand = sample_free_space()            # 在已知自由空间中采样
        q_near = tree.nearest(q_rand)           # 最近节点
        q_new  = steer(q_near, q_rand, delta)   # 步长限制的扩展

        if collision_free(q_near, q_new, map):
            tree.add_edge(q_near, q_new)
            q_new.gain = ray_cast_gain(q_new, map)  # 射线投射信息增益

    # 2. 选择最佳分支（增益/代价比最高的叶到根路径）
    best_branch = argmax_{leaf} [sum(gain) / sum(edge_length)]

    # 3. 只执行最佳分支的第一条边（滚动时域）
    execute_motion(best_branch[0], best_branch[1])
    update_map(sensor_data)

nbvplanner 的核心参数：

# nbvplanner 典型参数
nbvp:
  tree/extension_range: 1.0        # 每步最大扩展距离 (m)
  tree/number_of_iterations: 2000  # 每次规划的 RRT 采样数
  sensor/horizontal_fov: 90.0      # 水平视场角 (度)
  sensor/vertical_fov: 60.0        # 垂直视场角 (度)
  sensor/r_max: 5.0                # 最大感知距离 (m)
  sensor/n_horizontal: 32          # 水平射线数
  sensor/n_vertical: 24            # 垂直射线数
  gain/unmapped: 1.0               # unknown 体素的增益权重
  resolution: 0.2                  # 体素分辨率 (m)

nbvplanner 的四大局限（这些局限直接催生了第二代方法）：

贪婪短视：每次只看当前 RRT 的一步前瞻，没有全局序列优化。结果：在多个高增益前沿之间无序跳转
重复采样：RRT 每次从头构建，不复用历史树——大量已有的好节点被丢弃。mav_active_3d_planning 用持久化 RRT* 部分解决了这个问题
无 yaw 优化：yaw 跟随速度方向，不考虑信息增益。深度相机 FOV 只有 $90^\circ$，不优化 yaw 可能错过 $270^\circ$ 范围内的信息
OctoMap 瓶颈：大场景下 OctoMap 的 $O(\log N)$ 查询成为瓶颈

mav_active_3d_planning——学术代码中最干净的插件架构 ⭐⭐⭐¶

mav_active_3d_planning（Schmid 等, ETH ASL, RA-L 2020） 在 nbvplanner 基础上做了两个关键改进：持久化 RRT*（不丢弃历史树）和模块化插件架构（虚函数 + 工厂模式）。

为什么要专门讲它的架构？ 绝大多数学术代码是"一次性意大利面条"——函数之间紧耦合、参数硬编码、想换一个模块就要改三个文件。mav_active_3d_planning 投入了大量精力做软件工程，它的 Factory/Strategy 设计值得每个做无人机研究的工程师学习。

插件架构的类层次：

PlannerI (顶层接口)
├── TrajectoryGenerator (轨迹生成)
│   ├── RRTStar              — 持久化 RRT* 采样
│   ├── SegmentGenerator      — 直线段生成
│   └── RandomLinear          — 随机直线
│
├── TrajectoryEvaluator (轨迹评估)
│   ├── FrontierEvaluator     — 基于前沿的评估
│   ├── NaiveEvaluator        — 简单射线投射
│   └── VoxelWeightEvaluator  — 加权体素评估
│
├── SensorModel (传感器模型)
│   ├── CameraModel           — 针孔相机视锥
│   └── LidarModel            — 激光雷达模型
│
├── CostComputer (代价计算)
│   ├── SegmentTime           — 轨迹段飞行时间
│   └── EuclideanDist         — 欧氏距离
│
├── ValueComputer (价值计算 = gain - λ·cost)
│   ├── LinearValue           — 线性组合
│   └── RelativeGain          — gain/cost 比值
│
└── NextSelector (下一步选择)
    ├── SubsequentBest        — 累积最佳
    └── ImmediateBest         — 即时最佳

这个架构的工程价值在于：你只需要替换一个模块（比如换一个新的 SensorModel），其他所有模块原封不动。这正是 Strategy 模式的教科书应用。

阶段小结：到这里我们完成了第一代 NBV 方法的梳理。核心收获：（1）前沿是探索的基本驱动力；（2）信息增益量化了视点价值；（3）射线投射是增益计算的核心；（4）RRT 提供了可行的采样策略。但第一代方法的根本局限是**没有全局序列优化**——下一节的 FUEL 正是为此而来。

⚠️ 常见陷阱¶

编程陷阱 1：射线投射步长用固定值

错误做法：t += 0.1 固定步长步进
现象：在大场景（$r_{\max} = 20$ m）下，每条射线步进 200 步，计算极慢
根本原因：固定步长没有利用 ESDF 的距离信息。如果当前点距障碍物 5 m，完全可以安全步进 5 m
正确做法：使用 ESDF 做 sphere tracing：t += max(ESDF(current_point), min_step)。在远离障碍物的自由空间中，步长可以很大

概念误区 2：信息增益只看 unknown 体素数量

错误理解：两个视点看到同样多的 unknown 体素，信息增益就一样
正确理解：还要考虑（1）距离衰减——远处的 unknown 体素可能在实际观测时因为距离超过传感器范围而看不到；（2）遮挡——前面有障碍物时后面的 unknown 体素看不到；（3）分辨率——远处体素在图像中只占几个像素，深度估计精度低

练习¶

练习 D7.2.1 ⭐⭐：在 §D7.1 练习 1 的 2D 栅格地图基础上，实现射线投射信息增益计算。假设传感器模型为 2D LiDAR（$360^\circ$ FOV，最大距离 5 个格子，36 条射线等间隔分布）。对地图中每个 free 体素计算信息增益，用热力图可视化。

练习 D7.2.2 ⭐⭐⭐：对比 nbvplanner 和 Yamauchi 贪婪策略在 $T$ 形走廊环境中的行为。用你实现的 2D 探索器模拟：（1）Yamauchi 选最近前沿；（2）nbvplanner 式策略——采样 100 个随机 free 格子，计算每个的信息增益，选增益/距离比最高的。画出两种策略的时间-覆盖曲线。

D7.3 前沿信息结构——FUEL 的核心贡献 ⭐⭐⭐¶

动机——为什么 nbvplanner 不够快¶

nbvplanner 的效率瓶颈在于三个"每帧从零开始"：每帧从零构建 RRT、每帧从零做射线投射、每帧从零选下一步。这种"无记忆"的设计浪费了大量历史信息——上一帧发现的前沿、计算过的增益、搜索过的路径，下一帧全部丢弃。

FUEL 的核心洞察：前沿信息不应该每帧重建，而应该**增量维护**。地图的变化是局部的（每帧只更新传感器覆盖范围内的体素），前沿的变化也应该是局部的——只有地图变化区域附近的前沿需要更新。

这个洞察的工程价值是巨大的。FUEL 的论文中报告了 3-8 倍的加速——不是靠更好的硬件或更快的算法，而是靠**避免重复计算**。

如果不用增量更新会怎样¶

考虑一个 $50 \times 50 \times 3$ m 的室内环境，体素分辨率 0.1 m：

操作	全量方法（每帧）	FUEL 增量方法	加速
前沿检测	扫描全部 $7.5 \times 10^6$ 体素	只扫描更新区域 ~$10^4$ 体素	750x
射线投射	所有 RRT 节点（~1000 $\times$ 768 条）	只对 dirty 簇的 ~15 视点	50x
路径代价	全部簇对的 A*	只对新增/变化的簇对	10-50x

总的来说，FUEL 的计算量与**增量变化量**成正比，而非与**全图大小**成正比。这是一个从 $O(N_{\text{total}})$ 到 $O(|\Delta|)$ 的量级飞跃。

FUEL 系统架构 ⭐⭐⭐¶

FUEL（Fast UAV Exploration using Incremental Frontier Structure and Hierarchical Planning），由 Zhou, Zhang, Chen, Shen（HKUST）于 2021 年发表在 RA-L 上。

FUEL 系统总体架构:

传感器数据（深度相机/LiDAR）
    │
    ▼
┌──────────────────┐
│ 地图更新模块      │ ← ESDF/占据栅格增量更新（voxblox）
│ 输出: update_bbox │ ← 本帧地图变化的包围盒
└──────┬───────────┘
       │
       ▼
┌──────────────────────────────────────────┐
│ 前沿信息结构 (FIS) 增量维护              │
│ ┌────────────────────────────────────┐   │
│ │ 1. 前沿体素增量检测（只扫 update_bbox）│   │
│ │ 2. 连通分量增量聚类                  │   │
│ │ 3. PCA 包围盒计算（只算 dirty 簇）    │   │
│ │ 4. 候选视点生成 + 覆盖率评估          │   │
│ │ 5. A* 簇间代价预计算 + 缓存           │   │
│ └────────────────────────────────────┘   │
└──────────────┬───────────────────────────┘
               │
               ▼
┌──────────────────────────────────────────┐
│ 三层分层规划器                            │
│                                          │
│ Layer 1: 全局层                           │
│   N 个簇的最佳视点 → ATSP 代价矩阵       │
│   → LKH 求解近最优环游序列                │
│                                          │
│ Layer 2: 局部层                           │
│   5m 内每簇 15 个候选视点 → DAG            │
│   → Dijkstra 选最佳视点链                 │
│                                          │
│ Layer 3: 轨迹层                           │
│   最小时 B 样条                           │
│   NLopt 优化: 平滑 + 碰撞 + 动力学 + 时间 │
│                                          │
└──────────────┬───────────────────────────┘
               │ 位置轨迹 + yaw 轨迹
               ▼
           飞行控制器

FIS 数据结构详解 ⭐⭐⭐¶

FIS 是 FUEL 的灵魂。每个前沿簇不仅仅是一组体素坐标，而是一个**富数据结构**——携带了几何、感知、代价三方面的预计算信息。

// FUEL 前沿信息结构的核心数据类型（从源码提取并注释）

struct FrontierCluster {
    // ---- 几何信息 ----
    vector<Eigen::Vector3d> cells;         // 前沿体素的 3D 坐标集合
    Eigen::Vector3d center;                 // 质心（cells 均值）

    // ---- PCA 包围盒 ----
    Eigen::Matrix3d pca_axes;              // PCA 主轴方向（3×3 正交矩阵）
    Eigen::Vector3d pca_extents;           // 沿三个主轴的范围（半长）
    //  用途: (1) OBB-视锥相交快速剪枝
    //        (2) RViz 可视化
    //        (3) 簇分裂/合并判断
    //        (4) 法向估计（最小特征值方向）

    // ---- 候选视点 ----
    vector<ViewPoint> viewpoints;          // 按覆盖率排序的候选视点
    //  ViewPoint = {position, yaw, gain, coverage_ratio}
    //  生成方式: 在簇法向方向、距离 d_view 处均匀角度采样
    //  筛选: 位于自由空间 且 ESDF > d_safe 且 可见前沿体素 > 阈值

    // ---- 代价缓存 ----
    map<int, double> cost_to_neighbors;    // 到其他簇的 A* 最短路代价
    //  缓存策略: 首次查询时计算并存储，地图变化时失效

    // ---- 增量更新标记 ----
    bool is_dirty;                         // 地图更新区域与 PCA 包围盒相交 → dirty

    // ---- 元信息 ----
    int id;                                // 唯一标识
    int num_cells;                         // 前沿体素数量
};

为什么用 PCA 包围盒而不是轴对齐包围盒（AABB）？ 前沿簇通常是沿墙壁或地面的薄片状结构，它们的主方向不沿坐标轴。AABB 在这种情况下体积远大于实际簇的体积，导致 dirty 判断过于保守（很多不需要更新的簇被标记为 dirty）。PCA 包围盒（定向包围盒, OBB）紧密贴合簇的真实形状，减少了误标记。

增量更新机制——FUEL 效率的关键 ⭐⭐⭐¶

FUEL 的增量更新是一个精心设计的六步流水线。每一步都只处理"变化的部分"，避免全量重算：

时刻 t: 地图更新 → 返回 update_bbox (B_update)

Step 1: 前沿体素增量检测
    遍历 B_update 内的体素:
    ├── 新增前沿: 原来 unknown → 现在 free 且邻接 unknown
    ├── 删除前沿: 原来是 frontier → 现在邻域全是 free 或 occupied
    └── 复杂度: O(|B_update|) << O(N_total)

Step 2: 增量聚类
    ├── 新增前沿体素 → 查找最近已有簇
    │   距离 < d_merge → 归入    |  距离 > d_merge → 新建簇
    ├── 删除前沿体素 → 从所属簇移除
    │   簇仍连通 → OK    |  簇被分割 → BFS 重新分裂
    └── 簇太小（cells < min_cluster_size）→ 删除

Step 3: Dirty 标记
    遍历所有簇:
    ├── PCA 包围盒与 B_update 相交 → dirty = true
    └── 不相交 → dirty 不变

Step 4: PCA 重算（仅 dirty 簇）
    ├── center = mean(cells)
    ├── C = (1/N) Σ(x - center)(x - center)^T
    ├── 特征分解 C = U Λ U^T → axes, extents
    └── 过大则分裂

Step 5: 视点重生成（仅 dirty 簇）
    ├── PCA 法向方向采样 ~15 个候选
    ├── 碰撞检查: ESDF > d_safe
    ├── 射线投射评估覆盖率
    └── 按覆盖率排序保留 top-K

Step 6: 代价矩阵增量更新
    ├── 新增簇 → A* 计算到其他簇的代价
    ├── dirty 簇 → 缓存失效，需要时重算
    └── 删除簇 → 清理矩阵行/列

本质洞察：FUEL 的增量更新本质上是一个**惰性求值（Lazy Evaluation）**策略——只在需要时才重新计算，而非每帧预计算所有信息。dirty 标记是这个策略的核心机制：它把"哪些数据过时了"的判断（简单的 OBB 相交测试）和"重新计算过时数据"（昂贵的 PCA + 射线投射）分开，确保后者只在必要时执行。

三层分层规划详解 ⭐⭐⭐¶

FUEL 的规划器由三层组成，每层解决不同尺度的问题：

Layer 1：全局层——ATSP 求解前沿簇访问序列

全局层回答的问题是："我有 $N$ 个前沿簇要访问，最优顺序是什么？"

输入: N 个前沿簇，每簇有最佳视点 v_i*

Step 1: 构建 ATSP 代价矩阵
    C[i][j] = A*(v_i*, v_j*) 在 ESDF 栅格上的最短路长度
    注意: C[i][j] ≠ C[j][i]（有障碍物时路径不对称）
    → 这是 ATSP 而非 TSP 的原因

Step 2: 添加当前位置作为起点（depot）
    C[0][j] = A*(current_pos, v_j*)  对所有 j
    C[i][0] = 0                       ← 不需要返回起点
    → N+1 个节点的开放式 ATSP

Step 3: LKH 求解
    写 .par + .tsp 文件 → 调用 LKH → 读 .tour 文件
    → 得到访问序列 σ = (0, σ₁, σ₂, ..., σ_N)
    LKH 求解速度: N ≤ 50 时通常 < 10 ms

为什么是 ATSP 而不是 TSP？ 在有障碍物的环境中，从 $A$ 到 $B$ 的最短路可能和从 $B$ 到 $A$ 的不一样——因为障碍物的遮挡使得绕行方向不同。ATSP 允许代价矩阵不对称，更精确地建模了这个现实。LKH 内部使用 Jonker-Volgenant 变换将 $N$ 节点 ATSP 转为 $2N$ 节点 TSP 求解。

Layer 2：局部层——DAG 视点精修

全局层给出了簇的访问顺序，但每个簇有多个候选视点（约 15 个）。局部层在 5 m 半径内的相邻簇之间，通过 DAG（有向无环图）上的最短路选择每个簇的最佳视点。

输入: 全局序列中 5m 内的 k 个簇，每簇 ~15 个候选视点

构建 DAG:
  节点: 所有候选视点 + source(当前位置) + sink(虚拟终点)

  ┌──────────┐    ┌──────────┐    ┌──────────┐
  │ Cluster 1 │    │ Cluster 2 │    │ Cluster 3 │
  │ v₁₁ v₁₂..│ →  │ v₂₁ v₂₂..│ →  │ v₃₁ v₃₂..│
  └──────────┘    └──────────┘    └──────────┘

  边权 w(v_ia, v_jb) = λ_t · time(v_ia → v_jb)
                      - λ_g · gain(v_jb)
                      + λ_y · |yaw(v_ia) - yaw(v_jb)|

Dijkstra 最短路:
  在 DAG 上从 source 到 sink → 每簇选中一个视点
  复杂度: O(V + E) = O(k × n_vp + k² × n_vp²)

Layer 3：轨迹层——最小时 B 样条

输入: 视点序列 {v_0(当前), v_1*, v_2*, ..., v_k*}

B 样条参数化: 7 阶均匀 B 样条，控制点等间距初始化后优化

代价函数 (NLopt 优化):
  J = w_s · J_smooth     + w_c · J_collision
    + w_d · J_dynamics    + w_t · T

  J_smooth   = ∫₀^T ‖d³p/dt³‖² dt         ← 最小 jerk
  J_collision = Σ max(d_safe - ESDF(p_i), 0)²
  J_dynamics  = Σ max(‖v_i‖ - v_max, 0)² + Σ max(‖a_i‖ - a_max, 0)²

求解时间: < 20 ms（5-10 个控制点）

FUEL 代码精读路线图 ⭐⭐¶

fuel_planner/
├── exploration_manager/
│   └── src/
│       ├── fast_exploration_manager.cpp   ← ★ 三层规划调度
│       │     searchFrontiers() → computeGlobalTour() → refineLocalTour() → planTrajectory()
│       └── fast_exploration_fsm.cpp       ← 状态机: INIT→PLAN→EXEC→FINISH
│
├── active_perception/
│   └── src/
│       ├── frontier_finder.cpp            ← ★ FIS 增量维护（~600 行核心代码）
│       ├── heading_planner.cpp            ← yaw 规划
│       └── perception_utils.cpp           ← 射线投射
│
├── bspline_opt/
│   └── src/bspline_optimizer.cpp          ← B 样条代价 + 梯度
│
└── third_party/lkh_solver/               ← LKH TSP 求解器

⚠️ 常见陷阱¶

编程陷阱 1：LKH 的代价矩阵用浮点数

错误做法：直接将 A* 路径长度（浮点数）写入 .tsp 文件
现象：LKH 报错或返回垃圾结果
根本原因：LKH 只接受整数代价矩阵。浮点数会被截断
正确做法：将距离乘以 1000 后取整：cost_int = (int)(distance * 1000)

编程陷阱 2：多线程调用 LKH 文件名冲突

错误做法：所有线程写同一个 lkh.par 和 problem.tsp
现象：偶发的错误结果或文件损坏
根本原因：LKH 通过文件 I/O 通信，多线程同时读写同一文件导致竞态
正确做法：文件名加时间戳或线程 ID：problem_{thread_id}.tsp

概念误区 3：ATSP 序列一旦求出就固定不变

错误理解：全局序列算一次就够了
正确理解：每次前沿更新后都要重算。地图变化导致前沿簇增/删/变形，代价矩阵也随之变化。FUEL 的策略是在每个规划周期（约 0.5-1 秒）重新求解 ATSP。好在 LKH 对 $N < 50$ 只需毫秒级

练习¶

练习 D7.3.1 ⭐⭐⭐：在 FUEL 的 GitHub 仓库中，精读 frontier_finder.cpp 的 searchFrontiers() 函数。画出数据流图：哪些数据结构被哪些函数读/写。特别关注 is_dirty 标记的触发和消费。

练习 D7.3.2 ⭐⭐⭐：手动构造一个 5 节点 ATSP 的代价矩阵（$5 \times 5$，不对称），用贪婪最近邻求解和 2-opt 改进。对比两者的环游长度。然后计算精确最优解（枚举 $4! = 24$ 种排列）。贪婪和 2-opt 分别偏离最优多少？

D7.4 TARE——分辨率粒度原则 ⭐⭐⭐¶

动机——远处不需要精确¶

FUEL 对所有前沿簇一视同仁——不管簇在 5 m 外还是 50 m 外，都用同样的精度做视点生成和代价计算。但在实际探索中，远处的前沿在无人机飞到附近之前，其精确形状和最佳视点是**无关紧要的**——因为在飞行过程中地图会不断更新，远处前沿的信息会大幅变化。

**TARE（Cao, Zhu, Choset, Zhang, CMU, RSS 2021）**的核心洞察简单而深刻：

远处只需知道"那边有未探索空间"，不需要精确的视点规划；近处才需要精细的传感器覆盖路径。

这个洞察获得了 RSS 2021 的 Best Paper Award 和 Best System Paper Award（同一篇论文同时获得两个奖项，这在 RSS 历史上是第一次）。更值得一提的是，TARE 被 CMU-OSU 团队用于 DARPA Subterranean Challenge 决赛（Louisville Mega Cavern），团队的机器人在全部参赛队伍中完成了最完整的探索（28 个区域中探索了 26 个），赢得了"Most Sectors Explored Award"。

双分辨率框架 ⭐⭐⭐¶

TARE 双分辨率框架:

  全局层（Global Level）
  ┌───────────────────────────────────────────────┐
  │ 空间分解: 整个工作空间 → 大栅格(如 40m × 40m)   │
  │ 每格一个节点: 中心点 + 估计的未探索体积         │
  │ 构建图: 节点间的路网距离(A* 在 roadmap 上)     │
  │ 求解: 粗糙 TSP (OR-Tools)                     │
  │ 输出: 大尺度的探索方向序列                     │
  └───────────────────────────────────────────────┘
            ↕ 在边界点耦合
  局部层（Local Level）
  ┌───────────────────────────────────────────────┐
  │ 精细分解: 机器人周围(如 40m 半径) → 小栅格(~5m) │
  │ 每格精细: 表面覆盖视点 + 精确信息增益            │
  │ 构建图: 视点间的精确路径距离                    │
  │ 求解: 精细 TSP (OR-Tools)                     │
  │ 输出: 局部的探索路径                           │
  └───────────────────────────────────────────────┘

类比（有边界）：这像是你规划一次跨国旅行。全局层决定"先去法国，再去德国，最后去瑞士"（国家级粒度），局部层决定"在巴黎先去卢浮宫，再去埃菲尔铁塔"（景点级粒度）。你不需要在出发前就规划好卢浮宫里每幅画的观看顺序——那个等到了巴黎再决定。但这个类比的边界是：旅行中各国不会"消失"或"改变形状"，而探索中前沿会随时变化。

TARE vs FUEL：关键差异对比 ⭐⭐⭐¶

维度	FUEL	TARE
前沿表示	增量 FIS（PCA 包围盒）	子空间未探索体积
全局求解	LKH 解 ATSP	OR-Tools 解 TSP
局部求解	DAG + Dijkstra	OR-Tools 解精细 TSP
分辨率	单分辨率（前沿簇粒度）	双分辨率（近细远粗）
增量更新	FIS 增量维护	子空间增量更新
适合场景	中小规模室内	大规模室内外通用
传感器	深度相机为主	LiDAR 为主
轨迹后端	B 样条 + NLopt	路径跟踪
TSP 规模	~50 节点（前沿簇数）	~20 粗 + ~30 细
退化场景	前沿簇数爆炸 → ATSP 变慢	粗糙层精度不够 → 方向判断错误
实战验证	仿真 + 小型室内真机	DARPA SubT 决赛

本质洞察：FUEL 和 TARE 的哲学差异在于"信息在哪里精细"。FUEL 在**前沿簇**上精细——每个簇有 15 个候选视点、PCA 包围盒、覆盖率评估。TARE 在**空间**上分层精细——近处空间精细、远处空间粗糙。哪种更好取决于场景：小型室内环境中前沿簇数有限，FUEL 的精细前沿信息价值高；大型室内外环境中前沿数量爆炸，TARE 的分辨率粒度原则更好地控制了计算预算。

TARE 提供的标准化仿真基准 ⭐⭐¶

TARE 的附属贡献是提供了 Autonomous Exploration Development Environment——一套包含 6 个标准场景的仿真基准，后来成为该领域事实上的标准测试平台：

场景	尺寸	特点	测试重点
Campus	340m $\times$ 340m	起伏地形 + 复杂布局	全局方向规划
Indoor Corridors	130m $\times$ 100m	长窄走廊 + 大厅	狭窄空间导航
Multi-story Garage	140m $\times$ 130m, 5 层	多层 + 斜坡	3D 跨层规划
Tunnel Network	330m $\times$ 250m	分叉 + 死胡同	拓扑探索、回溯
Forest	150m $\times$ 150m	树木 + 房屋	杂乱避障
Matterport3D	真实室内扫描	多房间 + 家具	真实感室内

⚠️ 常见陷阱¶

概念误区 1：TARE 的"粗糙层"是低精度地图

错误理解：粗糙层使用低分辨率体素地图
正确理解：粗糙层的"粗糙"指的是**决策粒度**（大栅格级别的未探索体积估计），不是**地图分辨率**。底层地图分辨率始终一致
正确做法：理解"粗糙"是决策空间的分辨率，不是感知空间的分辨率

思维陷阱 2：双分辨率一定优于单分辨率

错误推论：既然 TARE 获得了 RSS Best Paper，双分辨率一定全面优于 FUEL 的单分辨率
实际情况：在小型室内环境（如 $10 \times 10$ m 单间）中，前沿簇数只有 5-10 个，FUEL 的精细前沿信息反而更有价值；TARE 的全局粗糙层在这种小场景中几乎退化为单层
正确思维：没有银弹。选择方法时要考虑场景尺度、传感器类型和计算预算

练习¶

练习 D7.4.1 ⭐⭐：安装 TARE 的 Autonomous Exploration Development Environment，在 Indoor Corridors 场景中分别运行 TARE 和你自己实现的贪婪最近前沿策略。记录时间-覆盖体积曲线并对比。

练习 D7.4.2 ⭐⭐⭐：设计一个"TARE 优于 FUEL"的场景和一个"FUEL 优于 TARE"的场景。用文字描述场景特征并分析原因。提示：考虑场景尺度、前沿数量、障碍物密度。

D7.5 RACER——去中心化多机协同 ⭐⭐⭐¶

动机——多机并行的理论与现实¶

单机探索的效率受限于单台机器人的传感器覆盖速度。$N$ 台机器人并行工作，理论上可以将探索时间缩短为 $1/N$。但多机协同引入了三个新的核心挑战：

挑战	本质	如果不解决
任务分配	如何将未探索空间分给 $N$ 台？	多机重复覆盖同一区域，$N$ 倍加速退化为 1.5 倍
通信约束	不一定能随时通信	集中式方案需要全连接——不可扩展
地图融合	不同机器人的局部地图如何合并？	无法做全局任务分配

RACER（Zhou, Xu, Shen, SYSU STAR, TRO 2023 Best Paper） 用运筹学方法系统性地解决了这三个挑战。

系统架构 ⭐⭐⭐¶

RACER 系统架构（每台 UAV 运行相同的软件栈）:

┌──────────────────────────────────────────────────┐
│                   UAV_i                           │
│                                                  │
│  传感器+SLAM → 在线分层栅格 (hgrid_i)             │
│                 ├── L0: 1m 细栅格                 │
│                 ├── L1: 4m 中栅格                 │
│                 └── L2: 16m 粗栅格                │
│                        │                         │
│  成对交互模块 ←─────────┤                         │
│  ├── 与 UAV_j 交换 hgrid 差分                     │
│  ├── 检测目标区域重叠                              │
│  └── 竞价: ID 小的优先保留                         │
│                        │                         │
│  CVRP 任务分配 ←────────┤                         │
│  ├── 分配到的栅格 → CVRP                          │
│  ├── 容量约束: 子路线覆盖时间 < T_max              │
│  └── LKH-3 求解                                  │
│                        │                         │
│  分层局部规划 ←──────────┘                         │
│  └── 全局序列 → 局部视点 → B 样条                  │
└──────────────────────────────────────────────────┘
                    │ 异步通信
              其他 UAV_j

成对交互协议——去中心化的关键 ⭐⭐⭐¶

为什么不用集中式协调？ 集中式方案需要一个中央服务器收集所有机器人的地图、做全局分配、再广播给每台机器人。问题：（1）中央服务器是单点故障；（2）需要全连接通信；（3）不可扩展——$N$ 台机器人的通信量为 $O(N)$（每台都要和中心通信）。

RACER 的去中心化方案只需要**成对通信**——两台 UAV 在通信范围内相遇时交换信息并协商。关键性质：异步、去中心化、最终一致、容错。

RACER 成对交互协议:

触发: UAV_i 和 UAV_j 进入通信范围

Step 1: 差分交换
    UAV_i ↔ UAV_j: 只发送自上次交互以来变化的栅格
    通信量: O(Δ) 而非 O(N_total)

Step 2: hgrid 合并
    对每个栅格 g: 取更新时间较晚的状态
    → 保证单调进展（信息只增不减）

Step 3: 竞价（重叠区域分配）
    if 目标栅格重叠:
        ID 小的保留，ID 大的让出 → 重新分配
    → 简单确定性规则，无需拍卖

Step 4: 各自重规划
    基于更新后的 hgrid → 重新求解 CVRP

CVRP 建模与 LKH-3 求解 ⭐⭐⭐¶

RACER 将多机探索建模为 CVRP（Capacitated Vehicle Routing Problem，带容量约束的车辆路由问题）：

探索概念	CVRP 对应
UAV 当前位置	仓库（depot）
被分配的未探索栅格	客户（customer）
预期覆盖飞行时间	需求（demand）
单次子路线最大飞行时间	容量（capacity）
栅格间路径距离	边权（distance）

LKH-3 是 LKH 的扩展版本，原生支持 CVRP。调用方式与 LKH 类似（文件 I/O + 子进程），但输入文件格式包含 CAPACITY 和 DEMAND 字段。

RACER 实验结果 ⭐⭐¶

仿真实验（50m × 50m × 3m 室内）:
  1 UAV: ~250s | 2 UAV: ~140s (1.79x) | 3 UAV: ~100s (2.50x)
  4 UAV: ~80s (3.13x) | 5 UAV: ~70s (3.57x)

真实实验:
  3 台微型四旋翼 + 深度相机 + VIO
  在 60% 丢包率下仍能完成协同探索

加速比没有达到理论 $N$ 倍的原因：（1）任务分配本身有通信和计算开销；（2）边界区域不可避免地有重叠覆盖；（3）机器人之间需要让路避免碰撞。

⚠️ 常见陷阱¶

概念误区 1：去中心化 = 没有协调

错误理解：每台 UAV 完全独立，互不干扰
正确理解：去中心化 $\ne$ 无协调。RACER 的成对交互就是一种协调机制——只是不通过中央服务器，而是通过局部成对协商达成全局一致

编程陷阱 2：LKH-3 文件路径用相对路径

错误做法：write_file("problem.tsp", ...); system("./LKH-3 problem.par");
现象：在 ROS 节点中运行时，工作目录可能不是你预期的目录，文件找不到
正确做法：始终用绝对路径或确保工作目录正确

练习¶

练习 D7.5.1 ⭐⭐⭐：手动模拟 RACER 的成对交互协议。给定 3 台 UAV 的初始位置和各自的目标栅格集合，模拟以下事件序列：$t=0$ UAV1 和 UAV2 相遇 → 交换 + 竞价 → 各自重规划；$t=5$ UAV2 和 UAV3 相遇 → 同上。画出每台 UAV 的目标栅格集合在每个时刻的变化。

练习 D7.5.2 ⭐⭐⭐：分析 RACER 成对交互的"最终一致性"。证明或举反例：在有限次成对交互后，所有 UAV 的 hgrid 一定收敛到相同状态。提示：考虑 hgrid 合并规则的单调性。

D7.6 FALCON——覆盖路径引导范式 ⭐⭐⭐¶

动机——前沿选择的根本缺陷¶

FALCON（Zhang, Chen 等, HKUST, TRO 2024）的核心论点是：包括 FUEL 在内的前沿选择方法存在根本性的效率缺陷。

前沿选择方法的三大缺陷：

缺陷	表现	根本原因
来回往返	在相邻前沿间反复切换	每次重算 ATSP 序列时前沿状态已变
重复覆盖	大量移动距离无信息增益	新序列可能穿越已探索区域
全局一致性缺失	不考虑未来前沿的出现	只基于当前前沿状态规划

覆盖路径引导方案 ⭐⭐⭐¶

FALCON 的核心创新是将"前沿选择"替换为"覆盖路径引导"：

FALCON 的关键区别（vs FUEL）:
  FUEL: 只覆盖当前前沿 → 前沿消失后重算 → 不稳定
  FALCON: 覆盖整个未探索空间 → 持久有效 → 稳定

系统架构:
  模块 1: 增量可达性感知空间分解
    自由空间 → 连通子区域 → 连通图

  模块 2: 全局覆盖路径规划
    在连通图上规划横跨整个未探索空间的覆盖路径
    → 持久引导: 路径跨多个规划周期保持一致

  模块 3: 局部前沿访问（受全局路径偏置）
    代价 = α · 移动距离 + β · 偏离全局路径的距离
    → 局部选择倾向于沿全局路径方向前进
    → 避免往回走访问小前沿

  模块 4: 轨迹生成（MINCO 后端）

EPEE 基准评价体系 ⭐⭐¶

FALCON 还提出了 EPEE（Exploration Performance Evaluation Environment）评价指标：

指标	公式	含义
体积效率 $\eta_V$	$V_{\text{explored}} / (v_{\text{avg}} \cdot T)$	单位时间单位速度探索的体积
移动效率 $\eta_T$	$V_{\text{explored}} / D_{\text{total}}$	单位移动距离探索的体积
覆盖连续性 $C$	$1 - N_{\text{revisit}} / N_{\text{total}}$	不重复访问的比例
$T_{95}$ / $T_{99}$	达到 95%/99% 覆盖率的时间	完成效率

实验结果（TARE 的仿真环境中）：

场景	FALCON $T_{95}$	FUEL $T_{95}$	TARE $T_{95}$
Indoor (130m$\times$100m)	180s	310s	240s
Campus (340m$\times$340m)	420s	780s	520s

FALCON 在所有场景中全面胜出。FUEL 在大场景退化严重（前沿簇数 > 100 时 ATSP 变慢），TARE 表现稳健但效率低于 FALCON。

⚠️ 常见陷阱¶

思维陷阱 1：覆盖路径引导在所有场景下都优于前沿选择

错误推论：FALCON 全面碾压 FUEL，前沿选择已过时
实际情况：在高度动态的环境中（门开关、人员走动），全局覆盖路径可能快速失效——因为之前认为"未探索"的区域可能因为门关闭而变得不可达。此时 FUEL 的"每帧重算"反而是优势
正确思维：覆盖路径引导适合静态或缓慢变化的环境；前沿选择适合动态环境

练习¶

练习 D7.6.1 ⭐⭐⭐：设计一个环境使得 FALCON 的覆盖路径引导**失效**。提示：考虑一个有"活动门"的环境——探索过程中某些门会打开或关闭，改变空间连通性。

D7.7 FC-Planner——骨架引导的覆盖规划 ⭐⭐⭐¶

核心思想 ⭐⭐⭐¶

FC-Planner（Feng 等, HKUST, ICRA 2024 Best UAV Paper Finalist） 与 FUEL/TARE/FALCON 的"探索未知环境"不同——它假设场景的**粗略几何已知**（如从 LiDAR 点云快速获取），目标是规划覆盖路径来获取高质量图像用于 3D 重建。

FC-Planner 流程:

输入: 3D 点云/网格（目标场景的粗略几何）

Step 1: ROSA 骨架提取 → 线状骨架 S = {s_1, ..., s_K}
Step 2: 骨架引导空间分解 → Voronoi 式子空间
Step 3: Set Cover 视点生成 → 最小视点集覆盖所有表面
Step 4: 子空间间 ATSP → LKH 求解访问序列
Step 5: 轨迹生成 → 完整覆盖轨迹

FC-Planner 的优势在于**将大问题分解为小问题**：骨架分解使得每个子空间内部的视点规划是独立的、可并行的，而子空间之间的连接用 ATSP 优化。

下面逐一拆解三个最关键的技术环节——骨架为什么是好的分解基底、Set Cover 如何把"覆盖整个表面"压缩成最小视点集、以及这套方法的适用边界。

为什么用骨架做分解基底 ⭐⭐⭐¶

要理解 ROSA（Rotational Symmetry Axis，旋转对称轴）骨架的价值，先看一个反面：如果不做骨架分解，而是直接在整个场景的点云上一次性求解"最小视点集覆盖所有表面"，会发生什么？这是一个超大规模的 Set Cover 问题——视点候选数和表面元素数都是上万量级，组合爆炸。更糟的是，求出的视点集没有任何空间结构，访问顺序的 ATSP 要在上千个散乱视点间求解，既慢又容易产生来回穿越。

骨架的作用是给这个混沌的空间**强加一个一维拓扑骨干**。直观类比：把一栋建筑想象成人体，ROSA 骨架就像脊柱和四肢的中轴线——它沿着物体的"延伸方向"穿过物体内部。

类比边界：骨架像人体骨架的地方在于"它是物体的低维中轴、刻画了整体走向"；不像的地方在于人体骨架是刚性的、连接关系固定，而 ROSA 骨架是从点云统计出来的、可能断裂或分叉，对薄板状物体（如一面墙）骨架会退化成一个面而非一条线——这正是练习 D7.7.1 要考察的退化情形。

有了骨架，空间分解就有了天然的"种子"：每段骨架 $s_k$ 周围的点云划归一个子空间，相当于沿中轴做 Voronoi 切分。这样得到的子空间有两个好性质——一是每个子空间内部的表面是"局部连续、朝向一致"的，便于独立规划视点；二是子空间之间的相邻关系由骨架的连接关系直接给出，ATSP 只需在十几个子空间级别上求解，规模骤降。

骨架引导分解的规模对比（直觉量级，非精确值）:

  无分解（朴素 Set Cover）:
    视点候选 ~ 10^4   表面元素 ~ 10^4   ATSP 节点 ~ 10^3
    → 单次求解分钟级，且无空间结构

  骨架分解后:
    每个子空间: 视点候选 ~ 10^2   表面元素 ~ 10^2
    子空间数 ~ 10        子空间间 ATSP 节点 ~ 10
    → 子空间内并行求解秒级，ATSP 毫秒级

Set Cover 视点生成 ⭐⭐⭐¶

子空间内部的核心问题是：用尽可能少的视点，看遍这个子空间的所有表面。这正是经典的集合覆盖（Set Cover）问题——每个候选视点 $v$ 能"看到"的表面元素构成一个集合 $S_v$，目标是选出最少的视点使得 $\bigcup S_v$ 覆盖全部表面。

Set Cover 是 NP-hard 的，但贪婪算法有理论保证（近似比 $\ln n$），且实践中效果很好：

def greedy_set_cover(surfaces, viewpoints, visibility):
    """visibility[v] = 视点 v 能看到的表面元素集合
       返回覆盖所有表面的近似最小视点集"""
    uncovered = set(surfaces)
    selected = []
    while uncovered:
        # 每轮选"新增覆盖最多"的视点——贪婪核心
        best_v = max(viewpoints,
                     key=lambda v: len(visibility[v] & uncovered))
        if not (visibility[best_v] & uncovered):
            break  # 剩余表面无任何视点可见（遮挡死角）
        selected.append(best_v)
        uncovered -= visibility[best_v]
    return selected, uncovered  # uncovered 非空 = 存在覆盖盲区

注意最后返回的 uncovered——这是工程上极易忽略的一点。如果某些表面被任何候选视点都看不到（深凹槽、内部腔体），贪婪循环会在 break 处退出，留下覆盖盲区。FC-Planner 的工程实现必须显式处理这种盲区（增加候选视点采样密度，或标记为"不可达表面"），而不是假装覆盖完整。

本质洞察：FC-Planner 把一个"连续的几何覆盖问题"翻译成了两个离散的组合优化问题——子空间内的 Set Cover（选哪些视点）+ 子空间间的 ATSP（按什么顺序访问）。这种"先离散化、再用成熟组合优化求解器"的范式，是整个探索/覆盖领域反复出现的元模式：FUEL 用它（前沿簇 → ATSP），RACER 用它（子区域 → CVRP），FC-Planner 也用它。一旦认出这个模式，新论文的"创新点"往往就落在"如何离散化"这一步，求解器反而是现成的。

与探索方法的本质区别 ⭐⭐⭐¶

FC-Planner 与前面所有方法（FUEL/TARE/FALCON）有一条不可逾越的边界：它不探索未知，它覆盖已知。这不是程度差异，而是问题定义的根本不同。探索方法的输入是"未知空间"，要在飞行中边建图边决策；FC-Planner 的输入是"已知粗几何"，可以离线把整条覆盖路径算好再执行。

维度	探索（FUEL/TARE/FALCON）	覆盖规划（FC-Planner）
先验	完全未知	粗略几何已知
决策时机	在线、边飞边算	可离线、一次算完
核心不确定性	"前方有什么"	"怎么看得最全"
失败模式	漏掉未知角落	漏掉已知表面
典型应用	灾后搜救、未知洞穴	建筑巡检、文物数字化

⚠️ 常见陷阱¶

概念误区 1：FC-Planner 适用于完全未知环境

错误描述：把 FC-Planner 当成 FUEL/TARE 的同类探索方法，在完全未知的环境里直接部署。
现象/后果：系统因为拿不到"粗略几何"输入而无法启动骨架提取，或被迫用空的先验运行，规划出的视点集毫无意义。
根本原因：混淆了"探索"（Exploration，输入是未知空间）与"覆盖规划"（Coverage Planning，输入是已知几何）这两类问题——它们的输入假设根本不同。
正确做法：FC-Planner 用于已有粗略几何先验的场景（建筑巡检 BIM 模型已知、文化遗产先粗扫后精扫）。若环境完全未知，应先用探索方法建出粗图，再交给 FC-Planner 做精细覆盖。

编程陷阱 2：忽略 Set Cover 的覆盖盲区

错误描述：直接采用贪婪 Set Cover 的输出视点集，默认它覆盖了 100% 表面。
现象/后果：重建结果在深凹槽、内部腔体处出现空洞，且空洞位置难以事后定位。
根本原因：贪婪算法在"剩余表面无任何候选视点可见"时会提前退出，这部分表面静默地未被覆盖。
正确做法：始终检查并显式处理贪婪算法返回的 uncovered 集合——加密视点采样、放宽可见性判据，或明确标记为"几何不可达"，绝不假装覆盖完整。

练习¶

练习 D7.7.1 ⭐⭐⭐：分析 FC-Planner 的 ROSA 骨架提取对以下物体的效果：（1）一栋长方体建筑；（2）一棵树；（3）一个雕塑。哪种物体的骨架最有用？哪种最没用？为什么？（提示：结合上文"类比边界"中薄板状物体骨架退化的讨论。）

练习 D7.7.2 ⭐⭐⭐：手动模拟贪婪 Set Cover。给定 5 个表面元素 $\{a,b,c,d,e\}$ 和 4 个视点，可见性为 $S_1=\{a,b,c\}$、$S_2=\{c,d\}$、$S_3=\{d,e\}$、$S_4=\{b,e\}$。贪婪算法会选出哪几个视点？得到的解是最优解吗？如果不是，最优解是什么？这说明贪婪近似比的什么含义？

D7.8 感知引导——yaw 作为一等公民 ⭐⭐⭐¶

动机——为什么"看哪里"和"去哪里"一样重要¶

到目前为止，所有探索方法都在回答"去哪里"——选择哪个前沿、什么顺序访问。但有一个同样重要的问题被忽略了："去的路上和到达后，看哪个方向？"

这个问题对四旋翼尤为关键。深度相机的 FOV 通常只有 $90^\circ \times 60^\circ$——只能看到前方一个锥形区域。如果 yaw 跟随速度方向（经典做法），那么飞行中只有前方被观测，左右两侧 $270^\circ$ 范围完全盲区。在走廊环境中，侧方往往有门通向新房间——如果相机一直朝前看，就永远发现不了侧方的入口。

物理基础：微分平坦下 yaw 的特殊地位 ⭐⭐⭐¶

四旋翼的微分平坦性是感知引导规划的物理基础。平坦输出 $\sigma = (x, y, z, \psi)^\top$ 中，yaw 角 $\psi$ 具有特殊地位：

四旋翼微分平坦下 yaw 的特殊性:

推力方向 t_B 由 (ẍ, ÿ, z̈ + g) 决定 → 与 ψ 无关
推力大小 f = m·‖(ẍ, ÿ, z̈ + g)‖     → 与 ψ 无关
roll (φ) 和 pitch (θ) 由推力方向决定  → 与 ψ 无关

唯一影响: ψ 决定体轴 x/y 方向的旋转
→ ψ 是"免费"的自由度——可以任意设置而不影响位置跟踪
→ 这是"主动感知"的物理基础

如果 yaw 不是"免费的"会怎样？ 对于固定翼无人机，yaw 与侧滑角耦合——改变 yaw 会影响气动力，进而影响位置。对于多旋翼倾转旋翼机，yaw 变化会改变推力方向。在这些平台上，感知引导规划需要考虑 yaw 变化对位置跟踪的影响——代价函数中需要加入 yaw-position 耦合项。四旋翼是唯一可以"免费"旋转 yaw 的常见飞行器，这使得感知引导在四旋翼上最容易实现。

本质洞察：yaw 的"免费"性质不是凑巧的——它是欠驱动（4 个输入控制 6 个自由度）的直接后果。四旋翼的 4 个电机提供 1 个推力 + 3 个力矩，恰好控制 $\mathbb{R}^3$ 位置 + 1 个 yaw 角。推力方向被位置控制"锁定"后，yaw 是唯一剩余的自由度——因此可以自由分配给感知任务。

RAPTOR：yaw 图搜索 ⭐⭐⭐¶

**RAPTOR（Zhou, Pan, Gao, Shen, TRO 2021）**提出了系统化的 yaw 规划方法——将 yaw 优化建模为时间-yaw 格上的图搜索问题。

RAPTOR yaw 规划:

Step 1: 固定位置轨迹 τ_pos(t)（B 样条已优化）

Step 2: 在每个时间节点 t_k 采样 yaw ∈ {0°, 30°, ..., 330°}（12 个候选）
    对每个 (t_k, ψ_k): 射线投射 → gain(t_k, ψ_k)

Step 3: 构建图
    节点: (t_k, ψ_k) —— 时间 × yaw 的 2D 栅格
    边权: w = -λ_g · gain     ← 信息增益（负号因为求最短路）
          + λ_s · |Δψ|        ← 平滑性
          + λ_r · max(|Δψ|/Δt - ψ̇_max, 0)  ← yaw 速率约束

Step 4: Dijkstra 求最短路 → 最优 yaw 序列 {ψ_0*, ..., ψ_N*}
    复杂度: O(N_time × N_yaw²) = O(20 × 144) ≈ 2880 次

Step 5: B 样条拟合 → 连续 yaw 轨迹

yaw 图搜索示意（Dijkstra 在时间-yaw 格上）:

yaw (°)
 330 ─ ○───○───○───○───●───○───○     ● = 最优路径
 300 ─ ○───○───○───●───○───○───○     ○ = 其他候选
 270 ─ ○───○───●───○───○───○───○
 ...
  60 ─ ○───●───○───○───○───○───○
  30 ─ ●───○───○───○───○───○───○     约束: |Δψ| ≤ ψ̇_max · Δt
   0 ─ ○───○───○───○───○───○───○
       t₀  t₁  t₂  t₃  t₄  t₅  t₆

PAMPC：位置-yaw 联合优化 ⭐⭐⭐⭐¶

**PAMPC（Falanga 等, UZH RPG, IROS 2018）**采用了不同的策略——将感知目标直接编入 NMPC 的代价函数：

PAMPC 代价函数:
  J = J_tracking + λ_p · J_perception

J_perception 包含:
  J_visibility: POI 偏离图像中心的惩罚
    = ‖π(R_k^T · (p_POI - p_k)) - c_img‖²

  J_pixel_velocity: POI 在图像中的像素速度惩罚
    = ‖d/dt[π(R_k^T · (p_POI - p_k))]‖²
    → 防止运动模糊

RAPTOR vs PAMPC 对比：

特性	RAPTOR	PAMPC
优化方式	位置/yaw 交替	位置/yaw 联合
计算量	轻量（图搜索, < 1 ms）	重量（NMPC, 10-20 ms）
适用性	探索（多前沿）	跟踪（单 POI）
耦合度	弱耦合	强耦合

VIO 可观性约束 ⭐⭐⭐⭐¶

近年来研究开始考虑更深层的感知约束——不仅要看到未知区域，还要确保 VIO 的定位精度不退化。核心问题：如何在"探索新区域"和"回看特征丰富区域以保持定位"之间权衡？

量化 VIO 可观性的三种方法：

方法	公式	含义
Fisher 信息矩阵	$\lambda_{\min}(\mathbf{I}(\theta))$	最弱方向的信息量
特征共视性	$N_{\text{covis}}(v_1, v_2)$	连续帧共视特征数
可定位走廊	$L_{\text{score}}(t) \geq L_{\text{threshold}}$	沿轨迹的可定位性分数

⚠️ 常见陷阱¶

概念误区 1：yaw 优化只对深度相机有用

错误理解：LiDAR 有 $360^\circ$ FOV，不需要 yaw 优化
正确理解：即使 LiDAR 有 $360^\circ$ 水平 FOV，其垂直 FOV 通常只有 $30^\circ$-$70^\circ$。在需要观测天花板或地面的场景中，pitch 优化（通过调整 yaw + 飞行方向）仍然重要

思维陷阱 2：yaw 变化越快越好（看更多方向）

错误推论：快速转动 yaw 可以覆盖更多方向
现实约束：快速 yaw 变化导致图像运动模糊，VIO 特征跟踪失败，状态估计发散。RAPTOR 中的 $\dot{\psi}_{\max}$ 约束正是为了防止这个问题

练习¶

练习 D7.8.1 ⭐⭐⭐：实现 RAPTOR 的 yaw 图搜索。给定一条 2D 位置轨迹（10 个时间节点）和一个简单的 2D 地图（有 unknown 区域），离散化 yaw 为 12 个方向，构建图并用 Dijkstra 求解最优 yaw 序列。可视化结果。

练习 D7.8.2 ⭐⭐⭐⭐：分析以下场景中 RAPTOR（弱耦合）和 PAMPC（强耦合）的表现差异：一条 $S$ 形走廊，两侧墙壁分别有 3 个门通向不同房间。无人机需要沿走廊飞行同时观测两侧的门。画出两种方法的 yaw 时间序列和观测覆盖图。

D7.9 多机任务分配与通讯策略 ⭐⭐⭐⭐¶

运筹学问题映射 ⭐⭐⭐¶

多机探索的核心是将空间探索问题映射为经典运筹学问题：

探索概念	运筹学对应
前沿簇/子空间	TSP/VRP 的客户节点
机器人当前位置	仓库（depot）
飞行距离/时间	边权（代价）
电池续航	容量约束
多机	多车辆
负载均衡	min-max 目标

问题类型	代表系统	求解器
TSP	FUEL（单机）	LKH
ATSP	FUEL（全局）、FC-Planner	LKH
CVRP	RACER	LKH-3
MD-VRP (min-max)	MUI-TARE	OR-Tools

LKH vs OR-Tools ⭐⭐¶

特性	LKH/LKH-3	Google OR-Tools
接口	文件 I/O + 子进程	C++/Python API
求解质量	极高（< 1% 偏差）	较好（2-5% 偏差）
线程安全	需要文件名唯一化	原生线程安全
部署	单个可执行文件	大型依赖包

MUI-TARE：未知初始位姿的多机探索 ⭐⭐⭐⭐¶

**MUI-TARE（Yan 等, CMU, RA-L 2023）**解决了更具挑战性的问题：机器人初始相对位姿未知。解法是两阶段：先独立探索 + AutoMerge 地图匹配，匹配成功后切换为协同探索 + min-max MD-VRP 任务分配。

到这里有一个容易被一带而过、却决定多机系统好坏的关键——优化目标到底是 min-sum 还是 min-max。下面把这件事讲清楚，它是多机探索区别于单机的真正难点所在。

min-sum vs min-max：多机的目标函数之争 ⭐⭐⭐¶

单机 TSP 的目标天经地义是"总路程最短"（min-sum）。但多机探索一旦照搬 min-sum，会立刻翻车。考虑 3 台 UAV、9 个前沿簇的场景：min-sum 只在乎所有机器人路程之和最小，它完全可能给出"1 号机跑 8 个簇、2 号和 3 号各跑半个"的解——因为这样恰好总路程最小。可探索任务的完成时间取决于**最慢那台机器人**，1 号机累死、另外两台闲置，整体反而最慢。

3 台 UAV、9 个前沿簇的两种分配:

  min-sum 最优（总路程最短）:        min-max 最优（最长路程最短）:
    UAV1: ●●●●●●●  (路程 70)          UAV1: ●●●  (路程 28)
    UAV2: ●         (路程  8)          UAV2: ●●●  (路程 26)
    UAV3: ●         (路程  9)          UAV3: ●●●  (路程 30)
    Σ = 87, max = 70                   Σ = 84, max = 30
    → 完成时间 ∝ 70（最慢的 UAV1）     → 完成时间 ∝ 30

右边的 min-max 解总路程 84 比左边的 87 还略短只是巧合；关键是它的 max 从 70 降到 30——完成时间快了一倍以上。这就是为什么 RACER 的 CVRP、MUI-TARE 的 MD-VRP 都用 min-max（最小化最大单机代价） 而非 min-sum 作为目标。

本质洞察：多机协同的难点不在"让总量最优"，而在"让负载均衡"。min-sum 优化的是吞吐量，min-max 优化的是延迟（完成时间）。探索任务的用户体验由完成时间决定，所以必须用 min-max。这也解释了为什么多机 VRP 比单机 TSP 难得多——min-max 目标是非光滑的（max 函数），且"分配"和"路由"两个子问题强耦合，不能分开求解。

对比性思维：负载均衡不是"把任务平均分"。如果 9 个簇里有 3 个在很远的角落，把它们平均分给三台机器，每台都要长途跋涉一趟；更优的做法可能是让一台机器专门清扫那个远角落、另两台密集清扫近处。min-max 追求的是"最大代价最小"，而非"代价相等"——这是一个微妙但关键的区别。

容量约束从何而来 ⭐⭐¶

CVRP 里的"容量"（Capacity）在探索语境下对应**电池续航**。每段飞行消耗能量，一台 UAV 一个架次能访问的前沿簇总"需求"（飞行时间/距离）不能超过其剩余续航。这把无约束的任务分配变成了带背包约束的分配——某些诱人的远处前沿可能因为"这趟回不来"而必须留给别的机器人或下个架次。

约束类型	探索语境对应	违反后果
容量上界	单架次续航	电量耗尽坠机
时间窗	多机交会时刻	协同动作错位
节点互斥	同一前沿不重复分配	重复覆盖、浪费

为什么是组合优化而非贪婪 ⭐⭐⭐¶

新手常想：直接让每台机器人贪婪地选"离自己最近的前沿"不就行了？问题在于贪婪是**短视**的。两台机器人可能同时扑向同一个近前沿（冲突），或都避开一个谁都不想要的中等距离前沿（遗漏）。全局组合优化（VRP 求解器）一次性考虑所有机器人和所有前沿的分配，才能避免这类局部决策的全局次优。RACER 的精妙之处在于：它不在中心节点求解全局 VRP（去中心化没有中心），而是通过成对交互（§D7.5）让相邻机器人**局部交换任务**，多次成对优化逼近全局 min-max——这是把全局组合优化分解成可去中心执行的局部协商。

⚠️ 常见陷阱¶

概念误区 1：TSP 和 VRP 是同一个问题

错误描述：把 VRP 当成"多个独立 TSP 的简单并列"，先把前沿平均分给各机器人，再各自解 TSP。
现象/后果：分配阶段拍脑袋平分，导致某台机器人路程远超其他，完成时间被这台拖慢；或多台扑向同一前沿产生冲突。
根本原因：VRP 的难点恰恰在"分配"——需要在多个旅行商之间分配客户使得 min-max 代价最小，这个分配本身就是一个组合优化问题，无法用平分替代。
正确做法：用专门的 VRP 求解器（LKH-3、OR-Tools）联合求解"分配 + 路由"，并以 min-max 为目标；去中心场景用成对交互逐步逼近全局最优。

概念误区 2：多机任务分配用 min-sum 目标

错误描述：照搬单机 TSP 的"总路程最短"（min-sum）作为多机分配目标。
现象/后果：求解器给出极不均衡的分配（一台累死、其余闲置），整体探索完成时间反而变长。
根本原因：探索完成时间取决于最慢的机器人，而 min-sum 不约束单机最大代价，与"尽快完成探索"的真实目标错位。
正确做法：用 min-max（最小化最大单机代价）作为目标，显式追求负载均衡；注意 min-max 是非光滑目标，需用支持它的求解器配置。

练习¶

练习 D7.9.1 ⭐⭐⭐：用 Python 的 ortools 包实现一个 5 节点、2 车辆的 CVRP 求解器。定义代价矩阵和需求向量，求解并可视化路线。

练习 D7.9.2 ⭐⭐⭐⭐：在练习 D7.9.1 的代码基础上，分别用 min-sum 和 min-max 两种目标求解同一组 3 车辆、9 节点的实例（节点位置自拟，使其中 3 个明显偏远）。对比两种解的最大单机路程和总路程，验证本节"min-sum 会产生不均衡分配"的论断。在什么情况下两种目标会给出相同的解？

D7.10 感知-规划一体化架构 ⭐⭐⭐⭐¶

四个耦合层次 ⭐⭐⭐¶

Level 0: 完全分离（传统方案）
  感知 → 地图 → 规划 → 控制 → 无反馈

Level 1: 弱耦合（RAPTOR）
  规划器优化 yaw 以增加信息增益
  → 感知影响 yaw，不影响位置

Level 2: 中耦合（PAMPC）
  NMPC 代价函数包含感知项
  → 轨迹轻微偏离位置最优，换取更好的感知

Level 3: 强耦合（2025+）
  VIO 可观性作为硬约束
  → 不允许飞入特征稀疏区域

Level 4: 端到端学习（研究中）
  传感器 → 直接到控制输出

Active SLAM ⭐⭐⭐⭐¶

Active SLAM 同时优化两个目标：探索效率和定位精度。

Active SLAM 目标:
  min J = w_explore · J_exploration + w_slam · J_localization

权衡:
  w_explore 大 → 贪婪探索，可能定位退化
  w_slam 大    → 保守重访，探索效率低

自适应策略:
  if tr(Σ_pose) > threshold:
      target = nearest_feature_rich_region()   ← 定位退化，回去看特征
  else:
      target = next_frontier()                  ← 定位稳定，继续探索

⚠️ 常见陷阱¶

思维陷阱 1：耦合越强越好

错误推论：Level 3 强耦合一定优于 Level 1 弱耦合
实际情况：强耦合增加了优化问题的维度和非凸性，求解更慢、可能陷入局部最优。在 VIO 不退化的场景中（特征丰富的室内），弱耦合足够了

练习¶

练习 D7.10.1 ⭐⭐⭐⭐：设计一个实验来量化感知-规划耦合的收益。在同一场景中分别运行 Level 0（yaw 跟随速度）和 Level 1（RAPTOR yaw 规划），记录 VIO 的位姿估计误差和探索完成时间。预测在什么场景下 Level 1 的改善最大。

D7.11 传感器模型与环境表示 ⭐⭐¶

深度相机 vs LiDAR ⭐⭐¶

特性	深度相机	LiDAR
FOV	$60^\circ \times 45^\circ$ ~ $90^\circ \times 60^\circ$	$360^\circ \times 30^\circ$ ~ $70^\circ \times 77^\circ$
最大距离	5-10 m（结构光）; ~20 m（ToF）	30-200 m
重量	5-72 g	500g-1kg
yaw 规划重要性	关键（FOV 窄）	相对次要（FOV 宽）
代表系统	FUEL, RACER	TARE, FALCON

地图表示选择 ⭐⭐¶

地图表示	优点	缺点	代表系统
OctoMap	多分辨率、概率更新	查询 $O(\log N)$、无距离场	nbvplanner
voxblox (TSDF/ESDF)	查询 $O(1)$、有距离场	固定分辨率、内存大	FUEL
滚动栅格	固定内存	只保留局部	TARE
混合	取长补短	实现复杂	FALCON

选择原则：小场景（< 50 m）用 voxblox/ESDF；大场景（> 100 m）用混合表示；多机场景需要可差分传输的表示。

传感器和地图表示看似是"底层基础设施"，但它们的选择会一路向上传导，决定上层规划器的形态。下面把这条传导链讲透：FOV 决定 yaw 规划是否必要，距离场决定碰撞检测和优化能否用梯度。

视锥模型：FOV 如何向上决定规划器形态 ⭐⭐⭐¶

回顾 §D7.8 的一个论断：yaw 规划对深度相机"关键"、对 LiDAR"次要"。这个差异的根源就在传感器的视锥（view frustum）模型。深度相机的视锥是一个窄角金字塔（$90^\circ \times 60^\circ$），LiDAR 的视锥接近一个扁圆盘（水平 $360^\circ$）。

俯视图对比（同一架无人机，朝向 → 方向）:

  深度相机 FOV ~90°:        LiDAR FOV 360°:
        ╱│╲                      ___
       ╱ │ ╲                   ╱     ╲
      ╱  →  ╲                 │   →   │   ← 水平全向
     盲区 270°               ╲ _____ ╱
   （左右后方看不见）         （唯一盲区: 上下）

这张图直接解释了上层规划器的分化。深度相机有 $270^\circ$ 的水平盲区，所以"看哪里"（yaw）成为一个必须主动决策的自由度——FUEL、RACER 这类用深度相机的系统都内置 yaw 规划。LiDAR 水平全向，"看哪里"几乎不影响能看到什么，所以 TARE、FALCON 这类用 LiDAR 的系统可以把 yaw 简单地设为速度方向，省去整个 yaw 规划模块。

本质洞察：传感器 FOV 不只是一个硬件参数，它从底层决定了规划问题的维度。窄 FOV 把"感知"和"运动"耦合起来（必须转头才能看全，转头又受 yaw 速率限制），宽 FOV 把两者解耦（看和走互不干扰）。这解释了一个反直觉现象：在探索任务里，更贵更重的 LiDAR 反而让规划问题变简单了——它用硬件成本买下了软件复杂度。

信息增益的计算也直接依赖视锥模型。射线投射（§D7.2）本质上是在视锥内部均匀采样若干条射线、逐条步进直到撞上 occupied 或 unknown 体素。视锥越窄，覆盖同样立体角需要的视点越多——这又反过来增加了前沿簇的视点采样数。可见，"传感器 → 信息增益 → 视点数 → ATSP 规模"是一条完整的向上传导链。

距离场为什么是规划的"硬通货" ⭐⭐¶

地图表示这一节最容易被新手低估的，是 ESDF（Euclidean Signed Distance Field，欧氏符号距离场）的价值。OctoMap 只回答"这个体素占据概率多少"（一个标量），ESDF 回答"这个点到最近障碍物有多远"（一个带梯度的标量场）。差别看似不大，对规划却是天壤之别。

能力	占据概率（OctoMap）	距离场（ESDF/voxblox）
碰撞检测	离散"是/否"，需逐点查询 $O(\log N)$	连续距离，$O(1)$ 查询，一次判 $d<d_{\text{safe}}$
梯度优化	无梯度，无法做连续优化	$\nabla d$ 现成，可推安全代价梯度
安全裕度	只知碰/不碰	知道"离障碍还有多远"，可设软裕度
视点安全判据	需另算	直接用 $\text{ESDF}(p) > d_{\text{safe}}$

正因如此，几乎所有现代轨迹优化器（FUEL 的 B 样条后端、FALCON 的 MINCO）都把安全约束写成 ESDF 上的形式 $d(p) \ge d_{\text{safe}}$，并用 $\nabla d$ 做梯度下降。OctoMap 适合"建图和可视化"，ESDF 适合"喂给优化器"——这就是为什么实践中常见的流水线是"OctoMap/TSDF 建图 → 转 ESDF → 规划"。

对比性思维：这里的关键不是"OctoMap 不好"，而是"占据概率和距离场回答的是不同的问题"。占据概率回答"这里有没有东西"，距离场回答"我离最近的东西多远"。规划器需要的是后者——它要在自由空间里找一条带安全裕度的路，而不仅仅是判断单点碰撞。把这两者混为一谈，是导致"为什么我的碰撞检测又慢又没法优化"的常见根源。

多机场景的额外约束 ⭐⭐¶

单机看不出来、一到多机就暴露的约束是**地图的可传输性**。RACER（§D7.5）要求各机交换"谁探索了哪里"的信息，如果地图表示是稠密的 voxblox 体素数组，每次同步要传输几十 MB，通信带宽根本扛不住。这就是为什么 RACER 用稀疏的 hgrid（分层栅格）+ 前沿摘要做差分传输——只传"变化的格子"，而非整张地图。

表示	单机适用性	多机可传输性	原因
稠密 voxblox	优秀	差	数据量大，难差分
OctoMap	良好	中等	八叉树可剪枝传输
hgrid + 摘要	一般（精度低）	优秀	稀疏、可增量同步

⚠️ 常见陷阱¶

编程陷阱 1：直接用 OctoMap 做碰撞检测

错误描述：对每个轨迹采样点直接查询 OctoMap 的占据概率来判断碰撞。
现象/后果：碰撞检测耗时长（每次查询 $O(\log N)$），而且只得到离散的"是/否"结果，无法用于梯度优化。
根本原因：占据概率回答的是"单点有没有障碍"，不提供"到最近障碍的距离"和梯度，与连续轨迹优化所需的信息不匹配。
正确做法：先从 OctoMap/TSDF 生成 ESDF，碰撞检测用 $O(1)$ 查询 ESDF 值；同时得到连续距离 $d$ 和梯度 $\nabla d$，可直接写成安全约束 $d \ge d_{\text{safe}}$ 喂给优化器。

概念误区 2：用窄 FOV 传感器却套用宽 FOV 的规划假设

错误描述：在深度相机平台上，把 yaw 简单设为速度方向（沿用 LiDAR 系统的做法），不做 yaw 规划。
现象/后果：飞行中只观测前方锥形区域，左右侧方的门洞、岔路被系统性漏检，探索完成度卡在某个数值上不去。
根本原因：深度相机有 $270^\circ$ 水平盲区，"看哪里"是必须主动决策的自由度；照搬 LiDAR（水平全向）的假设忽略了这个盲区。
正确做法：窄 FOV 平台必须启用 yaw 规划（RAPTOR 式图搜索或 PAMPC 联合优化），让相机主动扫视侧方；或在硬件上换用更宽 FOV 的传感器。

练习¶

练习 D7.11.1 ⭐⭐：对比 OctoMap 和 voxblox 在 $50 \times 50 \times 3$ m 场景中的内存消耗和查询速度。假设分辨率 0.1 m。OctoMap 的八叉树深度是多少？voxblox 的体素数组大小是多少？

练习 D7.11.2 ⭐⭐⭐：画出深度相机（$90^\circ \times 60^\circ$，最大距离 5 m）和 LiDAR（水平 $360^\circ$、垂直 $30^\circ$，最大距离 50 m）在悬停一周（yaw 转 $360^\circ$）后各自能覆盖的体积。结合本节"向上传导链"，说明为什么前者的探索系统必须做 yaw 规划而后者可以省略。

D7.12 前沿工作与开放问题 ⭐⭐⭐⭐¶

3DGS/NeRF 驱动的主动感知 ⭐⭐⭐⭐¶

3D Gaussian Splatting（3DGS）正在改变主动感知的范式。**FisherRF（ECCV 2024）**用 Fisher 信息矩阵量化每个高斯原语的不确定性，直接在连续表示上做 NBV 选择——不需要体素化。

开放挑战：实时性（3DGS 渲染快但训练慢）、大尺度退化、动态场景。

LLM 引导的语义探索 ⭐⭐⭐⭐¶

LLM 引入了全新的可能性——用自然语言描述探索目标（"找到红色灭火器"），LLM 将语义目标转化为空间先验（"灭火器通常在走廊墙壁上"），用先验偏置前沿选择。

其他开放问题 ⭐⭐⭐⭐¶

问题	挑战	方向
小时级 GNSS 拒止	VIO 累积漂移	周期性回环 + 地图锚点
纳米无人机群（< 50g）	MCU 级算力	边缘卸载 + 轻量化
动态环境	地图失效	时间衰减占据概率
能量受限	10-25 min 续航	返回充电 + 多机接力

练习¶

练习 D7.12.1 ⭐⭐⭐⭐：阅读 FisherRF（ECCV 2024）的论文摘要和方法部分。与 nbvplanner 的射线投射信息增益对比：两者分别在什么"表示空间"上计算信息增益？3DGS 表示相比体素表示有什么优势和劣势？

D7.13 系统集成与工程实践 ⭐⭐¶

完整探索系统软件栈 ⭐⭐¶

典型探索系统（以 FUEL 为例）:

    Hardware Layer
┌──────────────────────────────────────┐
│ 飞控 (PX4)  |  深度相机 (D435i)      │
│ IMU (BMI088)  |  机载计算 (Jetson NX) │
└──────────────────┬───────────────────┘
                   ▼
    Estimation Layer
┌──────────────────────────────────────┐
│ VIO: VINS-Fusion → T_wb @ 200 Hz    │
└──────────────────┬───────────────────┘
                   ▼
    Mapping Layer
┌──────────────────────────────────────┐
│ 深度图 → voxblox TSDF → ESDF        │
│ + 占据栅格 + 更新包围盒              │
└──────────────────┬───────────────────┘
                   ▼
    Exploration Layer
┌──────────────────────────────────────┐
│ FUEL: FIS → ATSP → DAG → B 样条     │
│ 状态机: INIT → PLAN → EXEC → FINISH │
└──────────────────┬───────────────────┘
                   ▼
    Control Layer
┌──────────────────────────────────────┐
│ B 样条采样 → SE(3) 控制器 → 飞控    │
└──────────────────────────────────────┘

状态机设计 ⭐⭐¶

FUEL 探索状态机:

INIT ──[传感器就绪]──→ WAIT_TRIGGER
WAIT_TRIGGER ──[触发]──→ PLAN
PLAN ──[规划成功]──→ PUB_TRAJ ──→ EXEC_TRAJ
PLAN ──[无前沿]──→ FINISH
PLAN ──[规划失败]──→ REPLAN（延迟后重试）
EXEC_TRAJ ──[地图更新/到达视点]──→ REPLAN
EXEC_TRAJ ──[轨迹异常]──→ PLAN（紧急重规划）
FINISH ──[新前沿出现]──→ PLAN（罕见）

定时器: exec_timer_ (50 Hz) | safety_timer_ (100 Hz) | vis_timer_ (2 Hz)

ROS 话题与参数配置 ⭐⭐¶

# FUEL 关键参数
frontier/cluster_min: 50         # 最小簇大小
frontier/cluster_size_xy: 2.0    # 合并距离阈值 (m)
viewpoint/sample_num: 15         # 每簇采样视点数
viewpoint/min_dist: 2.0          # 视点到前沿最小距离 (m)
plan/max_vel: 2.0                # 最大速度 (m/s)
plan/max_acc: 2.0                # 最大加速度 (m/s²)
plan/replan_time: 0.1            # 最小重规划间隔 (s)
lkh/runs: 5                     # LKH 运行次数

本章常见误解汇总¶

误解	正确理解
前沿 = 障碍物边界	前沿 = free 与 unknown 的边界
yaw 跟随速度方向就够了	yaw 是独立可优化的自由度
TSP 必须精确求解	在线探索中快速近似远比慢速精确好
覆盖路径引导总是优于前沿选择	动态环境中前沿选择的"重算"是优势
去中心化 = 没有协调	成对交互是去中心化的协调机制
3D 探索是 2D 探索的简单扩展	计算量、前沿检测、视锥模型全都不同

本章小结¶

术语速查表¶

术语	英文	定义
前沿	Frontier	free 与 unknown 的边界体素
信息增益	Information Gain	视点覆盖的 unknown 体素数
射线投射	Ray Casting	模拟传感器沿视线步进
NBV	Next-Best-View	选信息增益最高的下一视点
FIS	Frontier Information Structure	FUEL 的增量前沿数据结构
ATSP	Asymmetric TSP	非对称旅行商问题
CVRP	Capacitated VRP	带容量约束的车辆路由问题
hgrid	Hierarchical Grid	RACER 的分层栅格

知识点总表¶

编号	知识点	核心要点	对应节	难度
1	探索形式化	序贯决策 + NP-hard	§D7.1	⭐⭐
2	前沿概念	free-unknown 边界	§D7.1	⭐⭐
3	信息增益	射线投射 + 体素计数	§D7.2	⭐⭐
4	FUEL FIS	增量维护 + dirty 标记	§D7.3	⭐⭐⭐
5	FUEL 三层规划	ATSP + DAG + B 样条	§D7.3	⭐⭐⭐
6	TARE 双分辨率	近细远粗	§D7.4	⭐⭐⭐
7	RACER 多机	成对交互 + CVRP	§D7.5	⭐⭐⭐
8	FALCON 覆盖引导	持久全局路径	§D7.6	⭐⭐⭐
9	yaw 规划	微分平坦 → 免费自由度	§D7.8	⭐⭐⭐
10	感知-规划耦合	四层：分离 → 强耦合	§D7.10	⭐⭐⭐⭐

累积项目：本章新增模块¶

无人机自主探索系统（贯穿 D6-D8）

本章新增探索决策模块：

前沿检测器（§D7.1 练习）：2D 增量前沿检测 + BFS 聚类
信息增益计算器（§D7.2 练习）：射线投射 + 体素计数
yaw 规划器（§D7.8 练习）：时间-yaw 图搜索 + Dijkstra

上一章（D6）的 ESDF 地图作为本章所有模块的输入。下一章（D8）将在此基础上添加任务规划层。

延伸阅读¶

必读论文（按重要性排序）：

FUEL (Zhou 等, RA-L 2021) — 增量 FIS + 分层规划的完整方案 ⭐⭐⭐
TARE (Cao 等, RSS 2021) — 双分辨率原则 + DARPA SubT 实战 ⭐⭐⭐
RAPTOR (Zhou 等, TRO 2021) — yaw 图搜索的系统方法 ⭐⭐⭐

推荐精读代码（按从简到难）：

nbvplanner (~1000 行核心) — 最简单的探索代码，适合入门
mav_active_3d_planning — 最干净的 Factory/Strategy 设计
FUEL frontier_finder.cpp (~600 行) — 增量 FIS 的核心实现

综述与教材：

Placed 等, "A Survey on Active Simultaneous Localization and Mapping" (2023) — Active SLAM 综述 ⭐⭐⭐⭐

本章与后续章节的关系¶

后续章节	关系	铺垫知识点
D8 任务规划	探索是任务规划的子问题	前沿序列 → 任务调度
D9 编队控制	RACER 的多机架构	成对交互 + 去中心化

故障排查手册¶

故障 1：探索完成度卡在 ~85%¶

项目	内容
症状	探索体积增长在 85% 左右停滞，状态机在 PLAN 和 REPLAN 之间反复切换
可能原因	(1) 小前沿簇被 `cluster_min` 过滤；(2) 狭缝处 ESDF < d_safe，视点被判定不安全
排查步骤	1. 降低 `frontier/cluster_min`（如 50 → 20） 2. 检查 RViz 中残留的 unknown 区域位置——是否都在狭缝/角落 3. 降低 `viewpoint/min_dist`（如 2.0 → 1.5 m）
相关章节	§D7.3（FIS 参数）、§D7.11（ESDF 分辨率）

故障 2：LKH 返回错误结果或崩溃¶

项目	内容
症状	全局 ATSP 序列荒谬（如从一端跳到另一端），或 LKH 进程报错退出
可能原因	(1) 代价矩阵有浮点数（LKH 只接受整数）；(2) 代价矩阵有负值；(3) 文件路径错误
排查步骤	1. 打印 .tsp 文件内容，检查是否全为非负整数 2. 检查距离量化倍数（$\times$ 1000）是否导致溢出 3. 确认 LKH 可执行文件路径正确
相关章节	§D7.3（ATSP 求解）、§D7.9（LKH 使用方式）

故障 3：多机探索中某台 UAV "摸鱼"¶

项目	内容
症状	3 台 UAV 中有 1 台长时间原地悬停或在小区域打转
可能原因	(1) 成对交互后该 UAV 被分配了空的目标集合；(2) 通信丢包导致 hgrid 不一致
排查步骤	1. 检查该 UAV 的 hgrid 与其他 UAV 是否一致 2. 查看成对交互日志——是否有竞价失败 3. 手动触发与其他 UAV 的交互
相关章节	§D7.5（成对交互协议）、§D7.9（CVRP 分配）

故障 4：VIO 在探索中频繁漂移¶

项目	内容
症状	位姿估计出现米级跳变，轨迹跟踪异常
可能原因	(1) 飞入无纹理区域（白墙/天花板）；(2) yaw 变化过快导致运动模糊
排查步骤	1. 检查 VIO 的特征点数随时间的变化——是否在漂移前骤降 2. 检查 yaw 变化率是否超过 $\dot{\psi}_{\max}$ 3. 启用 RAPTOR yaw 规划，或降低 `plan/max_vel`
相关章节	§D7.8（yaw 规划）、§D7.10（VIO 可观性）

故障 5：大场景下前沿检测变慢¶

项目	内容
症状	探索进行 5 分钟后，规划频率从 10 Hz 降到 2 Hz
可能原因	(1) 未使用增量前沿检测（全图扫描）；(2) 前沿簇数过多导致 ATSP 变慢
排查步骤	1. profiling 确认瓶颈在前沿检测还是 ATSP 求解 2. 如果是前沿检测：改用增量方法（只扫描 update_bbox） 3. 如果是 ATSP：增大 `cluster_min` 减少簇数，或设置 LKH 的 `TIME_LIMIT`
相关章节	§D7.3（FIS 增量更新）、§D7.14（TSP 复杂度）

D7.14 数学基础补充¶

PCA 包围盒计算 ⭐⭐¶

给定前沿体素集合 X = {x_1, ..., x_N} ⊂ ℝ³

Step 1: 质心 μ = (1/N) Σ x_i
Step 2: 协方差 C = (1/N) Σ (x_i - μ)(x_i - μ)^T
Step 3: 特征分解 C = U Λ U^T → axes = U, extents = sqrt(Λ_ii)

Eigen 实现:
  Eigen::SelfAdjointEigenSolver<Eigen::Matrix3d> solver(cov);
  auto eigenvalues = solver.eigenvalues();   // 升序
  auto eigenvectors = solver.eigenvectors();  // 对应列向量

TSP/ATSP 复杂度 ⭐⭐⭐¶

方法	复杂度	实际可行规模
暴力枚举	$O(n!)$	$n \leq 12$
Held-Karp DP	$O(n^2 \cdot 2^n)$	$n \leq 25$
Concorde 分支定界	指数级（实际快很多）	$n \leq 85000$
LKH 启发式	约 $O(n^{2.2})$ 实测	$n \leq 10^6$

对探索问题：前沿簇数 $N < 50$，LKH 毫秒级；地图每秒更新，TSP 也每秒重算——快速近似远比慢速精确更有价值。

DAG 最短路 ⭐⭐¶

def shortest_path_dag(dag, source, sink):
    """DAG 上拓扑排序后单遍松弛，O(V+E)"""
    dist = {v: inf for v in dag.vertices}
    dist[source] = 0
    prev = {}

    for u in topological_sort(dag):
        if dist[u] == inf: continue
        for v in dag.neighbors(u):
            w = dag.edge_weight(u, v)
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u

    path = backtrace(prev, source, sink)
    return path, dist[sink]

API 速查表¶

系统	核心 API / 文件	功能
FUEL	`frontier_finder.searchFrontiers(bbox)`	增量前沿检测
FUEL	`fast_exploration_manager.computeGlobalTour()`	ATSP 全局序列
FUEL	`fast_exploration_manager.refineLocalTour()`	DAG 局部精修
TARE	`tare_planner.updateGlobalPlan()`	粗糙全局 TSP
TARE	`tare_planner.updateLocalPlan()`	精细局部 TSP
LKH	`system("./LKH problem.par")`	TSP/ATSP 求解
OR-Tools	`RoutingModel.SolveWithParameters(params)`	VRP 求解
nbvplanner	`RrtTree.iterate()`	RRT 生长 + 增益计算

研究实践建议¶

入门级（本科生/硕士一年级）：

运行 nbvplanner 或 TARE 的仿真环境，理解探索的基本流程
精读 FUEL 的 frontier_finder.cpp，理解增量更新机制
实现 2D 版本的贪婪前沿探索

进阶级（硕士/博士）：

对比 FUEL/TARE/FALCON 在不同场景下的性能
在 FUEL 基础上添加 yaw 规划（RAPTOR 式图搜索）
尝试将 Active SLAM 的定位代价加入探索代价函数

研究级（博士/博后）：

3DGS + 主动感知的端到端系统
LLM 引导的语义探索
异构多机（地面 + 空中）协同探索

参考文献¶

核心论文:

[1] Yamauchi, B. (1997). "A Frontier-based Approach for Autonomous Exploration."
    CIRA 1997.

[2] Bircher, A., et al. (2016). "Receding Horizon NBV Planner for 3D Exploration."
    ICRA 2016 / Autonomous Robots 2018.

[3] Schmid, L., et al. (2020). "An Efficient Sampling-Based Method for Online
    Informative Path Planning in Unknown Environments." RA-L 2020.

[4] Cao, C., Zhu, H., Choset, H., Zhang, J. (2021). "TARE: A Hierarchical
    Framework for Efficiently Exploring Complex 3D Environments."
    RSS 2021 (Best Paper + Best System Paper).

[5] Zhou, B., Zhang, Y., Chen, X., Shen, S. (2021). "FUEL: Fast UAV Exploration
    Using Incremental Frontier Structure and Hierarchical Planning." RA-L 2021.

[6] Zhou, B., Pan, J., Gao, F., Shen, S. (2021). "RAPTOR: Robust and Perception-
    aware Trajectory Replanning for Quadrotor Fast Flight." TRO 2021.

[7] Zhou, B., Xu, H., Shen, S. (2023). "RACER: Rapid Collaborative Exploration
    With a Decentralized Multi-UAV System." TRO 2023 (Best Paper).

[8] Feng, C., et al. (2024). "FC-Planner: A Skeleton-guided Planning Framework
    for Fast Aerial Coverage of Complex 3D Scenes."
    ICRA 2024 (Best UAV Paper Finalist).

[9] Zhang, Y., Chen, X., et al. (2024). "FALCON: Fast Autonomous Aerial
    Exploration Using Coverage Path Guidance." TRO 2024.

[10] Yan, L., et al. (2023). "MUI-TARE: Cooperative Multi-Agent Exploration
     with Unknown Initial Position." RA-L 2023.

[11] Falanga, D., et al. (2018). "PAMPC: Perception-Aware Model Predictive
     Control for Quadrotors." IROS 2018.

补充参考:

[12] Helsgaun, K. (2017). "An Extension of the Lin-Kernighan-Helsgaun TSP Solver
     for Constrained Traveling Salesman and Vehicle Routing Problems."

[13] Hornung, A., et al. (2013). "OctoMap: An Efficient Probabilistic 3D Mapping
     Framework Based on Octrees." Autonomous Robots.

[14] Oleynikova, H., et al. (2017). "Voxblox: Incremental 3D Euclidean Signed
     Distance Fields for On-Board MAV Planning." IROS 2017.

[15] Lee, T., et al. (2010). "Geometric Tracking Control of a Quadrotor UAV
     on SE(3)." CDC 2010.

预计学习时间¶

2 周（20-28 小时），其中：

模块	内容	时间
§D7.1-D7.2	探索形式化、信息增益、NBV 范式、nbvplanner	4 小时
§D7.3	FUEL 的 FIS + 三层规划	4 小时
§D7.4	TARE 双分辨率、仿真环境	3 小时
§D7.5	RACER 多机、CVRP、成对交互	3 小时
§D7.6-D7.7	FALCON 覆盖路径引导、FC-Planner	2 小时
§D7.8	感知引导（yaw 规划、RAPTOR、PAMPC、VIO 可观性）	3 小时
§D7.9-D7.10	多机任务分配、感知-规划一体化	2 小时
§D7.11-D7.12	工程实践、前沿方向	2 小时
实战练习	A/B 型练习 + 思考题	5 小时

术语索引¶

本索引按主题归类全章术语，给出一句话定义和首次/主要出现的小节，便于回查。与 §本章小结的"术语速查表"互补——速查表只列最核心的 8 个，本索引覆盖全部。中英对照以英文全称为准。

A. 探索问题基础¶

术语（中/英）	一句话定义	主要小节
探索 / Exploration	在未知环境中边建图边决策"去哪里"以最快覆盖未知空间	§D7.1
覆盖规划 / Coverage Planning	在已知粗几何上规划路径以看全所有表面（非探索）	§D7.7
前沿 / Frontier	free 与 unknown 体素的边界，是"已知与未知的交界"	§D7.1
前沿簇 / Frontier Cluster	聚类后的一组相邻前沿体素，作为规划的基本单元	§D7.3
视点 / Viewpoint	一个候选的"位置 + yaw"组合，从此处观测某前沿	§D7.2
序贯决策 / Sequential Decision	当前决策改变未来可选项的多步决策结构（探索本质）	§D7.1

B. 信息论与 NBV¶

术语（中/英）	一句话定义	主要小节
信息增益 / Information Gain	某视点能新观测到的 unknown 体素数（或熵减少量）	§D7.2
射线投射 / Ray Casting	沿视线步进模拟传感器，统计命中的 unknown 体素	§D7.2
NBV / Next-Best-View	选信息增益最高的下一观测视点的范式	§D7.2
视锥 / View Frustum	传感器 FOV 张成的可视锥体，决定单次观测范围	§D7.11

C. 数据结构与规划算法¶

术语（中/英）	一句话定义	主要小节
FIS / Frontier Information Structure	FUEL 增量维护的前沿数据结构（dirty 标记局部更新）	§D7.3
增量更新 / Incremental Update	只重算地图变化包围盒内的前沿，避免全图扫描	§D7.3
TSP / Traveling Salesman Problem	访问所有节点一次且总代价最小的路径问题	§D7.3
ATSP / Asymmetric TSP	代价矩阵不对称（去↔回代价不同）的 TSP	§D7.3
DAG 最短路 / DAG Shortest Path	有向无环图上拓扑排序后单遍松弛求最短路，$O(V+E)$	§D7.14
B 样条 / B-spline	FUEL 轨迹后端用的分段多项式，凸包性保证安全	§D7.3
MINCO	FALCON 轨迹后端的最小控制量参数化	§D7.6
Set Cover / 集合覆盖	用最少集合（视点）覆盖全部元素（表面）的 NP-hard 问题	§D7.7
ROSA 骨架 / Rotational Symmetry Axis	从点云提取的物体一维中轴，用于空间分解	§D7.7

D. 多机协同与运筹¶

术语（中/英）	一句话定义	主要小节
VRP / Vehicle Routing Problem	多车辆分配 + 路由的联合组合优化（比多 TSP 难）	§D7.9
CVRP / Capacitated VRP	带容量（续航）约束的 VRP，RACER 所用	§D7.5
MD-VRP / Multi-Depot VRP	多仓库 VRP，MUI-TARE 所用	§D7.9
min-max 目标	最小化"最大单机代价"，追求负载均衡而非总量最优	§D7.9
成对交互 / Pairwise Interaction	相邻机器人局部交换任务，去中心逼近全局最优	§D7.5
hgrid / Hierarchical Grid	RACER 的稀疏分层栅格，可差分传输	§D7.5
去中心化 / Decentralized	无中心节点，靠局部协商达成全局协调	§D7.5

E. 感知引导¶

术语（中/英）	一句话定义	主要小节
微分平坦 / Differential Flatness	四旋翼状态/输入可由平坦输出 $(x,y,z,\psi)$ 及其导数表示	§D7.8
yaw 图搜索 / Yaw Graph Search	RAPTOR 在时间-yaw 格上做图搜索优化偏航	§D7.8
PAMPC / Perception-Aware MPC	把感知项写进 NMPC 代价的位置-yaw 联合优化	§D7.8
VIO 可观性 / VIO Observability	视觉惯性里程计能否稳定估计位姿（依赖纹理/特征）	§D7.10
Active SLAM	同时优化探索效率与定位精度的主动建图	§D7.10
感知-规划耦合 / Perception-Planning Coupling	从完全分离到端到端的四个耦合层次	§D7.10

F. 地图表示与评价¶

术语（中/英）	一句话定义	主要小节
ESDF / Euclidean Signed Distance Field	每点到最近障碍的带梯度距离场，规划的"硬通货"	§D7.11
TSDF / Truncated SDF	截断符号距离场，voxblox 的中间表示	§D7.13
OctoMap	基于八叉树的多分辨率概率占据地图	§D7.11
双分辨率 / Dual-Resolution	TARE 近处细、远处粗的分辨率粒度原则	§D7.4
EPEE	FALCON 提出的探索性能评价指标体系	§D7.6
$T_{95}/T_{99}$	达到 95%/99% 覆盖率所需时间，完成效率指标	§D7.6

使用建议：第一遍阅读时不必记忆本索引；遇到陌生缩写（如 ATSP、MINCO、ESDF）时回查即可。第二遍精读时，可遮住"一句话定义"列自测——若能复述某术语的定义和它在系统中的位置，说明该知识点已掌握。

困难	本质原因	后果
信息不完全	地图 \(M_t\) 随探索逐渐揭示，\(t\) 时刻无法知道 \(t+1\) 时刻的地图	不可能做全局最优规划，只能做在线滚动决策
NP-hard 子问题	即使知道所有前沿/视点的位置，最优访问顺序是 TSP/ATSP	精确求解不可行，必须用启发式近似
在线实时性	无人机以 2 m/s 飞行，必须在飞行中（毫秒级）做出决策	计算预算极其有限，不能离线跑优化器
感知-规划耦合	传感器朝向（yaw）影响观测范围，进而影响地图更新	规划必须同时决定"去哪里"和"看哪里"

增益度量	公式	适用场景	代表系统
加权体积增益	\(\text{IG}_w = \sum_{w \in S(\mathbf{v})} \frac{1}{\\|\mathbf{w}-\mathbf{v}\\|^2} \cdot \mathbb{1}[M(w) = \text{unknown}]\)	重视近处体素	nbvplanner
熵减少	$\text{IG}_H = H(M) - H(M	z_\mathbf{v}) = \sum_{w} [H(P(w)) - H(P(w	z_\mathbf{v}))]$
表面前沿增益	$\text{IG}_{\text{surf}} =	{w \in S(\mathbf{v}) : w \in \partial(\text{free} \cap \text{unknown}) \wedge w \text{ 靠近表面}}	$

优化策略	做法	加速比	代价
稀疏射线采样	减少射线数（\(16 \times 12 = 192\) 条）	4x	精度降低
自适应步长	在 ESDF 中按距离场步进（sphere tracing）	3-10x	需要 ESDF
增量更新	只对地图变化区域重新计算	10-100x	实现复杂
GPU 加速	并行射线投射（OctoMap-RT）	41x	需要 GPU
近似估计	用前沿体素数近似信息增益	100x+	精度最低

操作	全量方法（每帧）	FUEL 增量方法	加速
前沿检测	扫描全部 \(7.5 \times 10^6\) 体素	只扫描更新区域 ~\(10^4\) 体素	750x
射线投射	所有 RRT 节点（~1000 \(\times\) 768 条）	只对 dirty 簇的 ~15 视点	50x
路径代价	全部簇对的 A*	只对新增/变化的簇对	10-50x

场景	尺寸	特点	测试重点
Campus	340m \(\times\) 340m	起伏地形 + 复杂布局	全局方向规划
Indoor Corridors	130m \(\times\) 100m	长窄走廊 + 大厅	狭窄空间导航
Multi-story Garage	140m \(\times\) 130m, 5 层	多层 + 斜坡	3D 跨层规划
Tunnel Network	330m \(\times\) 250m	分叉 + 死胡同	拓扑探索、回溯
Forest	150m \(\times\) 150m	树木 + 房屋	杂乱避障
Matterport3D	真实室内扫描	多房间 + 家具	真实感室内

挑战	本质	如果不解决
任务分配	如何将未探索空间分给 \(N\) 台？	多机重复覆盖同一区域，\(N\) 倍加速退化为 1.5 倍
通信约束	不一定能随时通信	集中式方案需要全连接——不可扩展
地图融合	不同机器人的局部地图如何合并？	无法做全局任务分配

指标	公式	含义
体积效率 \(\eta_V\)	\(V_{\text{explored}} / (v_{\text{avg}} \cdot T)\)	单位时间单位速度探索的体积
移动效率 \(\eta_T\)	\(V_{\text{explored}} / D_{\text{total}}\)	单位移动距离探索的体积
覆盖连续性 \(C\)	\(1 - N_{\text{revisit}} / N_{\text{total}}\)	不重复访问的比例
\(T_{95}\) / \(T_{99}\)	达到 95%/99% 覆盖率的时间	完成效率

场景	FALCON \(T_{95}\)	FUEL \(T_{95}\)	TARE \(T_{95}\)
Indoor (130m\(\times\)100m)	180s	310s	240s
Campus (340m\(\times\)340m)	420s	780s	520s

方法	公式	含义
Fisher 信息矩阵	\(\lambda_{\min}(\mathbf{I}(\theta))\)	最弱方向的信息量
特征共视性	\(N_{\text{covis}}(v_1, v_2)\)	连续帧共视特征数
可定位走廊	\(L_{\text{score}}(t) \geq L_{\text{threshold}}\)	沿轨迹的可定位性分数

特性	深度相机	LiDAR
FOV	\(60^\circ \times 45^\circ\) ~ \(90^\circ \times 60^\circ\)	\(360^\circ \times 30^\circ\) ~ \(70^\circ \times 77^\circ\)
最大距离	5-10 m（结构光）; ~20 m（ToF）	30-200 m
重量	5-72 g	500g-1kg
yaw 规划重要性	关键（FOV 窄）	相对次要（FOV 宽）
代表系统	FUEL, RACER	TARE, FALCON

地图表示	优点	缺点	代表系统
OctoMap	多分辨率、概率更新	查询 \(O(\log N)\)、无距离场	nbvplanner
voxblox (TSDF/ESDF)	查询 \(O(1)\)、有距离场	固定分辨率、内存大	FUEL
滚动栅格	固定内存	只保留局部	TARE
混合	取长补短	实现复杂	FALCON

能力	占据概率（OctoMap）	距离场（ESDF/voxblox）
碰撞检测	离散"是/否"，需逐点查询 \(O(\log N)\)	连续距离，\(O(1)\) 查询，一次判 \(d<d_{\text{safe}}\)
梯度优化	无梯度，无法做连续优化	\(\nabla d\) 现成，可推安全代价梯度
安全裕度	只知碰/不碰	知道"离障碍还有多远"，可设软裕度
视点安全判据	需另算	直接用 \(\text{ESDF}(p) > d_{\text{safe}}\)

方法	复杂度	实际可行规模
暴力枚举	\(O(n!)\)	\(n \leq 12\)
Held-Karp DP	\(O(n^2 \cdot 2^n)\)	\(n \leq 25\)
Concorde 分支定界	指数级（实际快很多）	\(n \leq 85000\)
LKH 启发式	约 \(O(n^{2.2})\) 实测	\(n \leq 10^6\)

术语（中/英）	一句话定义	主要小节
微分平坦 / Differential Flatness	四旋翼状态/输入可由平坦输出 \((x,y,z,\psi)\) 及其导数表示	§D7.8
yaw 图搜索 / Yaw Graph Search	RAPTOR 在时间-yaw 格上做图搜索优化偏航	§D7.8
PAMPC / Perception-Aware MPC	把感知项写进 NMPC 代价的位置-yaw 联合优化	§D7.8
VIO 可观性 / VIO Observability	视觉惯性里程计能否稳定估计位姿（依赖纹理/特征）	§D7.10
Active SLAM	同时优化探索效率与定位精度的主动建图	§D7.10
感知-规划耦合 / Perception-Planning Coupling	从完全分离到端到端的四个耦合层次	§D7.10