文献精读：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 Fi 建立一个 F I i FI_i FIi
- 包括以下参数：
- C i C_i Ci ：包含在簇中的前沿单元
- p a v g , i \mathbf{p}_{avg,i} pavg,i ： C i C_i Ci 的平均位置
- B i B_i Bi ： C i C_i Ci 的 Axis-aligned bounding box
- V P i VP_i VPi ：覆盖簇的视点集
- L c o s t , i L_{cost,i} Lcost,i ：存储簇与簇之间cost的双链列表
-
Incremental Frontier Detection and Clustering
- 每次更新地图后，都记录更新区域的bounding box B m B_m Bm
- 对 bounding box 与 B m B_m Bm 相交的前沿簇进行检查，如果包含不再是前沿的单元，则将该前沿簇移除
- 搜索新前沿并组成簇
- 对于较大尺寸的簇，采用Principal Component Analysis(PCA) 递归地分为小簇
-
Viewpoint Generation and Cost Update
-
创建一个簇 F i F_i Fi 时，生成一个视点集 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}， x i , j = ( p i , j , ξ i , j ) \mathbf{x}_{i,j}=(\mathbf{p}_{i,j},\xi_{i,j}) xi,j=(pi,j,ξi,j)
-
V P i VP_i VPi 通过在以簇中心为原点的圆柱坐标系中进行均匀采样生成， ξ \xi ξ 能最大化传感器对簇的覆盖率，覆盖率定义为符合传感模型且不被占据体素遮挡的前沿单元数量
-
覆盖率超过阈值的视点被保留，且按覆盖率降序排序，最多保留 N v i e w N_{view} Nview 个视点
-
两视点间移动的时间下限，定义为：
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{ vmaxlength(P(pk1,j1,pk2,j2)),ξ˙maxmin(∣ξk1,j1,ξk2,j2∣,2π−∣ξk1,j1,ξk2,j2∣)}
-
对于每一对簇 ( F k 1 , F k 2 ) (F_{k_1},F_{k_2}) (Fk1,Fk2)，我们选择覆盖率最高的视点，将 t 1 b ( x k 1 , 1 , x k 2 , 1 ) t_{1b}(\mathbf{x}_{k_1,1},\mathbf{x}_{k_2,1}) t1b(xk1,1,xk2,1) 作为两簇间的连接代价，其中 P ( p k 1 , 1 , p k 2 , 1 ) P(\mathbf{p}_{k_1,1},\mathbf{p}_{k_2,1}) P(pk1,1,pk2,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 M t s p \mathbf{M}_{tsp} Mtsp ， M t s p \mathbf{M}_{tsp} Mtsp 为一个 N c l s + 1 N_{cls}+1 Ncls+1 阶方阵
-
M t s p \mathbf{M}_{tsp} Mtsp 的主要部分为 N c l s × N c l s N_{cls} \times N_{cls} Ncls×Ncls 块，包含了各每对前沿簇之间的连接代价，即
M t s p ( k 1 , k 2 ) = M t s p ( k 2 , k 1 ) = t 1 b ( x k 1 , 1 , x k 2 , 1 ) , k 1 , k 2 ∈ { 1 , 2 , . . . , N c l s } \mathbf{M}_{tsp}(k_1,k_2)=\mathbf{M}_{tsp}(k_2,k_1)=t_{1b}(\mathbf{x}_{k_1,1},\mathbf{x}_{k_2,1}),k1,k2\in\{1,2,...,N_{cls}\} Mtsp(k1,k2)=Mt 标签： uav传感器
-