多約束條件下某智能飛行器航跡快速規劃

馮禮鴻，蔣勝

（200093 上海市 上海理工大學）

0 引言

近年來，無人機快速發展并得到廣泛應用。美國自 1980 年就已經著手研發應用于國防、軍事等領域的航跡規劃系統[1]。而多約束條件下對航距計算時采用平面直線距離算法會造成較大誤差[2]。高空長航時，無人機的航跡規劃研究急需擺脫功能單一、適應環境單一、反應速度慢的問題[3]。為了解決此問題，本文采用遺傳算法擴展而來的NSGA-Ⅱ實現航跡長度盡可能小和經過校正區域進行校正的次數盡可能少的兩個優化目標，同時提高航跡校正點校正概率。

1 飛行區域和航跡約束

1.1 飛行區域

飛行器的飛行區域如圖1 所示，出發點為A點，目的地為B 點。

圖1 飛行器航跡規劃區域示意圖Fig.1 Schematic diagram of aircraft trajectory planning area

1.2 航跡約束

（1）垂直/水平誤差增加量為δ/m，要求到達終點時垂直/水平誤差＜θ，假設垂直/水平誤差均＜θ，飛行器可按規劃路徑飛行；（2）誤差校正：通過若干個校正點（垂直/水平校正點）后到達目的地；（3）A 點(出發點)垂直/水平誤差為0；（4）垂直誤差校正點使得垂直誤差為0，水平誤差不變；（5）水平誤差校正點使得水平誤差為0，垂直誤差不變；（6）垂直誤差校正條件：垂直誤差≤α1，水平誤差≤α2；（7）水平誤差校正條件：垂直誤差≤β1，水平誤差≤β2；（8）飛行器的最小轉彎半徑為200 m。

各約束條件及第4 章公式的符號含義如表1所示。

表1 符號說明Tab.1 Symbol description

2 數據集說明與3 種多約束條件航跡規劃要求

2.1 數據集說明

本文研究的飛行區域給定的校正點共有612個，其示例如表2 所示

表2 數據集示例Tab.2 Data example

表2 中校正點類型1 表示垂直誤差校正點，0 表示水平誤差校正點；校正概率為第3 種多約束航跡規劃的數據，1 表示該校正點可能有問題，0 表示正常校正；該數據集下的參數為：α1=25，α2=15，β1=20，β2=25，θ=30，δ=0.001。

2.2 3 種多約束條件航跡規劃要求

（1）規劃滿足約束條件（1）—（7）時，航跡長度盡可能小、校正次數盡可能少的飛行器航跡。

（2）規劃滿足約束條件（1）—（8）時，航跡長度盡可能小、校正次數盡可能少的飛行器航跡。

（3）規劃滿足約束條件（1）—（7）時，航跡長度盡可能小、校正的次數盡可能少以及校正點校正概率滿足要求的飛行器的航跡。

3 基于NSGA-Ⅱ算法的航跡規劃基本原理

3.1 NSGA-Ⅱ算法的基本原理

本文采用NSGA-Ⅱ[4]（帶精英策略的非支配排序的遺傳算法）算法中的兩種行為產生新解：

（1）交叉行為：本質上即路徑規劃，則兩條路徑解比較優的交叉方式還是2 個解分別取1點將2 條路徑分為4 條，之后通過兩兩交叉組合即可得2 條新解，并且點的選擇根據距離確定；

（2）變異行為：根據約束條件，本文設定兩種優化策略，一種是路徑上相近2 個校正點交換，一種是直接剔除1 個校正點。

3.2 求解流程

使用MATLAB 軟件求解，其實現流程的整體框圖如圖2 所示。

圖2 求解流程框圖Fig.2 Solution process flow diagram

4 3 種多約束條件航跡規劃結果

4.1 滿足約束條件（1）—（7）時飛行器的航跡

4.1.1 建模

據約束條件，建立目標函數如下：

Err 更新行為都發生在i 時刻：

（1）誤差累加

（2）水平校正

（3）垂直校正

4.1.2 求解結果

多條航跡是圖上一些最短路徑平滑的結果[5]，或者對種群進行空間聚類，使得某一條航跡只在一個特定空間區域內進化產生[6]。迭代完成得到最優解如圖3 所示，相應的最優規劃三維路徑圖如圖4 所示，航跡規劃結果見表3。

圖3 最優解結果Fig.3 Optimization result

圖4 最優規劃三維路徑圖Fig.4 Optimal planning three-dimensional path diagram

表3 航跡規劃結果Tab.3 Trajectory planning results

（續表）

4.2 滿足約束條件（1）-（8）時飛行器的航跡

4.2.1 建模

根據航跡平滑算法進行路徑規劃[7]，找一個過B 點的半徑為200 m 的圓，然后在圓上找兩點（記為E、F 點）使得就近B 點的校正點（記為C）有AE 和CF 分別與圓相切，目標函數如下：

Err 更新行為都發生在i 時刻：

（1）誤差累加

（2）水平校正

（3）垂直校正

存在locz作為圓心滿足公式:

4.2.2 求解結果

根據相切及曲率半徑等概念得到三點A、B、C，在平面中形成直線AB 轉曲線后轉直線BC 示意圖如圖5 所示，相應最優路徑規劃圖如圖6 所示，圖7 為飛行器在飛行過程中沿x、y、z 軸3個方向上的位移時間變化關系圖。航跡規劃結果如表4 所示。

圖5 直線轉圓弧連接示意圖Fig.5 Diagram of straight to arc connection

圖6 最優規劃三維路徑圖Fig.6 Optimal planning three-dimensional path diagram

表4 航跡規劃結果Tab.4 Trajectory planning results

圖7 飛行路徑在xyz 三軸上的變化圖Fig.7 Flight path changes on the xyz axis

4.3 滿足約束條件（1）-（7）和校正點校正概率的飛行器的航跡

4.3.1 建模

建立目標函數如下：

Err 更新行為都發生在i 時刻：

（1）誤差累加

（2）水平校正

若失敗，則：

（3）垂直校正

若失敗，則

4.3.2 求解結果

限定連續出現問題節點的次數，以保證成功概率，通過蒙特卡洛算法[8]計算真實概率。迭代完成得到最優解，如圖8 所示，相應的最優規劃三維路徑圖如圖9 所示，航跡規劃結果見表5。

圖8 最優解結果Fig.8 Optimization result

圖9 最優規劃三維路徑圖Fig.9 Optimal planning three-dimensional path diagram

表5 航跡規劃結果Tab.5 Trajectory planning results

5 結論

通過對某飛行器在多約束條件下的分析和建模，結合NSGA-Ⅱ算法，實現了飛行器航跡快速規劃。本文針對三種不同的多約束要求進行了驗證分析，三種航跡規劃難度逐漸加大。計算結果表明，本算法能有效實現飛行器的航跡快速規劃優化。有效解決了復雜環境下由于系統結構限制，飛行器定位系統無法對自身進行精準定位可能導致任務失敗的問題。本文所建立的算法有效地解決了遍歷規劃的時間復雜性問題，可以為飛行器航跡快速規劃提供有價值的參考。