謝濟銘,肖國梅,秦雅琴,勾 鈺,謝碧珊

(1.昆明理工大學 交通工程學院，云南 昆明 650504; 2.重慶交通大學 經(jīng)濟與管理學院，重慶 400074)

0 引 言

隨著航空技術(shù)的發(fā)展，飛行器航跡規(guī)劃也得到空前的發(fā)展.飛行器是一種飛行空間在大氣層內(nèi)或大氣層外的器械，其控制方式通常有三種：一是由混合編隊中的有人駕駛飛機通過近距離數(shù)據(jù)通信鏈實現(xiàn)；二是利用遠距離的空中或地面指揮平臺進行通信控制；除此，通過衛(wèi)星控制飛行器也較常見[1].上述方法的共同點在于都是利用外界的數(shù)據(jù)通信鏈實現(xiàn)對飛行器的控制，但在惡劣的飛行環(huán)境下，通信鏈的可靠性可能會下降，此時對飛行器的控制可能失效，產(chǎn)生無法預(yù)料的后果.因此，對于在復(fù)雜環(huán)境中工作的飛行器，則必須要求其具有一定的自主飛行控制決策能力，以適應(yīng)復(fù)雜多變的環(huán)境[2].

航跡規(guī)劃的約束條件和不確定因素均較多，且各因素之間的關(guān)聯(lián)性不強.航跡規(guī)劃問題求解方法通常包括數(shù)值法、反解法和搜索法三類經(jīng)典算法.數(shù)值法是通過控制目標函數(shù)的最值得到最優(yōu)路徑，分為概率法和目標函數(shù)法.反解法是在給定起訖點及過渡點狀態(tài)的條件下，采用運動學方法反解起訖點可行路徑.搜索法是根據(jù)路徑形式特點，基于人工智能算法搜索可行路徑并求解，分為單元分解法、人工勢能場法[3]、遺傳算法[4-7]、粒子群算法[8-10]、蟻群算法[11-13]和路線圖法，其中路線圖法還包括A*算法、深度優(yōu)先搜索法、可視圖法、輪廓法以及Voronoi圖法[14]等.

上述方法中，數(shù)值法可較精確的計算并得到最優(yōu)路徑，一般用于弧線或螺旋線等單一路徑問題的求解，或某種特定路徑形式下的最優(yōu)解，不過數(shù)值法適應(yīng)性較差，對于混合型路徑的規(guī)劃與求解，受限于算法結(jié)構(gòu)，難以從路徑規(guī)劃的角度求得真正意義上的最優(yōu)解.反解法不能保證有解和最優(yōu)，對于全局規(guī)劃問題，通常不優(yōu)先考慮反解法.搜索法則基于人工智能搜索算法，為得到高精度結(jié)果如采用單元分解法，會導致算法復(fù)雜度急劇提升；人工勢場法往往求得的結(jié)果為局部最優(yōu)，導致飛行器會在多個目標點附近來回抖動，其結(jié)果不能保證最優(yōu)；遺傳算法具有簡單通用、魯棒性強、隱并行性和更好的全局尋優(yōu)能力，在許多的領(lǐng)域特別是在求解組合優(yōu)化的問題中得到了廣泛的應(yīng)用[15],不過該方法容易出現(xiàn)過早收斂、編碼不準確等問題.總體而言，相比數(shù)值法和反解法，人工智能算法由于其啟發(fā)式尋優(yōu)的特點，可有效提升飛行器自主導航飛行的效率，不過仍有待進一步提升智能算法的實時性、魯棒性及并行性.

針對智能算法的局限性，國內(nèi)外學者從諸多方面做出了優(yōu)化，主要包括編碼方式[5]、算法融合[11]、算法精度[12]、協(xié)同進化[16]等方面.飛行器航跡規(guī)劃是在綜合考慮飛行時間、區(qū)域以及設(shè)備故障威脅等約束條件下，為飛行器規(guī)劃出相對較優(yōu)的飛行路徑，從而保證飛行器能夠成功完成飛行任務(wù)[15].

可見，飛行器在執(zhí)行任務(wù)過程中會受到諸多外在因素影響和自身約束條件的限制，如何使生成的航跡滿足這些約束條件，是當前航跡規(guī)劃研究需要解決的關(guān)鍵問題.本文重點從轉(zhuǎn)彎半徑、航跡規(guī)劃、校正定位因素3個方面建立代價函數(shù)，并構(gòu)建協(xié)同控制模型，控制飛行器運行航跡最短、經(jīng)過校正點最少，并對算法的有效性和適用性進行討論.

1 背景描述與模型假設(shè)

1.1 背景描述

復(fù)雜情況下，飛行器受系統(tǒng)結(jié)構(gòu)的限制，其定位系統(tǒng)無法對自身位置進行精準定位，定位誤差累積到一定程度將導致任務(wù)失敗.因此，在飛行過程中，飛行器不僅要對航跡進行快速規(guī)劃，還要校正定位誤差，飛行區(qū)域中存在一些校正點，即安全位置，可用于校正定位誤差，避免飛行一段距離之后，飛行器難以繼續(xù)前進、導致任務(wù)失敗的情況發(fā)生.

上述情況即為面向?qū)嶋H航跡規(guī)劃問題中的約束條件，具體指的是在航跡規(guī)劃時飛行器的動力學特性約束與任務(wù)的特殊要求約束，可分為上層硬件性能約束與底層算法效率約束兩方面，硬件性能主要包括最大爬升角、最大下滑角、精準定位、轉(zhuǎn)彎半徑等動力學特性約束，而算法效率則主要考慮飛行航跡等任務(wù)規(guī)劃問題.

由于飛行器最大爬升角、最大下滑角屬于飛行器起降階段考慮的條件，航跡規(guī)劃問題不受其影響. 此外，交通領(lǐng)域應(yīng)用以往研究大都聚焦于算法效率方面的提升，考慮硬件性能方面因素相對較少，本文結(jié)合算法效率與硬件性能兩方面，重點針對航跡規(guī)劃過程面臨的精準定位、轉(zhuǎn)彎半徑與算法效率等約束，構(gòu)建航跡規(guī)劃的一般模型和算法，如圖1所示. 模型目標為智能飛行器從起點飛到目的地的航跡長度盡可能小、校正次數(shù)更少.

圖1 飛行器規(guī)劃建模示意圖Fig. 1 Sketch of aircraft planning and modeling

1.2 模型假設(shè)

飛行器在空間飛行過程中的定位誤差包括垂直誤差和水平誤差.垂直誤差與水平誤差隨飛行器每飛行1 m將各增加δm，而飛行器一次只能校正一種誤差，即水平或垂直誤差，不能同時對水平與垂直誤差清零.另外，飛行器的最小轉(zhuǎn)彎半徑為γm，這是因為在轉(zhuǎn)彎時，飛行器受結(jié)構(gòu)和控制系統(tǒng)的限制，無法完成即時轉(zhuǎn)彎.飛行器按照正常軌跡飛行的假設(shè)條件設(shè)置如下：

1)飛行器在垂直誤差和水平誤差均小于θ個單位時，仍能夠按照規(guī)劃路徑飛行；

2)飛行器可以按照規(guī)劃路徑飛行，通過若干個校正點，對水平誤差和垂直誤差校正后到達終點；

3)在起點A處，飛行器的垂直誤差和水平誤差均為0；

4)飛行器在垂直誤差校正點進行誤差校正后，垂直誤差為0，水平誤差不變；

5)飛行器在水平誤差校正點進行誤差校正后，水平誤差為0，垂直誤差不變；

6)在飛行過程中，垂直誤差不大于α1個單位，水平誤差不大于α2個單位時，飛行器才能校正垂直誤差；

7)在飛行過程中，垂直誤差不大于β1個單位，水平誤差不大于β2個單位時，飛行器才能校正水平誤差；

8)任意相鄰的兩個點之間，飛行器都能按照直線飛行；

9)飛行器在飛行過程中不會出現(xiàn)設(shè)備故障、燃料不充足等問題；

10)不考慮霧霾、雷雨天氣等因素對飛行器的正常飛行造成的影響.

主要符號變量說明如表1所示.

表1 符號變量說明

2 模型及算法

2.1 航跡規(guī)劃模型

理想狀態(tài)下，三維坐標圖中，假設(shè)已知飛行器的起點和終點位置坐標，要使飛行器的航跡長度盡可能地小，說明飛行器在滿足轉(zhuǎn)彎半徑至少為γm的情況下盡量按直線飛行，以飛行的總成本最小或者在滿足約束條件的前提下通過的路徑最短及校正次數(shù)最少設(shè)置為目標函數(shù)，建立如下模型：

(1)目標函數(shù)

理想狀態(tài)下，在不考慮飛行器轉(zhuǎn)彎的情況下，在三維坐標圖中，已知飛行器的起點和終點，要使飛行器的航跡長度盡可能小，飛行器盡量以直線飛行并且中途無轉(zhuǎn)彎或者掉頭的情況出現(xiàn)，因此航跡規(guī)劃的總目標是使總成本最小[17]或者在滿足模型約束的基礎(chǔ)上路徑最短.此次目標函數(shù)為選擇的路徑最短，設(shè)定的目標函數(shù)為：

(1)

受自身結(jié)構(gòu)和控制系統(tǒng)的限制，飛行器不能立即轉(zhuǎn)彎，其轉(zhuǎn)彎半徑不小于γm,假設(shè)飛行器在第i點轉(zhuǎn)彎，那么飛行器在轉(zhuǎn)彎時至少要在飛行半徑γm的范圍內(nèi)，記第i+1點轉(zhuǎn)彎為飛行器剛好飛至γm處的轉(zhuǎn)彎點，飛行器需要轉(zhuǎn)彎到達的點為第i+2個點，因此目標函數(shù)可設(shè)為：

(2)

為使飛行器從起點到終點的路徑最短，設(shè)此目標函數(shù)為飛行器從起點到終點的歐式距離最短即為路徑最短：

(3)

飛行器在飛行途中，隨著里程數(shù)的增加，誤差也隨之增加，為保證飛行器飛行途中經(jīng)過校正區(qū)域校正的次數(shù)盡可能地少，可設(shè)置途中增加的水平誤差與垂直誤差之和最小.

(2)約束條件

飛行器最終的飛行距離等于垂直飛行距離和水平飛行距離的平方和的平方根：

(4)

飛行器在出發(fā)點時，矯正垂直和水平誤差均為零：

Cv(xv0)=0,且Ch(xh0)=0

(5)

飛行器從垂直誤差校正點1到垂直誤差校正點2的垂直誤差的累積表達式為：

Cv(xv2)=Dis·δ+Cv(xv1)

(6)

飛行器從水平誤差校正點1到水平誤差校正點2的水平誤差的累積表達式為：

Ch(xh2)=Dis·δ+Ch(xh1)

(7)

飛行器在抵達某一垂直校正點時，控制累積垂直誤差與水平誤差小于θ：

Cv(xi)≤θ,且Ch(xi)≤θ

(8)

飛行器經(jīng)過垂直校正點后，垂直誤差清零，水平誤差保持不變：

Cv(xvi)≤α1,且Ch(xvi)≤α2

(9)

飛行器經(jīng)過水平校正點后，水平誤差清零，垂直誤差保持不變：

Cv(xhi)≤β1,且Ch(xhi)≤β2

(10)

當飛行器的垂直誤差不大于α1個單位，水平誤差不大于α2個單位時，飛行器才能進行垂直誤差校正：

Cv(xvi)=0,且Ch(xvi)=Ch(xvi)

(11)

飛行器垂直誤差不大于β1個單位，水平誤差不大于β2個單位時，飛行器才能進行水平誤差校正：

Cv(xvi)=0,且Ch(xvi)=Ch(xvi)

(12)

飛行器由于無法即時轉(zhuǎn)彎，且轉(zhuǎn)彎半徑至少為γm的約束條件：

(13)

2.2 求解算法

飛行器在飛行過程中，需要不斷地進行航跡校正，才能沿原定目標繼續(xù)進行.為保證飛行器的效率性與經(jīng)濟性，飛行器目標函數(shù)設(shè)置為飛行距離最短以及校正次數(shù)最少，采用具有不易陷入局部最優(yōu)等優(yōu)點的NSGA-II(Non-dominated Sorting Genetic Algorithm)全局優(yōu)化算法.具體思路為：首先將航跡規(guī)劃轉(zhuǎn)化為三維求解問題，將曲率半徑求解轉(zhuǎn)換為立體曲率半徑求解；然后考慮到減少校正次數(shù)和縮短路程兩個目標函數(shù)之間并不完全正相關(guān)，采用多目標優(yōu)化模型進行優(yōu)化；最后基于Pareto排序的多目標遺傳算法求出更優(yōu)的航跡規(guī)劃解.

NSGA-II算法原理為，通過引入精英策略的快速非支配排序，擴大采樣空間，避免丟失最優(yōu)個體.可見，算法既可以滿足多目標規(guī)劃的要求，也可計算飛行器在三維坐標中從起點到終點的最短路徑.由于本文不考慮飛行器運行期間的速度波動、氣候異常問題，因此在既定的起終點及初始航向條件下，當航線所有校正點及航段都可行時，通過求解每個校正點校準功能與航線距離，即確定飛行器航線.據(jù)此，在NSGA-II算法基礎(chǔ)上，構(gòu)建如圖2所示航跡規(guī)劃流程.

圖2 基于NSGA-II算法的航跡規(guī)劃流程Fig.2 Route planning process based onNSGA-II algorithm

STEP 1：參數(shù)設(shè)定.算法將航線節(jié)點規(guī)劃轉(zhuǎn)換為染色體基因表達問題，選取適應(yīng)度函數(shù)(Fitness Function)，即航跡評價函數(shù)，用以反映航線的優(yōu)劣. 設(shè)N為初始化種群規(guī)模，t為進化代數(shù)，航跡評價函數(shù)Jk如下：

(14)

STEP 2：編碼解碼.編碼技術(shù)是NSGA-II的核心，選擇合理的編碼方式與解碼操作是保證算法有效性的前提.經(jīng)典的NSGA-II中編碼技術(shù)為二進制，編碼過程簡便，交叉和遺傳操作容易實現(xiàn).不過，對于特定問題的最優(yōu)解，二進制編碼方式不一定最優(yōu)[17].本文根據(jù)所研究航跡規(guī)劃涉及的控制參數(shù)特點，引入基于航向變化量的實數(shù)編碼方式，提高編碼方式與求解問題形式之間匹配度，以及算法的局部搜索能力.

基于此，假設(shè)基于實數(shù)編碼得到的基因結(jié)果為[ΔΨ1,…，ΔΨn]，則對應(yīng)航向為[λ1,…，λn]，通過解碼分析將航向變化量轉(zhuǎn)換為直角坐標系空間，結(jié)合起終點坐標、飛行時間信息，求得相應(yīng)飛行距離[D1，…，Dn]，得出飛行器空間位置信息，解碼操作如圖3所示.其中，ΔΨi、λi、Di,1≤i≤n分別代表航向變化量編碼結(jié)果、以及相應(yīng)的航向方位與航向距離.

圖3 解碼操作Fig.3 Decoding operation

STEP 3：初始種群.采用改進的實數(shù)基因編碼方式進行編解碼形成初始種群P0，此時t=0.根據(jù)航跡規(guī)劃特性，選擇了比輪盤賭策略性能更優(yōu)的錦標賽策略，對Pt進行染色體優(yōu)選，即航跡優(yōu)選，進而產(chǎn)生優(yōu)化種群.

STEP 4：交叉變異.從Pt中選擇N個個體(染色體)進行交配，基于序值和擁擠距離選擇序值小、擁擠距離大的個體，接著對交配池中個體進行交叉與變異操作.產(chǎn)生子代種群Qt，將Qt與Pt組合為Rt.其中，交叉操作約束航跡距離與航向校正，變異操作則基于高斯變異產(chǎn)生隨機數(shù)以替換原數(shù)值.

STEP 5：環(huán)境選擇.采用非支配排序方法對Rt進行環(huán)境選擇，維持種群規(guī)模N，產(chǎn)生新的親本種群Pt+1.

STEP 6：結(jié)果判斷.判斷是否滿足條件T(T為最大進化代數(shù))，當t

3 算例分析

數(shù)據(jù)來源于2019年中國研究生數(shù)學建模比賽，通過對數(shù)據(jù)中的612個坐標進行目標搜索，以飛行器起點到終點航跡最短和校正點最少優(yōu)化目標，其參數(shù)的值分別設(shè)置為：γ=200，θ=30，α1=25，α2=15，β1=20，β2=25，δ=0.001，分別得出飛行器在不考慮及考慮轉(zhuǎn)彎半徑的航跡規(guī)劃圖和誤差大小情況，以及兩種情況的校正坐標個數(shù)與航跡距離.

為驗證NSGA-II全局優(yōu)化算法(模型I)的有效性，構(gòu)建了基于遺傳算法的對比模型[18](模型II適用于三維全局航跡規(guī)劃問題求解).基于相同驗證場景，統(tǒng)計模型II的航跡長度、校正點個數(shù)、任務(wù)失敗概率、計算時間與迭代次數(shù)等指標，與模型I結(jié)果進行對比.

3.1 不考慮轉(zhuǎn)彎半徑的航跡規(guī)劃結(jié)果

當不考慮轉(zhuǎn)彎半徑時，飛行器的運行軌跡如圖4所示.藍色點為飛行器從起點到終點可選擇飛行與校正的坐標，黑色五角星為航跡校正點.可以看出，飛行器在不考慮轉(zhuǎn)彎半徑的情況下，通過Pareto多目標求解，從局部最優(yōu)尋求全局最優(yōu)的校正點分布，以歐幾里得二范數(shù)最小的目標函數(shù)，最終實現(xiàn)了航跡114 590.96 m、經(jīng)過11個校正點飛達目的地的最短路徑目標.

圖4 不考慮轉(zhuǎn)彎半徑的航跡規(guī)劃圖Fig.4 Route planning without considering turning radius

表2列出了各模型航跡長度及校正點數(shù)量，可以看出：(1)模型I、II航跡長度分別為114 590.96 m、121 787.02 m，模型I航跡更短，顯著優(yōu)于模型II；(2)模型I、II校正點個數(shù)分別為11個、12個，表明模型I效果更優(yōu)，具備更佳的誤差校正能力.總體上，模型I可更好地實現(xiàn)航跡規(guī)劃任務(wù)，說明結(jié)合任務(wù)特性制定算法規(guī)則可有效提升復(fù)雜航跡規(guī)劃問題的結(jié)果，更符合實際需求.

表2 模型結(jié)果對比

3.2 考慮轉(zhuǎn)彎半徑的航跡規(guī)劃結(jié)果

如圖5所示，考慮到轉(zhuǎn)彎半徑的情況，飛行器根據(jù)新約束條件的變化，更新數(shù)據(jù)并重新進行快速航跡規(guī)劃.假設(shè)飛行器需要在第i點轉(zhuǎn)彎，則飛行器轉(zhuǎn)彎時必須要再飛行半徑至少為200 m的范圍. 記第i+1點(該點為切點)轉(zhuǎn)彎為飛行器剛好飛200 m處的轉(zhuǎn)彎點，飛行器需要轉(zhuǎn)彎到達的點為第i+2個點,第i+2個點與第i個點的歐氏距離最短，相當于以第i點為圓心，半徑為200 m球體的切面的交點與第i+2個點的距離最短.最終實現(xiàn)飛行器的總行駛距離為117 866.12 m，經(jīng)過10個校正點飛達目的地的最短路徑目標.

圖5 考慮轉(zhuǎn)彎半徑的航跡示意圖Fig.5 Track diagram considering turning radius

基于相同場景驗證考慮轉(zhuǎn)彎半徑條件下模型的有效性，表3展示了模型Ⅰ、模型Ⅱ的航跡長度及校正點數(shù)量，可以看出：模型I、II航跡長度分別為117 866.12 m、123 273.02 m，校正點個數(shù)分別為10個、11個，模型I航跡更短、校正點個數(shù)更少，顯著優(yōu)于模型II.總體上，模型I對于考慮轉(zhuǎn)彎半徑條件與不考慮轉(zhuǎn)彎半徑條件均表現(xiàn)更優(yōu)，說明基于NSGA-II算法的航跡規(guī)劃算法具有更好的適用性.

表3 模型結(jié)果對比

圖6為飛行器轉(zhuǎn)彎過程示意圖，其中B點為轉(zhuǎn)彎相切點，洋紅色線為飛行器經(jīng)過一個切點的運行軌跡.由圖7可看出(x,y,z)取值變化，當x和y值都在不斷增加時，z值在平穩(wěn)中不斷的上下飄浮；當y與z值分別取得最大時，隨著x值的增加，y和z的值不斷下降，各個變量的值逐漸平穩(wěn)，x的值也逐漸與軸線平行，模型收斂. 可以看出，模型Ⅰ收斂速度較快，可滿足實時性要求.

圖6 轉(zhuǎn)彎半徑示意圖Fig.6 Diagram of turning radius

圖7 收斂圖Fig.7 Convergence graph

3.3 不同場景結(jié)果分析

通過對比兩種實驗場景下校正點距離及其誤差，從表4～表5可以看出：

表4 不考慮轉(zhuǎn)彎半徑的航跡規(guī)劃結(jié)果表

表5 考慮轉(zhuǎn)彎半徑的航跡規(guī)劃結(jié)果表

1)除起始點外，不考慮轉(zhuǎn)彎半徑的航跡規(guī)劃模型校正點個數(shù)為11個，需要校正的水平誤差為5.86、垂直平均校正誤差為6.622.

2)整體來看，不考慮轉(zhuǎn)彎半徑場景下校正點更少，飛行器飛行距離更短，說明在航跡規(guī)劃任務(wù)中，還應(yīng)考慮改善飛行器轉(zhuǎn)彎半徑的限制條件，避免過度受機械機動性能約束，以更好完成實際運行目標.

3)任務(wù)失敗概率方面，在不考慮轉(zhuǎn)彎半徑的條件下，基于模型II執(zhí)行飛行任務(wù)時，在第4、5、6、13號校正點出現(xiàn)失敗概率；而在考慮轉(zhuǎn)彎半徑的條件下，模型II在第3、5、9、11號校正點出現(xiàn)失敗概率，模型I在兩種場景下任務(wù)失敗概率均為0，驗證了模型I的有效性與魯棒性.

可見，飛行器在飛行過程中，環(huán)境可能隨時間變化而變化，受到環(huán)境和技術(shù)條件的影響，飛行器在進行誤差校正時，有部分校正點將無法準確校正，應(yīng)提前預(yù)估飛行器的航跡并及時重新規(guī)劃軌跡，提高飛行器校正成功的概率.

選取算法計算時間與收斂迭代次數(shù)兩個指標，驗證模型Ⅰ性能，結(jié)果如表6所示. 可以看出，在考慮轉(zhuǎn)彎半徑與不考慮轉(zhuǎn)彎半徑兩種場景下，模型Ⅰ的計算時間與收斂迭代次數(shù)均比模型Ⅱ表現(xiàn)更優(yōu)，表明基于NSGA-Ⅱ算法的航跡規(guī)劃算法具有更好的普適性與實時性.

表6 算法性能對比

4 結(jié) 論

針對航跡規(guī)劃過程面臨的精準定位、轉(zhuǎn)彎半徑與算法效率等約束，本文建立了考慮硬件性能約束與算法效率約束的航跡規(guī)劃方法，構(gòu)建了包括考慮轉(zhuǎn)彎半徑、不考慮轉(zhuǎn)彎半徑的實際規(guī)劃問題場景，提出了基于NSGA-II的全局優(yōu)化算法，最終實現(xiàn)了航跡的快速有效規(guī)劃.實例驗證表明，本文方法航跡規(guī)劃效果優(yōu)于經(jīng)典遺傳算法，航跡長度、校正點個數(shù)、任務(wù)失敗概率、計算時間與迭代次數(shù)等指標均更優(yōu)，進一步表明模型具有良好的適應(yīng)性，能更好地分配時空資源，實現(xiàn)規(guī)劃效率和任務(wù)需求的均衡.

由于飛行場景的復(fù)雜多樣性，本文航跡規(guī)劃方法仍存在一定的局限性，模型參數(shù)與優(yōu)化設(shè)置仍需進一步研究.同時，航跡規(guī)劃問題約束條件相對較多，在此基礎(chǔ)上若加以考慮速度波動、氣候異常等更多環(huán)境約束情形，可進一步推廣應(yīng)用.此外，考慮模型本身的魯棒性和隱含并行性，處理過程較復(fù)雜，下一步研究將從設(shè)計方面完善遺傳操作，適應(yīng)飛行環(huán)境變化的同時提高算法的實時性，有望實現(xiàn)飛行軌跡實時重規(guī)劃.