文献精读：FUEL: Fast UAV Exploration Using Incremental Frontier Structure and Hierarchical Planning

• 主要分为两个部分：Incremental Frontier Information Structure前沿信息处理；Hierarchical Planning用于体育规划

Incremental Frontier Information Structure

• Frontier Information Structure (FIS)

  • 对应每一个前沿簇 $F_i$ 建立一个 $F{I}_i$
  • 包括以下参数：
  • $C_i$ ：包含在簇中的前沿单元
  • ${\mathbf{p}}_{avg,i}$ ：$C_i$ 的平均位置
  • $B_i$ ：$C_i$ 的 Axis-aligned bounding box
  • $V{P}_i$ ：覆盖簇的视点集
  • $L_{cost,i}$ ：存储簇与簇之间cost的双链列表

• Incremental Frontier Detection and Clustering

  • 每次更新地图后，都记录更新区域的bounding box $B_m$
  • 对 bounding box 与 $B_m$ 相交的前沿簇进行检查，如果包含不再是前沿的单元，则将该前沿簇移除
  • 搜索新前沿并组成簇
  • 对于较大尺寸的簇，采用Principal Component Analysis(PCA) 递归地分为小簇

• Viewpoint Generation and Cost Update

  • 创建一个簇 $F_i$ 时，生成一个视点集 V P i = { x i , 1 , x i , 2 , . . . , x i , n i } VP_i=\{\mathbf{x}_{i,1},\mathbf{x}_{i,2},...,\mathbf{x}_{i,n_i}\} VPi​={ xi,1​,xi,2​,...,xi,ni​​}，${\mathbf{x}}_{i,j}=({\mathbf{p}}_{i,j},{\xi }_{i,j})$

  • $V{P}_i$ 通过在以簇中心为原点的圆柱坐标系中进行均匀采样生成，$\xi$ 能最大化传感器对簇的覆盖率，覆盖率定义为符合传感模型且不被占据体素遮挡的前沿单元数量

  • 覆盖率超过阈值的视点被保留，且按覆盖率降序排序，最多保留 $N_{view}$ 个视点

  • 两视点间移动的时间下限，定义为：

    t 1 b ( x k 1 , j 1 , x k 2 , j 2 ) = m a x { l e n g t h ( P ( p k 1 , j 1 , p k 2 , j 2 ) ) v m a x , m i n ( ∣ ξ k 1 , j 1 , ξ k 2 , j 2 ∣ , 2 π − ∣ ξ k 1 , j 1 , ξ k 2 , j 2 ∣ ) ξ ˙ m a x } t_{1b}(\mathbf{x}_{k_1,j_1},\mathbf{x}_{k_2,j_2})=max\{\frac{length(P(\mathbf{p}_{k_1,j_1},\mathbf{p}_{k_2,j_2}))}{v_{max}},\frac{min(|\xi_{k_1,j_1},\xi_{k_2,j_2}|,2\pi-|\xi_{k_1,j_1},\xi_{k_2,j_2}|)}{\dot{\xi}_{max}}\} t1b​(xk1​,j1​​,xk2​,j2​​)=max{ vmax​length(P(pk1​,j1​​,pk2​,j2​​))​,ξ˙​max​min(∣ξk1​,j1​​,ξk2​,j2​​∣,2π−∣ξk1​,j1​​,ξk2​,j2​​∣)​}

  • 对于每一对簇 $(F_{k_1},F_{k_2})$，我们选择覆盖率最高的视点，将 $t_{1b}({\mathbf{x}}_{k_1,1},{\mathbf{x}}_{k_2,1})$ 作为两簇间的连接代价，其中 $P({\mathbf{p}}_{k_1,1},{\mathbf{p}}_{k_2,1})$ 用 A* 算法得到

Hierarchical Exploration Planning

• 分为三步：Global Exploration Tour Planning，Local Viewpoint Refinement，Minimum-Time B-Spline Trajectory

• Global Exploration Tour Planning

  • 将问题建模为非对称旅行商问题（ATSP）

  • 设计一个 engaged cost matrix ${\mathbf{M}}_{tsp}$ ，${\mathbf{M}}_{tsp}$ 为一个 $N_{cls}+1$ 阶方阵

  • ${\mathbf{M}}_{tsp}$ 的主要部分为 $N_{cls}\times N_{cls}$ 块，包含了各每对前沿簇之间的连接代价，即

    ${\mathbf{M}}_{tsp}(k_1,k_2)={\mathbf{M}}_{t元器件数据手册}$、IC替代型号，打造电子元器件IC百科大全！