Active Exploration方向论文精读

FASTEX 的成功给所有从事移动机器人探索（包括水下机器人不要浪费远处的信息：即使传感器精度在远处下降，用它来构建粗略的连通性图 (Connectivity Graph) 也能大幅提升规划的全局视野。增量式思维：在动态环境中，完全重算往往是没必要的。局部精细更新 + 全局拓扑维护”是解决大规模问题的金钥匙。对于水下扫测应用，FASTEX 的Segment思想尤为可贵——可以将长距离的声纳扫测条带

大‭‭麒麟儿

388人浏览 · 2026-02-04 11:17:53

大‭‭麒麟儿 · 2026-02-04 11:17:53 发布

深度解读 FASTEX：大场景无人机自主探索的“极速”之道

论文题目：FASTEX: Fast UAV Exploration in Large-Scale Environments Using Dynamically Expanding Grids and Coverage Paths

会议来源：IROS 2025 (Hangzhou, China)

核心关键词：自主探索、覆盖路径规划、动态网格、增量式规划、ATSP/SOP

在大规模复杂环境（如茂密森林、地下洞穴）中进行自主探索，一直是移动机器人领域的“硬骨头”。现有的顶尖算法（如 FUEL, TARE, RACER）往往面临着两难抉择：要么为了算得快而牺牲全局覆盖率，要么为了追求完美路径而导致计算量爆炸 。

2025年 IROS 的这篇 FASTEX 论文提出了一套全新的解决方案，通过高效的环境预处理和层次化的增量规划框架，实现了探索效率与计算速度的双重突破。

本文将从原理层面，带你详细拆解它的三大核心模块。

一、核心痛点与解决思路

在传统的探索框架中，随着地图的扩大，系统需要处理的数据量呈指数级增长。主要瓶颈在于：

地图维护重：仅更新传感器截断距离内的地图，浪费了远处的感知信息。
路径搜索慢：在大尺度栅格地图上进行 A* 搜索极其耗时。
重复路径多：贪婪策略容易导致机器人频繁“折返跑

FASTEX 的破局之道：

预处理层：用 动态扩展网格 (DEGrids) 替代传统固定边界，并构建 稀疏路线图 (Sparse Roadmap) 加速搜索。
决策层：将全局规划建模为 ATSP (非对称旅行商问题)，并采用增量式 (Incremental) 更新策略；将局部规划建模为 SOP (顺序排序问题) 以保证执行连贯性。

这是真实森林里的探索结果。注意那条红色的轨迹，它非常平滑且覆盖了整个区域，没有像无头苍蝇一样乱撞。

这是系统的“大脑结构图”。

左边是 环境预处理 (Preprocessing)：负责把复杂的点云简化成网格和路线图。
右边是 分层规划 (Hierarchical Planning)：先由 Global Planner 定大方向，再由 Local Planner 走好脚下的路。

二、高效环境预处理 (Efficient Environment Preprocessing)

这一模块是整个系统“快”的基础。

1. 动态扩展网格 (DEGrids)

传统方法通常会截断 LiDAR 数据（例如只保留 15m 内的点）。FASTEX 认为，远处的数据虽然稀疏，但足以判断区域的连通性 。

机制：网格不是预先分配的，而是根据点云实时生成的。
状态机：每个网格维护三种状态：
- Unexplored (未探索)：刚初始化的网格。
- Exploring (探索中)：网格内检测到了新的边界点 (Frontiers)。
- Explored (已探索)：网格内的边界点已被清空。
  
  这种设计让系统能快速锁定“哪里还有未知区域”，而无需遍历整个地图。

无人机 (UAV) 在中间。
蓝色格子 (Existing Grids)：是已经建立的已知区域。
红色格子 (New Grids)：这是亮点！无人机探测到了传感器截断距离以外的点，系统没有丢弃它们，而是立刻生成了红色的新网格。
意义：这让无人机有了“超视距”的感知能力，知道远处哪里可能通，不用飞到了再算。

2. 增量式稀疏路线图 (Incremental Roadmap)

为了避免在稠密的体素地图上跑 A*，系统构建了一个稀疏图：

节点来源：
- 固定节点：在 DEGrids 生成时按固定分辨率采样。
- 随机节点：在传感器更新范围内随机撒点（增强连通性）。
- 动态激活：只有处于“Exploring”状态网格内的节点才是活跃 (Active) 的。一旦网格变为“Explored”，其内部节点自动休眠 (Inactive)，不再参与路径搜索。这使得搜索图的规模始终维持在一个较小水平，不随环境变大而膨胀。
- 图解：
- 蓝色点 (Fixed Nodes)：每个格子里固定生成的“公交站点” 。
- 橙色点 (Random Nodes)：在空旷区域随机撒的“临时停靠点”，增加连通性。
- 实线 (Active Edge)：当前正在探索区域的路，是通的。
- 虚线 (Inactive Edge)：后面灰色的区域（Explored Grid）已经探索完了，路网自动休眠，不再参与计算。
- 意义：用完即弃。只维护无人机附近的活跃路网，计算量不再随地图变大而爆炸。

三、层次化探索规划 (Hierarchical Exploration Planning)

这是论文的算法核心，分为全局和局部两层。

1. 全局覆盖路径规划 (Global Coverage Path Planning)

目标：规划一条能遍历所有可达未知区域 (Reachble Unknown Regions, RUR) 的最短时间路径。

A. 物理感知的时间代价模型

不同于简单的欧几里得距离，FASTEX 考虑了无人机的加减速动力学。两点间的转移时间t被计算为：

这个公式确保了规划器倾向于选择顺畅的直线路径，而不是需要频繁急停急转的路径。

B. 增量式规划策略 (Incremental Planning) [核心创新]

为了解决大场景下 TSP 求解慢的问题，FASTEX 提出了一种“近细远粗”的策略：

这张图解释了系统是如何在毫秒级的时间内，更新一条横跨整个大地图的规划路径的。它的核心逻辑可以概括为：“近处精细算，远处打包算”。

我们按 (a) -> (b) -> (c) 的顺序来拆解这个过程：

图 (a)：上一秒的记忆 (The Past)
状态：这是无人机在上一时刻规划好的全局路径。
紫红色的折线 (Last Global path)：连接了所有当时已知的“未知区域中心点”（灰点）。
问题：随着无人机（中间的 X）向前飞，它发现了新的环境信息（比如前面的橙色/绿色格子），而且原来的路径可能已经不再是最优的了，必须重算。
图 (b)：聪明的分类与压缩 (The Process)

这是算法发挥“魔法”的时刻。系统没有把所有点扔进池子里重算，而是进行了分类：

划定“精算区” (Local Range)：
- 看到那个粗的蓝色虚线框了吗？这是以无人机为中心的局部范围（Local Range, $R_l$ ）。
- 在这个框以内的点（带有粉色光圈的点），被认为是“当务之急”，保留为独立节点，参与全量计算。
远处“打包” (Segmentation)：
- 在蓝色框以外的路径，被认为是“以后再去的地方”。
- 注意上方和右侧的深蓝色虚线椭圆 (Segments)。算法把这些远处的连续节点直接打包成了线段。
- 省流原理：算法不再关心椭圆内部这几个点怎么走（因为上一秒已经算过了），只关心从哪里进（粉圈 Entry）、从哪里出（蓝圈 Exit）。这把几十个点的计算量瞬间压缩成了2个点。
吸纳新目标 (New Discovery)：
- 注意左下角和右上角的红框 (New Grid) 和 红点 (New unknown region)。
- 这是无人机刚刚探测到的新未知区域。它们被直接加入到了当前的规划池中。
粉红色的实线 (New Global path)：这是求解 ATSP 后生成的新路径。
路径逻辑：
1. 无人机先处理了近处新发现的红点（左下角）。
2. 然后顺路去看了近处原本遗留的灰点。
3. 最后才飞向远处的“打包线段”（右上角）。
关键点：注意右上角那个红点（新发现的远方目标），它被插入到了路径的末端。算法非常智能地把新任务插入到了全局最优的位置，而没有打乱远处线段内部的顺序。
图 (c)：新的规划结果 (The Result)
局部范围内：保留所有独立节点，进行精细规划。
局部范围外：利用上一帧的规划结果，将连续的远端节点打包成线段 (Segments)。
数学建模：在构建 ATSP 代价矩阵时，线段内部的连接代价被设为负无穷，强制求解器必须按顺序访问线段，从而将 N 个节点的排序问题降维成少量线段的排序问题。

2. 局部 SOP 规划 (Local SOP Planning)

目标：在全局路径的引导下，优化局部视点 (Viewpoints) 的访问顺序，生成平滑轨迹。

问题建模：这是一个 顺序排序问题 (SOP)。

简单来说，这张图回答了这样一个问题：“当全局导航告诉我‘往东走’，但我发现身边有一堆零散的角落没看时，我该先看哪个，再怎么顺路接上大方向？”

以下是分步拆解：

图 (a)：规划前的状态与输入

左图展示了机器人（无人机）在做局部决策时面临的信息：
当前位置 (X)：
- 图中间那个黑色的 X 代表无人机的位置。
眼前的任务 (Viewpoints)：
- 无人机附近有一些黄色的方块（Frontiers，未探索边界）。
- 为了看清这些边界，算法生成了几个小圆点（Viewpoints，视点），即图中央那一簇橙色/绿色的小点。这是无人机必须要去的地方。
  - 这里补充一下，如何生成的小圆点呢？
    1. 第一步：找到“边界” (Frontiers Extraction)
    
    视点存在的意义是为了消除未知。所以首先要找到已知空间 (Free Space) 和 未知空间 (Unknown Space) 的交界处。
  - 做法：系统遍历体素地图，如果一个体素是“未知的”，但它旁边紧挨着“已知的空闲”体素，那它就是边界体素 (Frontier Voxel) 。
  - 结果：这一步得到了一堆零散的边界点。
  - 2. 第二步：计算“朝向” (Normal Estimation)
    
    找到边界还不够，无人机必须知道站在哪里看才能看清这个边界。这就需要计算边界的法向量 (Normal)。
  - 核心逻辑：如果一面墙在我面前，我必须正对着它看，而不是站在侧面或后面。
  - 公式 (Equation 1)：论文通过计算边界体素周围 K×K×K个邻域内的几何中心偏移量来估算法向量
  - - 这里的 $s_j$ 是权重，只有当邻居体素是“空闲 (Free)”时才为 1，否则为 0。
    - 目的：确保算出来的法向量 $n_i$ 也是指向空闲空间的（即无人机可以飞到的地方）
  - 3. 第三步：聚类与采样 (Clustering & Sampling)
    
    如果对每一个边界体素都生成一个视点，计算量会太大。
  - 聚类：将空间上挨得很近的一大坨边界体素打包成一个簇 (Cluster) 。
  - 采样生成：对于每一个簇，根据它包含的边界点的平均位置和平均法向量，反推一个最佳观测位置。
    - 这个位置通常位于：边界中心 + 沿法向量方向延伸一定距离。
    - 形象理解：假设发现了一块未知的“黑幕”，算法算出黑幕的中心，然后沿着垂直于黑幕的方向往后退几米，那个位置就是生成的视点 (Viewpoint)。
远方的指引 (Global Path)：
- 粉红色的折线是全局规划器算出来的路径。它连接了所有灰色的点（未知区域中心）。
- 这条线的意义是告诉无人机：“大方向是沿着粉线往右上方探索”。
分段策略 (Segmentation) —— 关键细节：
- 请注意那些蓝色的虚线椭圆 (Segments)。
- 算法把远处的那些灰色点打包成了“线段（Segment）”。
- 粉色虚线圈是“入口点 (Entry node)”，蓝色虚线圈是“出口点 (Exit node)” 。
- 意义：对于远处的路，局部规划器不需要关心具体怎么走，只需要知道“从哪进、从哪出”就行，这样简化了计算。
先清理局部 (Local Exploration)：
- 绿线从 X 出发，并没有直接飞向远方，而是先灵巧地串联了附近那几个视点（Viewpoints）。这保证了无人机能把身边的死角先扫干净，避免以后还要折返。
顺势切入全局 (Align with Global)：
- 扫完局部视点后，绿线非常顺滑地连接到了最近的一个独立节点 (Independent node)（绿色虚线圈里的灰点）。
- 随后，它沿着全局路径（粉线）的方向，指向了远处蓝色椭圆的“入口”。
顺序约束 (Constraints)：
- 注意绿线是严格顺着粉线的流向走的。
- SOP 算法在数学上强制了这种顺序（通过将逆向代价设为 -1），防止无人机因为贪图距离近，跳过中间的步骤直接飞到远处的出口。
图 (b)：规划后的结果 (SOP Result)

右图展示了计算出的最终飞行路径（绿色实线）：
广义节点：将全局路径中剩余的部分看作一个“超级节点”。
约束矩阵：

矩阵下三角的 $-1$ 是硬约束，意味着必须先完成当前行的任务，才能执行下一行的任务 。这保证了机器人不会为了贪图远处的一个点而打乱整体的覆盖节奏。

四、实验数据与效果

研究团队在模拟器 (MARSIM) 和真实环境（森林、花园）中进行了广泛测试，对比了 FUEL, RACER, GBP, TARE 等主流算法。

1. 效率对比 (Efficiency)

在森林、走廊和洞穴三个场景中，FASTEX 的探索时间最少，相比其他算法提升了 25% ~ 30% 。

森林场景：比 RACER 快 29.4%。
走廊场景：比 TARE 快 25.8%。

2. 计算开销 (Computational Cost)

这是最惊人的数据。得益于稀疏路线图和增量规划，FASTEX 的单次规划耗时极低：

平均规划耗时：仅需 0.04s ~ 0.09s 。
相比之下，GBP 和 TARE 在复杂场景下往往需要数秒甚至更长。

3. 实机验证

在配备 Intel NUC (i7) 和 Livox Mid-360 LiDAR 的四旋翼无人机上，FASTEX 成功在 608秒内完成了 $90 \times 90 \times 6 m^3$ 的森林探索，轨迹平滑且几乎没有冗余的重复访问。

五、总结与启示

FASTEX 的成功给所有从事移动机器人探索（包括水下机器人）的研究者提供了两个重要的设计思路：

不要浪费远处的信息：即使传感器精度在远处下降，用它来构建粗略的连通性图 (Connectivity Graph) 也能大幅提升规划的全局视野。
增量式思维：在动态环境中，完全重算往往是没必要的。“局部精细更新 + 全局拓扑维护”是解决大规模问题的金钥匙。

对于水下扫测应用，FASTEX 的 Segment 思想尤为可贵——可以将长距离的声纳扫测条带视为一个 Segment，只在转弯换线（局部）时进行精细的动力学规划，这将极大节省板端计算资源。

1. 根据当前视角定义下一最佳视角

对应文章 III. 高效环境预处理（III.A-III.C），核心是通过环境感知与候选视点生成，明确 “潜在最佳视角” 的范围与筛选标准：

动态网格扩展（III.A）：基于实时点云数据增量创建网格，标记 “未探索 / 探索中 / 已探索” 状态，锁定可达未知区域（RUR），为视角定义划定空间范围。
稀疏路线图构建（III.B）：生成固定节点（网格内）和随机节点（地图更新范围），动态标记活跃 / 非活跃状态，确保候选视角的可达性校验基础。
边界提取与视点采样（III.C）：提取自由空间与未知空间的边界体素，计算指向自由空间的法向量，聚类形成边界簇后，基于簇内体素和法向量采样候选视点，完成 “下一最佳视角” 的候选集定义。

2. 下一视角的选择

对应文章 IV. 分层探索规划（IV.A-IV.C），核心是通过全局优先级约束与局部优化，从候选集中筛选出最优视角：

未知区域连通图（IV.A）：建模可达未知区域的连通关系，仅保留有探索价值的 RUR centroids 作为全局规划节点，缩小视角选择的空间范围。
全局覆盖路径规划（IV.B）：通过增量式 ATSP 算法，优先规划邻近未知区域的全局路径，确定下一视角所在的目标区域优先级。
局部 SOP 规划（IV.C）：将局部候选视点与全局路径约束结合，构建 SOP 成本矩阵（强制局部视角访问顺序与全局一致），筛选出 “旅行成本最低、覆盖效率最高” 的具体下一视角（确保首目标为视点）。