基于改進(jìn)粒子群算法的無(wú)人直升機(jī)航路規(guī)劃

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

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

0 引言

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

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

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

1 航路規(guī)劃模型

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

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

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

li>lmin

(1)

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

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

ψi<Δψmax

(2)

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

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

(3)

Lmax為最大航程。

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

hi≥hmin

(4)

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

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

(5)

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

1.2 航路代價(jià)函數(shù)

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

(6)

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

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

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

標(biāo)準(zhǔn)PSO算法中，每個(gè)粒子僅有速度和位置2個(gè)屬性，粒子通過(guò)跟蹤個(gè)體最優(yōu)解Pi和種群最優(yōu)解Pg實(shí)現(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個(gè)粒子的速度和位置；R1和R2為0～1之間的隨機(jī)數(shù)；ci和c2為加速常數(shù)，表示粒子受個(gè)體認(rèn)知和社會(huì)認(rèn)知的影響程度;w為慣性權(quán)重因子，當(dāng)w較大時(shí)，算法具有較強(qiáng)的全局搜索能力，w較小則算法傾向于局部搜索。一般是將w初始化為wmax，并使其隨迭代次數(shù)的增加線性遞減至wmin。w的線性變化由下式確定：

(9)

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

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

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

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

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

(10)

fi為粒子個(gè)體適應(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)為雜交算子。

子代速度由下式計(jì)算：

(12)

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

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

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

(13)

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

2.3 算法流程

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

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

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

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

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

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

e.通過(guò)輪盤賭的方式，從種群中選擇一部分粒子按照式(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 實(shí)驗(yàn)結(jié)果及分析

在MATLAB 2017b環(huán)境下，分別使用標(biāo)準(zhǔn)粒子群算法PSO-1和改進(jìn)粒子群算法PSO-2進(jìn)行了仿真驗(yà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算法能夠快速有效地為無(wú)人直升機(jī)進(jìn)行任務(wù)航路規(guī)劃。

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

圖2 三維航路圖

圖3 等高線圖

4 結(jié)束語(yǔ)

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