多目標優(yōu)化下智能飛行器三維航跡快速規(guī)劃

丁 超，吳梓杰，張 航

(1.中南大學計算機學院，湖南 長沙410083;2.中南大學自動化學院，湖南 長沙410083)

1 引言

智能飛行器類似于無人機，具有結(jié)構(gòu)精巧，體積較小的優(yōu)點，而且它更加先進和智能化，非常適合用于軍事偵察和對敵設(shè)施的破壞。國外學者則更多的關(guān)注其路徑規(guī)劃，解決如何將貨物送至不同站點的問題[1-2]，而對于智能飛行器所處的復(fù)雜環(huán)境和飛行器自身性能的問題卻缺少研究。在實際應(yīng)用中，由于智能飛行器自身以及環(huán)境復(fù)雜性，合理的路徑是貨物安全、經(jīng)濟、快捷送至目的地的重要保障，故研究智能飛行器的復(fù)雜飛行環(huán)境和自身性能技術(shù)有著極其重要的現(xiàn)實意義。周浪提出了一種運輸路徑規(guī)劃解決方法，它構(gòu)建不同運輸路徑優(yōu)化模型，采用遺傳算法求解模型，最終僅僅達到了運輸成本上的優(yōu)化[3]；Torabbeigi提出了一種變預(yù)處理算法以提高求解模型的速度，但只針對飛行器本身電池能耗問題[4]；Abeywickrama等考慮不同場景及條件對無人機能耗的影響，提出涵蓋無人機飛行全過程的能耗模型[5]；Dorling等建立無人機路徑規(guī)劃的混合整數(shù)線性模型，綜合考慮了飛行器的運輸成本和電池能耗[6]；王云常、戴朱祥、李濤提出了一種基于A星算法與人工勢場法的無人機路徑規(guī)劃，提高了避障效果，縮短了飛行器搜索時間，主要通過引力場來控制飛行器的飛行方向，從而達到避讓大型障礙物的效果[7]；馬云紅、張恒等提出了一種三維無人機路徑規(guī)劃，同時為了滿足無人機俯仰角、偏航角等性能約束，提出了一系列優(yōu)化算法，最終也只是考慮到了對無人機自身性能的優(yōu)化[8]；縱觀已有成果，常用的方法是將飛行器的路徑規(guī)劃問題簡化成一種道路車輛路徑規(guī)劃問題，文獻[3-6]要么僅僅考慮飛行器的運輸成本，要么只是考慮到了飛行器的能耗問題，沒有體現(xiàn)出飛行器空中機動能力和應(yīng)變能力。文獻[7-8]在航跡規(guī)劃中也沒有考慮到飛行環(huán)境因素且未將飛行器自身性能等影響要素組合考慮，規(guī)劃結(jié)果并不理想。本文結(jié)合智能飛行器的復(fù)雜飛行環(huán)境和自身性能優(yōu)化的特點，進一步改進了飛行器三維航跡規(guī)劃算法，提升效率，減少航程代價，保證飛行器能夠通過定位校正到達目的地，完成飛行任務(wù)。

2 問題描述與相關(guān)假設(shè)

2.1 問題描述

智能飛行器受限于系統(tǒng)結(jié)構(gòu)的大小，在飛行過程中會不斷產(chǎn)生飛行誤差。當飛行誤差積累到一定程度，就會偏離目標點，導(dǎo)致飛行任務(wù)失敗。因此在航跡快速規(guī)劃時，如何在智能飛行器定位精度的限制下，對定位誤差進行校正是一項重要課題。飛行器的定位誤差分為垂直飛行誤差和水平飛行誤差，假設(shè)飛行器每前進1m，垂直誤差和水平誤差將各增加δ個專用單位，當飛行器的垂直飛行誤差和水平飛行誤差均小于θ個單位時，飛行器可以按照已規(guī)劃的軌跡飛行，并準確到達目標，從而完成飛行任務(wù)。根據(jù)飛行區(qū)域的特殊地形標識，飛行區(qū)域內(nèi)一些點可以單獨對飛行器進行垂直誤差或水平校正。校正垂直和水平誤差的位置可根據(jù)地形在航跡規(guī)劃前確定(如圖1所示， 紅色的點為水平誤差校正點，藍色的點為垂直誤差校正點，A為出發(fā)點，B為目的地)。

圖1 飛行器航跡規(guī)劃區(qū)域示意圖

問題一：在對飛行器定位誤差進行校正時，當飛行器到達垂直校正點時，飛行器的垂直誤差不大于α1個單位，水平誤差不大于α2個單位時才能進行垂直誤差校正。經(jīng)過校正，垂直誤差變?yōu)?，而水平誤差保持不變；同理，當飛行器到達水平校正點時，飛行器的垂直誤差不大于β1個單位，水平誤差不大于β2個單位時才能進行水平誤差校正。經(jīng)過校正，水平誤差變?yōu)?，而垂直誤差不變。問題二：由于飛行器結(jié)構(gòu)和控制系統(tǒng)的限制，飛行器的前進方法無法突然改變，需要通過圓弧路徑進行過渡，且轉(zhuǎn)彎的最小半徑為200m。問題三：考慮飛行過程中部分校正點校正失效的問題。在飛行中由于某些不可控的因素(如天氣、通訊故障等)導(dǎo)致飛行器到達校正點時無法進行理想的誤差校正，無法將在該處將誤差降低至0。根據(jù)給定的信息，飛行器在部分校正點能夠成功將某個誤差校正為0的概率是80%，如果校正失敗，則校正后的剩余誤差為min(error，5)個單位(其中error為校正前誤差，min為取小函數(shù))。已知信息：出發(fā)地A點，飛行器的垂直和水平誤差均為0；給出空域校正點的位置及校正信息；相關(guān)參數(shù)：α1=25，α2=15，β1=20，β2=25，θ=30，δ=0.001

2.2 相關(guān)假設(shè)

假設(shè)飛行器為一質(zhì)點，飛行器在飛行過程中不會出現(xiàn)突然故障的情況。飛行器的飛行速度對到達校正點校正效果無影響，當垂直誤差和水平誤差均小于θ個單位時，飛行器仍能夠按照規(guī)劃路徑飛行，并且飛行器的最小轉(zhuǎn)彎半徑為200m，飛行器在部分校正點能夠成功將某個誤差校正為0的概率是80%，如果校正失敗，則校正后的剩余誤差為min(error，5)個單位(其中error為校正前誤差，min為取小函數(shù))。

3 優(yōu)化目標與約束條件確定

飛行器在執(zhí)行任務(wù)的時候需要考慮到多方面的影響要素，本文綜合考慮飛行器自身性能約束與飛行器復(fù)雜的飛行環(huán)境，從飛行器的定位誤差校正、機動性能、部分校正點失效等角度建立多約束條件的飛行器三維航跡快速規(guī)劃模型，設(shè)計了飛行器定位誤差校正策略和飛行器轉(zhuǎn)彎控制策略。

3.1 飛行器定位誤差校正策略

該目標主要研究在準確抵達終點時，飛行器的航跡長度最短，并且經(jīng)過校正點的次數(shù)盡可能少。校正次數(shù)與航跡長度存在正相關(guān)的關(guān)系，即校正次數(shù)越多，航跡長度也越長。所以，以航跡最短為求解目標，相對應(yīng)的校正次數(shù)就會越少。目標函數(shù)如式(1)所示，n為飛行器誤差校正次數(shù)。

(1)

3.1.1 約束條件一

為保證飛行器能夠按照規(guī)劃航跡飛行，垂直誤差和水平誤差均應(yīng)小于θ個單位。即

γp≤θ

(2)

γh≤θ

(3)

γp=(Sii+1-Sii)δ，ii∈np

(4)

γh=(Sjj+1-Sjj)δ，jj∈nh

(5)

(6)

式中，γp為垂直誤差，γh為水平誤差。Sii和Sjj分別為飛行器經(jīng)過垂直誤差和水平誤差校正后再次飛行的距離。

3.1.2 約束條件二

在對飛行器垂直誤差校正時，當飛行器的垂直誤差不大于α1個單位，水平誤差不大于α2個單位時才能進行垂直誤差校正，且經(jīng)過校正，垂直誤差變?yōu)?，水平誤差不變。垂直校正點的校正誤差約束為

(7)

3.1.3 約束條件三

在對飛行器水平誤差校正時，當飛行器的垂直誤差不大于β1個單位，水平誤差不大于β2個單位時才能進行水平誤差校正，且經(jīng)過校正，水平誤差變?yōu)?，垂直誤差不變。水平校正點的校正誤差約束為

(8)

3.2 飛行器轉(zhuǎn)彎控制策略

該目標主要研究飛行器在結(jié)構(gòu)和控制系統(tǒng)的控制下，無法及時改變飛行方向，需要通過轉(zhuǎn)彎控制策略進行控制，飛行器的最小轉(zhuǎn)彎半徑為200m。本文中提出一種轉(zhuǎn)彎控制策略如圖2所示，即在誤差校正點首先進行轉(zhuǎn)彎，調(diào)整飛行方向，然后沿直線飛行，最終到達下一個目標校正點。

圖2 飛行器轉(zhuǎn)彎控制策略圖

約束條件除了以上的三種約束條件，還多了一條機動性能約束條件，飛行器的最小轉(zhuǎn)彎半徑最小為200m。即在問題一約束條件的基礎(chǔ)上，增加了飛行器最小轉(zhuǎn)彎半徑的約束，即

Ri≥Rmin=200

(9)

因此，以航跡最短求解目標，增加飛行器的機動軌跡，構(gòu)建轉(zhuǎn)彎半徑約束下的飛行器快速路徑規(guī)劃的目標函數(shù)如式(10)所示，n為飛行器誤差校正次數(shù)。

(10)

式中

li=?πR/180

(11)

(12)

(13)

(14)

程序設(shè)計中通過對當前規(guī)劃的路徑進行曲率半徑估計，判斷飛行器航跡飛行段近似曲率半徑是否大于等于200m，來確定飛行器是否能在現(xiàn)實環(huán)境下飛行。

3.3 部分校正點失效情況

當校正節(jié)點集合中存在問題節(jié)點時候，為了盡可能保證成功到達的概率下，盡可能減少校正次數(shù)和路程，根據(jù)分析可知問題節(jié)點的特點是校正誤差到不了0，只能降到5個單位，也就是在問題一的基礎(chǔ)上，考慮校正點失效的概率，即成功校正誤差的概率為80%，校正后的誤差為0；校正誤差失敗的概率為20%，校正后的誤差為min(error，5)。

(15)

4 算法優(yōu)化與仿真結(jié)果分析

4.1 NSGA2遺傳算法優(yōu)化

本文中研究的約束一定程度上還是比較嚴格的，而且規(guī)模很大，大規(guī)模問題結(jié)合嚴格約束的問題，這對算法就提出了兩點要求：①初始解產(chǎn)生策略必須可以產(chǎn)生大量的隨機的有效解；②新解的產(chǎn)生策略必須保證可以有一定的有效解。又因為要求的兩個目標，也就是減少校正次數(shù)和減少路程并不完全正相關(guān)，尤其在這種復(fù)雜的約束的優(yōu)化問題中，因此考慮采用多目標群智能優(yōu)化算法，群智能優(yōu)化算法無論其大小如何，該算法都可以解決問題。從自然界中汲取靈感來開發(fā)計算效率高的算法是解決現(xiàn)實世界中最優(yōu)化問題的一種方法[9]。例如遺傳算法，遺傳算法是歷史上最早提出的基于種群的隨機算法之一，主要方法是選擇、交叉和變異[10]。這里考慮使用遺傳算法改進的智能優(yōu)化算法NSGA2遺傳算法，流程圖如圖3所示。問題一的模型優(yōu)化求解使用的是智能優(yōu)化算法NSGA2遺傳算法[11]，與傳統(tǒng)的遺傳算法上做了一些改進。為了更好的描述NSGA2遺傳算法對優(yōu)化模型進行求解，將優(yōu)化過程分為了一下幾個步驟：Step1：初始化種群，給定種群規(guī)模pop、迭代次數(shù)Gen、對初始化種群進行非支配快速排序和擁擠度計算。Step2：選擇：本文對選擇算子進行了一些改進，以Pij式(16)來做輪盤賭法的權(quán)值，其中Wmaxl為最大約束參數(shù)系數(shù)，將點與點之間的距離dij做線性變換，變換后的等式的倒數(shù)作為輪盤賭法的權(quán)值Pij，當兩個校正點的距離足夠小時，則對應(yīng)的權(quán)值Pij將會非常大(Pij<1)，因此被選中的概率也就非常大，這正好符合了實際問題對應(yīng)的航跡長度盡可能的小的要求。Step3：交叉：本文采用多點交叉法，所謂交叉，是指把兩個父代個體的部分結(jié)構(gòu)加以替換重組而生成新個體的操作，通過交叉，遺傳算法的搜索能力得以飛躍提高[12]。本文采用的交叉主要是通過輪盤賭法選擇了一組節(jié)點，以這組節(jié)點為分界線將兩條路徑分為四條路徑，四條路徑兩兩組合，生成兩條新路徑。Step4：變異：變異是對基因鏈上的某個基因按較小概率改變，以此保持個體的多樣性，克服早熟現(xiàn)象。變異算子是遺傳算法產(chǎn)生新個體的重要操作，是影響算法收斂性能的關(guān)鍵[13]。

(16)

(17)

圖3 NSGA2遺傳算法流程圖

4.2 蒙特卡羅算法

蒙特卡羅算法是一類隨機方法的統(tǒng)稱。這類方法依賴于使用計算機進行隨機實驗[14]。這種方法通常用于隨機模型或分布中取樣或估計與模擬模型相關(guān)的特定數(shù)量[15]。其工作原理就是隨著迭代次數(shù)的越來越多，近似結(jié)果是最終結(jié)果的概率也在增大。由于本文存在兩個方向的校正，垂直方向和水平方向，任何出現(xiàn)問題的方向很可能由于這5的單位而導(dǎo)致失聯(lián)，而這種現(xiàn)象可能下一個校正節(jié)點出現(xiàn)，也可能過了很多個校正節(jié)點才出現(xiàn)，統(tǒng)計其概率就會比較復(fù)雜，因此這里就提出了一種與概率正相關(guān)的參數(shù)作為優(yōu)化目標，從而來代替實際概率。因此本文提出了一種新的實現(xiàn)策略，定義概率作為參數(shù)，從而成為三個目標優(yōu)化問題，設(shè)初始失敗概率為0，初始成功概率為1，在每次都失敗的情況下，將會導(dǎo)致那幾次無法校正，每次出現(xiàn)失敗，就更新概率函數(shù)，概率函數(shù)如式(18)所示

(18)

式中Psuccessprob是成功概率，Pfailprob是失敗概率，這里的失敗概率不是真實中的失敗概率，只是與失敗概率正相關(guān)的參數(shù)。

4.3 仿真結(jié)果分析

4.3.1 數(shù)據(jù)集預(yù)處理

根據(jù)從起點A到終點B的航行路線，本文設(shè)計了一種圓環(huán)形包絡(luò)面算法，提高模型的求解效率如圖4所示。圓環(huán)形包絡(luò)面算法描述如下：首先根據(jù)點A和終點B的坐標信息，建立AB空間直線方程；然后以該直線為圓形中心線，以兩倍左右的臨界校正距離為半徑maxr，對該直線圓周內(nèi)校正點的數(shù)據(jù)進行搜索包絡(luò)，保留圓環(huán)內(nèi)的校正點數(shù)據(jù)，刪除剩余的校正點的數(shù)據(jù)，最終形成了一個圓環(huán)形包絡(luò)面數(shù)據(jù)集。相對于初始空域校正點集，預(yù)處理后的校正點數(shù)量大大減少。此外，采用兩倍的臨界校正距離為篩選半徑，可以保證校正點搜索空間充足，不會遺漏最優(yōu)校正點，從而不會影響最優(yōu)搜索路徑。

(19)

圖4 圓環(huán)形包絡(luò)面數(shù)據(jù)集

4.3.2 結(jié)果分析

以下是對問題一中的校正點進行航線規(guī)劃以后得出的結(jié)果，在經(jīng)過算法的處理后，得到了以下三個候選結(jié)果，分別是圖5、圖6、圖7所示。

圖5 飛行器規(guī)劃路徑a

表1 備選結(jié)果信息表

圖6 飛行器規(guī)劃路徑b

圖7 飛行器規(guī)劃路徑c

針對以上三個的候選航線，為了選出最佳航線，決定利用模糊綜合評價法來篩選出最優(yōu)航線，具體步驟如下所示：Step1：定義以下參數(shù)集合：{校正點數(shù)u1，航線總距離u2，最終誤差u3}；定義評價等級集合：{優(yōu)秀的v1，良好的v2，及格的v3，不及格的v4}；將權(quán)重賦值給每一個參數(shù)：{0.05，0.75，0.2}；Step2：可以計算得到三個模糊綜合評價矩陣R1，R2，R3，結(jié)果如下所示：{航線1：[0.18，0.48，0.315]；評價等級：優(yōu)秀};{航線2：[0.2，0.56，0.228]；評價等級：良好};{航線3：[0.23，0.64，0.13]；評價等級：良好}

綜上所述，選擇航線1作為最優(yōu)航線，在該航線中，經(jīng)過的校正點數(shù)為9個，航線的總距離為1.0945105米，垂直誤差為8.490014，水平誤差為19.686960，滿足約束條件。

航跡路徑規(guī)劃具體結(jié)果如表2所示：

表2 航跡規(guī)劃結(jié)果表a

問題二中的校正點經(jīng)過算法處理后的結(jié)果如圖8所示，飛行器的駕駛航線總共經(jīng)過了9個校正點，其中經(jīng)過了5個水平校正點和4個垂直校正點，飛行器的航線較為曲折，該航線經(jīng)過的總距離為1.1524e+05米，相較于AB之間的直線距離1.0046e+05米增加了14780米，符合經(jīng)過的校正點數(shù)盡可能少，經(jīng)過的航線總距離盡可能短的要求。

圖8 飛行器規(guī)劃路徑圖

航跡路徑規(guī)劃具體結(jié)果如表3所示：

表3 航跡規(guī)劃結(jié)果表b

下面利用校正點失效概率模型重新對該問題進行求解。求解得到的結(jié)果如圖9所示，該航線飛行的總距離為1.1828105m，相比較于AB點之間的直線距離1.0046105m，航線距離增加了17820m，相對增加了17.7%。飛行器共經(jīng)過了12個校正點，其中為6個水平校正點和6個垂直校正點。經(jīng)過的可能出現(xiàn)誤差的校正點編號為69，123，302，346，可能出現(xiàn)的無法到達的概率為8.39%。相比于上一種特殊情況，飛行器經(jīng)過的校正點數(shù)量減少了4個，飛行距離縮短了2362m，飛行效率比較高。

圖9 校正點失效概率模型飛行器規(guī)劃路徑圖

航跡路徑規(guī)劃具體結(jié)果如表4所示：

表4 航跡規(guī)劃結(jié)果表c

5 結(jié)論

1) 仿真驗證表明，圓環(huán)形包絡(luò)面算法可以保證校正點搜索空間充足，不會遺漏最優(yōu)校正點，降低了計算量，縮短了計算時間。

2) 在出現(xiàn)問題校正點時，本文提出的策略所生成的航跡路線，總體代價較小。在滿足最短路程和校正次數(shù)最少的基礎(chǔ)上，能夠完成飛行任務(wù)。

3) 本文采用的組合策略充分考慮了飛行器的復(fù)雜飛行環(huán)境和自身性能，表中數(shù)據(jù)也表明飛行器可以在復(fù)雜的飛行環(huán)境中不斷的定位誤差校正，最后精確地到達目的地，完成飛行任務(wù)。