基于时空数据挖掘的无人机航线自动寻优规划

张淏凌，冯杰成，陈炳海，戴荣璨，顾志伟

（国网江苏省电力有限公司兴化市供电分公司，江苏兴化 225700）

近年来，无人机及其相关技术发展速度飞快，受到了多个领域的广泛关注与应用。无人机应用范围的扩大使其面临的工作环境愈加复杂，航线数据缺失现象使越障航线规划任务愈加困难，不利于无人机安全飞行[1]。在最新无人机航线规划研究中，有面向多目标侦察任务的无人机航线规划方法[2]与复杂低空环境下考虑区域风险评估的无人机航路规划方法[3]。但这两种方法由于数据处理效果较差，无法获得最佳的航线规划结果，故提出基于时空数据挖掘的无人机航线自动寻优规划方法研究，解决航线寻优规划越障性能提升的问题。

1 航线自动寻优规划方法研究

1.1 无人机航线数据预处理

无人机航线自动寻优规划需要获取全部航线数据。但是采集设备的自身缺陷，加之环境方面的不利因素，致使获得的航线数据存在异常与缺失现象，不利于后续时空数据的深度挖掘。因此，应对无人机航线数据进行预处理。采用线性插值方法对缺失的航线数据进行补全处理[4]，步骤如下：

步骤一：计算缺失起点A 点与缺失终点B 点的无人机飞行加速度数值，公式为：

式中，aA与aB分别表示A 点与B 点加速度数值；ΔVA-1与ΔTA-1分别表示A 点与其邻近A-1 点的飞行速度差值与飞行时间差值；ΔVB与ΔTB分别表示B 点的飞行速度差值与飞行时间差值[5]。

步骤二：计算待补全航线数据的时间间隔，表达式为：

步骤三：采用线性插值方法求解待补全航线段轨迹点对应的加速度数值，将其记为a1,a2,…,an。以同样程序获取补全航线段轨迹点的方向与速度，分别记为ϑ1,ϑ2,…,ϑn与V1,V2,…,Vn；

步骤四：以步骤三输出数据为基础，预测待补全航线段轨迹点的坐标信息，公式为：

式中，(xi,yi)与(xi-1,yi-1)表示第i个与第i-1 个轨迹点的坐标信息；Vi-1、ai-1与ϑi-1分别表示第i-1 个轨迹点对应的飞行速度、加速度与方向[6]。

依据上述步骤即可完成无人机航线数据的补全，但存在航线冗余的现象，因此需要对无人机航线的相似性进行衡量，以此为基础，删除冗余航线，为后续时空划分提供便捷条件[7]。无人机航线相似性采用欧氏距离进行衡量，公式为：

式中，D(Li,Lj)表示无人机航线Li与Lj之间的欧氏距离。

以式（4）计算结果为基础，制定冗余航线判定规则，具体如下式所示：

依据式（5）所示规则即可判定无人机航线是否为冗余航线，对冗余航线进行删除处理，最终获得精准的无人机航线数据集为L={L1,L2,…,Lm}，其中m代表航线的总数量，为后续航线数据集的时空划分提供依据。

1.2 无人机航线数据集的时空划分

以上述获得的无人机航线数据集L={L1,L2,…,Lm}为基础，划分航线集的时间与空间，为后续时空数据深度挖掘做好充足的准备。

为了方便研究的进行，设定无人机飞行速度是匀速的。在上述背景条件下，将每一条无人机航线Li划分为k个时段，每个时段均具有不同的轨迹点数据，获得航线数据集时间划分结果为R={R1,R2,…,Rk}[8]。

而航线集空间划分需要依据航线分布情况、主要航线等多种参数进行精准划分。依据航线分布密集程度的不同，将空间分为若干个区域，按航线分布密集程度由高到低进行编号[9]。航线分布密集程度计算公式为：

式中，ρ表示航线分布密集程度；r表示圆形范围半径数值。

将式（6）计算结果ρ作为空间划分的依据，即可完成无人机航线集内时间数据与空间数据的精准划分，为后续的研究提供支撑。

1.3 无人机航线时空数据挖掘

以上述航线集时间与空间数据划分结果为依据，将不同时间与空间尺度下的无人机航线数据转化为矩阵形式，通过分解处理获取时空数据相应特征，为后续的航线自动寻优规划提供依据[10]。

若是直接对航线时空数据进行深入挖掘，运算量过大，使得航线自动寻优规划效率较低，影响无人机的应用性能[11]。因此，将无人机航线时空数据转化为矩阵形式，记为Ok×p。其中，p表示空间区域编号，取值范围为[1,8][12]。对无人机航线时空数据矩阵进行分解处理，公式为：

式中，Ck×q表示时间特征值向量；Eq×p表示空间特征向量。由于航线数量是正数，故Ck×q与Eq×p的取值均大于0。

为了验证矩阵分解是否准确，即得到的高阶特征向量与特征向量是否精确，对原矩阵与还原矩阵之间的近似度进行计算，公式为：

式中，Δζ表示原矩阵与还原矩阵之间的近似度；O～k×p表示分解矩阵Ck×q与Eq×p相乘获得的还原矩阵。

当式（8）计算结果Δζ无限趋近于100%时，获得的分解矩阵Ck×q与Eq×p更加精确，前者为时间特征，后者为空间特征，为后续航线寻优规划提供便利。

1.4 无人机航线自动寻优规划

以上述时空数据挖掘结果——时间特征Ck×q与空间特征Eq×p为依据，应用蚁群算法对无人机航线进行自动寻优规划，获得最佳的无人机航线，为无人机的应用与发展提供助力。

在时空特征集合中，提取每一条航线的时间与空间特征数值，记为Ci与Ei。蚁群算法中信息素固定，寻优路径越短，信息素浓度越高，蚁群选择此路径的概率越高。经过多次迭代后，求解蚂蚁状态转移概率最大值，即可取得最优解。以此为基础，计算蚂蚁状态转移概率，公式为：

式中，P表示蚂蚁状态转移概率；Wi表示第i条航线的信息量；ηi表示第i条航线的长度；α(t)表示蚂蚁路径更新信息素浓度。

不断迭代蚂蚁路径更新信息素浓度α(t)，直至蚂蚁状态转移概率P达到最大值为止[13-16]。信息素浓度更新公式为：

式中，α(t+1) 表示更新后的信息素浓度；β表示辅助更新因子；Δα表示信息素浓度差值。

当P数值达到最大值时，其对应的无人机航线即为航线自动寻优规划结果，能最大限度地保障无人机飞行安全，为无人机的后续发展提供帮助。

2 实验与结果分析

分别选取文献[2]和文献[3]作为对比方法1 与对比方法2，设计对比实验，验证提出方法的应用效果，具体实验过程如下。

2.1 实验准备阶段

实验以无人机在某市的飞行任务区域作为实验区域，采用拍摄该地区的20 m 分辨率DEM 数据作为基础数据。航行任务区域基本信息如下：地面分辨率为0.1 m，区域高程值范围为469～725 m，区域面积是31.09 km2，航摄风速为1 级。无人机选择蜂鸟4 轴4 旋翼智造巡查无人机F401。在Windows 10 操作系统中使用Matlab 2019a 平台进行航迹建模。具体情况如图1 所示。

图1 实验区域示意图

如图1 所示，灰色线段表示道路，无人机的主要任务是对实验区域内某些目标点的实时情况进行观察与记录。实验区域高空布设多条输电线路，会干扰无人机飞行，作为航线规划障碍物进行考虑。由此可见，选取的实验区域符合应用性能测试需求。此研究设置两种差异性较大的实验工况[17]：

实验工况一：重点区域数量为3 个，缺失航线轨迹点数量为89 个。

实验工况二：重点区域数量为4 个，缺失航线轨迹点数量为124 个。

2.2 实验结果分析

通过时空数据挖掘深度系数与无人机航线自动寻优规划结果体现提出方法的应用效果。时空数据挖掘深度系数决定航线时空数据特征提取的精准性，间接影响航线规划结果，两者呈现为显著的正相关关系。在两种实验工况下分别进行5 次实验，获得时空数据挖掘深度系数结果如表1、表2 所示。

表1 工况一下时空数据挖掘深度系数表

表2 工况二下时空数据挖掘深度系数表

如表1 与表2 数据所示，在两种实验工况下，相较于两种对比方法，应用该文方法获得的时空数据挖掘深度系数更大，平均值分别为9.05 与8.91，表明该文方法对时空数据的挖掘效果更好。

3 种方法的寻优收敛效果如图2 所示。

图2 寻优收敛效果

由图2 可知，该文方法在迭代50 次左右即完成收敛，且最优值远高于其他方法。而其他方法的收敛速度较慢，可知该文方法的航迹规划优化效果最佳。

通过实验获得无人机航线自动寻优规划结果如图3 所示。

图3 无人机航线自动寻优规划结果示意图

如图3 所示，在两种实验工况下，应用该文方法获得的无人机航线自动寻优规划结果成功避开所有建筑物和输电线路，航线平滑性较好，航线规划效果较好，而两种对比方法的航线规划结果无法躲避所有障碍物，飞行难度较大，表明该文方法的无人机航线自动寻优规划结果质量更好。

3 结束语

为了提升无人机的应用效果，文中提出基于时空数据挖掘的无人机航线自动寻优规划方法研究。测试结果表明该方法提升了时空数据挖掘深度系数与无人机航线自动寻优规划效果，解决了无人机的安全避障问题。