改進(jìn)蝙蝠算法的無人機(jī)路徑規(guī)劃

丁元明,侯孟珂

(1.遼寧省通信網(wǎng)絡(luò)與信息處理重點實驗室,遼寧 大連 116622; 2.大連大學(xué) 信息工程學(xué)院,遼寧 大連 116622)

0 引言

無人機(jī)的路徑規(guī)劃是無人機(jī)(unmanned aerial vehicle,UAV)根據(jù)飛行任務(wù)的要求,在綜合考慮各種因素和條件下,找到一條無人機(jī)從出發(fā)點到目標(biāo)點的最優(yōu)飛行軌跡[1]。目前國內(nèi)對無人機(jī)路徑規(guī)劃優(yōu)化算法設(shè)計進(jìn)行了大量的嘗試和突破,但仍存在求解精度和搜索時間難以平衡這一較大的局限性。未來UAV航跡規(guī)劃的發(fā)展趨勢應(yīng)該兼顧計算快、精度高、容錯率高等特點。

規(guī)劃決策可以將無人機(jī)路徑規(guī)劃算法分為傳統(tǒng)經(jīng)典算法和現(xiàn)代群智能算法等2類[2]?，F(xiàn)代群智能算法成為當(dāng)前UAV路徑規(guī)劃優(yōu)化的主要手段[3]。結(jié)合約束條件、環(huán)境模型、目標(biāo)函數(shù),再利用群智能算法以及迭代技術(shù)求解最優(yōu)無人機(jī)路徑。群智能技術(shù)已被證實在解決具有挑戰(zhàn)性的優(yōu)化問題方面是非常有效的[4]。最近,受不同動物群體行為的啟發(fā),一些基于群智能的算法被開發(fā)并在文獻(xiàn)中提出,如人工蜂群(artificial bee colony algorithm,ABC)[5]、布谷鳥搜索(cuckoo search,CS)[6]、螢火蟲算法(firefly algorithm,FA)[7]、粒子群算法(particle swarm optimization,PSO)、蝙蝠算法(firefly algorithm,BA)等。這些群智能算法正在不斷地在無人機(jī)路徑規(guī)劃中得到應(yīng)用。PSO在無人機(jī)路徑規(guī)劃中因搜索效率高而得到廣泛應(yīng)用,但算法結(jié)構(gòu)缺陷,容易陷入局部極值問題[8-12]。文獻(xiàn)[8]提出了改變粒子群拓?fù)浣Y(jié)構(gòu)的改進(jìn)PSO結(jié)構(gòu)的算法。大量的粒子和更加復(fù)雜的拓?fù)浣Y(jié)構(gòu)也使得搜索時間的增加,求解速度變慢。文獻(xiàn)[9]提出了一種通過動態(tài)分治策略和A*算法改進(jìn)的PSO優(yōu)化算法。但算法復(fù)雜度變高,求解速度變慢,求解精度和速度難以平衡。文獻(xiàn)[10]為了提高PSO的收斂速度和尋優(yōu)能力,在粒子種群個體中引入了質(zhì)心的概念,并通過柯西變異運算對粒子進(jìn)行但算法加重了粒子種群個體的信息負(fù)載,算法冗雜。文獻(xiàn)[11]是將PSO和細(xì)菌覓食(bacterial foraging algorithm,BFO)算法進(jìn)行結(jié)合,再引入遷徙算子,會在粒子群陷入局部最優(yōu)時使得算法有跳出局部最優(yōu)的能力,增大了算法結(jié)構(gòu)復(fù)雜度,求解速度變慢。文獻(xiàn)[12]針對PSO解決維數(shù)遞增問題,提出了一種結(jié)合模糊C均值( fuzzy c-means algorithm,FCM)算法的改進(jìn)粒子群算法。但是改進(jìn)之后的算法依然容易陷入局部極值。PSO兼容性強(qiáng)、執(zhí)行效率高等優(yōu)點被廣泛應(yīng)用與UAV航跡規(guī)劃上,但傳統(tǒng)PSO存在容易過早收斂和容易陷入局部極值的問題。

2010年Yang教授提出了新的群智能啟發(fā)式算法,即蝙蝠算法(BA)[13]。BA在迭代搜尋最優(yōu)解過程中,在最優(yōu)解周圍通過隨機(jī)飛行產(chǎn)生局部最優(yōu)解,加強(qiáng)局部搜索,可以極大程度地避免算法陷入局部極值[14]。但由于BA算法在局部搜索上精細(xì)搜索,因此求解速度較慢,沒有平衡求解速度和求解精度。文獻(xiàn)[15]提出一種基于差分進(jìn)化的蝙蝠算法(DEBA)。通過應(yīng)用這些策略,蝙蝠種群的種群信息得到了充分的利用,探索能力得到了相對提高。經(jīng)過策略改進(jìn)之后的DEBA搜索無人機(jī)航跡規(guī)劃路徑的成功率有所降低,求解速度會有所變慢。文獻(xiàn)[16]提出了一種將差分進(jìn)化中的變異引入BA的混合元啟發(fā)式算法,并利用BA來挖掘種群信息,變異之后的算法仍然沒有提高求解速度。

1 飛行空間模型與目標(biāo)函數(shù)

為了測試算法的可靠性,健壯性,需要建立起模擬真實環(huán)境中的飛行空間模型。保證UAV安全、有效到達(dá)目標(biāo)點,需要實現(xiàn)在飛行長度約束、飛行高度約束、威脅區(qū)距離約束、山地環(huán)境約束條件下,無碰撞安全的到達(dá)目標(biāo)點位。將搭建飛行空間模型和目標(biāo)函數(shù)數(shù)學(xué)模型模型。

1.1 飛行空間模型

在全局空間模型中,山地地圖是空間建模的重要部分,采用文獻(xiàn)[17]中的山地建模方式,如圖1所示。

圖1 山地仿真地圖

由于在實際飛行過程中,環(huán)境是變化的,該山地模型中的山峰隨機(jī)產(chǎn)生,增加了環(huán)境隨機(jī)性,對路徑規(guī)劃算法的健壯性、普適性有更加嚴(yán)格的要求。其數(shù)學(xué)模型為:

(1)

式(1)中:(xi,yi)為第i個山峰的中心坐標(biāo);n為隨機(jī)生成山峰的個數(shù);hi為地形參數(shù),控制第i座山峰的高度;xsi、ysi分別為隨機(jī)生成的第i個山峰沿著x軸方向和y軸方向的山峰坡度。并對山體的表面進(jìn)行了平滑處理。

無人機(jī)在飛行過程中 需要依據(jù)山勢保持安全距離,即提升安全高度h。由于飛行燃油、飛機(jī)性能的限制,UAV不能無限制的升高,因此0

H(x,y)=z(x,y)+h

(2)

式(2)中,H(x,y)為飛行的安全高度,與山體有一定距離,實現(xiàn)安全飛行。并且h

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

UAV飛行路徑是指在約束條件下生成最優(yōu)飛行路線,其目標(biāo)是在合理的時間、成本內(nèi)找到UAV的最優(yōu)飛行路線。在飛行過程中,要考慮飛行成本。飛行成本主要分為3個部分:飛行路徑長度成本、威脅區(qū)成本和飛行高度成本?？偝杀竞瘮?shù)用W表示。最小成本函數(shù)Wmin可以表示為

Vmin=k1VL+k2VT+k3JH

(3)

式(3)中:VL為飛行路徑長度成本;VT為威脅區(qū)成本;VH為飛行高度成本;k1、k2、k3為比重權(quán)值,0

飛行路徑長度成本為

(4)

式(4)中:VL為飛行路徑長度成本,總飛行路徑的長度被分成n段路徑軌跡段;lij為軌跡段的長度所花費的成本。

威脅代價VT為

(5)

式(5)中:tk為威脅因素,也是威脅源和無人機(jī)節(jié)點之間威脅級別的度量;Nt為威脅源總數(shù)UAV坐標(biāo)為(x,y,z),威脅源中心的坐標(biāo)為(xk,yk,zk)。

飛行高度代價JH為

(6)

式(6)中:H為無人機(jī)飛行安全回路的高度,無人機(jī)的飛行高度不應(yīng)超過該高度;W0為無人機(jī)在一定高度下的能源成本;h為無人機(jī)的當(dāng)前高度。

2 改進(jìn)蝙蝠算法

2.1 經(jīng)典算法

2.1.1經(jīng)典粒子群算法

PSO是一種基于種群的智能隨機(jī)算法,PSO模擬種群行為在搜索空間中進(jìn)行全局搜索和局部開發(fā),并根據(jù)目標(biāo)函數(shù)得出當(dāng)前搜索周期內(nèi)的全局最優(yōu)gbest和個體最優(yōu)pbest;并根據(jù)前一代的gbest、pbest決定下一代粒子,最終得出最優(yōu)解。粒子的速度和位置更新公式為

(7)

式(7)中:k為粒子迭代次數(shù);w為慣性權(quán)重;c1為局部速度參數(shù);c2為全局速度參數(shù);r1和r2為0～1的隨機(jī)值的數(shù)。

2.1.2基本蝙蝠算法

蝙蝠算法(BA)的靈感來自于自然界中的蝙蝠,是通過模擬蝙蝠回聲定位抽象出的群智能算法。算法利用與飛行相關(guān)的變量代替蝙蝠避障飛行中的回聲頻率,并根據(jù)聲波頻率和當(dāng)前全局最優(yōu)解更新迭代下一代的速度與位置,最終得出最優(yōu)解。模擬蝙蝠回聲頻率的參數(shù)迭代公式為

fi=fmin+(fmax-fmin)×β

(8)

式(8)中:β為一隨機(jī)值,且滿足β∈[0,1];fi為蝙蝠發(fā)出的聲波頻率;fmax為頻率最大值;fmin為頻率最小值。可以看出fi會在fmax到fmin的范圍內(nèi)取值,隨機(jī)跳動,以保證了飛行搜索的隨機(jī)性。

1) 在隨機(jī)飛行搜索過程中,蝙蝠個體在時間節(jié)點t處的位置和速度的更新公式為

(9)

(10)

2) 在局部搜索階段,若蝙蝠在全局最優(yōu)解處時,蝙蝠個體根據(jù)響度A更新位置。

xnew=xold+εAk

(11)

3) 參數(shù)更新。接受新解,則代表著更進(jìn)一步靠近最優(yōu)解,則降低響度,并不斷增加回聲發(fā)射速率ri,其更新公式為

(12)

(13)

2.2 改進(jìn)蝙蝠算法

本文中改進(jìn)蝙蝠算法(PSOBA)保留了蝙蝠算法的全局搜索和局部搜索的搜索過程。但PSOBA算法允許在全局搜索過程加入種群個體最優(yōu)的因素。傳統(tǒng)BA算法回聲頻率fi是對全局最優(yōu)解的調(diào)整,其本質(zhì)還是趨向于對全局最優(yōu)解的搜索,降低了搜索的隨機(jī)性,容易使算法過早收斂,導(dǎo)致求解的精度有所損失。

1) 在全局隨機(jī)搜索過程中,PSOBA引入個體最優(yōu)的概念,本質(zhì)上擴(kuò)大了搜索的范圍,如圖2所示。當(dāng)種群進(jìn)行迭代時,x*以及回聲頻率f都是指向全局最優(yōu),從而導(dǎo)致原BA搜索前期收縮快。加入個體最優(yōu),分擔(dān)了快速靠近全局最優(yōu)的比重,增加了路徑搜索的廣度。但前一代的個體最優(yōu)搜索方向與搜索的目標(biāo)方向是相同的,對算法的搜索效率不會有太大的損失。

圖2 PSOBA搜素示意圖

在PSO中有明確的全局最優(yōu)和個體最優(yōu)的定義。由PSO中個體最優(yōu)的定義出發(fā)改進(jìn)BA,則PSOBA在隨機(jī)全局搜索的速度與位置迭代模型為

(14)

由式(14)可以得出,速度迭代加入了個體最優(yōu)的因素,使得種群搜索的方向不再單一指向全局最優(yōu),種群整體的搜索范圍覆蓋更廣。繼而在無人機(jī)飛行過程中獲取更多信息,從而進(jìn)行有效飛行。

2) 在局部搜索階段,PSOBA也引入了取值在0～1的均勻分布數(shù)R1,若R1>r1,則開始局部搜索,否則繼續(xù)全局隨機(jī)搜索。并且PSOBA算法對xnew的更新進(jìn)行重定義為

(15)

式(15)中:R2為0～1服從均勻分布的隨機(jī)數(shù);k為當(dāng)前迭代次數(shù);K為最大迭代數(shù);C(-1,0)是服從標(biāo)準(zhǔn)柯西分布的隨機(jī)數(shù),范圍為-1到0;N(0,1)是服從高斯分布的隨機(jī)數(shù),范圍為0到1。

2.3 最優(yōu)成功率策略動態(tài)調(diào)整慣性權(quán)值

OS-PSOBA算法雖然在全局隨機(jī)搜索過程中加入了個體最優(yōu)的變量,增加了路徑搜索的廣度和隨機(jī)性,但降低了上一代種群速度對當(dāng)前種群速度影響的比重,沒有動態(tài)繼承上一代種群的優(yōu)勢。若上一代種群搜索結(jié)果較好,但沒有繼承或延伸優(yōu)勢,就會延長搜索時間;降低了PSOBA的搜索精度。若上一代種群搜索結(jié)果很差,在搜索前期個體最優(yōu)和全局最優(yōu)的比重較小,則迭代種群也會繼承上一代種群的劣勢。因此,將慣性權(quán)值引入到PSOBA的速度迭代更新中,并利用最優(yōu)成功率策略對其自適應(yīng)動態(tài)調(diào)整,即OS-PSOBA。

首先在式(14)中引入慣性權(quán)值,有

(16)

式(16)中:w為加入的慣性權(quán)值。

進(jìn)而,將最優(yōu)成功率策略用于動態(tài)調(diào)節(jié)慣性權(quán)值w,這使得慣性權(quán)重與種群的最佳成功率相關(guān)。最優(yōu)成功率策略動態(tài)調(diào)節(jié)的自適應(yīng)慣性權(quán)重為

(17)

(18)

(19)

OS-PSOBA通過最優(yōu)成功率策略動態(tài)的調(diào)整w,使得種群按照k-1代的搜索結(jié)果進(jìn)行收斂搜索,或是靠近全局最優(yōu)和個體最優(yōu)進(jìn)行發(fā)散搜索,并在搜索過程中維持種群搜索的多樣性,整個搜索路徑的過程形成一個外部穩(wěn)定,核心自適應(yīng)動態(tài)調(diào)整的整體。

2.4 改進(jìn)蝙蝠算法的無人機(jī)路徑規(guī)劃流程

本文中提出 OS-PSOBA流程如圖3所示。

圖3 PSOBA算法流程圖

OS-PSOBA算法具體步驟描述如下。

步驟1初始化種群,包括種群個體規(guī)模N,最大迭代數(shù)k,局部加速因子c1和全局加速因子c2,回聲頻率f的最大值與最小值以及慣性權(quán)值w。

步驟2根據(jù)目標(biāo)函數(shù),即式(3)計算種群各個個體的適應(yīng)度。

步驟3按照個體適應(yīng)度進(jìn)行對比,找出個體最優(yōu)解pbest以及全局最優(yōu)解gbest。

步驟4判斷最優(yōu)解的隨機(jī)數(shù)R1是否大于脈沖發(fā)射頻率r。若R1>r,則將在最優(yōu)解附近隨機(jī)飛行;若R1

步驟6按照式(16)對種群個體的速度和位置進(jìn)行迭代更新。

步驟7如未達(dá)到結(jié)束條件(通常為足夠好的適應(yīng)值或達(dá)到一個預(yù)設(shè)的最大迭代數(shù)),則返回步驟2,直至達(dá)到結(jié)束條件,找出最優(yōu)路徑。

3 模擬實驗與討論

為了驗證OS-PSOBA的可行性和有效性,在i7-7700HQ CPU和8 G內(nèi)存的計算機(jī)上,利用Matlab進(jìn)行算法的仿真實驗。在二維、三維空間環(huán)境中,且在多種約束下對PSOBA算法進(jìn)行仿真實驗,最后設(shè)置PSO、BA、OS-PSOBA的對比仿真實驗。

3.1 二維空間下的仿真實驗

為了快速了解OS-PSOBA的性能,先對OS-PSOBA進(jìn)行簡單二維環(huán)境下的無碰撞、避障仿真實驗。實驗中設(shè)置威脅區(qū),并利用二維環(huán)境下的B樣條曲線進(jìn)行平滑處理,從而得到UAV飛行路徑軌跡。二維環(huán)境下的實驗參數(shù)如表1所示。

表1 PSOBA算法參數(shù)

二維空間仿真中,起始坐標(biāo)為(0,100),目標(biāo)點位(400,450)。設(shè)置7個威脅區(qū)域,其中心坐標(biāo)分別為(250,150)、(100,100)、(300,350)、(50,300)、(400,100)、(170,300)、(156,207)、威脅半徑為60、65、70、50、60、30、20。二維空間下仿真結(jié)果如圖4所示。

圖4 二維空間下UAV路徑規(guī)劃

圖4中平滑曲線為無人機(jī)路徑軌跡,圓圈為仿真模擬的威脅區(qū)域和障礙區(qū)域。軌跡與威脅區(qū)無交叉、重疊點,二維環(huán)境下可以完成避障,躲避威脅區(qū)的任務(wù)目標(biāo)。且在躲避后可以回歸原定規(guī)劃路線。得到路線盡可能短、平滑、無突變,符合路徑規(guī)劃要求。并且成功到達(dá)目標(biāo)點。

3.2 三維空間下的仿真實驗

3.2.1隨機(jī)變換三維空間下仿真實驗

構(gòu)建三維空間模型,利用隨機(jī)生成山峰,得到不同的三維山地空間。按照OS-PSOBA算法進(jìn)行山地環(huán)境下的UAV路徑規(guī)劃,起始坐標(biāo)為(1,1,1),終點為(100,100,80),仿真結(jié)果如圖5所示。圖5(a)、圖5(b)分別為同一山地環(huán)境下的正視圖和俯視圖,圖5(c)、圖5(d)也是同一山地環(huán)境下的正視圖和俯視圖,圖5(a)與圖5(c)是不同山地環(huán)境下的路徑規(guī)劃仿真結(jié)果。紅色曲線為無人機(jī)路徑規(guī)劃軌跡,軌跡平滑、無突變,符合無人機(jī)飛行轉(zhuǎn)角約束。并且從起始點成功到達(dá)目標(biāo)點位,沒有與山地交叉點位,無山體碰撞。飛行軌跡與山峰保持安全距離的同時,不會越過山峰,飛行成本更低,航跡更加隱蔽。

圖5 隨機(jī)三維環(huán)境下仿真

3.2.2復(fù)雜三維空間下避障仿真實驗

構(gòu)建更加復(fù)雜的三維空間,增加山地的崎嶇程度,并且在山地中增加威脅區(qū),威脅區(qū)在三維空間中建模為半球狀,威脅區(qū)在此表示為(x,y,z,r)。r代表威脅半徑。2個威脅區(qū)坐標(biāo)分別為(230,190,350,50)(207.1,333.3,389.9,30)、(410,330,349.2,50)。UAV飛行起始點坐標(biāo)為(15.15,30.3,349.9),目標(biāo)點坐標(biāo)為(449.5,459.6,422)。仿真結(jié)果如圖6所示,黑色曲線為UAV飛行軌跡,黑色半球狀為威脅輻射區(qū)。無人機(jī)可以在進(jìn)行山地?zé)o碰撞飛行的同時,避開威脅輻射區(qū),從起始點成功到達(dá)目標(biāo)點。

圖6 復(fù)雜三維環(huán)境下避障仿真實驗

3.3 三維環(huán)境下對比實驗

為了驗證OS-PSOBA的實際優(yōu)越性進(jìn)行對比仿真實驗。算法與BA和PSO算法進(jìn)行對比仿真實驗。構(gòu)建三維空間環(huán)境模型。為了保證對比實驗的公平性,只改變路徑規(guī)劃算法這一差異,設(shè)置迭代次數(shù)相同、種群數(shù)目相同、實驗仿真環(huán)境一致,具體參數(shù)如表2所示。

表2 對比實驗參數(shù)設(shè)置

對比實驗進(jìn)行5次,以避免偶然性對實驗結(jié)果產(chǎn)生影響。每次將對比實驗結(jié)果的路徑長短、路徑搜索時間、目標(biāo)函數(shù)收斂情況和任務(wù)成功率作為比較參數(shù)。對比實驗認(rèn)為路徑中無碰撞、無斷點,軌跡平滑,且從目標(biāo)點成功到達(dá)目標(biāo)點即為成功,運行結(jié)果如圖7所示。

圖7 三維空間下算法路徑對比圖

圖7(a)、圖7(b)、圖7(c)為5組對比試驗的一組仿真結(jié)果。通過對比實驗可以得出3種算法都可以得出平滑的UAV航跡,并且完成飛行任務(wù),3種算法都具有一定的魯棒性。但OS-PSOBA(黑色曲線)相比于PSO(紅色曲線)、BA(藍(lán)色曲線)可以看出,可以得到最短的UAV飛行軌跡。在相同UAV的條件下,OS-PSOBA可以更快地完成飛行任務(wù),故OS-PSOBA搜索精度得到提升。

圖8為3種算法在相同實驗環(huán)境下5組對比仿真實驗的UAV飛行路徑長度。由圖8可以明顯看出,OS-PSOBA所搜索到的路徑長度短于其余2種算法的路徑長度,則表明OS-PSOBA求解精度要高于BA和PSO。求解精度越高,才能在避開飛行障礙,符合飛行和環(huán)境約束條件下,飛行路徑更短。進(jìn)而路徑長度結(jié)果證明OS-PSOBA在UAV路徑搜索可以提高搜索精度。

圖8 算法路徑長度統(tǒng)計圖

表3中數(shù)據(jù)分別是3種算法在5組對比實驗中的路徑搜索時間?？梢悦黠@的得出,OS-PSOBA使用的時間要要少于PSO和BA的路徑搜索時間。僅由搜索時間可得,OS-PSOBA平均搜索時間比BA提升約9%,相對于PSO搜索時間提升了約18%。因此,利用OS-PSOBA進(jìn)行無人機(jī)路徑規(guī)劃可以提高搜索速率。

目標(biāo)函數(shù)值收斂曲線比較圖如圖9所示。OS-PSOBA算法得到的飛行成本目標(biāo)函數(shù)曲線一直處于PSO、BA算法函數(shù)曲線之下,證明OS-PSOBA算法可以降低飛行成本。由于飛行成本大多是由飛行距離和飛行高度決定,側(cè)面證明OS-PSOBA算法所搜尋路徑,距離短、精度高。

圖9 目標(biāo)函數(shù)值收斂曲線比較圖

4 結(jié)論

改進(jìn)之后的蝙蝠算法OS-PSOBA可以有效地解決無人機(jī)路徑規(guī)劃搜索中,搜索精度和搜索速度難以平衡的問題。結(jié)論如下:

1) 在全局隨機(jī)搜索中,加入個體最優(yōu)因素,避免了搜索過早收斂,增加了路徑搜索的廣度,提高了算法的精度。

2) 在局部搜索過程中,路徑搜索依靠于高斯分布和柯西分布,集中逼近最優(yōu)解,減少了搜索次數(shù),提高了搜索速度和搜索精度。

3) 在此基礎(chǔ)上,通過最優(yōu)成功率策略調(diào)節(jié),避免了不必要的迭代搜索,使得搜索速度和精度再次提升。實驗仿真證明,OP-PSOBA算法可以使無人機(jī)路徑規(guī)劃搜索精度和搜索速度雙提升。