丁 超，吳梓杰，張 航

(1.中南大學(xué)計(jì)算機(jī)學(xué)院，湖南 長沙410083;2.中南大學(xué)自動(dòng)化學(xué)院，湖南 長沙410083)

1 引言

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

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

2.1 問題描述

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

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

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

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

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

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

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

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

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

(1)

3.1.1 約束條件一

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

γ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 約束條件二

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

(7)

3.1.3 約束條件三

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

(8)

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

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

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

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

Ri≥Rmin=200

(9)

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

(10)

式中

li=?πR/180

(11)

(12)

(13)

(14)

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

3.3 部分校正點(diǎn)失效情況

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

(15)

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

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

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

(16)

(17)

圖3 NSGA2遺傳算法流程圖

4.2 蒙特卡羅算法

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

(18)

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

4.3 仿真結(jié)果分析

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

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

(19)

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

4.3.2 結(jié)果分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)論

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

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

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