席劍銳,楊金孝,張博亮,陳志星

(西北工業(yè)大學 電子信息學院,西安 710129)

?

無人機三維實時航跡規(guī)劃

席劍銳,楊金孝,張博亮,陳志星

(西北工業(yè)大學 電子信息學院,西安 710129)

無人機航跡規(guī)劃是無人機任務規(guī)劃中最重要也是最復雜的環(huán)節(jié)，針對基本粒子群航跡規(guī)劃算法后期容易陷入局部最優(yōu)解、算法容易“早熟”、規(guī)劃出的航跡精度不高等問題，提出了一種以并行方式進行的雙種群粒子群航跡規(guī)劃算法;雙種群粒子群算法由兩個向相反方向搜索的種群構成，這兩個種群協(xié)同優(yōu)化，擴展了搜索范圍，克服了基本粒子群算法后期容易陷入局部最優(yōu)解的問題，提高了航跡的精度;如果無人機在飛行過程中檢測到突發(fā)威脅，則尋找鄰近航跡點作為實時重規(guī)劃點，規(guī)劃其到目標點的航跡;通過仿真驗證了算法的有效性，并滿足了實時性的要求。

無人機;三維航跡規(guī)劃;雙種群粒子群算法;實時性

0 引言

無人機是“無人駕駛空中飛行器”(UAV)的簡稱。隨著航空航天技術的日新月異以及高新技術的快速發(fā)展，無人機作為一種新興的航空軍事力量在現(xiàn)代戰(zhàn)場中的作用越來越明顯，必將左右未來戰(zhàn)場的格局[1]。無人機航跡規(guī)劃(route planning for unmanned aerial vehicles)是無人機任務規(guī)劃(mission planning)的一項重要組成部分，對于無人機圓滿完成作戰(zhàn)任務有著非常重要的意義。一條好的航跡不但可以符合無人機自身的約束以及各種地理環(huán)境的約束，而且能夠有效地躲避戰(zhàn)場上的各種威脅[2]。無人機航跡規(guī)劃問題究其本質是最優(yōu)化問題，具體的來說，最優(yōu)化問題就是在約束條件的限定范圍之內尋找一組數(shù)據，該組數(shù)據能夠使函數(shù)(或系統(tǒng))的一些指標特性達到最小或者最大值。航跡規(guī)劃算法對于無人機航跡規(guī)劃至關重要，目前用在無人機航跡規(guī)劃上的算法有許多，根據不同的標準可以將航跡規(guī)劃算法進行劃分。根據航跡規(guī)劃決策的計算方式來分，可以分成智能優(yōu)化算法和傳統(tǒng)的經典算法。由于傳統(tǒng)經典算法存在著：計算的工作量較大、容易陷入局部最優(yōu)解以及不具有智能搜索功能等缺點。因此，目前的主流方式是采取智能優(yōu)化算法對航跡規(guī)劃問題進行求解。在智能優(yōu)化算法中，遺傳算法、A-Star算法、蟻群算法和粒子群算法是經常用到的算法?；玖Ｗ尤核惴敯粜詮?、計算量小、不需要梯度的信息、易于實現(xiàn)，但算法容易陷入局部最優(yōu)解，算法容易“早熟”。因此，本文提出了一種雙種群粒子群航跡規(guī)劃算法。

1 航跡規(guī)劃建模

1.1 威脅信息轉化

在無人機航跡規(guī)劃中，需要對威脅信息進行回避。威脅信息主要包括兩種類型：探測威脅(包括可見光、紅外射線、音響、雷達等)和火力威脅(機載、車載導彈系統(tǒng)以及不同口徑的火炮等)。如果利用傳統(tǒng)的方法將威脅信息轉化為數(shù)學上的約束條件，那么在每一次迭代的過程中代價函數(shù)的計算量將大大增加，使航跡規(guī)劃過程變得非常復雜。因此，本文采取了威脅信息融合技術，將飛行區(qū)域內已知地形和威脅信息融合成一種綜合的地形，將威脅的規(guī)避轉化為地形的規(guī)避，降低了航跡規(guī)劃過程中的計算量，使得實時性要求得以滿足。

對威脅信息融合需要首先將威脅等效為地形高程數(shù)據，如式(1)所示：

(1)

式中,T(x，y) 為威脅等效高度在點(x，y)的值；z0為威脅中心處的地形高度；r 為航跡點與威脅中心的水平距離；Rmax為威脅的最大作用半徑。

然后將各種威脅等效的高程數(shù)據離散化，并采用如式(1)的方法，從而得到融合后的綜合地形高程數(shù)據h。

(2)

式中，hth為地形高程數(shù)據；htd1，htd2，…，htdm為 m個威脅的等效高程數(shù)據。

對威脅的融合采用取極大值而非高程值直接相加的方法，這樣能夠更好地利用地形隱蔽信息的作用。如果在某區(qū)域內，地形點的高度值大于該區(qū)域威脅等效后的高度值，那么說明該區(qū)域內的地形對威脅具有很好的隱蔽作用。因此可以不考慮威脅產生的影響，而只考慮該區(qū)域內的地形信息。

1)高炮威脅。設高炮的水平坐標為(x0，y0)，在各個方向上的作用半徑相同均為R0，則高炮等效地形程為：

(3)

式(3)是旋轉拋物面的方程，因此等效地形跟山峰模型相似。

2)雷達威脅。假設在雷達最大作用距離Rfmax處無人機被發(fā)現(xiàn)的概率為某一定值，那么可用如下等效高程來描述：

(4)

式(4)中，a為小于1的常數(shù)；b為大于1的常數(shù)；HR為一很大常數(shù)。

治療后兩組的Vmax、PAPs值低于治療前，同組治療前后比較差異有統(tǒng)計學意義（P＜0.05）；觀察組治療后也低于對照組，差異有統(tǒng)計學意義（P＜0.05），見表3。

1.2 最小安全曲面

如果在綜合等效曲面h(x, y)上疊加一個最佳安全離地高度hc，那么將得到一個新的曲面，顯然無人機在該曲面上飛行是安全的，將該曲面稱為安全曲面。最佳安全離地高度hc需要根據區(qū)域地理特征及已知威脅殺傷特性來確定。國外文獻認為，最佳離地高度：海面上空15～30 m，陸地平原地區(qū)上空為60～80 m，丘陵山區(qū)上空為120 m左右。在得到了安全曲面后，最佳航跡的存在空間便縮小到安全曲面上了，從而可把三維航跡規(guī)劃的優(yōu)化過程限制在一個二維曲面上，大大地降低了計算量，滿足了航跡規(guī)劃中實時性的要求。

1.3 代價函數(shù)的確立

假設S:S={s1,s2,s3,…, sm}表示規(guī)劃空間的所有節(jié)點組成的集合,E:E={e1, e2, e3,…, en}是兩兩相鄰可通節(jié)點組成的可飛航跡集合。若第i段航跡ei(ei∈E)是由兩個相鄰節(jié)點si和si+1和(si,si+1∈S)構成，該段航跡的代價可由代價函數(shù)F求得，航跡規(guī)劃的目的就是要使所以航跡代價的總和最小[3]。前文已經將無人機在作戰(zhàn)任務中可能遇到的威脅納入考慮，在實際飛行過程中，無人機自身的機動性能和生存概率也是影響航跡規(guī)劃的重要因素。在實際飛行過程中，無人機自身的機動性能和生存概率也是影響航跡規(guī)劃的重要因素。這其中包括航跡總長度、最大轉彎角、最大爬升/下滑角、最小航跡長度、最低飛行高度和靠近目標程度。若將規(guī)劃空間離散化，航跡可以用節(jié)點的形式表示[4]，則總代價函數(shù)F：

(5)

其中：fi為各子代價函數(shù)，ki為每個子函數(shù)的加權系數(shù)，每個權重系數(shù)的大小可以根據無人機自身的機動性能以及無人機具體的飛行環(huán)境和任務而改變，但應滿足：

(6)

2 基本粒子群算法

2.1 標準粒子群算法

標準粒子群算法中，每個粒子(Particle)代表一個可能的解，所有的粒子組成群體(Swarm)。粒子在解空間中根據自身的歷史信息和群體信息共同決定其“飛翔(fly)”的速度和方向，以此來尋找最優(yōu)解。假設在D維搜索空間中進行問題求解，群體由m個粒子組成，Swarm={x1(t), x2(t),…,xm(t)}。t時刻第i個粒子在搜索空間中的位置向量為xi(t)=[xi1(t),xi2(t),…,xid(t)]，i=1,2，…，m，xik(t)表示這個粒子在第k維坐標中的位置，同時也是問題的一個可能解。與該個體位置向量相對應的是其速度向量vi(t)={vi1(t), vi2(t),…,vid(t)}，vik(t)為該粒子在第k維坐標下的速度，描述了此粒子在第k維上的運動情況。標準粒子群算法的鄰域函數(shù)在每一次迭代中根據粒子自身位置向量、速度向量、個體歷史信息、群體信息和擾動產生新的位置狀態(tài)。標準粒子群算法中第i個粒子在t+1時刻的鄰域函數(shù)計算公式如下[5]：

(6)

(7)

標準粒子群算法中，個體極值pibest=(pi1, pi2,…, pid)，代表了單個粒子從開始搜索到當前對應的代價函數(shù)最小的解；全局極值gibest=(gi1, gi2,…,gid)，代表了整個粒子群從開始搜索到當前對應的代價函數(shù)最小的解。粒子群中的每個粒子根據個體極值pibest和全局極值gbest的位置和速度，按照公式6、7來更新自己的位置和速度，使粒子向著最優(yōu)解移動，從而產生下一代群體，t代表PSO的優(yōu)化迭代次數(shù)，i=1,2,…,n。非負常數(shù)c1、c2為學習因子，也稱為加速因子，它使粒子可以向群體中的最優(yōu)個體學習并具有自我總結能力，從而使粒子向個體極值和全局極值兩個最優(yōu)點移動。在粒子群算法中，學習因子對收斂所起的作用并不大，但是對學習因子進行適當?shù)恼{整可以減少局部最優(yōu)值的困擾，也可以加快收斂速度。rand1、rand2是介于0～1之間的兩個隨機數(shù)，可以保持群體的多樣性。慣性權重ω表示上一迭代時刻搜索速度在下一迭代時刻的慣性保留值，適當設置慣性權重ω的值，可以控制算法探測(exploration)和開發(fā)(exploitation)能力。

2.2 慣性權值的調整

本文采取一種多樣性反饋的自適應慣性權重調整策略[6]。為了引入這種慣性權重調整策略，首先介紹一種基于熵概念的多樣性評價機制。初始化參數(shù)，在n維搜索空間內，設粒子集合X={x1, x2, …, xm}，m為粒子數(shù)目，xi為n維向量。假設粒子群在搜索空間內最長對角線長度為d(xi, xj)=L，粒子xi和xj連線的方向矢量為v。按照式(8)計算每個粒子(除去xi和xj)在方向為v上的投影，便得到m個一維樣本ym。

yi=vTxi

(8)

將xi和xj的連線按長度劃分成m個等距離的子區(qū)域，統(tǒng)計區(qū)域內樣本yi的數(shù)目hi(i=1，2,3,…,m)，且。計算分布熵：

(9)

上述評價機制量化了粒子在搜索空間內的離散程度，分布熵越大，多樣性越好，反之，多樣性較差。按照以上評價策略將慣性權重ω按以下方式進行自適應調節(jié)：

(10)

由上式可知，ω會隨著E(t)做單調變化，因此ω將會隨著搜索過程中的多樣性來自適應的進行調整。當E(t)較大時，ω隨多樣性成單調遞增趨勢，有利于增強算法的全局搜索能力；當E(t)較小時，ω隨多樣性成單調遞減趨勢，有利于算法的局部探索能力。

2.3 雙種群粒子群算法

雙種群粒子群算法受到并行優(yōu)化思想的啟發(fā)，設置兩個搜索方向相反的主、輔種群協(xié)同優(yōu)化，并通過比較兩個種群間代價函數(shù)來評價兩個種群中粒子位置的優(yōu)劣，以此來擴大搜索范圍，能夠快速而準確的響應極值點的變化情況。下面給出雙種群粒子群算法的實現(xiàn)思想：隨機初始化一組種群后將其平均分成兩個相互獨立的種群。其中一個種群稱為主子群，按照式(6)、(7)的速度、位置更新公式進行迭代搜索；另一個種群稱為輔子群，速度更新方法與主子群一致，但按照主子群相反的方向進行迭代搜索，即位置更新按照公式(11)進行[7]：

(11)

每次迭代更新完成之后比較兩個種群個體最優(yōu)位置pibest所對應的代價函數(shù)值的大小，代價函數(shù)值較大的個體粒子被淘汰。在進行下一次迭代時，主輔種群從當前最優(yōu)位置出發(fā)，向兩個相反的方向進行迭代搜索全局最優(yōu)解gbest。這樣在不增加粒子規(guī)模的前提下，兩個種群相互補充、協(xié)同進化，極大程度了擴大了搜索范圍，并在搜索空間內極大地發(fā)掘出有用信息，有效地降低了算法后期標準粒子群算法易于陷入局部最優(yōu)解的可能性。同時，雙種群粒子群算法并沒有增加算法的復雜度，延續(xù)了基本粒子群算法高效的搜索效率，滿足了對實時性的要求。因此，雙種群粒子群算法能夠更加快速而準確地響應動態(tài)變化的極值，不會產生因算法后期陷入局部最優(yōu)解而產生的停滯進化的現(xiàn)象。本文將反饋自適應慣性權重與雙種群粒子群算法結合，每個粒子代表一個潛在的航跡，則航跡規(guī)劃流程圖如圖1所示。

圖1 雙種群粒子群算法流程圖

3 無人機實時航跡規(guī)劃

在實際應用中，由于反威脅裝置的存在，很多威脅是無法預知的，只有當無人機飛行到它的附近時才能通過機載設備感知發(fā)現(xiàn)，這種威脅一般稱為(pop-up)威脅[8]，如果依然按照整體規(guī)劃的航跡飛行，會大大地降低無人機安全飛行的概率。因此，當無人機探測到規(guī)劃空間有突發(fā)威脅時，需要對其航跡進行重規(guī)劃，以保證無人機能夠安全地到達目的地并完成飛行任務。

一般處理突發(fā)威脅有兩種方法：第一種將威脅信息等效成數(shù)字地形加載到數(shù)字地圖中去，進行全局航跡的重規(guī)劃，這樣雖然可以得到較優(yōu)的航跡，但卻以犧牲時間為代價，并且重新規(guī)劃出的航跡很難與無人機正在飛行的航跡有交匯點，也就是說無人機無法從當前位置飛到規(guī)劃的航跡上去，那么規(guī)劃出的航跡也就失去了意義；第二種是進行局部重規(guī)劃，即在原來整體參考航跡的基礎之上進行局部重規(guī)劃，將威脅等效成數(shù)字高程信息后，以無人機當前坐標位置為起點，規(guī)劃其到終點的航跡路線。這種方法規(guī)劃時間短，滿足了在線航跡規(guī)劃實時性的要求。因此，本文采用第二種方法對突發(fā)威脅進行規(guī)避。

4 仿真

本文采用MalabR2008a分別對無人機的整體航跡規(guī)劃、在線航跡規(guī)劃進行仿真分析。雙種群粒子群算法中選取初始粒子數(shù)為20，c1=c2=1.4，最大迭代次數(shù)為100次。設置規(guī)劃空間大小為100*100，第一個山峰模型基準高度為0，中心坐標為(30,30)，山峰高度h1=1000，x軸和y軸的坡度向量依次為xsi=13，ysi=13;第二座山峰基準高度為0，中心坐標為(70,70)，山峰高度h2=800，x軸和y軸的坡度向量依次為xsi=16，ysi=16，無人機最小飛行長度為3，最大轉彎角為90°，最大爬升/下滑角為60°，單位步長內無人機所能抬升的最大高度為100。設置兩個高炮威脅以及兩個雷達威脅，雷達和高炮威脅如表1所示。

表1 威脅坐標

圖2 基本粒子群算法循環(huán)迭代圖

圖3 雙種群粒子群算法循環(huán)迭代圖

圖2、圖3為整體航跡規(guī)劃的循環(huán)迭代圖，由循環(huán)迭代圖可以看出基本粒子群算法大約在28代開始收斂，收斂值約為2 230。而在雙種群粒子群算法中，算法大約在80代開始收斂，收斂值約為1 860。這說明雙種群粒子群算法在算法后期，可以借助兩個種群的協(xié)同作用跳出局部最優(yōu)解，解決基本粒子群算法中的“早熟”問題，從收斂值可以看出，雙種群粒子群算法規(guī)劃的航跡要更加優(yōu)于基本粒子群算法所規(guī)劃的航跡，證明了雙種群粒子群算法在三維航跡規(guī)劃中的可行性。

圖4 三維實時航跡規(guī)劃

無人機起始點坐標為(5，5)，終點坐標為(100，50)，假設在其飛行航跡點(58，23)的A處發(fā)現(xiàn)坐標中心位于(70，30)的雷達威脅，威脅半徑為5，此時無人機對此威脅進行響應，進行航跡重規(guī)劃。如圖5等高線圖所示，無人機在原航跡坐標為(60，25)的B處進行了航跡重規(guī)劃，(a)線代表原先規(guī)劃的航跡，(b)線為重規(guī)劃后的航跡。從圖中可以得出，如果按照原先規(guī)劃好的航跡，那么無人機將會暴露在雷達威脅下，而重規(guī)劃后的航跡躲避掉了雷達威脅，滿足了實時性的要求。

5 結論

針對基本粒子群航跡規(guī)劃算法后期易于陷入局部最優(yōu)解，

圖5 三維實時航跡規(guī)劃等高線圖

規(guī)劃出的航跡精度不高等問題，本文提出了雙種群粒子群航跡規(guī)劃算法予以改進，同時慣性權重的選擇采取多樣性反饋的自適應慣性權重調整策略。通過仿真可以看出：改進后的粒子群算法能夠跳出局部最優(yōu)解，提高了航跡規(guī)劃的精度。同時，針對在真實環(huán)境中所出現(xiàn)的突發(fā)威脅，采用在整體參考航跡的基礎之上進行局部修改，將威脅等效成數(shù)字高程信息后，以無人機當前坐標位置為起點，規(guī)劃其到終點的航跡路線，仿真結果也驗證了其有效性。

[1] 丁阿維.我國軍用無人機發(fā)展趨勢及現(xiàn)狀分析[J]. 硅谷, 2015(3): 152-153.

[2] ?zalp N, Sahingoz O K. Optimal UAV path planning in a 3D threat environment by using parallel evolutionary algorithms[A]. 2013 International Conference on Unmanned Aircraft Systems (ICUAS)[C]. Grand Hyatt Atlanta, Atlanta, GA, 2013: 308-317.

[3] 王緒芝.不確定環(huán)境下無人機航跡動態(tài)規(guī)劃及仿真研究[D]. 南京：南京航空航天大學，2013.

[4]姚永杰，席慶彪，劉慧霞. 基于改進遺傳蟻群算法的無人機航路規(guī)劃[J]. 計算機仿真, 2011,28(6):44-47.

[5] Shi Y, Eherhart R C. Parameter selection in particle swarm optimization[A]. Proc.Seventh Annual Conference on Evolutionary Programming[C]. 1998:591-600.

[6]湯可宗，吳 雋，趙 嘉. 基于多樣性反饋的自適應粒子群優(yōu)化算法[J]. 計算機應用, 2013,33(12):3372-3374.

[7] Sun S Y， Li J W. A two-swarm cooperative particle swarms optimization [J]. ScienceDirect,2014(15):1-18.

[8] Beard R W， Mdain T W， Goodrich M，et al．Coordinated target assignment and intercept for unmanned air vehicles[J]．IEEE Trans．on Robotics and Automation(to appear),2002,18(6).

UAV Three Dimensional Real-time Route Planning

Xi Jianrui, Yang Jinxiao, Zhang Boliang, Chen Zhixing

(School of Electronics and Information, Northwestern Polytechnical University, Xi′an 710129,China)

UAV path planning is the most important and most complex part of UAV mission planning.Because particle swarm algorithm is easy to fell into local optimal solution and “premature”, and the precision of planning flight route is low, a parallel implementation of two-swarm particle swarm algorithm for route planning is presented, this algorithm is comprised of two particle swarm algorithms which have reverse direction of search, and this algorithm can extend the range of search through cooperation of two particle swarm algorithms, overcome the problem of falling into local optimal solution and improve the precision of flight route. With unexpected threat detected in flight, UAV will search near point of flight route and then replan route from this point to target point.Simulation results show the effectiveness of the algorithm.

UAV; three-dimensional path planning; two-swarm particle swarm optimization; real-time

2015-12-03；

2016-01-07。

席劍銳(1990-)，男，陜西西安人，碩士，主要從事微電子與固體電子學方向的研究。

1671-4598(2016)06-0181-04

10.16526/j.cnki.11-4762/tp.2016.06.050

V279

A