【Hierarchical Coverage Path Planning in Complex 3D Environments】

算法分两层，一层高级一层低级：
高层算法将环境分离多个子空间，如果给定体积中有大量的结构，则空间会进一步细分。全局TSP问题；低层算法采用简单的采样路径规划，解决每一个子空间的详细覆盖扫描问题。

视点采样

选择视点，并在各个子空间中计算详细的覆盖路径以形成路径。一个视点信息包含 位置信息x,y,z，和三维旋转角pitch,roll,yaw ：[x,y,z,roll,pitch,yaw]；roll = 0;

规定视点距离表面的距离D；在八叉树地图中保存视点，对空间进行划分。如果一个空间中的视点个数大于一定数量，这个空间将被细分为8个子空间。

全局TSP

将视点放入八叉树地图中，根据以上的视点个数原则对八叉树进行划分，获得子空间；用TSP求解器确定子空间的访问顺序；再遍历每一个子空间，用TSP求解器求出子空间中视点的最佳访问顺序，作为无人机的初始搜索路径。当计算TSP巡回时，子空间中的开始视点和结束视点分别被选择为最接近前个子空间的结束视点和下个子空间的开始视点。处理的两个步骤对许多K∈Z+迭代重复。然后，来自子空间的最短路径被级联，以在算法2中的行19上形成整个覆盖路径。

其中，在子空间的遍历中，SelectViewpoints子空间中的视点选取法则根据最小基数选取，考虑视点覆盖区域的大小作为优先级，视点选取的概率与优先级成正比，随机选取（而不是直接选取覆盖区域最大的视点），选取视点完成后，适当减少其他视点的奖励（优先级），直到没有更多的可接受奖励的视点为止。输出的表示子空间全覆盖视点。