張偉聰，韓偉娜，白雪麗，韓 旭，任 寬，田麗麗

（1.北華航天工業(yè)學(xué)院機(jī)電工程學(xué)院；2.北華航天工業(yè)學(xué)院遙感信息工程學(xué)院，河北廊坊 065000）

0 引言

現(xiàn)代飛行器技術(shù)經(jīng)過多年發(fā)展，結(jié)構(gòu)和操作越來越復(fù)雜，在安全突防任務(wù)難度愈來愈大的情況下，智能飛行器航跡規(guī)劃占有重要地位?？焖贉?zhǔn)確的航跡規(guī)劃可有效節(jié)約能源提高效率，其研究具有重大意義。

智能飛行器航跡規(guī)劃通常存在約束工況比較復(fù)雜和優(yōu)化規(guī)模較大等問題時，一般情形會采用啟發(fā)式智能優(yōu)化算法，如蟻群算法、粒子群算法、模擬退火算法、遺傳算法等［1］。Patcher 等［2］討論了路徑規(guī)劃問題中的關(guān)鍵優(yōu)化技術(shù)及其復(fù)雜性；Dong 等［3］、Zhang 等［4］、Nikolos 等［5］系統(tǒng)研究了路徑規(guī)劃中進(jìn)化算法的優(yōu)化原理；Wu 等［6］最早將遺傳算法應(yīng)用于航行器的路徑規(guī)劃問題；朱海斌等［7］引入量子遺傳算法克服了遺傳算法早熟問題；李文廣等［8］改進(jìn)轉(zhuǎn)彎航跡規(guī)劃算法，降低了15%路徑。近年有關(guān)智能飛行器航跡規(guī)劃優(yōu)化研究主要集中于對啟發(fā)式智能優(yōu)化算法進(jìn)行改進(jìn)［9-13］。

傳統(tǒng)的遺傳算法在搜索空間和目標(biāo)函數(shù)方面要求不高，具有范圍廣、魯棒性高以及全局搜索能力較強(qiáng)的優(yōu)點(diǎn)，但是容易陷入局部求解，且收斂結(jié)果易反復(fù)。非支配排序遺傳算法（NSGA）經(jīng)過個體支配關(guān)系的分層，在速度上有了很大提升。本文利用帶精英策略的非支配排序遺傳算法（NSGA-II）應(yīng)用于智能飛行器的航跡規(guī)劃問題中，主要解決NSGA 的排序速度慢以及找到最優(yōu)解時收斂容易反復(fù)的缺陷。

1 航跡規(guī)劃問題

智能飛行器航跡規(guī)劃指在環(huán)境及戰(zhàn)場危險情況如飛行時間、燃油消耗等全方位約束條件下，找到一條自給定起點(diǎn)至目標(biāo)點(diǎn)的優(yōu)質(zhì)飛行軌跡，這是一個典型的多目標(biāo)優(yōu)化問題［14］。

復(fù)雜環(huán)境下的航跡快速規(guī)劃是智能飛行器控制課題的重要組成部分，飛行器的定位系統(tǒng)往往由于其自身結(jié)構(gòu)限制無法做到精準(zhǔn)定位，當(dāng)誤差累積達(dá)到一定程度會導(dǎo)致整體任務(wù)失敗。

1.1 航跡規(guī)劃基本要求

假設(shè)智能飛行器飛行區(qū)域中出發(fā)點(diǎn)為A 點(diǎn)，目的地為B 點(diǎn)，其航跡約束如下：

（1）飛行器在空間飛行過程中需要實(shí)時定位，其定位誤差包括垂直誤差和水平誤差。飛機(jī)每飛行1m，垂直誤差和水平誤差將增加δ個專用單位（以下簡稱單位），到達(dá)終點(diǎn)時垂直誤差和水平誤差均小于θ個單位。為簡化問題，假設(shè)當(dāng)垂直誤差和水平誤差均小于θ個單位時飛行器仍可按照規(guī)劃路徑飛行。

（2）飛行器在飛行過程中需要對定位誤差進(jìn)行校正。飛行區(qū)域中存在一些安全位置（稱之為校正點(diǎn)）可用于誤差校正，當(dāng)飛行器到達(dá)校正點(diǎn)即可根據(jù)該位置的誤差校正類型進(jìn)行誤差校正。校正垂直和水平誤差的位置可根據(jù)地形在航跡規(guī)劃前確定。若垂直誤差、水平誤差都能得到及時校正，則飛行器可以按照預(yù)定航線飛行，通過若干個校正點(diǎn)進(jìn)行誤差校正后最終到達(dá)目的地。

（3）在出發(fā)地A 點(diǎn)，飛行器的垂直和水平誤差為0；飛行器在垂直誤差校正點(diǎn)校正后，其垂直誤差將變成0，水平誤差保持不變；飛行器在水平誤差校正后，其水平誤差將變成0，垂直誤差保持不變；飛行器在垂直誤差不大于α1個單位、水平誤差不大于α2個單位時才能進(jìn)行垂直誤差校正；在垂直誤差不大于β1個單位、水平誤差不大于β2個單位時才能進(jìn)行水平誤差校正。

（4）飛行器在轉(zhuǎn)彎時受到結(jié)構(gòu)和控制系統(tǒng)限制，無法完成即時轉(zhuǎn)彎，最小轉(zhuǎn)彎半徑設(shè)為200m。

1.2 智能飛行器航跡問題

本文研究智能飛行器的航跡規(guī)劃是根據(jù)2019 年全國研究生數(shù)學(xué)建模競賽F 題中的問題二改編［15］。綜合考慮優(yōu)化目標(biāo)，要求航跡長度盡可能小，在校正區(qū)域進(jìn)行校正的次數(shù)盡可能少。繪制出數(shù)據(jù)集的航跡規(guī)劃，并求出飛行器從起點(diǎn)出發(fā)經(jīng)過誤差校正點(diǎn)的編號及校正前誤差，討論算法的有效性。

2 智能飛行器航跡規(guī)劃

2.1 航跡規(guī)劃數(shù)學(xué)模型

在智能飛行器起點(diǎn)A 到終點(diǎn)B 的航跡規(guī)劃中，根據(jù)問題要求假設(shè)飛行器從一個校正節(jié)點(diǎn)到另一個校正節(jié)點(diǎn)之間始終進(jìn)行勻速直線運(yùn)動，記C=[c1,c2,c3...,ci,...,cn]為校正點(diǎn)集，n 為校正點(diǎn)個數(shù)；U=[u1,u2,u3...,ui,...,um]為水平校正集，V=[v1,v2,v3...,vi,...,vQ]為垂直校正集，m 為水平校正點(diǎn)個數(shù)，Q 為垂直校正點(diǎn)個數(shù)。

智能飛行器飛行路程目標(biāo)函數(shù)為：

飛行器經(jīng)過校正點(diǎn)的目標(biāo)函數(shù)為：

式中：

上一個點(diǎn)到下一個點(diǎn)的路程長度為：

基于基本要求的約束條件如下：

其中Pij是兩個校正點(diǎn)之間的誤差增量。

對最小轉(zhuǎn)彎半徑約束為：

2.2 NSGA-II 算法求解過程

NSGA-II 算法的核心是父代與子代的合并，基于傳統(tǒng)遺傳算法進(jìn)行基本操作。

（1）基于NSGA-II 遺傳算法的智能飛行器航跡規(guī)劃算法流程如圖1 所示。

Fig.1 Route planning flow of intelligent vehicle based on NSGA-II genetic algorithm圖1 基于NSGA-II 遺傳算法的智能飛行器規(guī)劃航跡流程

（2）智能飛行器航跡規(guī)劃算法添加以下約束：①當(dāng)前后兩個校正節(jié)點(diǎn)距離超過最大誤差和單位距離誤差的比值時，解無效，生成的下一個節(jié)點(diǎn)間距離必須小于最大誤差和單位距離誤差的比值；②水平校正點(diǎn)和垂直校正點(diǎn)需分開進(jìn)行約束，且節(jié)點(diǎn)到達(dá)下一個校正后才能校正誤差，利用當(dāng)前誤差余量對下一個解的距離進(jìn)行約束；③每個節(jié)點(diǎn)只能用一次，節(jié)點(diǎn)到達(dá)B 點(diǎn)附近就可嘗試直接連接B 點(diǎn)。

（3）產(chǎn)生的新解帶入目標(biāo)函數(shù)找到優(yōu)化目標(biāo)下的最佳航跡：①利用交叉和變異因子產(chǎn)生新解；②輸出可行解，得出最優(yōu)航跡；③記錄遍歷的校正點(diǎn)，得出最優(yōu)航跡對應(yīng)的最優(yōu)校正點(diǎn)。

3 仿真結(jié)果

根據(jù)數(shù)據(jù)集中附件1 的數(shù)據(jù)，利用NSGA-II 算法將數(shù)據(jù)帶入約束進(jìn)行迭代，本次迭代次數(shù)為30 次，得出對應(yīng)的智能飛行器最優(yōu)航跡規(guī)劃如圖2 所示，其中A 點(diǎn)代表起點(diǎn)，B 點(diǎn)代表終點(diǎn)，其它點(diǎn)分別是垂直和水平校正點(diǎn)。

Fig.2 NSGA-II genetic algorithm for optimal path planning of intelligent vehicle圖2 NSGA-II 遺傳算法智能飛行器規(guī)劃最優(yōu)航跡

通過NSGA-II 算法綜合考慮實(shí)際情況，得到一條從起點(diǎn)A 到終點(diǎn)B 的最優(yōu)路徑長度、最佳校正節(jié)點(diǎn)數(shù)的航跡規(guī)劃：起 點(diǎn)A→180→344→165→534→316→312→198→340→583→終點(diǎn)B。根據(jù)算法得到多約束規(guī)劃的值分別為：

從圖2 得到智能飛行器從起點(diǎn)A 出發(fā)經(jīng)過誤差校正點(diǎn)的編號及校正前的誤差結(jié)果如表1 所示。

Table 1 Route planning results表1 航跡規(guī)劃結(jié)果

與NSGA 算法相比，NSGA-II 算法能實(shí)現(xiàn)快速、準(zhǔn)確的搜索性能。分析智能飛行器航跡規(guī)劃總路徑和校正次數(shù)后發(fā)現(xiàn)，NSGA-II 算法相對于NSGA 算法收斂速度快了一倍，且最優(yōu)結(jié)果不易反復(fù)。在同時迭代50 次后，NSGA-II算法與NSGA 算法的對比結(jié)果如圖3 和圖4 所示。

Fig.3 Total distance iterative curve of intelligent vehicle based on two genetic algorithms圖3 兩種遺傳算法智能飛行器總路程迭代曲線

Fig.4 Two kinds of genetic algorithms for intelligent vehicle calibration圖4 兩種遺傳算法智能飛行器校正次數(shù)迭曲線

圖中虛線代表采用NSGA 算法進(jìn)行規(guī)劃的結(jié)果迭代情況，實(shí)線代表采用NSGA-II 算法進(jìn)行規(guī)劃的結(jié)果迭代情況。從圖中可以很容易看出，NSGA-II 算法避免了NSGA 算法的一些缺點(diǎn)，可以更準(zhǔn)確快速地獲得智能飛行器在滿足約束條件下的最優(yōu)軌跡，并且在找到最優(yōu)軌跡時收斂不會出現(xiàn)局部反復(fù)。

4 結(jié)語

本文采用NSGA-II 算法進(jìn)行了多約束條件下智能飛行器的航跡規(guī)劃。實(shí)驗(yàn)表明該算法能快速且準(zhǔn)確得出最優(yōu)軌跡，解決了NSGA 算法最終結(jié)果不收斂的問題。值得指出的是，改進(jìn)的遺傳算法越來越多，無疑對解決智能飛行器的航跡規(guī)劃問題提供了保障，但同時每次都需要通過對比實(shí)驗(yàn)進(jìn)行改進(jìn)，在很大程度上限制了遺傳算法的發(fā)展速度。