基于改進MAGA 的無人機航路規劃研究

朱代武，劉 豪，陳澤暉

（1.中國民用航空飛行學院圖書館，四川廣漢 618307；2.中國民用航空飛行學院空中交通管理學院，四川 廣漢 618307）

考慮到覆蓋率、數量、續航時間、障礙等諸多約束，無人機(UAV)的發展應用需解決路徑規劃、最優航跡規劃、編隊協同等相應問題[2]，其中最為重要的是航路規劃問題。實現靈活和平滑的飛行航路規劃，能幫助無人機規避風險、提高偵察和生存能力[3]。目前有學者提出相應的航路規劃算法，如利用多層次分解、傳統GA、基于Voronoi 圖對UAV 進行航路規劃等。但是已有算法因局限于特定場景的指定模型，無法實現UAV 多階段的整體航路規劃[4]。因此綜合UAV 協同、障礙和時間、巡航覆蓋率等約束，運用基于改進操作算子的MAGA 對航路進行精細規劃，通過坐標定義的航路點選擇和確定的飛行航跡，就能實現任意兩點間的直線飛行或者最大限度選擇最便捷的航路[5]。

1 MAGA無人機航路規模型建立

考慮到地理環境、威脅風險及平臺運動因子所產生的影響，分析UAV 的外部條件以及自身機動性能限制，建立UAV 飛行過程中的空間約束模型。基于該空間約束模型，以最優化目標函數的方式對航路進行規劃，從而生成UAV 最優化模型。

航路規劃目的是綜合考慮UAV 性能升限的限制，規避在巡航過程中的諸多風險威脅到達指定點，在保證生存能力的同時提高其運行效率。為實現上述的目標，需對UAV 航路運行進行評價，在所用算法滿足約束條件的情況下，使迭代結果趨于最優。

文中采用2D 空間模型，因UAV 任務剖面在巡航時段高度保持一致，且能夠比較直觀地反映其在同一高度平面的航路規劃問題，同時建立3D 立體巡航區作為避障參考。

文中建立直角坐標系XOY，將指定航路劃分為M等分，得到R1(x1,y1)，R2(x2,y2)，…，Rm(xm，ym)共m個航路點。航路點的集合表示如下：

其中，S表示起始點，E表示結束點。

在給定數量為M的目標集合中，有N架UAV從目標R1出發，分別訪問剩余的M-1 個航段點，目標函數為UAV 的總航程最短，此時定義0-1 變量，即：

為使UAV 在巡航過程中燃油消耗及威脅系數最低，從航路長度、耗油量、航路點受限程度、航路段是否跨越威脅區等方面進行分析，對其代價函數的權重進行調整，這里使用多Agent 系統進行評估。每一個Agent 的目標都是使航段點和UAV 最優化，為此提出評估系統性能的評價函數：

其中，B(z)為該航路內所有UAV 的懲罰代價之和；C(z)為各航段點的懲罰代價之和；α為歸一化系數，表示兩種代價的重要程度。

總代價懲罰是所有UAV 懲罰代價之和，即：

C(z)為各航段點的懲罰代價之和，表示為：

式中，Ca(z)為經過i航點的UAV 為k時的代價懲罰，其表示為：

其中，kt是航段點k在t時刻的油耗代價，Cs為在航段點k時的平均油耗；δ為階躍系數，滿足上述式（2）、式（3）的0-1 變量關系。

同時，文中在基于MAGA 編碼方式及航路代價條件的基礎上建立合適的適應度函數，提出包含航路長度f1、航路點是否在威脅區域罰函數f2、航段是否穿越威脅區罰函數f3的適應度函數[5]，即適應度函數F可描述為：

其中，罰函數f2、f3取1 時，航路點在威脅區域內或者穿越威脅區域，否則取0；w1、w2、w3為相對應的權重系數，也滿足上述式（2）、式（3）的0-1 變量關系之一，即：

2 MAGA操作算子改進

MAGA 算法主要對算子包括如下操作：所涉參數的設計、原始種群大小的設定、適應度函數的設置、遺傳迭代次數設置及參數約束的選取。其步驟為：

1）進行編碼策略選取，將參數集合X和參數域轉換為位串結構空間s；

2）對適應度函數f(X)和適應值進行定義；

3）在遵循遺傳算法理論的基礎上，按照給定要求進行篩選處理，主要從群體m的選擇、雜交、變異3個方面進行考慮；

4）初始化處理形成群體P，并通過迭代處理使算子選取具有隨機性；

5）對群體中個體位串進行解碼，隨后計算適應值f(X)；

6）利用選擇功能使雜交和變異算子作用于種群，形成新一代種群；

7）對種群進行評判。若滿足設定的標準，則進行下一次迭代；若不滿足則停止迭代或者修改評價標準，其流程如圖1 所示。

圖1 MAGA算法基本流程圖

按照生物學仿真實驗特性及無人機巡航性能要求，文中采用依次置換交叉的方式，以確保目標不被重復訪問或者出現數據丟失遺漏的情況。即在兩個父本上隨機選取染色體個數相同的基因序列進行交換，其余位置的染色體依次與交換位置的染色體進行比較；如果出現基因相同的情況，則按照出現的先后次序逐一排列，如表1 所示。

表1 交叉操作前基因位序表

隨機選取從位置6 到位置9 對父本染色體進行交換，經過交換后，兩個個體如表2 所示。

表2 交叉操作后基因位序表

其余位置的基因依次與交換后的基因相比，S1中基因1 和基因5 均出現重復。根據基因1 的前一個原始基因0，選擇基因2、3、6 中與原始基因距離最近的基因代替基因1，以完成一次交叉。

在使用置換交叉的基礎上，文中對操作算子進行改進，按照對應的適應度系數從大到小依次排列，并指定相應的閾值S。若大于閾值S，則對該個體進行復制，反之不予復制。

在研究過程中，擬選取較小的Pm對單獨片段基因進行修改，以變異概率Pm選取兩個基因位；對交叉概率Pc也選擇兩個體的基因片段進行修改。通過工程實踐可知，當個體的適應性接近種群平均適應度時，其交叉概率Pc和變異概率Pm的值越低，優良基因保留的可能性越大。因此文中基于Logistic 方程對交叉概率Pc和變異概率Pm進行修改，實現兩者的自適應，即：

其中，fmax代表種群中最大個體適應度；favg代表種群所有個體的平均適應度；f為要變異個體的適應度[6]。

隨著f的變化需設置不同的變異概率以防止算法陷入局部最優。若favg與f相等，迭代過程中就會出現局部最優的情況。為防止局部最優情況的發生，基于大數定律引入穩態比例矩陣：

其中，diag(f)為m×m的對角矩陣，t為迭代次數。

如果在選擇之后變異，并且Mji是染色體xj到xi的概率，則對式（12）進行改進，得到：

其中，MT為M的轉置矩陣。如果p(t)達到穩定態，則有pss=p(t-1)=p(t)，即：

3 仿真模擬

文中選取真實UAV 巡航任務案例，應用實際坐標和海拔數據，建立基于改進操作算子的MAGA 航路規劃模型[7]。已知坐標數據及海拔建立矩陣D=d(i，j)km，共計2 850 列、2 767 行。第一行為原點坐標Z(0，0)，坐標點之間等距設為100 m，即i處的數據為x=100×(i-1)，y=100×(j-1)[8]。選取8 個地方的中心點坐標，設為A、B、C、D、E、F、G、H，其坐標如表3 所示。

表3 選取地區中心點坐標表

對表3 建立坐標系，將ARCGIS 圖像導入Matlab中可得相應的圖[9]，并對地區坐標點進行標注，如圖2、圖3 所示。

圖2 UAV巡航區域圖

圖3 UAV巡航區域立體圖

UAV 巡航區域的上限高度為H0=2 km，即H0以下為主要目標巡航區，滿足其對地巡航可視化范圍，且具有明顯不規則邊界劃分。UAV 從基站S出發，經過高低不同的區域到達上述的8 個中心點，UAV飛行高度He為固定高度1 500 m，UAV 續航時間為5 h，平均飛行速度為60 km/h。基于MAGA 算法的思想，針對典型UAV 航路規劃任務，設原始種群為100，最大迭代次數為500[10]。

利用基于改進操作算子的MAGA 算法對UAV在該區域內的航路進行最優化處理。該算法在陷入局部極小解以及極大值時隨時終止循環，使得全局的整體結果最優。考慮到實際UAV 飛行性能以及越障情況，為使數據在模擬方面更具有真實性和操作性，這里取Pc1=0.9，Pc2=0.6，Pm1=0.1，Pm2=0.001[11]。規劃區域的航跡如圖4、圖5 所示。

圖4 UAV航路越障圖

在目標區域內，由H0決定的有效區呈現不規則地形，H0為巡航有效范圍內的基準海拔，且各區域內按照MAGA 算法規劃設計出詳細的運動軌跡，軌跡要求對8 個區域進行覆蓋。文中將連線分為多段，由于模型中的E 和D 無法滿足巡航目標區，因此UAV 不對兩點進行巡航(圖4 及圖5 中E1、E2 和E3為E 地區的劃分子區)。H 區域距離A 點較遠，UAV巡航時間不能得到滿足，則不對H 區域進行研究。同時按照可用面積比例，將目標區域分解為300 個子區域(其中A 區域符號范圍為1～40，B 區域符號范圍為41～136，C 區域符號范圍為137～187，D 區域符號范圍為188～203，E 區域符號范圍為204～215，F 區域符號范圍為216～247，G 區域符號范圍為248～300)，結合QT4 算法，利用Matlab 進行迭代分析[12]，其結果如表4、5 所示。

圖5 UAV航路避障圖

表4 UAV在目標區域內改進MAGA路線編號

表5 UAV在目標區域內改進MAGA路線編號

傳統MAGA 算法規劃的航路不能到達E 和D 區域，即在E 和D 區域內無法正常巡航；而改進MAGA能夠有效覆蓋E 和D 區域，使得能夠到達E 和D 中心點，保證無人機全階段任務順利完成。結果證明，經過改進操作算子的MAGA 相比于傳統算法迭代速度更快，航路更平滑，更有利于UAV航路任務的開展[13-14]。

4 結論

文中在傳統MAGA 的基礎上，通過對交叉概率Pc和變異概率Pm遺傳操作算子進行改進，并引入穩態比例矩陣對UAV 航路進行規劃研究[15-17]。通過對UAV 指定環境下模型構建、UAV 航路規劃等問題進行研究，提出基于改進操作算子的MAGA 算法，解決了避障規劃、多機協同問題，最后通過仿真實例證明改進MAGA 算法的有效性及魯棒性。