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

馮禮鴻，蔣勝

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

0 引言

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

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

1.1 飛行區(qū)域

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

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

1.2 航跡約束

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

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

表1 符號(hào)說明Tab.1 Symbol description

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

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

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

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

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

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

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

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

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

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

3.1 NSGA-Ⅱ算法的基本原理

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

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

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

3.2 求解流程

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

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

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

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

4.1.1 建模

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

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

（1）誤差累加

（2）水平校正

（3）垂直校正

4.1.2 求解結(jié)果

多條航跡是圖上一些最短路徑平滑的結(jié)果[5]，或者對種群進(jìn)行空間聚類，使得某一條航跡只在一個(gè)特定空間區(qū)域內(nèi)進(jìn)化產(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）時(shí)飛行器的航跡

4.2.1 建模

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

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

（1）誤差累加

（2）水平校正

（3）垂直校正

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

4.2.2 求解結(jié)果

根據(jù)相切及曲率半徑等概念得到三點(diǎn)A、B、C，在平面中形成直線AB 轉(zhuǎn)曲線后轉(zhuǎn)直線BC 示意圖如圖5 所示，相應(yīng)最優(yōu)路徑規(guī)劃圖如圖6 所示，圖7 為飛行器在飛行過程中沿x、y、z 軸3個(gè)方向上的位移時(shí)間變化關(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）和校正點(diǎn)校正概率的飛行器的航跡

4.3.1 建模

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

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

（1）誤差累加

（2）水平校正

若失敗，則：

（3）垂直校正

若失敗，則

4.3.2 求解結(jié)果

限定連續(xù)出現(xiàn)問題節(jié)點(diǎn)的次數(shù)，以保證成功概率，通過蒙特卡洛算法[8]計(jì)算真實(shí)概率。迭代完成得到最優(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-Ⅱ算法，實(shí)現(xiàn)了飛行器航跡快速規(guī)劃。本文針對三種不同的多約束要求進(jìn)行了驗(yàn)證分析，三種航跡規(guī)劃難度逐漸加大。計(jì)算結(jié)果表明，本算法能有效實(shí)現(xiàn)飛行器的航跡快速規(guī)劃優(yōu)化。有效解決了復(fù)雜環(huán)境下由于系統(tǒng)結(jié)構(gòu)限制，飛行器定位系統(tǒng)無法對自身進(jìn)行精準(zhǔn)定位可能導(dǎo)致任務(wù)失敗的問題。本文所建立的算法有效地解決了遍歷規(guī)劃的時(shí)間復(fù)雜性問題，可以為飛行器航跡快速規(guī)劃提供有價(jià)值的參考。