基于蟻群算法對飛行器航跡規劃的研究

劉文文，朱家明

(1.中央民族大學 經濟學院，北京100081; 2.安徽財經大學 統計與應用數學學院， 蚌埠233030)

飛行器航跡規劃的任務就是在多種條件的約束下，為無人飛行器尋找一條從起點到終點的最優路徑.飛行器在飛行過程中，由于系統結構的限制和飛行環境帶來的各種擾動往往會產生累積的定位誤差，這種誤差會隨著飛行時間和飛行距離的增加而不斷累積，從而最終導致飛行任務失敗.這一問題的通常解決辦法是，在航跡的特定位置對累積誤差進行校正，不僅能保證無人飛行器的安全，還能保證飛行任務的高精度完成.

蟻群算法是指蟻群可以在不同的環境下，尋找到達食物源的最短路徑.因為蟻群內的螞蟻可以通過“信息素”實現信息的傳遞.“信息素”濃度越高的路徑有越大的概率被螞蟻選擇，而每只路過的螞蟻都會在路上留下“信息素”，形成一種正反饋的機制，經過一段時間后，最終整個蟻群就會沿著最短路徑到達食物源了[1].而航跡規劃問題本質上就是在滿足既定的飛行約束條件下，在眾多可行的飛行路徑中尋找一條最優(最短)的飛行路徑，這與蟻群尋食的情景非常相似.因此，在解決航跡規劃問題時最容易想到的現代智能優化算法就是蟻群算法.

目前國內外已有很多學者做了相關方面的研究，Zhao Q等(2015)針對雷達威脅環境下的多架無人機編隊的路徑規劃問題，提出了一種基于改進蟻群算法的智能方法[2].Calik，Seda Kazdal(2016)提出了一種針對無人機的全局最優軌跡規劃問題的解決方法，該模型被建模為具有多主體結構的蟻群優化(ACO)，仿真結果表明ACO極大地優化了航線長度，減少了無人機航路規劃的平均飛行時間[3].趙丹和戚龍(2017)在滿足無人機飛行約束條件的情況下, 為無人機航跡規劃提供一種蟻群-粒子群融合算法, 充分利用蟻群算法良好的分布機制、信息反饋機制和粒子群算法收斂，保證了飛行器航線的完整性和最優性[4].Wu Zhenyu，Li Jinhuan，Zuo Jiaming等 (2018)針對動態環境下多無人機通信狀態信息噪聲引起的不一致問題，提出了一種基于卡爾曼算法的狀態估計方法.為了實現飛機的航跡規劃，最終計算出群集狀態預測和碰撞概率，以避免編隊無人機的群集在飛行過程中在路徑上發生沖突[5].王瓊，劉美萬，任偉建等(2019)對航跡規劃常用算法進行了綜述，并且預測了無人機四維航跡規劃算法的未來發展[6].

為了研究方便，本文主要以2019全國研究生數學建模競賽F題所給的背景為主要研究背景，研究無人飛行器在系統定位精度限制下的航跡快速規劃問題.首先，對實際的航跡規劃問題進行適度的簡化，提出一定的假設條件，在此基礎上提出對航跡規劃問題的數學模型，并利用蟻群算法對此數學模型進行求解.在模型求解過程中，我們將對利用蟻群算法求解航跡規劃問題中的關鍵問題進行詳盡分析.

1 數據來源

本文數據來源于2019全國研究生數學建模競賽F題的附件1(本文的附錄2列出了其中部分數據).附件1給出了612個矯正點(包括起點和終點)的三維空間坐標(X坐標、Y坐標、Z坐標)，坐標單位米(m).并標出了每個矯正點的矯正點類型和矯正點質量.對于矯正點類型：1表示垂直誤差校正點，0表示水平誤差校正點；對于矯正點質量：1表示可能出現問題的點，0表示正常校正點.

2 飛行器的航跡約束

飛行器的飛行區域如圖1所示，出發點為A點，目的地為B點.形象地說，飛行器的航跡就是一條以A點(附件1中的出發點)為出發點，以B點(附件1中的終點)為終點，中間串連了許多矯正點的曲線.航跡的具體約束如下：

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

1)飛行器在運動過程中需要時刻進行定位，飛行過程中產生的定位誤差包括水平誤差和垂直誤差.飛行器每飛行1 m，垂直誤差和水平誤差將各增加δ個專用單位，以下簡稱單位.飛行器到達終點時垂直誤差和水平誤差均應小于θ個單位，并且為簡化問題，假設當垂直誤差和水平誤差均小于θ個單位時，飛行器依然可以根據規劃路徑飛行.

2)飛行區域中有一些安全位置(校正點)可以對飛行中的飛行器進行誤差校正，飛行器到達校正點根據矯正點類型進行誤差校正.垂直和水平誤差的校正位置可以根據地形在航跡規劃前確定(如圖1為某條航跡的示意圖,圖中●是水平誤差校正點，▲是垂直誤差校正點，A點出發，終點B，曲線表示飛行器的一條航跡).地形影響可校正的飛行區域分布，無統一規律，若垂直誤差、水平誤差都能得到及時校正，則飛行器按規劃航跡進行飛行，經過若干個校正點的校正后到達終點.

3)飛行器的出發點為A，垂直和水平誤差均為0.

4)在垂直誤差校正點，飛行器校正垂直誤差使其為0，水平誤差不變.

5)在水平誤差校正點，飛行器校正水平誤差使其為0，垂直誤差不變.

6)飛行器垂直誤差校正的條件為：垂直誤差不大于α1個單位，水平誤差不大于α2個單位.

7)飛行器水平誤差校正的條件為：垂直誤差不大于β1個單位，水平誤差不大于β2個單位.

8)由于結構和控制系統的限制，飛行器無法完成即時轉彎(即前進方向無法突然發生變化)，假設飛行器的最小轉彎半徑為200 m.

為了方便模型建立與求解，我們首先將上述航跡約束條件進行數學抽象表達.

(1)

其中：H為上一個水平校正點或起點，其中V為上一個垂直校正點或起點，P(x，y，z)為當前位置點.Jh={H1,H2,…HN}為水平校正點集合，Jh={J1,J2,…JN}為垂直矯正點集合.此式為水平誤差和垂直誤差的累積方式.

(2)

其中：Hend、Vend、Pend分別為航跡中的最后1個水平矯正點、最后1個垂直矯正點和終點.此式為飛行器成功飛抵終點的條件.

δh=0,如果:P∈JH,且δh<α1,δv<α2

δv=0,如果:P∈JV,且δh<α1,δv<β2

(3)

如果到達矯正點，且飛行誤差在矯正點的可矯正范圍之內，則將相應的誤差清零.

3 基礎模型

為了建立有效的數學模型，必須把現實問題進行適當的假設與簡化，進而映射到數學空間.本文本著由易到難的研究辦法，首先建立較為基礎模型，在完成基礎模型的求解之后，進一步改進數學模型，考慮更多現實因素，使模型更加貼近實際情況.

3.1 模型的建立

基礎模型基于3個假設：首先假設航跡從A出發，B結束，且只需要滿足上述航跡約束的前7條，其次假設航跡是折線，即矯正點之間直線飛行，在矯正點處突然改變航向.最后上述約束中參數為：α1=25，α2=15，β1=20，β2=25，θ=30，δ=0.001.數學模型的求解目標是尋找一條使得飛行器航跡盡可能短、航跡上的矯正點盡可能少的航跡，其數學表達形式為：

(4)

其中：α、β分別為航跡長度和矯正點數的權重因子，Li為航跡上矯正點間的距離，這里所有的矯正點包括起點和終點，其計算公式如下：

(5)

3.2 基于蟻群算法的模型求解

根據蟻群算法解決航跡規劃問題的整體解決思路，模擬蟻群在遵守約束條件的情況下從A點爬到B點(Nm是指蟻群中螞蟻的個數)，然后對螞蟻走過的所有路徑進行評分，從Nm條螞蟻走過的路徑中選擇出一條最優路徑，更新最優路徑上各校正點的評分，同時更新歷史最優路徑，并判斷最優路徑的評分是否收斂，確定收斂則得出最優路徑，否則回到開始繼續模擬螞蟻從起點到終點.蟻群算法的整體流程框圖如圖2所示.

圖2 蟻群算法的整體流程框圖

3.2.1 每只螞蟻的模擬過程

為了能在最短的時間內找到最優航跡，并且保持一定的全局最優性.我們將每只螞蟻視為獨立的個體，且具有一定的智能性，螞蟻之間只通過信息素交換信息.模擬螞蟻從起始點到終點的算法框圖如圖3所示，具體流程為：

圖3 螞蟻從起始點到終點的算法流程框圖

1)參數初始化，包括螞蟻個數N，出發點和到達點等.

2)讀入已知的數據，建立規劃空間模型，獲取飛行區域校正點類型信息.

3)開始循環.

4)在當前誤差選擇在下一個校正點要校正水平誤差δH還是垂直誤差δV.若校正δH，則h_or_v=0(注：h_or_v=0，指校正水平誤差；h_or_v=1，指校正垂直誤差).

5)根據當前誤差和h_or_v的值計算最大飛行距離，即可行域半徑R.

6)根據R和h_or_v的值選擇可行域中的校正點，并且把這些點作為候選點.

7)對所有候選點進行評分，分數用s表示.

8)依據概率密度函數f(s)隨機從候選點中選擇一個點作為下一個校正點.

9)螞蟻到達下一個校正點后，更新當前位置點和當前誤差.

10)判斷是否到達終點B，如果是，對此次螞蟻走過的路徑進行評分，輸出這條路徑的所有點和路徑評分；否則，回到步驟4)繼續執行[7-8].

11)算法結束.

3.2.2 矯正類型選擇方法

在航跡規劃中，選擇下一個矯正點矯正類型的方式，對航跡的規劃結果至關重要，不但影響航跡的長短和矯正點的多少，而且有可能讓螞蟻陷入“死胡同”，無法繼續航行，這種情況為：

當α2-δh>0，β1-δv>0時，同時無法矯正δh和δv.因此，下一個矯正點的矯正方式應慎重選擇，本文的選擇方法是首先考慮矯正的可行性，即選擇的下一個矯正類型必須在可矯正的誤差范圍之內.具體方法為：當α2-δh>0，β1-δv<0時，矯正δv；當α2-δh<0，β1-δv>0時，矯正δh.其次矯正的緊迫性，離可矯正誤差上限越近的誤差類型，被矯正的需求就越緊迫，具體方法為：當α2-δh<0，β1-δv<0時，同時可矯正δh和δv.

H_or_V=argmin{(α1-δv),(β2-δh)}

(6)

其中：H_or_V為矯正類型，H_or_V=0表示水平矯正，H_or_V=1表示垂直矯正.

3.2.3 選擇可行域半徑的方法

可行域半徑的選取同樣十分重要，如果半徑過小，不但會使航跡的矯正點數增加，還容易導致可行域內沒有可用的矯正點.如果半徑過大，會導致剩余誤差裕度過小，從而致使本次航行失敗.我們的選擇辦法具體為：

(7)

其中：R表示可行域半徑.即可行域半徑由當前兩個誤差裕度中的最小的一個決定，最小誤差裕度除以誤差因子就是當前的可行域半徑的長度.

3.2.4 可行域的選取方法

可行域是指下一個所有可能矯正點所在的區域，建立可行域將為形成下一個矯正點的候選點集合提供方便.我們建立的可行域是一種球面椎體，可行域中的矯正點P同時滿足如下兩個條件：

(8)

(9)

3.2.5 對候選點的評分方法

對候選點的評分方法是螞蟻智能性的直接體現，好的評分方法將會引導螞蟻走更優的路徑，反之，螞蟻螞蟻將會直接失去大腦.我們對候選點的評分方法具體如下：

(10)

其中：P為候選點的位置，Pend為終點位置，αs為評分因子，評分將會在下文詳細介紹.Js可行域中候選點的集合.即與終點越近的候選點評分越高，這種啟發式有點類似于貪婪搜索方法，總是給最短路徑評高分.評分因子刻畫的是螞蟻的信息素，評分因子越高，對應候選點的評分越高[10-11].

3.2.6 下一矯正點的選取方法

為了模擬螞蟻在選擇路徑時候的真實情況，根據上述對候選點的評分和概率密度函數f(s)選擇下一個矯正點.概率密度函數的表達式為：

(11)

其中：μ=0,σ=0.5，s為對矯正點的評分.即矯正點評分越高，被選擇的概率越大，矯正點的評分越低，被選擇的概率越小.

3.2.7 更新當前誤差的方法

為了滿足題目的約束條件，螞蟻每到達一個矯正點都需要更新水平誤差和垂直誤差.具體的更新方法為：

當H_or_V=0時：

δh=0

(12)

當H_or_V=1時：

δv=0

(13)

其中：Pi為當前矯正點的位置，Pi-1為前一矯正點的位置.

3.2.8 更新矯正點評分因子的方法

矯正點的評分因子對應一群的信息素，對于蟻群，信息素是螞蟻間交換信息的主要媒介，也是蟻群總能找到到達食物的最短路徑的最主要原因.對于蟻群算法，評分因子是決定其收斂性的最主要因素，我們計算評分因子的方法為：

(14)

其中：Vq為信息素的釋放速度，Vh為信息素的揮發速度，Jm為當前最優路徑上的矯正點集合.即每個矯正點的信息素都會在每次迭代中以一定的速度揮發，而最優路徑上的矯正點的信息素則會以一定速度增加.

3.2.9 路徑評分方法

路徑評分方法直接對應于算法的優化目標，由于優化目標一和二基本類似.優化目標中的路徑評分方法為：

(15)

其中：α、β分別為航跡長度、矯正點數和到達終點概率的權重因子，Li為航跡上矯正點間的距離，這里的矯正點包括起點和終點，n是航跡上矯正點的個數.可以明顯看出，不同于對候選點的評分，對路徑的評分越低越好.

3.3 模型的求解結果

根據題中給出的各誤差裕度，利用上述蟻群算法處理附件1數據，繪出以下航跡規劃路徑如圖4所示，程序仿真結果見表1，航跡規劃結果見表2.

表1 程序仿真結果

表2 航跡規劃結果

由圖4可以看出除終點B外，需要校正的8個點的具體位置.由表1、2可以看出，校正點里包括4個水平誤差校正點，4個是垂直誤差校正點，且校正前垂直誤差和水平誤差都比較大.滿足前7個約束條件的飛行器最佳航跡長105 244.151 m.

圖4 航跡規劃路徑

4 改進模型

4.1 模型的建立

即使在飛行前確定了校正點，飛行器的飛行環境可能隨時發生意想不到的變化，導致飛行器在部分誤差校正點無法達到理想的校正狀態(即將某個誤差精確校正為 0)，例如風向，氣流等不可控因素的影響.由于這個原因，提出基于4個假設的改進數學模型：1)假設航跡從A點出發，到B結束，且不只需要滿足上述前7條航跡約束，還要滿足第8條約束，即飛行器不能完成即刻轉彎;2)假設兩矯正點之間的距離為直線距離加半徑大于200 m的圓弧距離，且直線航跡與圓弧航跡是完美相切的;3)假設飛行器在部分校正點(質量標記為1的校正點)能夠百分百將誤差校正為0，在部分校正點(質量標記為0的校正點)能夠成功將誤差校正為0的概率是 80%.如果校正失敗，校正后的剩余誤差為 min(error，5)個單位，并且假設飛行器到達該校正點時即可知道在該點處是否能夠校正成功，但不論校正成功與否，均不能改變規劃航跡;4)上述約束中參數為α1=25，α2=15，β1=20，β2=25，θ=30，δ=0.001.我們的優化目標是基于這3條假設，尋找一條使得飛行器航跡盡可能短、航跡上的矯正點盡可能少、且能夠到達終點的可能性盡可能大的航跡，其數學表達形式如下[12-13]：

(16)

其中：α、β、γ分別為航跡長度、矯正點數和到達終點的概率的權重因子，Li為航跡上矯正點間的距離，這里所的矯正點包括起點和終點，它的計算公式如下：

(17)

其中：Δ為矯正點間帶圓弧的航跡與直線航跡的長度差.

4.2 模型的求解

對于改進的數學模型，求解過程與基礎模型基本一致，也是利用蟻群算法進行求解，只是當前誤差的更新方法(3.2.7所述)和路徑的評分方法(3.2.8所述)有所變化.改進模型的當前誤差的更新方法是：

當H_or_V=0時：

當H_or_V=1時：

改進模型的路徑評分方法是：

(18)

其中：α、β、γ分別為航跡長度、矯正點數和到達終點概率的權重因子，L′i為航跡上矯正點間的航跡長度，這里的矯正點包括起點和終點，n是航跡上矯正點的個數，P為問題3中飛行器能從起點到達終點的概率.

4.3 模型的求解結果

根據題中給出的各誤差裕度，利用上述蟻群算法處理附件1數據，繪出航跡規劃路徑如圖5所示，程序仿真結果如表3所示，航跡規劃表如表4所示.

圖5 數據航跡規劃路徑

表3 程序仿真結果

表4 航跡規劃結果

由圖5可以看出，加入了飛行器前進方向無法突然發生變化的約束條件后，飛行器的航跡在校正點不再跟圖4一樣是折線，變成了曲線.由表3、4可以看出，除終點B外，校正點有8個，包括4個水平誤差校正點，4個是垂直誤差校正點，且校正前垂直誤差和水平誤差都比較大.滿足8個全部約束條件的飛行器最佳航跡長106 970.774 m，飛行器成功到達終點B的可能性為0.8[14].

5 結 語

相比于基礎模型，改進的模型校正點數量不變，但是航跡更長，這是因為加入了飛行器無法即刻轉彎的約束條件，飛行器需要用曲線完成誤差修正.蟻群算法作為一種新興算法, 具有良好的分布式并行計算特點和較強的魯棒性，并且易于同其他算法結合實現優勢互補，在比較復雜的系統問題上展示出良好的性能，隱藏著無窮的潛力，并且擁有計算量少，計算復雜程度較低等優點[15].蟻群算法由于高度依賴各個參數，因此一個參數的微小改變可能會改變收斂方式，變使得結果大不相同.并且該模型存在收斂速度慢,易陷入局部最優解，通用性一般的問題.但是在本算法中，通過大量訓練，增加蟻群的數量，加快信息素的揮發等辦法使得蟻群算法跳出了局部最優解的缺陷.