基于Voronoi圖和蟻群算法的無人機航跡規劃

王欽禾，尹永鑫，戴 麗，鄒宇翔

(1.中國航天空氣動力技術研究院彩虹無人機，北京 100074；2. 國防科技大學文理學院，長沙 410073)

0 引言

與有人機相比，無人機(Unmanned Aerial Vehicle, UAV)具有零人員傷亡、持續作戰能力強、全壽命周期成本低，以及在尺寸、速度和機動性等方面的特有優勢[1-2]。無人機憑借這些優勢，廣泛應用于軍用和民用領域，其在戰場中的作用也越來越被重視。如何提高無人機任務執行能力，成為當下研究的熱點。而無人機航跡規劃是提高復雜任務環境下平臺生存性和完成任務有效性的關鍵技術之一。因此，研究無人機航跡規劃技術，為其找到一條從起點到終點的最優航跡，能夠有效保障無人機的飛行安全，提高任務的執行效率，減少不必要的損失[3]。

航跡規劃方法按照幾何學的觀點，可以分為基于柵格和基于圖形的算法。基于柵格的航跡規劃算法，利用柵格法對任務環境進行建模，優點是精度高、兼容性強，但是數據量大，對機載計算機的計算性能要求高?；赩oronoi圖的無人機航跡規劃方法，憑借其任務環境模型簡潔實用和計算快速等特點，一直是目前比較常用和有效的方法[4-6]。常規 Voronoi 圖構圖簡單，只能用于等威脅體的航跡規劃，對實際戰場環境的建模有較大的局限性。文獻[7-8]提出了基于Voronoi圖的新的建模思路，對Voronoi圖進行了改進，改進后的Voronoi圖更貼近現實情況，更能反映出不同威脅源對無人機威脅的差異性。在Voronoi圖的基礎上進行航跡規劃的算法，主要包括：Dijkstra算法[9]、遺傳算法[10]、蟻群算法[11]和粒子群優化算法[12]等。上述算法在進行航跡規劃時，各有優缺點，很難在復雜、規模較為龐大的任務環境模型中快速地規劃出最優航跡。由于蟻群算法具有分布式計算、群體智能、正反饋[13]、解的長度可變、解數據處理起來靈活方便等優點，因此被廣泛采用。但是蟻群算法也有容易陷入局部最優解的缺點和存在算法堵塞的現象。針對蟻群算法的特點和缺陷，本文提出了算法的改進原則,并基于這些原則提出了新的啟發式和信息素更新機制，將改進后的蟻群算法和改進后的Voronoi圖相結合，對無人機的航跡進行規劃，最后通過仿真驗證了算法的高效性，以及算法改進原則的有效性。

1 Voronoi圖建模過程

1.1 傳統Voronoi圖構建及特點

傳統Voronoi圖將各個相鄰的母點按照一定規則相連，生成Delaunay三角形，眾多的Delaunay三角形組成Delaunay三角網[14]。生成的Delaunay三角形是一種特殊的三角形，它能保證自己的外接圓不包含其他母點。已有學者證明，Delaunay三角形是最優的[15]。對Delaunay三角形的各條邊作垂直平分線，這些垂直平分線所形成的邊就是Voronoi圖的邊，即無人機的可選飛行軌跡。如圖1所示，藍色點代表威脅源，共有50個；藍色線段代表無人機可選飛行軌跡。但是這樣的建模過程沒有充分考慮各個威脅源的類型，以及各個威脅源對無人機威脅的大小，因此需要作出改進。

圖1 傳統Voronoi圖Fig.1 Traditional Voronoi diagram

1.2 改進型Voronoi圖的構造

如圖2所示，A、B、C為三個威脅點，對無人機的威脅程度各不相同，△ABC為Delaunay三角形，則AD的長度為

(1)

式中，LAB為A、B點的間距；LAD為A、D點的間距；TA和TB為A、B的威脅度。同理可以確定F、E點的位置。分別連接D、E、F點，得到分割三角形△DEF，然后作△DEF的內切圓，內切圓的圓心為O點，連接OD、OE、OF，所得的線段OD、OE、OF就是改進型Voronoi圖的邊。

圖2 改進型Voronoi圖構造過程Fig.2 Construct procedure of the improved Voronoi diagram

如圖3所示，藍色實線為傳統Voronoi圖，紅色實線為改進型Voronoi圖。從圖3中可以看出，紅色實線到兩側威脅源的距離不再相等，紅色實線對應的軌跡更偏向于對無人機威脅小的威脅源，較傳統Voronoi圖更能反映出各個威脅源對無人機威脅的差異性。

圖3 改進型Voronoi圖Fig.3 The improved Voronoi diagram

基于Voronoi圖規劃得到的航跡具有固有的威脅回避能力，無人機的飛行航跡只要在Voronoi圖的邊中選擇即可[16]，而每條邊包含兩個端點，這些端點就構成了無人機飛行的航跡點。

2 航跡規劃

2.1 航跡代價函數

無人機航跡規劃的本質是在一定的約束條件下找出從起點到終點能有序地避開威脅區域的最優航跡[17]。由于無人機巡航飛行的高度一般在3000m 以上，無法利用地形因素進行威脅規避機動，因此只考慮其橫向運動，航跡規劃問題就被簡化成為一個二維水平航跡規劃問題[18]。采用1.2節中改進型Voronoi圖的構圖方法，對無人機任務環境進行建模，不考慮禁飛區、障礙區、移動威脅源和面威脅源，則無人機航跡規劃就變成在改進型Voronoi圖中尋找有序子集，使無人機從起點到終點的航跡代價最小的問題。航跡代價可以為無人機飛行航跡總長，但是據此生成的飛行航跡所受的威脅總代價并不一定是最小的。本文綜合考慮飛行航程和飛行過程所受威脅，設計了無人機航跡規劃的航跡代價函數如下所示

(2)

2.2 蟻群航跡規劃算法的分析

自然界中，螞蟻蟻群在覓食過程中形成的軌跡往往是最短的。這個現象產生的原因主要是基于螞蟻的一個生物群體特征：信息素。螞蟻會在經過的航跡上留下信息素，信息素又會隨著時間逐漸揮發。航跡上經過的螞蟻越多，則信息素濃度高。隨著時間的推移，最優航跡因為路程短，且經過的螞蟻數量多，航跡上的信息素濃度逐漸升高。螞蟻自身在前進的過程中，又會選擇信息素濃度高的方向前進，則在最優航跡上的螞蟻數量會越來越多，信息素的濃度也會越來越高，直到信息素的揮發量等于信息素的增加量，此時信息素濃度保持不變，最優航跡與其他航跡被區分開來。

在蟻群尋優過程中，信息素體現了一種對歷史信息的記載：路程更短的航跡上信息素濃度更高，信息素濃度高又會引來更多的螞蟻，更多的螞蟻又會增加信息素的濃度，這一正反饋機制，就可以引導螞蟻找到最優航跡。根據蟻群算法原理，信息素是蟻群在覓食過程中對螞蟻產生吸引作用的信息載體，在一定程度上對算法的收斂速度和航跡規劃效果有著十分重要的影響[19]。因此，算法中信息素的更新方式和變化過程，必須能較好地反映出算法逐漸向最優解航跡收斂的過程。

蟻群算法在開始啟動時，默認各個點的信息素濃度是一樣的。如果算法單純的只有信息素機制，在算法迭代初期，蟻群算法就類似于群舉法，得出最優解航跡的時間太長，所以蟻群算法還有另外一個機制：啟發式。啟發式的作用是：對螞蟻產生一種牽引力，促使螞蟻朝著終點(解航跡)的方向前進。最簡單的啟發式可以定義為

(3)

式中，(x,y)為當前螞蟻所在航跡點的某一個可選鄰點坐標，(xt,yt)為目標點坐標。當可選鄰點到目標點的距離都很遠時，此時式(2)是一個小量，各個可選鄰點對應啟發式的值差異不大，此時啟發式不能很好地區分出各個可選鄰點的優劣。

為了使算法能更快地收斂于最優解，信息素與啟發式在算法迭代過程中對螞蟻前進過程的影響應該隨著算法的迭代而逐漸變化。迭代初期，各個點的信息素濃度差異不大，此時啟發式對螞蟻選擇下一個航跡點的影響應該要大一點，約束螞蟻向著終點的方向前進，即生成初始可行解航跡；當算法迭代到后期時，信息素的影響要大于啟發式，從而體現出歷史的痕跡。

綜上，提出了信息素和啟發式的改進原則：

啟發式機制改進原則：

1)算法運行初期，啟發式的影響要大于信息素；

2)具有明顯的使當前解航跡向最優解航跡靠近的趨勢；

3)在靠近最優解航跡時，這種趨勢要減弱，在最優解航跡附近時，啟發式對算法的影響要弱于信息素。

信息素機制改進原則：

1)當靠近最優解航跡時，解的微小變化引起的信息素濃度變化較明顯；

2)最優解航跡上的信息素能夠自動平衡，并在最優解航跡上達到最大值；

3)信息素值的變化能夠明顯反映出航跡代價函數值的變化、最優解航跡和次優解航跡的差距。

2.3 蟻群航跡規劃算法的改進

假定有50個威脅源，基于2.1節中提出的改進原則，提出了新的啟發式和信息素機制。

啟發式

(4)

式中，i指第i只螞蟻，j指第i只螞蟻的第j個航跡點，即螞蟻當前所在的點，k指第i只螞蟻第j個航跡點的第k個可選鄰點，ξi,j,k為當前螞蟻所在航跡點第k個可選鄰點的啟發式值；φ為啟發式極值控制系數，θ為啟發式形狀因子；li,j為當前螞蟻所在航跡點到目標航跡點的距離，li,j,k為螞蟻所在航跡點的第k個可選鄰點到目標航跡點的距離。啟發式以(li,j-li,j,k)為自變量，表明以當前螞蟻所在航跡點到目標航跡點的距離為基準，度量可選鄰點的優劣，距離目標點更近的可選鄰點更優。由式(4)決定的啟發式存在極限值，表明可選鄰點并不是單純的距終點越近越好，極限值的存在是為了防止算法陷入局部最優解，無法跳出局部最優解循環。

全局信息素更新中，信息素的增量為

(5)

式中，ρ為信息素揮發系數；Q為信息素修正系數；Ci為第i只螞蟻經過航跡的航跡總代價；Pr為航跡總代價預估值，計算公式為

(6)

式中，(xs,ys)為起點坐標;U為航跡代價平衡系數。則全局信息素更新為

τi,j=

(7)

其中，Pi,j代表第i只螞蟻的第j個航跡點；τi,j為第i只螞蟻第j個航跡點的信息素濃度。

2.4 算法堵塞現象的分析與處理

通過大量的實驗發現，在某些特殊的點處，算法會出現堵塞，堵塞現象會降低算法的運行速度，甚至會使算法陷入死循環。因此，為了提高算法的運行速度，不得不考慮堵塞現象。

堵塞現象的處理分為以下幾種情況：

1)如圖4所示，螞蟻的前進路線為A→B→C→D→B→C，此時螞蟻在C點，滿足約束條件的可選鄰點為B點和D點，而B、D兩點都在航跡中，D點出現一次，B點出現兩次，此時選擇出現次數少的鄰點作為下一個航跡點，即選擇D點。

圖4 第一種停滯現象Fig.4 The first stagnation

2)如圖5所示，螞蟻的前進路線為A→B→C→D→B→C，此時螞蟻在C點，滿足約束條件的可選鄰點為E點和D點，E點不在航跡中，D點在航跡中。針對這種情況，此時已經在航跡中出現過的可選鄰點的狀態轉移公式為

(8)

式中，ηi,j,k為已經在航跡中出現過的可選鄰點的選擇概率;μ為重復點選擇概率系數;λk為可選鄰點在航跡中出現的次數;α為信息素權重系數;β為啟發式權重系數;m為第i只螞蟻第j個航跡點的可選鄰點數。

圖5 第二種停滯現象Fig.5 The second stagnation

未在航跡中可選鄰點的狀態轉移公式為

(9)

式中，h為第i只螞蟻第j個航跡點的在航跡中已經出現過的可選鄰點數目。

3 蟻群航跡規劃算法設計

根據改進型Voronoi圖對任務環境進行建模，在此基礎上，利用改進后的蟻群航跡規劃算法求解無人機航跡規劃問題的算法流程如圖6所示。

圖6 算法流程Fig.6 Algorithm flow chart

4 實驗仿真

假定在200km×200km的數字地圖上，分布有50個威脅源，如圖3所示。在本文仿真中，螞蟻數量為200只，單次循環終止時需到達目的地的螞蟻數量為100只，信息素權重系數α=1，啟發式權重系數β=1，信息素揮發系數ρ=0.2，重復點選擇系數μ=0.5，信息素初始值和最小值為1.0，信息素修正系數Q=3，信息素擴散系數ζ=0.4，由航跡代價函數可知，航跡代價平衡系數U=2，啟發式極值控制系數φ=10，啟發式形狀因子θ=0.4。每一次實驗循環5次，在Windows 10-64bit，Matlab 2014a平臺進行1000次仿真實驗，并與傳統蟻群算法進行對比，結果如表1所示。

表1 蟻群算法實驗對比

由表1可知，改進型蟻群算法得到最優航跡的概率較傳統蟻群算法提高了144.62%，運行時間縮短了76.40%，得到最好的次優航跡的次數也提高了19次，可見，改進型蟻群算法的性能得到了大幅度的提升。

利用改進型蟻群算法，基于傳統Voronoi圖與改進型Voronoi圖的航跡規劃結果如圖7和圖8所示，兩者的最優航跡實驗數據對比結果如表2所示。

圖7 傳統Voronoi圖最優飛行航跡Fig.7 The optimal trajectory of the traditional Voronoi diagram

圖8 改進型Voronoi圖最優飛行航跡Fig.8 The optimal trajectory of the improved Voronoi diagram

對比傳統Voronoi 圖改進型Voronoi 圖改進型Voronoi 圖數據變化率/%總代價383.0691451.905217.97航程代價233.0095282.647721.30威脅代價164.253159.2575-0.30單位航程威脅代價0.70490.5634-20.07

由表2可知，改進型Voronoi圖的航程代價增加了21.30%，威脅代價卻基本沒變。從圖8可以看出，航程代價增長的部分是因為規劃生成的航跡有明顯的迂回規避意圖，從而增加了航程；改進型Voronoi圖的單位航程威脅代價比傳統Voronoi圖降低了20.07%，為無人機提供了一條更安全的飛行航跡。在無人機執行任務過程中，與其他因素相比，首先要降低無人機被威脅源發現、干擾和攻擊的可能性，以保證無人機能夠安全順利地完成任務，因此，改進型Voronoi圖更貼近真實任務環境。

式(4)中，啟發式隨(li,j-li,j,k)的變化過程如圖9所示。由圖9可知，啟發式的極限值約為60，當(li,j-li,j,k)=0時，啟發式基準值為32.5。

圖9 啟發式變化過程Fig.9 Changing process of heuristic value

進行多次航跡規劃實驗，統計20次輸出為最優航跡的程序運行結果，并對這20次程序運行過程中，每次循環的最大信息素值和航跡代價函數值取平均值，得到每次循環的最大信息素值均值和航跡代價函數值均值隨迭代次數變化的過程，如圖10所示。

圖10 航跡代價和最大信息素變化過程Fig.10 Changing process of trajectory cost and maximum pheromone value

從圖10中可以看出，隨著迭代次數的增加，航跡代價迅速減小，最大信息素值迅速增加，表明航跡規劃過程中，當前航跡正迅速向最優航跡靠近，滿足啟發式機制改進原則2)和信息素機制改進原則1)和3)；當迭代次數為1時，最大信息素均值為11.5982，小于啟發式基準值32.5，此時啟發式機制的作用大于信息素機制；經過5次迭代，最大信息素均值為64.3286，已經大于啟發式的極限值，此時信息素機制的作用大于啟發式機制，滿足啟發式機制改進原則1)和3)；當迭代次數大于10時，航跡代價已基本不變，此時算法已得到最優航跡；當迭代次數為20時，最大信息素均值趨于穩定，滿足信息素機制改進原則2)。

5 結論

本文針對無人機航跡規劃問題，提出了利用改進型Voronoi圖對任務環境進行建模，并在此基礎上利用改進型蟻群算法進行航跡規劃的方案。算法分析與實驗結果表明：

1)蟻群航跡規劃算法的信息素更新方式和啟發式對算法運行結果產生較大影響。本文提出的信息素機制改進原則和啟發式機制改進原則，為后續蟻群算法的改進提供了新的指導思路。

2)基于提出的改進原則，設計了新的信息素更新過程和新的啟發式機制，實驗仿真結果表明，改進后的蟻群航跡規劃算法與傳統蟻群算法相比，具有更高的運行效率。

3)本文所提無人機航跡規劃方案，在數字地圖尺寸和威脅源數量發生變化時，需要對一些參數進行等效處理，因此需要進一步完善。在威脅源數量較為龐大時，使用該航跡規劃算法需要結合其他算法的優點，以進一步縮短尋優時間。