Cao, Chao, et al. "TARE: A Hierarchical Framework for Efficiently Exploring Complex 3D Environments." Robotics: Science and Systems. 2021. 卡内基梅隆大学 PDF

1. 概述

自主探索存在的难点：

• 实时更新环境表示以跟踪已知区域
• 规划连续可遍历路径以指导探索
• 对于大型环境，需要确保对环境的完整探索

贡献点： 提出一种在复杂三维环境下的分层自主探索方法

• 一层密集维护数据，在局部范围内计算详细路径
• 一层稀疏维护数据，在全局范围内计算粗糙路径

在绿色立方体内，对路径进行详细规划

离开子区域后，在自由空间进行移动，前往下一个需要详细规划的子区域

2. 方法

2.1 视点采样

计算局部路径，需要先对视点进行采样，由离散的点转换为路径

将局部区域、未覆盖面、当前视点和两个边界点作为输入，生成局部路径

首先在局部区域内生成一组候选视点，计算每个候选视点的奖励，以此作为优先级；进入K次迭代，每次迭代都会生成一条局部路径，选择最佳路径作为最终输出。在迭代中，每次概率选择一个视点，并更新其他视点的优先级。将采样所得视点，作为算法2的输入。

2.2 路径生成

给定一组采样视点，需要生成穿过每个视点的最佳路径

将局部区域、视点集作为输入，生成局部路径

首先通过$A*$算法计算每个视点对之间的最短距离，再由TSP算法计算通过每个视点的最短路径，将每个视点设置为断点后，进入平滑阶段。由于机器人需要在断点处停止，因此平滑阶段的主要任务是，尽可能将视点转为为内点。在平滑阶段，尝试将每个视点设置为内点，之后计算若该视点为内点的代价，如果代价更小，则进行转换。最终输出该视点集的最佳路径。

2.3 全局路径规划

在局部空间中需要进行详细规划，在全局空间中，要对多个子区域进行粗略规划，找到一条全局路径。

在全局规划中，将子空间的质心作为视点，同样使用$A*$算法计算质心之间的最短距离，再通过TSP算法规划最短路径。提取出局部空间与全局空间的两个边界视点，再由算法1对局部路径进行详细计算，最终将全局和局部路径进行合并，生成最终路径。

3. 实验

实验环境： 使用地面和空中机器人进行评估

• 地面机器人探索复杂的多仓库建筑内部环境
• 空中机器人探索大型室外环境

对比实验： NBVP、GBP、MBP

• 表1比较了每秒探索效率和相对比值
• 表2展示了在该方法中，主要的时间消耗在局部路径规划，并且不会由于环境复杂度的提高而产生不同的代价规模
• 表3展示不同的局部空间范围对实验的影响，随着范围的扩大，局部规划的计算量会不断增加

实验结果： 相比于之前最先进的方法，在计算量降低50%以上的情况下，探索效率提高了80%

4. 结论

采用分层框架，对局部数据进行详细处理，对全局数据进行粗略处理，可以有效提高整体效率

动态TSP方法可以用于求解视点集的最短遍历顺序，减低探索代价