基于改進多目標蟻群算法的無人機路徑規劃

摘 要：針對無人機SEAD任務的路徑規劃問題，利用VORONOI圖構建初始路徑，分析了路徑代價計算方法，并使用改進的多目標蟻群算法對路徑進行優化選擇。針對該特殊應用場景，引入了各路徑段與起始點—目標點連線的夾角信息作為新的啟發信息，加快了算法的搜索速度，同時改進啟發信息的計算公式，適當縮小各可選路徑段啟發信息量的差異，加強了蟻群算法的全局搜索能力。仿真結果顯示，與基本多目標蟻群算法相比，改進后的算法有效提高了路徑搜索的效率和質量。

關鍵詞：無人機；路徑規劃；VORONOI圖；多目標蟻群算法

中圖分類號：TP391文獻標志碼：A

文章編號：1001-3695(2009)06-2104-03

doi:10.3969/j.issn.1001-3695.2009.06.031

UAV path planning using improved multiobjective ant colony system

WANG Zhen-hua，ZHANG Wei-guo，LI Guang-wen

(School of Automation， Northwestern Polytechnical University， Xi’an 710072， China)

Abstract:Based on the VORONOI diagram，this paper calculated the path costs， and then used the multiobjective ant colony system(MACS) algorithm to solve the route planning problem of the UAVs taking the SEAD mission.Calculated and introduced the angles between path segments and the line segment joining the start point and the target point， as heuristic information， into the MACS algorithm to accelerate the searching speed. And also，this paper improved the expression of the heuristic information， which reduced the differences among the path segments， and enhanced the global searching ability of the algorithm.The simulation results show that:compared with the original MACS，the improved algorithm can find a better result more efficiently.

Key words:UAV; path planning; VORONOI diagram; multiobjective ant colony system

0 引言

無人機最重要的特點是無須考慮人機系統，因而具有高機動性、零傷亡、費用低等一系列優點，在軍用、民用領域受到越來越廣泛的關注^[1]。尤其在軍事領域，無人機被用于執行偵察、電子干擾、充當誘餌、目標攻擊等任務。由于無人駕駛，無人機的任務規劃就顯得尤其重要。路徑規劃是任務規劃中最為基礎，也是最重要的部分。合理的航路規劃將有助于無人機有效地規避威脅、減小飛行路徑長度，提高其生存概率和作戰效率。

無人機路徑規劃方法主要有VORONOI圖搜索法、格柵搜索法、人工勢場法、基于生物激勵神經網絡的算法和基于模糊邏輯的路徑規劃算法等。文獻[2，3]中均以SEAD（suppression of enemy air defense）作戰任務為背景，利用VORONOI圖構建初始路徑，以最小化路徑長度和威脅強度為目標進行路徑的構建。對于該多目標優化問題，文獻[2]中采用滿意剪枝策略對搜索過程中的不滿足航路代價指標的航路直接進行剪枝，以搜索無人機初始航路集合；文獻[3]中使用了Dijkstra算法對路徑進行優化選擇。上述文章中均是通過線性加權和法將多目標優換問題轉換為單目標問題進行求解。這樣便面臨著權重系數如何選取的問題，同時，一旦任務決策者對各個目標的偏好程度發生變化，便需要更改權重系數，重新進行優化選擇。為了克服上述算法的缺點，本文通過引入新的啟發信息，同時修改啟發信息計算公式對基本多目標蟻群算法進行改進，利用改進的蟻群算法進行路徑選擇和優化，找出問題的Pareto最優解集提交給決策者，為決策者更好地作出決定提供了幫助。

1 問題描述及環境模型的建立

無人機的SEAD任務路徑規劃可以簡單描述為：給定起始點和目標點，規劃一條路徑使得從起始點出發的無人機能夠繞開障礙物和敵防空火力威脅順利到達目的地，從而執行其攻擊或監視任務。為了討論方便，本文將障礙物、威脅均簡化為點狀威脅，假設所有威脅點位置是已知且固定不變的，并且各個威脅對無人機的威脅強度是相同的。在該假設前提下，以各個威脅點為基礎構建VORONOI 圖，如圖1所示。VORONOI 圖的邊構造出了所有的可行路徑，這些邊的交點即為所有可行路徑點。

無人機路徑規劃是一個多目標的優化問題，本文以最小化路徑長度和最小化威脅代價為目標進行路徑的選擇優化。在已構建的初始路徑的基礎上，一條可行路徑由包括起始點和目標點在內的n個順序排列的路徑點所表示：path={p1，p2，…，pn-1，pn}。其中p1=ps和pn=pt分別表示給定的起始點和目標點。pi和pi+1(i=1，2，…，n-1)之間必須有VORONOI圖的邊（可行路徑）相連接。那么，對可行路徑的優化目標為

min F1=n-1i=1li， j+1(1)

min F2=n-1i=1ti， j+1(2)

其中:li，i+1和ti，i+1分別表示路徑點pi和pi+1之間路徑的長度和無人機選擇該路徑時所受到的威脅強度。

最常用的一種威脅模型認為，雷達對無人機的威脅與兩者之間的距離的四次方成反比：T=K×1/R4。因此，從路徑點pi到達pi+1的威脅強度為ti，i+1=∫Tdl。為了簡化計算，引文獻[2]中取每條邊的1/4、1/2和3/4處的三個點的代價求和，但是由于各條邊的長度差距懸殊，這使得采樣點的分布很不均勻，嚴重影響了計算的精確性。為此，本文作出如下改進：

在路徑點pi與pi+1之間的路徑上均勻地取k0個點，記為pik，k=1，2，…，k0∈N。其中k0由下式求解得到：k0=[li，i+1/interval]。Interval為預先設定的采樣點間距，采樣間距越小，則采樣點越多，威脅強度的計算越精確；[a]表示取實數a的整數部分。從而，由路徑點pi到達pi+1的威脅強度為

ti，i+1=k0k=11/d4ik+1/d4i+1(3)

其中:dik、di+1分別表示路徑點pik、pi+1與離它們最近的威脅點之間的距離。

對于多目標優化問題，各個目標要求之間經常是相互沖突的，對于其中一個目標最優的解對另一個目標而言往往并不好。因此，對于多目標優化通常是尋找它的Pareto最優解集。本文利用改進的蟻群算法對上述多目標優化問題進行求解。

2 蟻群算法

蟻群算法最初是Dorigo等人^[4]為了改善螞蟻算法在TSP中的表現而提出來的。相對于螞蟻算法，蟻群算法：a）使用了不同的狀態轉移規則；b）全局信息素更新規則只應用于最優的螞蟻路徑上；c）在螞蟻的搜索過程中使用局部更新規則。

文獻[4]中用蟻群算法求解TSP時，當螞蟻由當前路徑點（城市r）向下一個路徑點（城市s）移動時狀態轉移規則為

s=arg maxu∈Jk(r){[τ(r，u)]×[η(r，u)]} 若q≤q0

S否則(4)

其中：Jk(r)為從城市r出發的螞蟻k尚未訪問的所有城市的集合；τ為城市r與u之間路徑Rru上信息素的含量；

η(r，u)=1/Lru(5)

為路徑Rru長度的倒數，作為啟發信息引入到算法中來；q為[0，1]區間均勻分布的隨機數；q0為一事先確定的參數(0≤q0≤1)；s為根據式(6)確定的概率分布而隨機選定的城市。

pk(r，s)=[τ(r，s)]×[η(r，s)]β/

u∈Jk(r)[τ(r，s)]×[η(r，s)]β 若s∈Jk(r)

0否則(6)

在螞蟻完成一次搜索，構建出一個可行解時，螞蟻實施全局信息素更新。全局信息素更新規則為

τ（r，s）=(1-α)×τ(r，s)+α×Δτ(r，s)(7)

其中:

Δτ(r，s)=(Lgb)-1 若Rrs∈Rgb

0否則(8)

0＜α＜1為全局信息素的揮發系數；Lgb為目前搜索到的最優路徑Rgb的長度。只有全局最優的螞蟻釋放信息素，其目的是引導后續螞蟻在當前所找到的最優路徑的鄰域中搜索，使得搜索更具有指導性。

在螞蟻進行路徑搜索過程中，每確定一個路徑點，便運用局部信息素更新規則對該段路徑上的信息素進行更新。局部信息素更新規則為

τ(r，s)=(1-ρ)×τ(r，s)+ρΔτ(r，s)(9)

其中:0＜ρ＜1為局部信息素的揮發系數；Δτ(r，s)=τ0，τ0為初始信息素水平。文獻[4]中通過實驗發現，當

τ0=（n×Lnn）-1(10)

時，可以產生較好的效果。其中:n為城市的數量；Lnn為最優路徑長度的估計值，該估計值可由任意優化算法近似求得。當螞蟻由城市r向城市s移動時，局部更新規則使得相應軌跡上的信息素減少，從而避免所有的螞蟻都集中在最優解附近進行搜索。

3 基本多目標蟻群算法

蟻群算法最重要的特點就是創造性地使用了啟發信息，即通過引入信息素播撒機制，將之前搜索到的最優解用于指導后續的搜索。在蟻群算法的眾多改進算法中，對信息素播撒機制的改進是研究者最為關注的一點^[5]，本文的算法改進工作正是基于此。另外，蟻群算法與其他搜索算法相結合，來改進蟻群算法也是一條重要途徑^[6]。

由式(5)(8)和(10)可看出，狀態轉換規則和信息素播撒的量均為路徑長度的函數。而最小化路徑長度正是TSP中惟一的一個優化目標。因此，對于兩目標的優化問題，本文重新構造了狀態轉換規則和信息素播撒量函數，使得它們成為路徑長度和威脅強度的二元函數。文獻[7]將類似的方法用于帶時間窗口的車輛路徑問題的優化。

在本文第1章所建立的環境模型的基礎上，對多目標蟻群算法的表述如下：

對應于單目標蟻群算法中的式(5)，多目標蟻群算法狀態轉換規則中的啟發信息表示為

η（r，s）=1/(lrs×trs)(11)

對應于單目標蟻群算法中的式(10)，多目標蟻群算法局部信息素更新規則表示為

τ0=(n×Lp0×Tp0)-1(12)

其中:n為路徑點的數目；Lp0和Tp0分別為最小路徑長度和最小威脅強度的估計值，該估計值可由任意優化算法近似求得。

對應于單目標蟻群算法中的式(8)，多目標蟻群算法全局信息素更新規則表示為

Δτ(r，s)=k0k=1Δτk(r，s)(13)

其中：k0為到目前為止搜索到的Pareto解集中解的個數。即，對所有屬于Pareto最優解集中的路徑實施信息素全局更新，且

Δτk(r，s)=(LkTk)-1若Rrs是第k條Pareto最優路徑中的一段

0否則(14)

其中：Lk和Tk為第k條Pareto最優路徑的總長度和總威脅強度。

多目標蟻群算法通過將之前搜索到的最優解的路徑長度信息和威脅強度信息同時用于指導下一次的搜索，從而達到對兩個目標同時進行優化的目的。

4 算法改進及其流程

TSP中要求每個城市必須且只經過一次，且各城市之間都有路徑相連。此時，使用禁忌表可以很好地加快搜索速度，并避免同一個城市經過兩次的情況發生。但在前述VORONOI圖路徑規劃問題中，各路徑點之間的連接是由VORONOI圖的邊（即可行路徑段）所嚴格限制的。此時若使用禁忌表，搜索過程中一旦偏離目標方向，將會使搜索陷入無路可走的境地。若引入解禁策略，則又面臨著解禁策略難以制定、算法復雜性增加等問題。因此在本文的算法中擯棄了禁忌表的使用，同時引入了一個新的啟發信息。

在本文的路徑規劃問題中，由于路徑起始點和目的地的相對位置是已知的，考慮以此空間幾何關系作為啟發信息引入到算法中去，指引螞蟻的搜索方向。

如圖2所示，記pipj為由路徑點pi到路徑點pj的有向路徑段，pspt為連接起始點和目的地的有向線段，θij為pipj與pspt之間的夾角。根據矢量間夾角定義，圖2中以路徑點p1為例，給出了與其相連接的三條路徑段與pspt所構成的三個夾角：θ1s、θ12和θ13。筆者認為與pspt夾角越小的路徑段越有可能是全局最優路徑的一部分，螞蟻在進行路徑選擇時選中該路徑段的概率也越大。

在本文的路徑規劃問題中，對于單目標的蟻群算法，將啟發信息替換為上述角度信息后，啟發信息計算式(5)修改為

η（i， j）=1/(θij+1/Nu∈J(i)θiu)(15)

對于多目標蟻群算法，將路徑選擇的啟發信息計算式(11)修改為

η（i， j）=1/(θij×tij+1/Nu∈J(i)θiutiu)(16)

其中:J(i)為所有與當前路徑點之間有路徑段相連的路徑點所組成的集合，N為該集合中元素的個數。

由于與當前路徑點相連的各路徑段的夾角信息的值差距可能會很大，這將導致各路徑段的啟發信息量差異懸殊，從而使得螞蟻對個路徑段的選擇概率差距過大，再加上信息素播撒的正反饋效應，算法將迅速地收斂于局部極值。為了緩解該問題，本文在式(15)(16)中加入了1/Nu∈J(r)K項，適當縮小了各可選路徑段啟發信息量的差異，相對增加啟發信息量小的路徑段選擇該概率，使得算法的全局搜索能力得到加強。其效果相當于遺傳算法中增加了種群多樣性，避免了過早地收斂于局部極值。

螞蟻在搜索路徑的過程中，不可避免地會重復走一些路徑段。為了減小這些不必要的圈子對后續的搜索造成的不良影響，在全局信息素更新之前，先刪除掉路徑中重復的路徑段，然后對精簡后的路徑計算其長度并帶入式(14)計算信息素更新量，對精簡后的路徑實施全局信息素更新。

在此基礎上，本文給出用于路徑優化的多目標蟻群算法流程：

MainFunction:

/*初始化過程*/

只用啟發信息構造初始可行路徑；

Pareto最優解集；

利用式(12)計算；

Repeat/*主循環*/

對每一只螞蟻i∈{1，2，…，m}調用子程序，構建路徑pi；

對每一條路徑pi，計算F1和F2，若pi為Pareto最優解集的非支配解，則令P=P∪pi，同時去掉解集中被pi支配的解；

根據式(7)，對Pareto最優解集中的所有元素進行全局信息素更新；

Until 滿足終止條件。

/*算法結束*/

SubFunction construct_route(i)

pi={ps};/*第i條路徑的所有的路徑點依次存放在集合pi中。初始化，將一只螞蟻放在ps*/Repeat

根據式(16)，計算啟發信息η(i， j)；

根據式(6)，對所有與當前路徑點有可行路徑相連的路徑點，計算其被選擇的概率；

產生一個隨機數q，根據式(4)選擇下一個路徑點，pj；

pi=pi∪pj;

Until到達目的地。

去掉路徑pi中重復走過的路徑點；

根據式(9)，實施局部信息素更新；

/*子程序結束*/

5 算法仿真

為了比較基本多目標蟻群算法和改進多目標蟻群算法的性能，本文分別在150、180、300和400個威脅點的情況下進行了仿真驗證。兩個算法中，ρ、q0、α、β以及螞蟻數量等參數設置均相同。圖3給出了仿真實驗所得到的Pareto最優解集，圖中橫坐標表示路徑長度，縱坐標表示威脅強度。

注：improved表示改進算法的搜索結果；original表示基本算法的搜索結果。

圖3 兩種算法得到的Pareto前沿比較

在150個威脅點的情況下，基本多目標蟻群算法搜索得到的Pareto前沿上有三個解，而改進算法的Pareto前沿上有八個解，且完全支配基本算法得到的三個解。在180個威脅點時，改進算法得到的四個解也完全支配由基本算法得到的五個解。在400個點的情況下改進算法同樣是完全支配由基本算法得到的解。值得一提的是，在進行300個點的實驗時，基本算法一個可行解都沒有得到，而本文的改進算法的Pareto前沿上有四個解可供選擇。

圖4給出了180個威脅點時，由基本算法得到的Pareto前沿上的五條路徑和改進算法得到的四條路徑的對比圖。可以很直觀地看出，改進算法得到的結果要優于基本多目標蟻群算法。

6 結束語

路徑規劃是無人機任務規劃中最為基礎的且極為重要的一個環節。本文首先以VORONOI圖為基礎，構建了無人機的路徑規劃模型；其次，引入新的角度啟發信息，使得搜索更具有方向性，提高了算法的搜索效率，同時修改了啟發信息的計算公式，算法的全局搜索能力得到加強，避免了過早地收斂于局部極值；最后，使用改進的多目標蟻群算法進行路徑的選擇和優化。仿真結果表明，與基本多目標蟻群算法相比，改進的算法明顯提高了搜索結果的質量。

在得到Pareto解集后，決策者就可以根據自己的偏好，對路徑長度和威脅強度進行權衡，很方便地從其中選擇一條路徑，完成路徑規劃過程，進而，無人機便沿此路徑對目標實施攻擊。

參考文獻：

［1］朱戰霞，袁建平.無人機編隊飛行問題初探[J].飛行力學，2003，21(2):5-8.

［2］葉媛媛，閔春平， 沈林成， 等.基于VORONOI 圖的無人機空域任務規劃方法研究[J].系統仿真學報，2005，17(6):1353-1359.

［3］McLAIN T W，BEARD R W.Trajectory planning for coordinated rendezvous of unmanned air vehicles[C]//Proc of AIAA Guidance， Navigation，and Control Conference.Denver:[s.n.]，2000.

［4］DORIGO M，GAMBARDELLA L M.Ant colony system:a cooperative learning approach to the traveling salesman problem[J].IEEE Trans on Evolutionary Computation，1997，1（1）：53-56.

［5］王穎，謝劍英.一種自適應蟻群算法及其仿真研究[J].系統仿真學報，2002，14(1):31-33.

［6］丁建立，陳增強，袁著祉.遺傳算法與蟻群算法的融合[J].計算機研究與發展，2003，40(9):1531-1536.

［7］BARN B，SCHAERER M.A multiobjective ant colony system for vehicle routing problem with time window[C]//Proc of the 21st IASTED International Conference.Innsbruck:[s.n.]，2003:97-102.

［8］陳燁.變尺度混沌蟻群優化算法[J].計算機工程與應用，2007，43(3):68-70.

［9］劉利強，于飛，戴運桃.基于蟻群算法的水下潛器三維空間路徑規劃[J].系統仿真學報，2008，20（14）：3712-3716.