多目標優化下智能飛行器三維航跡快速規劃

丁 超，吳梓杰，張 航

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

1 引言

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

2 問題描述與相關假設

2.1 問題描述

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

圖1 飛行器航跡規劃區域示意圖

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

2.2 相關假設

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

3 優化目標與約束條件確定

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

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

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

(1)

3.1.1 約束條件一

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

γp≤θ

(2)

γh≤θ

(3)

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

(4)

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

(5)

(6)

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

3.1.2 約束條件二

在對飛行器垂直誤差校正時，當飛行器的垂直誤差不大于α1個單位，水平誤差不大于α2個單位時才能進行垂直誤差校正，且經過校正，垂直誤差變為0，水平誤差不變。垂直校正點的校正誤差約束為

(7)

3.1.3 約束條件三

在對飛行器水平誤差校正時，當飛行器的垂直誤差不大于β1個單位，水平誤差不大于β2個單位時才能進行水平誤差校正，且經過校正，水平誤差變為0，垂直誤差不變。水平校正點的校正誤差約束為

(8)

3.2 飛行器轉彎控制策略

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

圖2 飛行器轉彎控制策略圖

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

Ri≥Rmin=200

(9)

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

(10)

式中

li=?πR/180

(11)

(12)

(13)

(14)

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

3.3 部分校正點失效情況

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

(15)

4 算法優化與仿真結果分析

4.1 NSGA2遺傳算法優化

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

(16)

(17)

圖3 NSGA2遺傳算法流程圖

4.2 蒙特卡羅算法

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

(18)

式中Psuccessprob是成功概率，Pfailprob是失敗概率，這里的失敗概率不是真實中的失敗概率，只是與失敗概率正相關的參數。

4.3 仿真結果分析

4.3.1 數據集預處理

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

(19)

圖4 圓環形包絡面數據集

4.3.2 結果分析

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

圖5 飛行器規劃路徑a

表1 備選結果信息表

圖6 飛行器規劃路徑b

圖7 飛行器規劃路徑c

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

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

航跡路徑規劃具體結果如表2所示：

表2 航跡規劃結果表a

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

圖8 飛行器規劃路徑圖

航跡路徑規劃具體結果如表3所示：

表3 航跡規劃結果表b

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

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

航跡路徑規劃具體結果如表4所示：

表4 航跡規劃結果表c

5 結論

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

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

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