陳明強(qiáng)，李奇峰，馮樹(shù)娟，徐開(kāi)俊

(中國(guó)民用航空飛行學(xué)院 飛行技術(shù)學(xué)院，四川 廣漢 618307)

0 引言

隨著航空技術(shù)與智能技術(shù)的不斷進(jìn)步，無(wú)人機(jī)在各個(gè)領(lǐng)域都有著良好的應(yīng)用前景。無(wú)人機(jī)航跡規(guī)劃是實(shí)現(xiàn)無(wú)人機(jī)自主飛行的關(guān)鍵一步，得到了世界的廣泛關(guān)注和研究，目前仍是研究熱點(diǎn)之一。在考慮各種環(huán)境威脅和自身性能下，如何在當(dāng)前環(huán)境中規(guī)劃出一條最佳的飛行路徑，是一項(xiàng)非常重要并復(fù)雜的任務(wù)[1-2]。

無(wú)人機(jī)航跡規(guī)劃算法可以大致分為2類:傳統(tǒng)規(guī)劃算法和智能規(guī)劃算法。傳統(tǒng)規(guī)劃算法包括A*算法[3]、快速擴(kuò)展隨機(jī)數(shù)算法[4]、人工勢(shì)場(chǎng)算法[5]和概率圖算法[6]等。智能規(guī)劃算法包括遺傳算法[7]、粒子群(Particle Swarm Optimization，PSO)算法、蟻群算法[8]、動(dòng)態(tài)窗口算法[9]和灰狼優(yōu)化算法[10]等。PSO算法[11]是一種仿生智能算法，基本原理是利用群體與個(gè)體之間的協(xié)作和信息共享，得到最優(yōu)解，具有搜索速度快和收斂速度快的特點(diǎn)，但是具有容易產(chǎn)生早熟和陷入局部最優(yōu)值的缺點(diǎn)。

劉科等[12]利用Dijkstra算法粗略求得最短路徑后使用PSO算法和最小二乘法擬合出最優(yōu)路徑。該算法雖然規(guī)劃出了最優(yōu)路徑，但是只能適用于威脅和空間較小的環(huán)境。Zeng等[13]提出了一種基于非齊次馬爾可夫鏈和差分進(jìn)化的PSO優(yōu)化算法，用于智能機(jī)器人在環(huán)境中遇到障礙物時(shí)的路徑規(guī)劃。通過(guò)利用非齊次馬爾可夫鏈將PSO速度更新方程從一種模式跳躍到另外一種模式，加快了收斂的速度，同時(shí)差分進(jìn)化增強(qiáng)了粒子全局搜索的能力，但是計(jì)算非常復(fù)雜且規(guī)劃路徑不夠平滑。羅陽(yáng)陽(yáng)等[14]提出了一種使用突變算子更新粒子位置的方法。在PSO算法迭代的過(guò)程中，使用突變算子使得算法能快速收斂并擺脫局部最優(yōu)值。朱佳瑩等[15]提出了PSO與蟻群算法相結(jié)合的路徑規(guī)劃算法，利用PSO算法優(yōu)化蟻群算法初始信息素，再使用改進(jìn)后的蟻群算法進(jìn)行全局路徑規(guī)劃。2種算法結(jié)合后全局搜索能力得到了較大提升，并且迭代次數(shù)更少，但是算法拐點(diǎn)較多，導(dǎo)致規(guī)劃路徑多為折線，不利于運(yùn)行在實(shí)際環(huán)境中。

本文針對(duì)PSO算法的缺點(diǎn)，提出了一種將PSO算法搜索空間由原始的笛卡爾坐標(biāo)系改為球坐標(biāo)系，使得PSO算法能直接與無(wú)人機(jī)自身性能相關(guān)聯(lián)。同時(shí)引入天牛須(Beetle Antennae Search，BAS)算法，克服傳統(tǒng)PSO算法易陷入早熟、收斂速度慢的特點(diǎn)。

1 目標(biāo)函數(shù)

對(duì)于無(wú)人機(jī)航跡規(guī)劃問(wèn)題，目標(biāo)函數(shù)是用來(lái)評(píng)估規(guī)劃航跡的質(zhì)量，多是由一系列的約束條件和優(yōu)化條件組成，目標(biāo)函數(shù)值越小時(shí)，得到的航跡質(zhì)量越好。為了確定目標(biāo)函數(shù)，必須要考慮所有可能影響規(guī)劃航跡質(zhì)量的因素，例如：航跡距離、飛行高度、障礙物限制和航跡平滑度等[16]。假設(shè)航跡是由n個(gè)航跡點(diǎn)組成，(xi,yi,zi)表示第i個(gè)航跡點(diǎn)的位置。

1.1 航跡距離

航跡長(zhǎng)度是判斷規(guī)劃航跡質(zhì)量的重要指標(biāo)，考慮無(wú)人機(jī)的續(xù)航能力，規(guī)劃航跡越短越有利于無(wú)人機(jī)的實(shí)際飛行，因此航跡成本函數(shù)為：

(1)

1.2 飛行高度

無(wú)人機(jī)飛行過(guò)程中受自身性能的影響和任務(wù)的需要，一般飛行高度限制在最低飛行高度和最高飛行高度之間，無(wú)人機(jī)航跡飛行高度成本函數(shù)定義為：

(2)

1.3 障礙物限制

無(wú)人機(jī)飛行時(shí)需要距離障礙物一定的距離，假設(shè)空間中存在圓柱體障礙物，障礙物數(shù)量為T，無(wú)人機(jī)距障礙物距離為d，障礙物半徑為R，無(wú)人機(jī)尺寸為S，為了提升飛行時(shí)的安全，設(shè)定碰撞危險(xiǎn)區(qū)距離為D，障礙物模型如圖1所示。

圖1 障礙物模型Fig.1 Obstacle model

障礙物成本函數(shù)可以定義為：

(3)

(4)

1.4 航跡平滑度

規(guī)劃航跡應(yīng)該盡量少的偏航和高度切換，需要保持航跡的平滑，li表示2個(gè)航跡點(diǎn)之間的距離，式(5)和式(6)分別表示偏轉(zhuǎn)角ai和俯仰角bi，航跡平滑度成本函數(shù)可以定義為式(7)：

(5)

(6)

(7)

1.5 總目標(biāo)函數(shù)

無(wú)人機(jī)在執(zhí)行任務(wù)的過(guò)程中需要考慮自身性能限制與地形性質(zhì)，因此對(duì)無(wú)人機(jī)俯仰角、偏轉(zhuǎn)角和飛行高度進(jìn)行約束。以上約束條件參數(shù)均與成本函數(shù)參數(shù)有關(guān)，因此將飛行高度約束加入式(2)中，偏轉(zhuǎn)角和俯仰角約束在SPSO算法中對(duì)粒子更新時(shí)已經(jīng)做出了約束，所以無(wú)需對(duì)其設(shè)置額外的約束條件。

根據(jù)以上成本函數(shù)，可以構(gòu)建無(wú)人機(jī)規(guī)劃航跡的目標(biāo)函數(shù)，由于無(wú)人機(jī)執(zhí)行任務(wù)種類較多，并且每種任務(wù)所要求的航跡均不相同，所以定義wi，i=(1,2,3,4)分別為每種成本函數(shù)的系數(shù)，wi之間的關(guān)系如式(8)所示，根據(jù)任務(wù)的需求可以動(dòng)態(tài)地調(diào)整權(quán)重，因此目標(biāo)函數(shù)如式(9)所示：

(8)

F=w1Fl+w2Fa+w3Fo+w4Fs。

(9)

本文目標(biāo)函數(shù)參數(shù)設(shè)定為：最高飛行高度hmax為300 m；最低飛行高度hmin為20 m；無(wú)人機(jī)尺寸S為2 m；危險(xiǎn)區(qū)距離D為20 m；w1為0.4；w2，w3和w4均為0.2。

2 改進(jìn)PSO算法設(shè)計(jì)

2.1 SPSO算法

PSO算法是由Kennedy和Russell提出，是基于鳥(niǎo)群和魚(yú)群聚集行為的啟發(fā)式優(yōu)化算法。PSO算法具有認(rèn)知和社會(huì)一致性，根據(jù)這2個(gè)特性，可以使得PSO中的粒子根據(jù)自己的經(jīng)驗(yàn)和種群的經(jīng)驗(yàn)自行搜索求解，從而擺脫了原始的進(jìn)化算子。與其他的啟發(fā)式算法相比，PSO算法對(duì)初始條件和目標(biāo)函數(shù)的變化并不敏感，能夠在適應(yīng)多種環(huán)境的同時(shí)使用少量的參數(shù)，在較短的時(shí)間內(nèi)獲得具有收斂的全局解。

為了滿足無(wú)人機(jī)飛行的實(shí)際條件，在規(guī)劃無(wú)人機(jī)航跡的過(guò)程中應(yīng)當(dāng)考慮無(wú)人機(jī)的性能參數(shù)。在傳統(tǒng)的PSO坐標(biāo)下，通常需要根據(jù)無(wú)人機(jī)最大偏轉(zhuǎn)角和俯仰角在目標(biāo)函數(shù)設(shè)置約束條件。而SPSO將粒子的搜索空間由笛卡爾坐標(biāo)系轉(zhuǎn)換到球坐標(biāo)系，在球坐標(biāo)系(ρ,θ,φ)下，ρ表示航跡段的距離，θ表示俯仰角，φ表示偏轉(zhuǎn)角，PSO的搜索空間可以與無(wú)人機(jī)偏轉(zhuǎn)角和俯仰角之間產(chǎn)生相互關(guān)系，不僅增加了規(guī)劃航跡的安全性也對(duì)無(wú)人機(jī)偏轉(zhuǎn)角和俯仰角進(jìn)行了約束。

在SPSO下，粒子i對(duì)應(yīng)D維向量的一條航跡，每個(gè)向量代表了從一個(gè)航跡點(diǎn)到另一個(gè)航跡點(diǎn)的移動(dòng)，粒子位置Ωi表示為Ωi=(Ωi1,Ωi2,…,ΩiD)，其中Ωij表示為(ρij,θij,φij)，速度ΔΩi可以表示為ΔΩi=(ΔΩi1,ΔΩi2,…,ΔΩiD),其中ΔΩij表示為(Δρij,Δθij,Δφij)。

SPSO算法獲取到粒子在球坐標(biāo)下的坐標(biāo)點(diǎn)后，需要根據(jù)目標(biāo)函數(shù)來(lái)判定粒子質(zhì)量，獲得粒子個(gè)體最優(yōu)位置Pb和全局最佳位置Gb。因此，需要將粒子位置Ωi映射到笛卡爾坐標(biāo)系下粒子位置Xi，Xi=(Xi1,Xi2,…,XiD),其中Xij表示為(xij,yij,zij)，粒子在笛卡爾坐標(biāo)系下的更新方式為：

(10)

(11)

(12)

SPSO迭代過(guò)程中位置和速度更新公式為：

(13)

(14)

式中，w為慣性權(quán)重；C1和C2分別表示個(gè)體學(xué)習(xí)因子和群體學(xué)習(xí)因子；r1和r2均為0～1的均勻隨機(jī)數(shù)。

2.2 BAS算法

BAS算法[17]是一種生物啟發(fā)式優(yōu)化算法，與PSO算法都是基于不斷更新迭代獲得最優(yōu)解，但BAS算法是基于個(gè)體求解而非群體。BAS算法的優(yōu)點(diǎn)在于算法復(fù)雜度低，只需要少量參數(shù)就能求解最優(yōu)解[18]。

BAS算法是根據(jù)天牛的覓食行為而建立，將食物位置定義為最優(yōu)解位置，食物的氣味在空間中每個(gè)位置的濃度不同，將氣味濃度定義為目標(biāo)函數(shù)，當(dāng)天牛的2根觸須獲取食物氣味濃度存在差別時(shí)，其會(huì)隨著氣味濃度高的一側(cè)移動(dòng)，直至目標(biāo)點(diǎn)，這樣就可以建立起數(shù)學(xué)模型。

對(duì)于多維優(yōu)化問(wèn)題，首先需要確定天牛2根觸須的坐標(biāo)和觸須之間的距離，其基本模型如圖2所示，x表示天牛位置，xl表示左須坐標(biāo)，xr表示右須坐標(biāo)，d表示兩須之間的距離。算法基本步驟如下：

圖2 天牛模型Fig.2 Beetle model

① 根據(jù)式(15)給出的歸一化隨機(jī)向量確定天牛個(gè)體的朝向：

(15)

式中，k代表待優(yōu)化問(wèn)題維數(shù)。

② 更新第t次迭代天牛左右須位置：

(16)

③ 獲取到的天牛左右須位置后，計(jì)算目標(biāo)函數(shù)值，分別用F(xl)和F(xr)表示左須和右須的目標(biāo)函數(shù)值，根據(jù)天牛兩須探測(cè)到的濃度差異決定下一步移動(dòng)方向。

④ 迭代更新天牛位置：

xt+1=xt+δtbsign(F(xr)-F(xl))，

(17)

式中，δt為第t次迭代時(shí)天牛向下一個(gè)方向移動(dòng)的步長(zhǎng)；sign為符號(hào)函數(shù)。

⑤ 更新步長(zhǎng)：

δt+1=ηδδt，

(18)

式中，ηδ表示步長(zhǎng)衰減系數(shù)。

⑥ 判斷是否可以終止迭代，如不滿足，則回到步驟③，直至滿足迭代終止條件，跳出迭代。

2.3 SPSO與BAS算法相結(jié)合

PSO算法著重于群體對(duì)單個(gè)粒子的影響，所以具有很強(qiáng)的全局尋優(yōu)能力，但是也很容易陷入局部最優(yōu)解，當(dāng)粒子均趨向于全局最優(yōu)解時(shí)，可能失去粒子的多樣性。而B(niǎo)AS算法是只考慮個(gè)體，不考慮群體的影響，因此本文將PSO算法與BAS算法相結(jié)合，提出一種基于BAS算法的SPSO優(yōu)化算法，在每一次迭代的過(guò)程中，利用BAS算法對(duì)環(huán)境空間進(jìn)行判斷，有利于跳出局部最優(yōu)解，使得規(guī)劃路徑更加合理。

改進(jìn)的算法將每個(gè)粒子也看作一個(gè)天牛，其整體步驟和PSO算法相似，在對(duì)粒子位置和速度進(jìn)行更新的過(guò)程中加入BAS算法，改進(jìn)后算法粒子的速度和位置更新公式為：

C3r3δtbsign(f(xr)-f(xl))，

(19)

(20)

改進(jìn)后的算法，根據(jù)PSO算法的速度影響因子和BAS算法步長(zhǎng)和觸須的思想得到新的位置，算法的具體流程為：

① 初始化PSO參數(shù)，設(shè)置粒子維度D,學(xué)習(xí)因子c1，c2和c3，慣性權(quán)重W，以及天牛須兩須距離d0。

② 隨機(jī)化粒子初始位置和速度，并且計(jì)算適應(yīng)度函數(shù)，使用初始化的位置作為個(gè)體最優(yōu)解Pb，得到全局最優(yōu)解Gb。

③ 按照式(16)計(jì)算天牛左右須位置，并且計(jì)算左右須位置的適應(yīng)度函數(shù)，利用式(19)和式(20)更新粒子位置和速度。

④ 計(jì)算更新后粒子的適應(yīng)度函數(shù)，更新粒子個(gè)體最優(yōu)值、全局最優(yōu)值和天牛須步長(zhǎng)。

⑤ 判斷是否滿足終止條件，如滿足，則輸出最優(yōu)值；否則，回到步驟③，繼續(xù)迭代。

3 仿真分析

3.1 實(shí)驗(yàn)環(huán)境設(shè)置

為了驗(yàn)證改進(jìn)算法的有效性，在Matlab環(huán)境下對(duì)無(wú)人機(jī)路徑規(guī)劃進(jìn)行仿真建模。設(shè)計(jì)了2種仿真環(huán)境：一種環(huán)境中只有圓柱形障礙物，對(duì)應(yīng)于地形較為平坦的城市環(huán)境；另一種環(huán)境是在第1種環(huán)境中加上了真實(shí)的地形數(shù)據(jù)，對(duì)應(yīng)于地形較復(fù)雜的山區(qū)[19]。真實(shí)地形數(shù)據(jù)根據(jù)數(shù)字高程地圖(Digital Elevation Model，DEM)獲得，本文DEM數(shù)據(jù)由ALOS PALSAR數(shù)據(jù)庫(kù)得到，根據(jù)DEM得到高程點(diǎn)，將其均勻地離散化在1 000×1 000的坐標(biāo)空間中。

DEM數(shù)據(jù)選擇31°04′56″N～31°11′37″N，103°50′58″E～103°57′47″E，離散在坐標(biāo)空間后用x軸表示東經(jīng)，x∈[0,1 000]，y軸表示北緯，y∈[0,1 000]，z軸表示高度，為每一個(gè)坐標(biāo)點(diǎn)的真實(shí)高度。在環(huán)境1中設(shè)置起點(diǎn)為(330,40,50)，終點(diǎn)為(780,800,200)。環(huán)境2中設(shè)置起點(diǎn)為(1,1,50)，終點(diǎn)為(800,900,200)。

3.2 算法參數(shù)設(shè)置

SPSO算法參數(shù)設(shè)置為：最大迭代次數(shù)為300，粒子維數(shù)為10，慣性權(quán)重為1，自我認(rèn)知和社會(huì)認(rèn)知均為1.5。BAS算法參數(shù)設(shè)置為：天牛兩須寬度為1，初始步長(zhǎng)為0.1，天牛須認(rèn)知為1.2，步長(zhǎng)衰減系數(shù)為0.95。

3.3 仿真分析

本文分別采用標(biāo)準(zhǔn)PSO，SPSO和天牛須球坐標(biāo)粒子群(BSPSO)三種算法對(duì)無(wú)人機(jī)航跡規(guī)劃進(jìn)行仿真驗(yàn)證，得到的仿真結(jié)果如表1和圖3～圖5所示。表1中所示數(shù)據(jù)是在環(huán)境1和環(huán)境2下分別運(yùn)行10次所得到的仿真結(jié)果，其中數(shù)據(jù)為求得的平均值。圖3是在仿真環(huán)境1中規(guī)劃的航跡圖，圖4是在仿真環(huán)境2中規(guī)劃的航跡圖，圖5是目標(biāo)函數(shù)變化曲線圖。

表1 3種算法在2種環(huán)境中的仿真結(jié)果對(duì)比Tab.1 Comparison of simulation results of three algorithms in two environments

圖3 仿真環(huán)境1規(guī)劃航跡Fig.3 The planned trajectory in simulation environment 1

圖4 仿真環(huán)境2規(guī)劃航跡Fig.4 The planned trajectory in simulation environment 2

圖5 目標(biāo)函數(shù)曲線變化Fig.5 Change of the objective function curve

環(huán)境1為不帶地形數(shù)據(jù)的簡(jiǎn)單環(huán)境，根據(jù)圖3和表1可知，BSPSO規(guī)劃的航跡長(zhǎng)度明顯低于PSO和SPSO，其航跡長(zhǎng)度相比PSO和SPSO縮短了11.43%和3.5%。航跡平滑度BSPSO相比PSO和SPSO下降了48.57%和11.36%。飛行高度和障礙物限制上，3種算法的差距均不大，在加權(quán)后對(duì)應(yīng)的總目標(biāo)函數(shù)值均可忽略不計(jì)。在障礙物限制上PSO優(yōu)于SPSO和BSPSO，這是由于BSPSO規(guī)劃出的最優(yōu)路線需要穿過(guò)障礙物，會(huì)進(jìn)入障礙物危險(xiǎn)區(qū)，而PSO規(guī)劃的航跡選擇繞過(guò)障礙物，增加了航跡長(zhǎng)度。結(jié)合所有因數(shù)，加權(quán)總目標(biāo)函數(shù)值BSPSO比PSO和SPSO分別降低了14.15%和3.5%，BSPSO規(guī)劃航跡為最優(yōu)航跡。

環(huán)境2為帶地形數(shù)據(jù)的復(fù)雜山區(qū)環(huán)境，根據(jù)圖4和表1可知，BSPSO規(guī)劃的航跡長(zhǎng)度明顯低于PSO和SPSO，其航跡長(zhǎng)度相比PSO和SPSO縮短了10.77%和1.59%。航跡平滑度BSPSO相比PSO和SPSO下降了28.15%和4.83%，這表明BSPSO算法規(guī)劃的航跡更加平滑，偏轉(zhuǎn)和俯仰的次數(shù)更少或者變化角度越少。由于山區(qū)地形復(fù)雜，無(wú)人機(jī)機(jī)動(dòng)次數(shù)越少，不僅有利于節(jié)約能耗也有利于飛行安全。在障礙物限制上PSO明顯優(yōu)于SPSO和BSPSO，還是因?yàn)锽SPSO在確保相對(duì)安全的情況下穿過(guò)障礙物，犧牲了部分障礙物限制，降低航跡長(zhǎng)度。結(jié)合所有因數(shù)，加權(quán)總目標(biāo)函數(shù)值BSPSO比PSO和SPSO分別降低了13.44%和2.81%。因此，BSPSO算法規(guī)劃航跡在復(fù)雜地形中可以與地形的變化保持一致，滿足了山區(qū)等復(fù)雜地形的航跡規(guī)劃要求并且規(guī)劃航跡最優(yōu)。

根據(jù)圖5可知，3種算法的總目標(biāo)函數(shù)隨著迭代次數(shù)的增加都在減小，但是PSO和SPSO算法目標(biāo)函數(shù)值均大于BSPSO算法目標(biāo)函數(shù)值，顯然PSO和SPSO算法規(guī)劃的航跡不是最優(yōu)航跡，均陷入了局部最優(yōu)值。而改進(jìn)后的算法具有跳出局部最優(yōu)值的能力，是由于PSO算法更新后，不是直接進(jìn)入下一輪的搜索，而是利用BAS算法的更新規(guī)則，使粒子不再盲目地按照當(dāng)前速度向發(fā)現(xiàn)的全局最優(yōu)點(diǎn)聚攏，從而增加了對(duì)全體極值的搜索，使得局部搜索能力得到增強(qiáng)。因此驗(yàn)證BAS算法能夠幫助PSO算法跳出局部最優(yōu)值，證明了改進(jìn)后算法的有效性。

本文通過(guò)空間復(fù)雜度和時(shí)間復(fù)雜度分析改進(jìn)后算法的復(fù)雜度。改進(jìn)后的算法通過(guò)BAS算法更新了粒子，其只是將原有粒子替換，并未占用新的運(yùn)算空間，因此空間復(fù)雜度并未增加。由3種算法在仿真環(huán)境2下多次運(yùn)行后得到迭代總耗時(shí)的平均值可知，SPSO耗時(shí)最短為165 s，PSO耗時(shí)最長(zhǎng)為186 s，這是由于SPSO能對(duì)無(wú)人機(jī)性能條件直接約束，減少了計(jì)算量，而B(niǎo)SPSO在SPSO的基礎(chǔ)上引入了BAS算法，增加了一定的計(jì)算量，總耗時(shí)為178 s，但仍比PSO算法少。

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

本文考慮了無(wú)人機(jī)飛行航跡長(zhǎng)度、飛行高度約束、障礙物約束和航跡平滑度約束，建立了無(wú)人機(jī)航跡規(guī)劃模型。通過(guò)提出了一種SPSO算法結(jié)合BAS算法對(duì)航跡規(guī)劃模型求解，將傳統(tǒng)PSO的搜索空間從笛卡爾坐標(biāo)系轉(zhuǎn)換到球坐標(biāo)系，利用球坐標(biāo)系直接與無(wú)人機(jī)飛行航向角和俯仰角產(chǎn)生約束，同時(shí)結(jié)合BAS算法有助于幫助PSO算法跳出局部最優(yōu)解，獲得最優(yōu)航跡。通過(guò)Matlab仿真將改進(jìn)算法與SPSO和傳統(tǒng)PSO算法進(jìn)行仿真測(cè)試，測(cè)試結(jié)果表明改進(jìn)后的算法具有更強(qiáng)的全局搜索能力，并且規(guī)劃出的航跡更短、更平滑，提高了無(wú)人機(jī)規(guī)劃航跡的質(zhì)量。