采用新型蟻群算法的UAV動態航跡規劃

李皓婧

(新鄉廣播電視大學，河南新鄉453000)

采用新型蟻群算法的UAV動態航跡規劃

李皓婧*

(新鄉廣播電視大學，河南新鄉453000)

航跡規劃對UAV完成任務具有重要的意義。為解決突發威脅下的UAV航跡規劃問題，提出了一種改進蟻群算法。采用全新的目標吸引策略、引入信息素增量調節因子并將優先級和信息素揮發系數進行組合優化來對基本蟻群算法進行了改進，提高了算法的求解效率，并進行仿真驗證。根據戰場已知威脅源生成Voronoi加權圖，并與所提的改進蟻群算法相結合求解規劃空間中的最優航跡。仿真結果表明，利用改進的蟻群算法能夠有效地提高收斂速度和尋優能力，可以較好地解決突發威脅下的UAV航跡規劃問題，保證UAV能夠回避戰場威脅，順利飛抵目標點。

航跡規劃;UAV;蟻群算法;信息素;突發威脅

航跡規劃是UAV任務規劃的重要組成部分，近年來各種優化算法在航跡規劃中得到廣泛的應用，具有代表性的算法有Voronoi圖法［1］，RRT算法［2］，粒子群算法［3］，A*算法［4］，動態規劃算法［5］等。這些智能算法均有各自不同的優越性，但由于戰場環境是動態變化的，很難預先獲得全局精確的威脅信息，涉及到突發威脅下的UAV航跡規劃時，這些算法也將不能保證全局最優解，并且可能導致計算時間過長，很難應用于實時規劃。蟻群算法［6-7］作為一種隨機優化方法，它的搜索特點具有良好的動態特性，這對于航跡規劃中的實時航跡規劃問題特別有效。另外，在動態問題中蟻群算法具有良好的尋優計算能力，但是時間復雜度的限制使得必須對蟻群算法進行優化，而且算法運算過程其實是一個搜索過程，需要一個已知的可行航跡網來作為研究基礎，采用Voronoi圖法可以很好的解決這一問題。因此，本文提出了一種改進蟻群算法來解決突發威脅下的UAV航跡規劃問題。受人工勢場法的啟發，采用全新的目標吸引策略;引入信息素增量調節因子，改進信息素更新方式;通過優先級和信息素揮發系數的組合優化，對信息素揮發系數進行調整變化來對算法進行了改進。本文首先根據戰場已知威脅源生成Voronoi加權圖，然后與所提的改進蟻群算法相結合求解規劃空間中的最優航跡。仿真結果表明，利用改進蟻群算法能夠有效地提高收斂速度和尋優能力，可以較好地解決突發威脅下的UAV航跡規劃問題，保證UAV能夠回避戰場威脅，順利飛抵目標點。

1 基于Voronoi圖的威脅環境建模

1.1 規劃空間及威脅區域建模

Voronoi圖應用于UAV航跡規劃問題是根據戰場環境中威脅的分布情況依次作出相鄰威脅源的中垂線，將空間劃分成圍繞各個威脅源的多邊形區域，構建初始可選路徑集，確定航跡的走向和航區。然后依據UAV航跡規劃的性能指標計算出邊界的總權值，最后采用優化算法來獲得最優航跡。具有計算速度快，編程相對簡易的優點。

本文在整個規劃空間中根據威脅源的分布點集將每個威脅源的點的中心位置視為Voronoi圖的點集，現在問題簡化為在Voronoi圖上尋找UAV從起始點到目標點的最小航跡代價可行航跡，將無限維搜索問題縮減為有限的圖形搜索問題，大大提高了計算效率，能夠滿足突發威脅下的UAV航跡規劃問題的實時性要求［8］。

1.2 航跡性能指標

通過對UAV的飛行區域進行建模得到任務態勢Voronoi圖后，還需要確定各段航跡的性能指標。UAV航跡規劃不僅要依據預先獲得的威脅信息尋找安全的飛行軌跡，而且還要做到從起始點到目標點所用油耗最小。因此，本文采用按最短航跡和最小可探測性指標加權方法作為航跡的性能指標，如下式所示:

式中，J為航跡性能目標函數，又稱為廣義代價;Jthreat，i為第i段航跡的威脅代價，與可探測性指標相關聯; Jfuel，i為第i段航跡的油耗代價，是航程的函數;k為權重系數，表征航路制訂人員根據任務安排在制訂航路的過程中所做出的傾向性選擇，k∈［0，1］。

雷達、導彈等威脅源構成了與其臨近的Voronoi邊的威脅因素，嚴格地講，這兩類威脅的原理以及對UAV構成的威脅程度是不同的，但當簡化問題時，把兩類威脅都看成同類威脅，將導彈威脅近似為雷達威脅，采用和雷達威脅相同的方法來量化處理。

理論上，雷達信號正比于1/d4(d為UAV到敵方雷達、導彈威脅陣地的距離)，UAV的雷達威脅代價是飛過該邊的積分。為了簡化計算，將每條邊均勻地3等分，取兩端端點和中間點來代替整條邊的代價，如圖1所示。

圖1 雷達威脅量化圖

因此第i條航跡段的威脅代價Jthreat，i可以表示為:

式中，m為雷達威脅的個數，li為第i條航跡段的長度，da，j、d1/2，j、db，j分別代表第j個威脅距離該路徑端點Sa、Sb和1/2處的距離。

另一方面是UAV的油耗代價，假定UAV以恒速在同一高度飛行，油耗代價Jfuel，i是航程Li的函數，航程越短，則油耗代價越小，因此第i條航跡段的油耗代價Jfuel，i可以表示為:

此時根據任務態勢構造的Voronoi 圖就變成了加權Voronoi圖，其每條邊的代價為Ji，從而建立了UAV航跡規劃時所有可行航跡的集合。

2 基于改進蟻群算法的航跡規劃

2.1 目標吸引策略

基本蟻群算法求解UAV航跡規劃時，啟發信息選用了路徑段長度的倒數，導致不同位置的航跡點的啟發信息差異并不明顯，不能很好地引導螞蟻選擇路徑，從而降低對最優路徑的搜索效率。為了克服上述不足，本文受人工勢場法［9］的啟發，在蟻群算法中引入人工勢場的思想，采用全新的目標吸引策略，并重新定義了路徑選擇的啟發函數。人工勢場法航跡規劃的基本思想為:為目標點定義吸引勢能，威脅點定義排斥勢能，UAV在勢能的導向下，從起始點出發，避開威脅點，到達目標點。因此，本文采用UAV當前位置到目標位置的距離作為啟發信息的一部分，引導對最短路徑的搜索，使螞蟻盡快向目標點移動。同時引入了方向信息，使螞蟻在尋找路徑時受到方向信息的影響，從而克服了基本蟻群算法的不足，更利于得到最優解。改進算法的啟發信息函數公式如下:

式中，θ為可選結點b與目標結點的連線與初始終止點連線的夾角。da，end為UAV當前位置到目標位置的距離，其中，(xa，ya)為當前位置坐標，(xend，yend)為目標點坐標。

因此，在t時刻，設螞蟻k在航跡點a處，則按照下式確定螞蟻k在下一時刻將到達的節點s:

式中，α為信息素重要程度因子，其值越大，表示信息素的濃度在轉移中起的作用越大;β為啟發函數重要程度因子，其值越大，表示啟發信息在轉移中起的作用越大。allowed(a)是第k只螞蟻由航跡點a出發待訪問的所有可行航跡點的集合;τab(t)表示Voronoi圖中邊ab上的信息素值;r為(0，1)中均勻分布的隨機數，ro∈(0，1)，可以動態地調整ro的值。

可見，轉移概率pkab(t)與夾角θ的余弦值成正比。夾角θ越小，cosθ的值越大，螞蟻選擇結點b的可能性就越大。通過采用全新的目標吸引策略，可以使UAV在選擇下一個節點時能盡快地趨近目標點，并找到最優航跡。

2.2 引入信息素增量調節因子

為了避免搜索的停滯，最大-最小螞蟻系統［10］將各條路徑上的信息素量的值域限制在［τmin，τmax］內。按照其思想，當所有螞蟻完成一次路徑選擇時，Voronoi圖上的的信息素可以更新為:

式中，

為了增加解空間的多樣性，提高蟻群的全局搜索能力，避免出現局部收斂和早熟現象，本文引入信息素增量調節因子δ，根據每個螞蟻所求得解的質量的不同，對該螞蟻所經過路徑上的信息素自適應地更新。

式中，信息素增量調節因子δ可由下式求得:

以上各式中，Δτab(t)為本次循環產生的信息素增量; Δτkab(t)為本次循環中第k只螞蟻經過邊ab后的信息素增量;num是螞蟻的總數量，ρ為信息素揮發系數; Q值是一個常數;Jk為第k只螞蟻選擇的航跡廣義代價，Jave為螞蟻在本次循環選擇的航跡平均代價。

引入信息素增量調節因子，使得在短時間內可以通過信息素增量上的差別來區分開次優和其他路徑，在促使螞蟻找到最優路徑的同時，也大大提高了收斂速度，縮短了搜索時間。首先計算了每次循環以后所有螞蟻選擇的航跡代價的平均值，再跟據個體螞蟻選擇的航跡代價與該平均值之間的差異來對信息素進行相應的改變。實驗證明，改進后的蟻群算法比單純地改變全局最優解或局部最優解路徑中信息素的強度具有更好的搜索最優解的能力。

2.3 優先級和信息素揮發系數的組合優化

蟻群算法中，信息素揮發系數ρ的大小直接關系到算法的全局搜索能力及其收斂速度。為了避免算法陷入局部最優，本文引入一個優先級參數，用ξ(0＜ξ＜1)表示。ξ可以分為三級ξ1，ξ2，ξ3，如果一條路徑上的信息素濃度過大，則令ξ為一個較大的值，動態地調整信息素揮發系數ρ，使得路徑上的信息素濃度越高，揮發越快，信息素濃度越低，揮發越慢，平衡各路徑的信息素濃度，使螞蟻在較大范圍內進行搜索。當循環達到一定次數時，令ξ為一常數，使螞蟻找到最優路徑?；趦炏燃墻魏托畔⑺負]發系數ρ的組合優化如下式所示:

式中，ρmax，ρmin分別是信息素揮發系數ρ的上限和下限，通過設定ρ的最大、最小值，可以避免算法的收斂速度過慢，容易陷入局部最優解。

優先級ξx可由下式給出:式中，x=1時表示該條路徑的優先級最高，而當x=3時表示該條路徑的優先級最低。經過優先級和信息素揮發系數的組合優化后，使各條路徑上的信息素濃度趨于平衡，從而有效地避免算法陷入局部最優。

在信息素揮發系數ρ根據優先級ξ調整變化的同時，信息素τ也隨著動態更新，即式(8)變為:

從而通過將信息素揮發因子ρ用隨迭代自適應的ρ(t)來代替，提高了算法的全局性。為了提高算法的搜索速度和全局搜索能力，在每次循環搜索結束時，都將最優解保留，作為判斷ρ根據路徑優先級調整變化的條件。

2.4 改進算法的具體實現步驟

本文采用Voronoi圖和改進蟻群算法求解UAV航跡規劃問題的具體步驟如下:

Step 1根據戰場威脅源分布構造任務態勢Voronoi圖，并計算Voronoi圖中每條邊的總代價;參數初始化，對Voronoi圖所有邊賦初始信息素值;

Step 2將所有螞蟻置于距離出發點最近的Voronoi圖節點，并根據式(4)～式(7)將每只螞蟻由當前節點移動到可行的相鄰節點，直到所有螞蟻均到達目標點;

Step 3根據式(1)～式(3)計算出可行航跡的代價，并更新所找到的最優航跡;

Step 4對所有Voronoi邊的信息素值進行更新，其規則如式(8)～式(11);

Step 5應用式(12)、式(13)調節信息素揮發系數，并根據式(14)對信息素進行更新;

Step 6若滿足循環結束條件，即當前迭代次數達到最大值或已經找到最優解，則循環結束并輸出計算結果，否則轉入Step 2。

2.5 突發威脅下的航跡規劃

任務區域的復雜性使得UAV不能預先掌握全部的環境信息。有些威脅源只有當UAV飛抵其附近一定距離后才能獲知，因此UAV在遇到突發威脅時的航跡規劃具有重要意義［11］。在UAV按原有航線飛行的過程中，若探測到有突發威脅出現，則采用改進蟻群算法進行UAV航跡規劃，其步驟如下:

Step 1在UAV執行任務飛行的過程中，若探測到有突發威脅，則轉Step 2，否則UAV繼續按原航跡飛行;

Step 2更新任務態勢Voronoi圖和Voronoi圖所有邊上的啟發信息;

Step 3在更新后的任務態勢Voronoi圖上，使用改進蟻群算法進行航跡規劃;

Step 4 UAV按照規劃出的新航跡進行飛行。

3 算法仿真分析

為了驗證本文所提的改進蟻群算法在Voronoi圖中進行UAV航跡規劃的可行性和有效性，進行仿真實驗，UAV的航跡規劃空間為140 km×140 km，UAV的起飛點坐標為(18，18)，目標點坐標為(125，125)，進入敵方防御區域后，UAV需要根據自身所處的威脅環境完成航跡優化計算。利用仿真技術對UAV任務航跡進行了規劃，其中各參數的取值分別為:num=40，α=1.5，β=4.5，Q=100，ρmin=0.15，ρmax=0.9，r0=0.75，τmax=9.95，τmin=0.05，最大迭代次數為100。首先針對戰場威脅源建立相應的Voronoi圖，然后采用本文所提的改進蟻群算法在Voronoi圖中進行UAV航跡規劃。圖2給出了UAV進入威脅區域執行作戰任務時的航跡規劃結果，圖中的點代表雷達、導彈等威脅源、“*”代表UAV出發點、“Θ”代表UAV任務目標點，可行航跡則用實線表示。所得航跡具有較短的航程，同時有效地規避了已知的威脅區域，能夠保證UAV迅速、安全地飛抵目標位置，仿真結果表明這種航跡規劃方法是可行和有效的。

圖2 已知威脅下的UAV航跡規劃圖

圖3為UAV遇到突發威脅后的航跡規劃結果。圖中的“⊙”代表突發威脅，突發威脅的坐標可以自由設定，本次實驗設定為(84，70)。當UAV在執行任務飛行過程中，探測到有突發威脅存在，則更新任務態勢Voronoi圖，并調用改進蟻群算法進行航跡規劃，得到新的可行航跡如圖3中實線所示。通過仿真圖3可以看出，航跡能有效地避開威脅，并能使航跡代價指標最小。仿真實驗中航跡規劃的優化時間為5.7 s，能夠滿足實時性要求?？梢姡酶倪M蟻群算法行航跡規劃，可以滿足UAV應對突發威脅下航跡規劃的要求。

圖3 突發威脅下的UAV航跡規劃圖

圖4為生成UAV可行航跡的改進蟻群算法的各代迭代收斂曲線圖，其中虛線為各代平均代價收斂曲線;實線為最小代價收斂曲線。從圖4可以看出，航跡代價隨著迭代的進行，逐漸收斂到全局航跡最小代價，表明改進蟻群算法確實有效可行，保證了求解的多樣性，且收斂速度較快。最終獲得全局最優航跡的代價為22.89。

圖4 改進蟻群算法的UAV航跡規劃迭代收斂曲線圖

圖2、圖3中所給出威脅源數量相對較少，且分布較為稀疏，當威脅源的數量增加時，再次用本文所提的改進蟻群算法對其進行航跡規劃，最后得到的仿真結果如圖5所示。為了驗證本文所提的改進蟻群算法在增加威脅源的情況下，對于突發威脅的實時規劃依舊可行，增加突發威脅，設定其坐標為(80，60)，航跡規劃結果如圖6所示。

由圖5和圖6可見，本文所提出的改進蟻群算法可以有效地解決不同態勢環境下的UAV航跡規劃問題。

圖5 增加威脅源后的UAV航跡規劃圖

圖6 增加威脅源后在突發威脅下的UAV航跡規劃圖

4 結束語

本文根據UAV航跡規劃問題的要求，在研究現有算法的基礎上，提出了一種改進蟻群算法，對存在突發威脅情況下的航跡規劃問題進行了研究。受人工勢場法的啟發，采用全新的目標吸引策略，使UAV在選擇下一個節點時能盡快地趨近目標點，并找到最優航跡;引入信息素增量調節因子，在短時間內可以通過信息素增量上的差別來區分開次優和其他路徑，促使螞蟻找到最優路徑的同時，也大大提高了收斂速度，縮短了搜索時間;采用優先級和信息素揮發系數的組合優化，使各條路徑上的信息素濃度趨于平衡，從而有效地避免算法陷入局部最優。仿真實驗表明，本文所提出的改進蟻群算法，不但成功規劃出了從起始點到目標點的可行航跡，而且有效地躲避了突發威脅，提高了UAV的生存率及作戰效率。仿真實驗中突發威脅的位置以及起始點和目標點的位置都可以任意設定，此外還考慮了威脅源密集的情況，因而實驗具有很強的隨機性和可靠性。另外，規劃算法非常簡單，運算速度快，因而使得UAV在面對突發威脅時能夠迅速做出規避動作，順利飛抵目標點。根據戰場威脅的動態特性，對算法進行進一步擴展研究，同樣可以有效解決出現移動威脅時的航跡規劃問題。

［1］Pehlivanoglu Y V.A New Vibrational Genetic Algorithm Enhanced with a Voronoi Diagram for Path Planning of Autonomous UAV［J］.Aerospace Science and Technology，2012，16(1):47-55.

［2］潘廣貞，秦帆，張文斌.動態自適應快速擴展樹航跡規劃算法研究［J］.微電子學與計算機，2013，30(1):49-52.

［3］單敏瑜，劉以安，倪天權.QPSO在無人機偵察航路規劃中的應用研究［J］.計算機工程與設計，2009，30(20):4690-4692.

［4］杜繼永，張鳳鳴，吳鵬飛，等.無人飛行器航跡規劃的工程化稀疏A*算法［J］.計算機應用研究，2013，30(8):1756-1758.

［5］安柏義，曹云峰.基于動態規劃的無人機航路優化問題研究［J］.計算機測量與控制，2008，16(8):1177-1179.

［6］Tang X，Zhang P，Jiang B，etal.Ant Colony Optimization Based on Maximum Selection Probability for Path Planning in Unknown Environment［J］.Journal of Computational Information Systems，2012，8(24):10325-10332.

［7］盧斌文，曲東才，楊曉龍.一種基于蟻群智能算法的航跡優化方法［J］.科學技術與工程，2013，13(2):398-401.

［8］稅薇，葛艷，韓玉，等.基于混合蟻群算法的無人機航路規劃［J］.系統仿真學報，2011，23(3):574-576.

［9］李猛，王道波，柏婷婷，等.基于蟻群優化算法和人工勢場的無人機航跡規劃［J］.應用科學學報，2012，30(2):215-220.

［10］牟廉明，戴錫笠，李坤，等.求解二次指派問題的最優迭代最大最小螞蟻算法［J］.計算機應用，2014，34(1):199-203.

［11］劉月，魏瑞軒，劉敏，等.用改進變異粒子算法實現突發威脅下的無人機航跡規劃［J］.電光與控制，2010，17(1):22-25.

李皓婧(1980-)，女，漢族，河南新鄉人，新鄉廣播電視大學，云南大學計算機應用專業碩士研究生，高校講師，研究方向為計算機應用，lihaojing_vip@ 163.com。

Dynam ic Route Planning for UAV Based on Novel Ant Colony Algorithm

LIHaojing*

(The Radio and TVUniversity of Xinxiang，Xinxiang He’nan 453000，China)

Route planning plays an important part in accomplishing task for UAV.Aiming at the route planning problem of UAV with unexpected threats，amethod based on improved ant colony algorithm is proposed.In order to improve the solution efficiency of the algorithm，the new target attract strategy，the pheromone increment adjustment factor and the priority are introduced to improve the basic ant colony algorithm.Simulations are carried out.The weighted Voronoi diagram is created according to the certain threat sources，with the improved ant colony algorithm to search the optimal path in the space.Simulation results show that the proposed method can improve the search speed and the ability in searching the whole best solution of the route planning problem effectively，which is applicable to route planning of UAV with unexpected threats.So，the UAV can avoid the battlefield threats，reach the target point smoothly.

route planning;UAV;ant colony algorithm;pheromone;unexpected threats

C:6140

10.3969/j.issn.1005－9490.2017.01.025

TP391.9

:A

:1005－9490(2017)01－0130－06

2014-08-10修改日期:2016-04-18