基于時空數據挖掘的無人機航線自動尋優規劃

張淏凌，馮杰成，陳炳海，戴榮璨，顧志偉

（國網江蘇省電力有限公司興化市供電分公司，江蘇興化 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 結束語

為了提升無人機的應用效果，文中提出基于時空數據挖掘的無人機航線自動尋優規劃方法研究。測試結果表明該方法提升了時空數據挖掘深度系數與無人機航線自動尋優規劃效果，解決了無人機的安全避障問題。