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

馮禮鴻，蔣勝

（200093 上海市 上海理工大學(xué)）

0 引言

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

1 飛行區(qū)域和航跡約束

1.1 飛行區(qū)域

飛行器的飛行區(qū)域如圖1 所示，出發(fā)點為A點，目的地為B 點。

圖1 飛行器航跡規(guī)劃區(qū)域示意圖Fig.1 Schematic diagram of aircraft trajectory planning area

1.2 航跡約束

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

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

表1 符號說明Tab.1 Symbol description

2 數(shù)據(jù)集說明與3 種多約束條件航跡規(guī)劃要求

2.1 數(shù)據(jù)集說明

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

表2 數(shù)據(jù)集示例Tab.2 Data example

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

2.2 3 種多約束條件航跡規(guī)劃要求

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

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

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

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

3.1 NSGA-Ⅱ算法的基本原理

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

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

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

3.2 求解流程

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

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

4 3 種多約束條件航跡規(guī)劃結(jié)果

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

4.1.1 建模

據(jù)約束條件，建立目標(biāo)函數(shù)如下：

Err 更新行為都發(fā)生在i 時刻：

（1）誤差累加

（2）水平校正

（3）垂直校正

4.1.2 求解結(jié)果

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

圖3 最優(yōu)解結(jié)果Fig.3 Optimization result

圖4 最優(yōu)規(guī)劃三維路徑圖Fig.4 Optimal planning three-dimensional path diagram

表3 航跡規(guī)劃結(jié)果Tab.3 Trajectory planning results

（續(xù)表）

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

4.2.1 建模

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

Err 更新行為都發(fā)生在i 時刻：

（1）誤差累加

（2）水平校正

（3）垂直校正

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

4.2.2 求解結(jié)果

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

圖5 直線轉(zhuǎn)圓弧連接示意圖Fig.5 Diagram of straight to arc connection

圖6 最優(yōu)規(guī)劃三維路徑圖Fig.6 Optimal planning three-dimensional path diagram

表4 航跡規(guī)劃結(jié)果Tab.4 Trajectory planning results

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

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

4.3.1 建模

建立目標(biāo)函數(shù)如下：

Err 更新行為都發(fā)生在i 時刻：

（1）誤差累加

（2）水平校正

若失敗，則：

（3）垂直校正

若失敗，則

4.3.2 求解結(jié)果

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

圖8 最優(yōu)解結(jié)果Fig.8 Optimization result

圖9 最優(yōu)規(guī)劃三維路徑圖Fig.9 Optimal planning three-dimensional path diagram

表5 航跡規(guī)劃結(jié)果Tab.5 Trajectory planning results

5 結(jié)論

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