采用改進粒子群算法的無人機協(xié)同航跡規(guī)劃

朱收濤， 曹林平， 翁興偉， 董康生， 封普文

(空軍工程大學(xué)航空航天工程學(xué)院，西安 710038)

0 引言

近年來，隨著無人機技術(shù)的發(fā)展，各種無人機航路規(guī)劃算法也得到了快速發(fā)展，目前存在的研究方法主要有動態(tài)規(guī)劃算法、遺傳算法(GA)、A*算法、蟻群優(yōu)化算法(ACO)和粒子群(PSO)算法等。這些算法各有優(yōu)勢，并廣泛應(yīng)用于無人機的單機航跡規(guī)劃中。然而，隨著戰(zhàn)爭態(tài)勢的發(fā)展，單機作戰(zhàn)已不再適應(yīng)戰(zhàn)場需求，多無人機協(xié)同作戰(zhàn)將成為主要的作戰(zhàn)方式［1］。對于多架無人機來說，在規(guī)劃航跡時除了要保證單架無人機的運動限制、安全性等因素外，還需要處理各無人機航路在時間、任務(wù)上的協(xié)調(diào)關(guān)系。因此，本文從解決多無人機協(xié)同航跡規(guī)劃問題入手，提出了兩種解決方案，然后主要針對空間直接解決法，進行了詳細分析，最后結(jié)合一種改進的粒子群算法作了進一步的仿真分析。

1 多無人機協(xié)同航跡規(guī)劃問題分析

多無人機協(xié)同航跡規(guī)劃主要包括時間和空間上的協(xié)同［1－2］，即在研究多無人機協(xié)同航跡規(guī)劃時，不僅要考慮到各無人機在時間上的協(xié)同到達(同時到達或在一定的間隔時間內(nèi)到達)，還要重點考慮避免各無人機空間上的相互碰撞的問題。針對這一問題，解決的方法可以分為兩種:一是空間上的直接解決;二是時間上的間接解決。空間上的直接解決主要是在規(guī)劃無人機航跡時，使各無人機分布于不同的高度層，這樣各無人機就只在屬于自身的高度層飛行，結(jié)合相應(yīng)的時間要求，進行多機協(xié)同航跡規(guī)劃，執(zhí)行所攜帶的任務(wù)。時間上的間接解決主要是在規(guī)劃無人機航跡時，各無人機沒有相應(yīng)的高度空間限制，在滿足自身約束限制和時間協(xié)同基礎(chǔ)上的完全協(xié)同，使所規(guī)劃的各無人機航跡在同一時刻不會出現(xiàn)交叉點(碰撞點)，從而協(xié)同完成任務(wù)。圖1、圖2為兩種方法航跡規(guī)劃示意圖。

圖1 空間直接法下多機協(xié)同航跡規(guī)劃示意圖Fig.1 Multi－UCAV cooperative path planning through direct space method

圖2 時間間接法下多機協(xié)同航跡規(guī)劃示意圖Fig.2 Multi－UCAV cooperative path planning through indirect time method

2 協(xié)同變量與協(xié)同函數(shù)的構(gòu)建

在航跡規(guī)劃中，航跡的評價是極其重要的一部分。完整的航跡評價需要考慮影響無人機飛行的各種因素，并對各種因素進行量化，然后確定這些因素的影響權(quán)重，再進行綜合計算和航跡的尋優(yōu)操作。在研究無人機航跡規(guī)劃時，由于雷達威脅和路徑長度對無人機的評價有重要的影響，因此建立協(xié)同函數(shù)。

式中:Jxt表示N架無人機總的協(xié)同函數(shù)，為協(xié)同變量T的函數(shù);Ji表示第i架無人機的代價函數(shù);Ji_threat表示第i架無人機的雷達威脅代價;Ji_D表示第i架無人機的距離代價;wi_1表示第i架無人機威脅代價的權(quán)重;wi_2表示第i架無人機距離代價的權(quán)重，且有wi_1+wi_2=1;Ji_j表示第i架無人機第j條邊的威脅代價;kthreat為威脅系數(shù);li_j為第i架無人機第j條邊經(jīng)過雷達威脅區(qū)域AB段的距離;vi_j為AB段無人機的飛行速度;di_j為雷達中心O到AB段的距離;Rmax為雷達最大探測距離;kD為距離系數(shù);Di_j表示第i架無人機路徑中第j條邊的長度，如圖3所示。

圖3 雷達威脅示意圖Fig.3 Threat of radar

多架無人機要能夠協(xié)同作戰(zhàn)，首先要實現(xiàn)信息的交融與共享。文獻［3］在進行多無人機協(xié)同航跡規(guī)劃研究時，提出了一種基于分解策略的協(xié)同算法，并引入編隊預(yù)計到達目標(biāo)時間ETA(Estimated Team Arrival time)作為協(xié)同變量，飛行航跡的代價作為協(xié)同函數(shù)，通過協(xié)同函數(shù)傳遞各架飛機到達目標(biāo)的時間范圍，最終通過在協(xié)同規(guī)劃層調(diào)整ETA，尋找到既能滿足時間約束，又能使團隊代價最小，且盡量使單架無人機的個體代價次最小的航跡。文獻［4］通過構(gòu)建了多UCAV航跡規(guī)劃的系統(tǒng)總體結(jié)構(gòu)，并以協(xié)同時間作為指標(biāo)建立協(xié)同管理層的思想，給出了多UCAV協(xié)同飛行時間的確定方法，最終利用相關(guān)算法進行了航路規(guī)劃。這兩種方法的主要思想是從計算出協(xié)同時間出發(fā)，然后利用算法得出航跡，本文基于此思想進行了改進，然后利用粒子群算法進行航路規(guī)劃。文獻［3－4］的方法流程如圖4所示。

圖4 協(xié)同變量計算流程圖Fig.4 Flow chart of coordination variable calculation

由于無人機航路規(guī)劃中選取的目標(biāo)函數(shù)不同，所規(guī)劃的最優(yōu)路徑不一定是最短路徑。為了使最優(yōu)路徑等同于最短路徑，對規(guī)劃空間內(nèi)的各類威脅加以處理，就是使所有的威脅固化(或硬化)，然后形成除威脅外的可行空間，使其規(guī)劃的最優(yōu)航跡等同于最短航跡。具體的處理方法是:硬威脅區(qū)域不變，軟威脅進行威脅等效，威脅程度低于某一概率值時，處理為可行空間;威脅程度高于這一概率值時，處理為硬威脅，即不可行空間。圖5a、圖5b分別為避飛區(qū)和雷達威脅的硬化處理示意圖，其中，A區(qū)域為硬化區(qū)域，B區(qū)域為可行區(qū)域。另外，本文假設(shè)所有無人機為同一類型的無人機，各無人機均以 v勻速飛行，其中，v∈［vmin，vmax］。

圖5 避飛區(qū)和雷達威脅的硬化處理示意圖Fig.5 Ossifying of no－flying area and radar

如圖4所示，在進行各無人機到目標(biāo)點的最短路徑規(guī)劃后，要判斷是否存在交集，若存在，則選取編隊協(xié)同變量t和對應(yīng)的路徑編號以及相應(yīng)的飛行速度輸出到對應(yīng)的UCAV的路徑規(guī)劃層;若交集為空，路徑規(guī)劃層再為每個UCAV規(guī)劃第2、第3最短路徑，直到時間集合的交集不為空集。很明顯，在交集為空時，還需要第2次甚至多次的判斷才能尋找出協(xié)同變量t，然后找出相對應(yīng)的路徑。這樣的話，規(guī)劃時間就會有很大的不確定性，因此，需對此作以改進，其方法流程如圖6所示。

圖6 改進后的協(xié)同變量計算流程圖Fig.6 Flow chart of the improved coordination variable calculation

如圖6所示，在得到各無人機到目標(biāo)點的最短路徑規(guī)劃后，找出這些最短路徑中的最長路徑，并記該路徑所對應(yīng)的無人機為UCAVj，路徑長度表示為Lj。

假設(shè)UCAVj的最短路徑長度Lj為所有無人機最短路徑集合中的最長路徑，即 Lj=max{L1，L2，…，Lj，…，Ln}，n=1，2，…，N(N≥j)。在速度范圍 v∈［vmin，vmax］已知條件下，對應(yīng)的時間范圍 Tij=［Tjmin，Tjmax］。相應(yīng)的其他無人機在最短路徑下所對應(yīng)的時間范圍為Tin=［Tnmin，Tnmax］，其中 n≠j，n=1，2，…，N。易得 Tjmin≥max Tnmin，可知，若其他各無人機與UCAVj所對應(yīng)時間范圍交集不為空，則須有

然后，進行其他各無人機與UCAVj所對應(yīng)范圍交集判斷，若交集存在，則取協(xié)同變量Tjmin對應(yīng)的v為此架無人機的飛行速度，對應(yīng)的路徑為實際規(guī)劃的路徑，后面直接保存，不再規(guī)劃。若有其他的無人機與UCAVj所對應(yīng)時間范圍交集為空，則取Tjmin±Δt作為協(xié)同變量，Δt為同時到達允許誤差，取Vmin為每個無人機的飛行速度，然后進行路徑規(guī)劃，得出相應(yīng)的路徑。

這里取Vmin為每個無人機的飛行速度，是因為該無人機與UCAVj所對應(yīng)時間范圍交集為空，則表示該無人機的最短路徑長度太短，以致以Vmin飛行，所用的時間Tnmax仍小于Tjmin，進而形成交集為空。取Tjmin±Δt作為協(xié)同變量，只有以Vmin為每個無人機的飛行速度，其增加的路徑長度ΔL最少，即所增加的將會代價最少。

3 粒子群算法

粒子群(PSO)算法從生物種群行為這種特性中得到啟發(fā)并用于求解優(yōu)化問題。在粒子群優(yōu)化算法中，每個粒子都有自己的位置和速度，還有一個由被優(yōu)化函數(shù)決定的適應(yīng)值，并且知道自己到目前為止發(fā)現(xiàn)的最好位置(pbest)和現(xiàn)在的位置X。這個可以看作是粒子自己的飛行經(jīng)驗。除此之外，每個粒子還知道到目前為止整個群體中所有粒子發(fā)現(xiàn)的最好位置(gbest)(gbest是在所有pbest中的最好值)。其數(shù)學(xué)描述可以表示為

一般來說，為了節(jié)約管道資源，廚房和衛(wèi)生間都會設(shè)計在一起。但是，由于廚房會產(chǎn)生大量的煙霧，所以要注意通風(fēng)。首先要根據(jù)室內(nèi)通風(fēng)合理設(shè)置廚房的位置，這樣廚房的煙就可以通過煙機和窗戶迅速排出。其次，廚房設(shè)置為開放式或半開放式，以促進空氣流通。

式中:Vi(t)為第i個粒子的速度;Xi(t)為當(dāng)前第i個粒子的位置;w為慣性權(quán)重;pbest為個體極值;gbest為全局極值;rand()為介于(0，1)之間的隨機數(shù);c1，c2是學(xué)習(xí)因子。

雖然粒子群優(yōu)化算法具有形式簡單和性能高效的特點，但它也有一個缺陷，那就是容易陷入局部最優(yōu)而早熟收斂。因此，本文運用一種基于自然選擇的混合粒子群算法，以在后期對種群保持多樣性，進而能夠保證全局最優(yōu)搜索的精度［5］。

將自然選擇機理與粒子群算法相結(jié)合得到基于選擇的粒子群算法［6－7］，其基本思想為每次迭代過程中將所有粒子按適應(yīng)值排序，用群體最好的一半的粒子的速度和位置替換最差的一半的位置和速度，同時保留原來每個個體所記憶的歷史最優(yōu)值。將其運用到航跡規(guī)劃中，每一個粒子代表一條航跡，其算法步驟如下:

1)隨機初始化種群中各微粒的位置和速度;

2)評價每個微粒的適應(yīng)度，將當(dāng)前各微粒的位置和適應(yīng)值存儲在各微粒的pbest中，將所有pbest中適應(yīng)值最優(yōu)的個體的位置和適應(yīng)值存儲于gbest中;

3)更新每個微粒的速度和位置;

4)對每個微粒，將其適應(yīng)值與其經(jīng)歷過的最好位置作對比，如果較好，則將其作為當(dāng)前最好位置;

6)將整個粒子群按適應(yīng)值排序，用群體最好的一半的粒子的速度和位置替換最差的一半的位置和速度，保持 pbest和 gbest不變;

7)若滿足停止條件，搜索停止，輸出結(jié)果，否則返回3)繼續(xù)搜索。

一個粒子表示解空間中的一個可能解，即搜索空間中的一條備選航跡。航跡編碼的本質(zhì)是在種群中的每個粒子與搜索空間中的備選航跡之間建立一個一一映射關(guān)系。每個粒子代表唯一的一條航跡，每條航跡也對應(yīng)唯一的一個粒子［8－9］。

種群可以表示為一個矩陣 X=［X1，X2，…，Xm］T，其中:m為種群的大小;Xi為種群中的第i個個體(i=1，…，m)。由于每條航跡有相同的起始點和目標(biāo)點，所以起始點與目標(biāo)點不參與粒子的編碼。設(shè)每條航跡除起始點和目標(biāo)點外由n個航跡節(jié)點組成，為了記錄每個航跡節(jié)點的空間位置信息(x，y)，采用以下的定長實數(shù)編碼粒子結(jié)構(gòu)

式中，Xi，1，Xi，2，…，Xi，n和 Xi，n+1，…，Xi，2n分別記錄了 n個航跡節(jié)點在二維平面內(nèi)的橫坐標(biāo)值x和縱坐標(biāo)值y?；谏厦娴牧Ｗ咏Y(jié)構(gòu)，第i條航跡的第j個節(jié)點坐標(biāo)為(xi，j，xi，j+n)，其中，j=1，…，n。

由于對威脅作了處理，算法運行時，只在可行區(qū)范圍內(nèi)進行，此時wi_1=0，所以單架無人機的代價函數(shù)Ji變?yōu)?/p>

然后由此計算多架無人機的總的協(xié)同函數(shù)Jxt。

4 仿真驗證

為了減少無人機數(shù)據(jù)的計算量和信息的傳輸量，可由地面站直接為無人機編隊規(guī)定合理統(tǒng)一的到達時間Td(Td≤Tjmax)，使各無人機在這一到達時間值的要求下，各自規(guī)劃出最優(yōu)的航跡，這就把模型簡化成了在有時間要求下的無人機二維航跡規(guī)劃。這里按照圖6所示的方法進行仿真驗證。

在構(gòu)造二維規(guī)劃空間時，雷達威脅模型(包括雷達、高炮和地空導(dǎo)彈等)可以等效為含有威脅等級的圓形區(qū)域，規(guī)劃出具有突防效果的無人機航跡，具體威脅分布如圖7所示。

圖7 航跡規(guī)劃空間威脅分布圖Fig.7 Threat distribution of path planning

如圖7所示，在300 km×300 km規(guī)劃空間內(nèi)，起始點(0 km，0 km)，目標(biāo)點(300 km，300 km)，威脅包含兩處敵方防空雷達或武器威脅，兩處矩形禁飛區(qū)，一處矩形避飛區(qū)。設(shè)無人機飛行 Ma 數(shù)為［0.6，0.8］，協(xié)同時間約束T=2100±15 s。結(jié)合混合粒子群算法，進行基于協(xié)同時間約束下的單航跡規(guī)劃仿真實驗。

圖8 具有時間約束的單機航跡規(guī)劃圖Fig.8 UCAV path planning with time restriction

圖9 經(jīng)過平滑處理的航跡規(guī)劃圖Fig.9 UCAV path planning after smoothing

如圖8所示，紅色線條為所規(guī)劃的航跡，其距離代價為550.25 km，經(jīng)過平滑處理［7］后變?yōu)?546.128 km，以Ma為0.76勻速飛行，到達目標(biāo)點時間為2113.6 s，滿足協(xié)同時間約束的要求。為了使所規(guī)劃的航跡更加符合無人機真實航跡，進行平滑處理，結(jié)果如圖9中黑色軌跡所示。在進行多機協(xié)同航跡規(guī)劃仿真實驗時，協(xié)同變量按照圖6所示的流程計算得出。假設(shè)有3架無人機，其起始點分別是(0 km，0 km)，(0 km，150 km)和(150 km，0 km)，目標(biāo)點和規(guī)劃環(huán)境如圖7所示。初步規(guī)劃結(jié)果如圖10所示，為各無人機最短路徑俯視圖，其中UCAV1所規(guī)劃的最短(最優(yōu))航跡為3架無人機中的最長航跡，假設(shè)UCAV1以Ma為0.8勻速飛行到目標(biāo)點，則其用時2007.8 s?？傻脜f(xié)同變量 T=2007.8 s，加上誤差，則 T=2007.8 ±30 s。UCAV2最短航路長 420.5 km，其時間段為 T2=［1546.0 s，2058.8 s］，T2max＞T，則 UCAV2以 T 為協(xié)同變量，以該航跡為規(guī)劃航跡，以Ma為0.6飛行即可滿足要求。UCAV3最短航跡長度為362.3 km，該路徑下其時間段為 T3=［1331.99 s，1776.0 s］，由于 T3＜ T，所以需要對UCAV3進行以Ma為0.6的飛行，在協(xié)同時間T=2007.8±30 s的約束下進行航跡重規(guī)劃，即找出航跡長度在［403.5 km，415.7 km］的最優(yōu)航跡。

圖10 不同高度層多無人機航跡規(guī)劃俯視圖Fig.10 Top view of multi－UCAV path planning at different height layers

因此，利用本文改進的方法進行規(guī)劃，使無人機達到協(xié)同，仿真結(jié)果如圖11所示。

圖11 不同高度層多機協(xié)同航跡規(guī)劃俯視圖Fig.11 Top view of multi－UCAV cooperative path planning at different height layers

尋找到UCAV3在規(guī)定范圍內(nèi)的最優(yōu)航跡如圖中綠色軌跡所示，為410.2 km，滿足協(xié)同要求。

5 結(jié)束語

通過仿真驗證，可以看出本文構(gòu)建的協(xié)同變量和協(xié)同函數(shù)計算方法，使協(xié)同變量有了一定的確定性，進而提高了系統(tǒng)運算的速度。同時，提出空間直接法，較好地解決了多無人機協(xié)同航跡規(guī)劃問題。仿真結(jié)果表明，該方法在多無人機協(xié)同航跡規(guī)劃中具有較高的應(yīng)用價值。

［1］ 黃長強，翁興偉，王勇，等.多無人機協(xié)同作戰(zhàn)技術(shù)［M］.北京:國防工業(yè)出版社，2012.

［2］ 任敏，王克波，沈林成.多UAV協(xié)同突防規(guī)劃與仿真［J］.控制與決策，2011，26(1):157－160.

［3］ 安柏義.多無人機系統(tǒng)協(xié)同航跡規(guī)劃［D］.南京:南京航空航天大學(xué)，2008.

［4］ 高曉光，符小衛(wèi)，宋紹梅.多UCAV航跡規(guī)劃研究［J］.系統(tǒng)工程理論與實踐，2004，24(5):140－143.

［5］ 曹永恒.基于粒子群優(yōu)化算法的船舶航跡規(guī)劃方法研究［D］.上海:復(fù)旦大學(xué)，2010.

［6］ 龔存，王正林.精通MATLAB最優(yōu)計算［M］.北京:電子工業(yè)出版社，2012.

［7］ POUR N E.Path planning of unmanned aerial vehicle using particles swarm optimization and B－spline curves［D］.Canada:Royal Military College of Canada，2009.

［8］ 傅陽光.粒子群優(yōu)化算法的改進及其在航跡規(guī)劃中的應(yīng)用研究［D］.武漢:華中科技大學(xué)，2011.

［9］ HOLUB J S.Improving particle swarm optimization path planning through inclusion of flight mechanics［D］.Iowa:Iowa State University，2010.