深度解读 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 考虑了无人机的加减速动力学。两点间的转移时间被计算为 ：
这个公式确保了规划器倾向于选择顺畅的直线路径，而不是需要频繁急停急转的路径。
B. 增量式规划策略 (Incremental Planning) [核心创新]
为了解决大场景下 TSP 求解慢的问题，FASTEX 提出了一种“近细远粗”的策略 ：
图 (c)：新的规划结果 (The Result)
局部范围 (
) 内：保留所有独立节点，进行精细规划。
局部范围 (
) 外：利用上一帧的规划结果，将连续的远端节点打包成线段 (Segments)。
数学建模：在构建 ATSP 代价矩阵时，线段内部的连接代价被设为
（负无穷），强制求解器必须按顺序访问线段，从而将 N 个节点的排序问题降维成少量线段的排序问题 。
这张图解释了系统是如何在毫秒级的时间内，更新一条横跨整个大地图的规划路径的。它的核心逻辑可以概括为：“近处精细算，远处打包算”。
我们按 (a) -> (b) -> (c) 的顺序来拆解这个过程：
图 (a)：上一秒的记忆 (The Past)
状态：这是无人机在上一时刻规划好的全局路径。
紫红色的折线 (Last Global path)：连接了所有当时已知的“未知区域中心点”（灰点）。
问题：随着无人机（中间的X）向前飞，它发现了新的环境信息（比如前面的橙色/绿色格子），而且原来的路径可能已经不再是最优的了，必须重算。
图 (b)：聪明的分类与压缩 (The Process)
这是算法发挥“魔法”的时刻。系统没有把所有点扔进池子里重算，而是进行了分类：
划定“精算区” (Local Range)：
看到那个粗的蓝色虚线框了吗？这是以无人机为中心的局部范围（Local Range,
）。
在这个框以内的点（带有粉色光圈的点），被认为是“当务之急”，保留为独立节点，参与全量计算。
远处“打包” (Segmentation)：
在蓝色框以外的路径，被认为是“以后再去的地方”。
注意上方和右侧的深蓝色虚线椭圆 (Segments)。算法把这些远处的连续节点直接打包成了线段 。
省流原理：算法不再关心椭圆内部这几个点怎么走（因为上一秒已经算过了），只关心从哪里进（粉圈 Entry）、从哪里出（蓝圈 Exit）。这把几十个点的计算量瞬间压缩成了2个点。
吸纳新目标 (New Discovery)：
注意左下角和右上角的红框 (New Grid)和红点 (New unknown region)。
这是无人机刚刚探测到的新未知区域。它们被直接加入到了当前的规划池中 。
粉红色的实线 (New Global path)：这是求解 ATSP 后生成的新路径。
路径逻辑：
无人机先处理了近处新发现的红点（左下角）。
然后顺路去看了近处原本遗留的灰点。
最后才飞向远处的“打包线段”（右上角）。
关键点：注意右上角那个红点（新发现的远方目标），它被插入到了路径的末端。算法非常智能地把新任务插入到了全局最优的位置，而没有打乱远处线段内部的顺序。
2. 局部 SOP 规划 (Local SOP Planning)
目标：在全局路径的引导下，优化局部视点 (Viewpoints) 的访问顺序，生成平滑轨迹。
问题建模：这是一个顺序排序问题 (SOP)。
图 (b)：规划后的结果 (SOP Result)
右图展示了计算出的最终飞行路径（绿色实线）：
广义节点：将全局路径中剩余的部分看作一个“超级节点”。
约束矩阵：
矩阵下三角的
是硬约束，意味着必须先完成当前行的任务，才能执行下一行的任务。这保证了机器人不会为了贪图远处的一个点而打乱整体的覆盖节奏。
简单来说，这张图回答了这样一个问题：“当全局导航告诉我‘往东走’，但我发现身边有一堆零散的角落没看时，我该先看哪个，再怎么顺路接上大方向？”
以下是分步拆解：
图 (a)：规划前的状态与输入
左图展示了机器人（无人机）在做局部决策时面临的信息：
当前位置 (X)：
图中间那个黑色的X代表无人机的位置。
眼前的任务 (Viewpoints)：
无人机附近有一些黄色的方块（Frontiers，未探索边界）。
- 为了看清这些边界，算法生成了几个小圆点（Viewpoints，视点），即图中央那一簇橙色/绿色的小点。这是无人机必须要去的地方 。
远方的指引 (Global Path)：
粉红色的折线是全局规划器算出来的路径。它连接了所有灰色的点（未知区域中心）。
这条线的意义是告诉无人机：“大方向是沿着粉线往右上方探索”。
分段策略 (Segmentation)——关键细节：
请注意那些蓝色的虚线椭圆 (Segments)。
算法把远处的那些灰色点打包成了“线段（Segment）”。
粉色虚线圈是“入口点 (Entry node)”，蓝色虚线圈是“出口点 (Exit node)” 。
意义：对于远处的路，局部规划器不需要关心具体怎么走，只需要知道“从哪进、从哪出”就行，这样简化了计算。
先清理局部 (Local Exploration)：
- 绿线从X出发，并没有直接飞向远方，而是先灵巧地串联了附近那几个视点（Viewpoints）。这保证了无人机能把身边的死角先扫干净，避免以后还要折返 。
顺势切入全局 (Align with Global)：
扫完局部视点后，绿线非常顺滑地连接到了最近的一个独立节点 (Independent node)（绿色虚线圈里的灰点）。
随后，它沿着全局路径（粉线）的方向，指向了远处蓝色椭圆的“入口”。
顺序约束 (Constraints)：
注意绿线是严格顺着粉线的流向走的。
SOP 算法在数学上强制了这种顺序（通过将逆向代价设为 -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秒内完成了的森林探索，轨迹平滑且几乎没有冗余的重复访问 。
五、 总结与启示
FASTEX 的成功给所有从事移动机器人探索（包括水下机器人）的研究者提供了两个重要的设计思路：
不要浪费远处的信息：即使传感器精度在远处下降，用它来构建粗略的连通性图 (Connectivity Graph) 也能大幅提升规划的全局视野。
增量式思维：在动态环境中，完全重算往往是没必要的。“局部精细更新 + 全局拓扑维护”是解决大规模问题的金钥匙。
对于水下扫测应用，FASTEX 的Segment思想尤为可贵——可以将长距离的声纳扫测条带视为一个 Segment，只在转弯换线（局部）时进行精细的动力学规划，这将极大节省板端计算资源。
（支持资料、图片参考_相关定制）_文章底部可以扫码)
