作者： 19届 lz

论文：《FUEL: Fast UAV Exploration using Incremental Frontier Structure and Hierarchical Planning》

问题:

(a)现有自主探索方法缺乏有效的全局覆盖、保守的运动计划和较低决策频率。
(b)许多现有的自主探索方法以贪婪的方式探索运动，例如最大化即时信息增益，或者导航到最近的未知区域。贪心策略忽略了全局最优性，因此导致整体效率低下。
此外，大多数方法会产生相当保守的运动，以在以前未知的环境中同时保证信息增益和安全性。探索速度低。
(d)最后但并非最不重要的一点是，许多方法的计算开销很大，并且不能快速和频繁地响应环境变化。然而，为了实现更快的探索，只要有新的环境信息可用，就需要立即重新规划新的运动。

贡献:

1. 增量更新的 FIS(frontier information structure)，它捕获整个探索空间的基本信息并促进高频探索计划。
2. 一种分层​​规划方法，可生成高效的全局覆盖路径，以及用于高速探索的安全敏捷的局部机动。
   
   
   
   

研究过程及结果：

顶部：检测和移除过时的边界。
底部：检测到新边界（左）并执行 PCA，大集群被分成两个较小的集群（右）。

红色的Bm是更新后边界区域的AABB框(axis-aligned bounding box/轴对齐边界框)。
每次通过传感器测量更新地图时，更新区域 Bm 的 AABB(axis-aligned bounding box/轴对齐边界框) 也会被记录下来，在其中删除过时的边界聚类并搜索新的边界聚类。
具体流程:
1.遍历所有的边界集群，返回Bi与Bm相交的点。
2.对返回的集群进行精确检查，其中包含不再属于边界单元的集群将被删除

去除后，通过区域增长算法搜索新的边界并将其聚类成组。
在这些组中，由传感器观察产生的噪声通常被忽略(cell较少)。
然而，其余的组可能包含大尺寸的集群，不利于区分独特的未知区域和做出详细的决策。因此，我们对每个集群执行主成分分析 (PCA)，如果最大特征值超过阈值，则沿着第一个主轴将其分成两个统一的集群。拆分是递归进行的，以便将所有大集群划分为小集群。

为前沿集群生成候选视点。在以簇的平均位置为中心的圆柱坐标系内，点被均匀采样。对于位于自由空间内的每个采样点 p，确定最大化传感器覆盖到集群的角度。

tlb(xk1,j1, xk2,j2) 表示在两个视点 xk1,j1 和 xk2,j2 之间移动时的时间下界
vmax 和˙ξmax 是偏航速度和角速率的限制

步骤生成探索运动：
(1)全局规划: 找到覆盖整个环境中前沿集群的最短路径(旅行商问题)。
(非对称TSP:通过找到最优的闭环回路并检索其等价的开环回路来获得最优的开环回路)

(2)局部改善: 对全局规划的局部片段进行细化。

全球旅游规划找到了访问所有集群的有希望的顺序。尽管如此，它只涉及每个集群的单个视点，这不一定是所有视点中的最佳组合。
所以局部提供更多的视点来考虑
利用 Dijkstra 算法来使成本最小化

(3)最小时间B样条轨迹: 生成一条安全的最短时间轨迹到细化游的第一视点。

进一步优化B样条的所有参数，从而使总轨迹时间最小化
平衡平滑度和总体时间，并且保证了安全和运动可达

实验结果

算法每部分平均用时

不同算法路径比较

conclusion

分层规划器分三个连续步骤规划探索运动，找到有效的全局路径，选择一组局部最优视点，并生成最短时间的局部轨迹。

运行结果