基于改進粒子群算法的無人直升機航路規劃

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

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

0 引言

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

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

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

1 航路規劃模型

1.1 無人直升機航路約束條件

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

a.最小航段約束定義為無人直升機改變飛行姿態前必須保持穩態前飛的最小距離。在飛行過程中頻繁改變姿態會影響無人直升機的穩定性，嚴重時會導致墜機事故，所以應盡可能避免頻繁的姿態變換。則此約束為

li>lmin

(1)

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

b.最大轉彎角度約束定義為無人直升機在水平面內做圓周運動時的航向連續變化最大范圍。山谷大氣環境復雜，做大角度轉彎時，無人直升機極易受到山谷風影響，所以需要限制無人直升機的連續轉彎角度。則此約束為

ψi<Δψmax

(2)

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

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

(3)

Lmax為最大航程。

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

hi≥hmin

(4)

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

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

(5)

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

1.2 航路代價函數

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

(6)

在進行個體適應度計算時，必須先對航跡代價函數中的各部分代價值進行歸一化處理，避免各部分代價值數量級差異導致的計算誤差。

2 基于粒子群算法的無人直升機航路規劃

2.1 標準粒子群算法

標準PSO算法中，每個粒子僅有速度和位置2個屬性，粒子通過跟蹤個體最優解Pi和種群最優解Pg實現全局尋優，迭代中粒子的速度和位置更新公式為：

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之間的隨機數；ci和c2為加速常數，表示粒子受個體認知和社會認知的影響程度;w為慣性權重因子，當w較大時，算法具有較強的全局搜索能力，w較小則算法傾向于局部搜索。一般是將w初始化為wmax，并使其隨迭代次數的增加線性遞減至wmin。w的線性變化由下式確定：

(9)

tmax為最大迭代次數；t為當前迭代次數。

2.2 改進粒子群算法

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

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

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

(10)

fi為粒子個體適應度。

將子群D中的粒子隨機的兩兩雜交，產生同樣數目的子代粒子代替父代粒子。子代位置由父代粒子位置進行雜交產生。

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

(11)

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

子代速度由下式計算：

(12)

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

當連續幾代的全局最優適應值不變，認為種群陷入局部最優，此時隨機選取3個粒子，對粒子群進行變異操作，則有

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

(13)

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

2.3 算法流程

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

改進PSO算法的具體步驟如下：

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

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

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

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

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

f.判斷算法是否達到終止條件，是則轉步驟h，否則，進入步驟g。

g.判斷是否陷入局部最優，若是則根據式(13)進行變異，轉向步驟d，否則，轉向步驟c。

h.輸出航路種群中最優的航路作為航路規劃結果。

3 實驗結果及分析

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

圖1 適應度值變化曲線

由圖1可知，改進粒子群算法在第86代就已經收斂到最優，其收斂精度和收斂速度都優于標準粒子群算法，表明改進PSO算法能夠快速有效地為無人直升機進行任務航路規劃。

圖2和圖3分別是改進粒子群算法優化得到的無人直升機三維最優航路和二維等高線航路。可以看出，基于改進粒子群算法得出的最優航路成功地規避了所有障礙威脅，航路平滑且精度較高，滿足無人直升機性能約束，保證了飛行的安全性。

圖2 三維航路圖

圖3 等高線圖

4 結束語

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