王錦博，宋 偉，尚 帥，蘭庭信，盛守照

(南京航空航天大學(xué)自動化學(xué)院，江蘇 南京 210016)

0 引言

我國西部地區(qū)地形復(fù)雜，山區(qū)眾多，易發(fā)生山洪、泥石流和地震等突發(fā)性自然災(zāi)害，災(zāi)害發(fā)生后，無人直升機(jī)能夠第一時間深入災(zāi)區(qū)，到達(dá)受災(zāi)嚴(yán)重地區(qū)進(jìn)行偵查和救援。由于受災(zāi)地區(qū)多為山區(qū)，不論在進(jìn)行救援前的災(zāi)情調(diào)查還是物資運送活動，無人直升機(jī)往往需要在山谷之中穿行，為保證無人直升機(jī)飛行安全與救援效率，需要快速準(zhǔn)確地規(guī)劃出救援航路。

無人直升機(jī)的航路規(guī)劃需要綜合考慮飛行時間、飛行高度和障礙物威脅等，并結(jié)合無人直升機(jī)的性能約束，規(guī)劃出一條從初始位置到達(dá)任務(wù)目標(biāo)位置的最優(yōu)航路。常見的無人直升機(jī)路徑規(guī)劃算法有Dijkstra算法[1]、A*算法[2]、RRT算法[3]、人工勢場法[4]，以及以遺傳算法、蟻群算法、人工蜂群算法和鴿群算法為代表的智能優(yōu)化算法[5-9]。將智能優(yōu)化算法應(yīng)用在無人直升機(jī)路徑規(guī)劃中是當(dāng)前研究的熱點。

粒子群算法(PSO)的基本概念源于對鳥群覓食行為的研究，通過群體中個體之間的協(xié)作和信息共享來尋找最優(yōu)解[10]，具有操作簡單、算法易于實現(xiàn)和魯棒性好等優(yōu)點。PSO算法在初始時能很快向最優(yōu)值聚攏，但在最優(yōu)值附近收斂變慢，易陷入局部最優(yōu)。本文針對無人直升機(jī)航路規(guī)劃問題，對粒子群算法進(jìn)行了改進(jìn)，引入選擇操作和雜交操作增加種群多樣性，避免陷入局部最優(yōu)，當(dāng)檢測到種群陷入局部最優(yōu)時，通過變異算子跳出局部最優(yōu)解。

1 航路規(guī)劃模型

1.1 無人直升機(jī)航路約束條件

基于無人直升機(jī)性能限制，無人直升機(jī)的航路規(guī)劃需要滿足一定的約束條件。直升機(jī)主要約束有最小航段約束、最大轉(zhuǎn)彎角度約束、最大航程約束、最小離地高度約束和最大爬升角約束等。

a.最小航段約束定義為無人直升機(jī)改變飛行姿態(tài)前必須保持穩(wěn)態(tài)前飛的最小距離。在飛行過程中頻繁改變姿態(tài)會影響無人直升機(jī)的穩(wěn)定性，嚴(yán)重時會導(dǎo)致墜機(jī)事故，所以應(yīng)盡可能避免頻繁的姿態(tài)變換。則此約束為

li>lmin

(1)

li(i=1,2,…,n)為無人直升機(jī)第i個飛行航跡段長度；lmin為最小航跡段長度。

b.最大轉(zhuǎn)彎角度約束定義為無人直升機(jī)在水平面內(nèi)做圓周運動時的航向連續(xù)變化最大范圍。山谷大氣環(huán)境復(fù)雜，做大角度轉(zhuǎn)彎時，無人直升機(jī)極易受到山谷風(fēng)影響，所以需要限制無人直升機(jī)的連續(xù)轉(zhuǎn)彎角度。則此約束為

ψi<Δψmax

(2)

ψi(i=1,2,…,n-1)為無人直升機(jī)第i個轉(zhuǎn)彎角度；Δψmax為最大轉(zhuǎn)彎角度。

c.最大航程約束定義為無人直升機(jī)在飛行過程中由于攜帶的燃料限制或特殊任務(wù)要求，飛行航線的長度必須滿足小于或者等于1個預(yù)先設(shè)置的最大值。則此約束為

(3)

Lmax為最大航程。

d.最小離地高度約束定義為無人直升機(jī)在飛行過程中避免與地面相撞，必須滿足最小飛行高度。則此約束為

hi≥hmin

(4)

hi(i=1,2,…,n)為第i段航段最低離地高度；hmin為要求最小離地高度。

e.最大爬升角約束定義為直升機(jī)在規(guī)劃的航跡時需要限制爬升和下降的角度。則此約束為

(5)

θmax為直升機(jī)最大爬升角；|zi-zi-1|為第i段航跡的高度差；ai為第i段航跡的水平投影長度，i=1,2,…,n。

1.2 航路代價函數(shù)

在規(guī)劃航跡時主要考慮時間代價與威脅代價，并規(guī)劃出一條能夠安全、快速到達(dá)指定任務(wù)地點，滿足所有約束條件的可用航跡。無人直升機(jī)在山谷中飛行時，為了保證飛行安全，通常采用經(jīng)濟(jì)巡航速度執(zhí)行任務(wù)，保證最大剩余可用功率，能夠及時應(yīng)對突發(fā)情況，所以時間代價可以轉(zhuǎn)化為航程代價。為了保證飛行過程平穩(wěn)，還需考慮高度代價。設(shè)F為每條選出航跡的代價函數(shù)：

(6)

在進(jìn)行個體適應(yīng)度計算時，必須先對航跡代價函數(shù)中的各部分代價值進(jìn)行歸一化處理，避免各部分代價值數(shù)量級差異導(dǎo)致的計算誤差。

2 基于粒子群算法的無人直升機(jī)航路規(guī)劃

2.1 標(biāo)準(zhǔn)粒子群算法

標(biāo)準(zhǔn)PSO算法中，每個粒子僅有速度和位置2個屬性，粒子通過跟蹤個體最優(yōu)解Pi和種群最優(yōu)解Pg實現(xiàn)全局尋優(yōu)，迭代中粒子的速度和位置更新公式為：

vi(t+1)=w×vi(t)+R1c1(Pi-xi(t))+R2c2(Pg-xi(t))

(7)

xi(t+1)=xi(t)+vi(t+1)

(8)

vi∈[vmin,vmax]、xi∈[xmin,xmax]分別為第i個粒子的速度和位置；R1和R2為0～1之間的隨機(jī)數(shù)；ci和c2為加速常數(shù)，表示粒子受個體認(rèn)知和社會認(rèn)知的影響程度;w為慣性權(quán)重因子，當(dāng)w較大時，算法具有較強(qiáng)的全局搜索能力，w較小則算法傾向于局部搜索。一般是將w初始化為wmax，并使其隨迭代次數(shù)的增加線性遞減至wmin。w的線性變化由下式確定：

(9)

tmax為最大迭代次數(shù)；t為當(dāng)前迭代次數(shù)。

2.2 改進(jìn)粒子群算法

標(biāo)準(zhǔn)PSO算法通過粒子間的信息交流完成全局尋優(yōu)。當(dāng)粒子個體陷入局部最優(yōu)時只能通過其他粒子才能逃脫。迭代后期種群會呈現(xiàn)趨同性，搜索能力變差，容易陷入局部最優(yōu)解，從而導(dǎo)致PSO算法無法找到全局最優(yōu)解。

為了避免PSO算法中的粒子失去種群多樣性，在迭代過程中引入選擇操作和雜交操作。

采用輪盤賭的方式從群體中選取一部分粒子，記為子群D，個體的選擇概率與其適應(yīng)度值成比例，即

(10)

fi為粒子個體適應(yīng)度。

將子群D中的粒子隨機(jī)的兩兩雜交，產(chǎn)生同樣數(shù)目的子代粒子代替父代粒子。子代位置由父代粒子位置進(jìn)行雜交產(chǎn)生。

xs=CR×xp(1)+(1-CR)xp(2)

(11)

xp為父代粒子位置；xs為子代粒子位置；CR=rand(0,1)為雜交算子。

子代速度由下式計算：

(12)

vp為父代粒子速度；vs為子代粒子速度。

當(dāng)連續(xù)幾代的全局最優(yōu)適應(yīng)值不變，認(rèn)為種群陷入局部最優(yōu)，此時隨機(jī)選取3個粒子，對粒子群進(jìn)行變異操作，則有

xi=xl+F(xm-xn)i≠l≠m≠n

(13)

xl、xm、xn為隨機(jī)選取粒子位置；F為差分變異算子。

2.3 算法流程

無人直升機(jī)的飛行軌跡可定義為一系列有序的三維空間位置點的集合{PS,P1,P2,…,PG}，PS、PG分別是無人直升機(jī)的起始位置和目標(biāo)位置，Pi=(xi,yi,zi)(i=0,1,2,…,n-1)為中間航路點，相鄰的空間位置之間使用直線連接。在三維空間中進(jìn)行隨機(jī)搜索非常復(fù)雜，由于某點地面高度與該點縱橫坐標(biāo)有直接關(guān)系，所以可以將搜索空間降維到二維空間，再按照改進(jìn)PSO算法步驟進(jìn)行搜索，減少搜索時間。

改進(jìn)PSO算法的具體步驟如下：

a.將搜索空間沿x軸方向n等分(對應(yīng)n-1個中間航路點)。設(shè)置算法基本參數(shù)，包括群體規(guī)模N、最大迭代次數(shù)tmax、最大慣性權(quán)重wmax、最小慣性權(quán)重wmin、加速因子c1和c2、變異算子F等。

b.初始化粒子群位置矩陣，計算初始個體適應(yīng)值，并將最好個體適應(yīng)值記為初始全局最優(yōu)適應(yīng)值。

c.根據(jù)式(7)和式(8)更新粒子群位置和速度，并將其限制在速度與位置范圍內(nèi)。

d.比較每個粒子適應(yīng)值與其歷史個體最優(yōu)適應(yīng)值，如果優(yōu)于歷史個體最優(yōu)適應(yīng)值，則更新Pi。將所有個體最優(yōu)適應(yīng)值與全局最優(yōu)適應(yīng)值比較，更新Pg。

e.通過輪盤賭的方式，從種群中選擇一部分粒子按照式(11)和式(12)進(jìn)行雜交。

f.判斷算法是否達(dá)到終止條件，是則轉(zhuǎn)步驟h，否則，進(jìn)入步驟g。

g.判斷是否陷入局部最優(yōu)，若是則根據(jù)式(13)進(jìn)行變異，轉(zhuǎn)向步驟d，否則，轉(zhuǎn)向步驟c。

h.輸出航路種群中最優(yōu)的航路作為航路規(guī)劃結(jié)果。

3 實驗結(jié)果及分析

在MATLAB 2017b環(huán)境下，分別使用標(biāo)準(zhǔn)粒子群算法PSO-1和改進(jìn)粒子群算法PSO-2進(jìn)行了仿真驗證。粒子群算法的參數(shù)設(shè)置：PSO-1和PSO-2的種群數(shù)量N=30，最大迭代次數(shù)tmax=500，慣性權(quán)重因子wmax=0.9、wmin=0.4，加速常數(shù)c1=c2=2，PSO-2的變異常數(shù)F=0.15。設(shè)置性能指標(biāo)的權(quán)重系數(shù)分別為w1=w2=w3=1/3。 適應(yīng)度值變化曲線圖1所示。

圖1 適應(yīng)度值變化曲線

由圖1可知，改進(jìn)粒子群算法在第86代就已經(jīng)收斂到最優(yōu)，其收斂精度和收斂速度都優(yōu)于標(biāo)準(zhǔn)粒子群算法，表明改進(jìn)PSO算法能夠快速有效地為無人直升機(jī)進(jìn)行任務(wù)航路規(guī)劃。

圖2和圖3分別是改進(jìn)粒子群算法優(yōu)化得到的無人直升機(jī)三維最優(yōu)航路和二維等高線航路?？梢钥闯觯诟倪M(jìn)粒子群算法得出的最優(yōu)航路成功地規(guī)避了所有障礙威脅，航路平滑且精度較高，滿足無人直升機(jī)性能約束，保證了飛行的安全性。

圖2 三維航路圖

圖3 等高線圖

4 結(jié)束語

針對傳統(tǒng)PSO算法易陷入局部最優(yōu)的缺點，引入選擇、雜交、變異操作，對粒子群算法進(jìn)行改進(jìn)。仿真實驗結(jié)果表明，本文所提出的改進(jìn)PSO算法能合理有效地規(guī)劃無人直升機(jī)航路，并迅速地得到無人直升機(jī)的最優(yōu)航路。