基于粒子群算法的無人機滅火路徑規(guī)劃仿真

李銳君,董素鴿

(1.鄭州西亞斯學(xué)院電信與智能制造學(xué)院,河南 鄭州 451150 2. 信息工程大學(xué)信息與系統(tǒng)工程學(xué)院,河南 鄭州 450000)

1 引言

隨著科技的發(fā)展無人機已經(jīng)逐步從單純的飛行設(shè)備轉(zhuǎn)變?yōu)槎喙δ艿闹悄芟到y(tǒng),被大量應(yīng)用在民用以及軍事等領(lǐng)域內(nèi)[1]。在民用領(lǐng)域內(nèi),無人機被大量運用在關(guān)鍵區(qū)域火災(zāi)滅火、建筑施工路線勘察及農(nóng)情監(jiān)測等方面,而在軍事領(lǐng)域內(nèi),無人機可被作為軍事武器應(yīng)用于戰(zhàn)場上[2]。其中滅火無人機的應(yīng)用與相關(guān)問題的研究已成為當(dāng)下諸多學(xué)者的重點研究方向。無人機滅火方式可解決傳統(tǒng)人工滅火人員傷亡問題,大幅度降低火災(zāi)環(huán)境中滅火人員的危險等級[3,4]。而對于無人機滅火方式而言,保障無人機在實際滅火環(huán)境中無碰撞、高效率完成滅火行為的關(guān)鍵即為最優(yōu)滅火路徑的規(guī)劃問題,需通過研究恰當(dāng)?shù)臒o人機滅火路徑仿真規(guī)劃方法,獲得長度最短、耗時最低、水平轉(zhuǎn)角最平緩且可完全避開障礙與危險區(qū)域的路徑,為無人機滅火方式提供保障[5]。

粒子群算法屬于一類迭代優(yōu)化算法,它通過模擬鳥群覓食過程,將每只鳥看成一個粒子,即優(yōu)化中的可能解之一,鳥群看成粒子群,通過運用相關(guān)適應(yīng)度函數(shù)實現(xiàn)粒子群的迭代進化,尋得最優(yōu)解[6,7]。該算法的優(yōu)點是早期搜尋效率高,缺點是搜尋時易錯失最優(yōu)解,且易步入局部最優(yōu)[8]。細菌覓食算法屬于一類群智能優(yōu)化算法,是通過對腸道中大腸桿菌覓食過程實施模擬獲得的,其關(guān)鍵組成部分為趨向算子、復(fù)制算子及遷徙算子[9],該算法具有可并行搜索、群智能性、尋優(yōu)范圍廣等優(yōu)點,可避免所優(yōu)化算法陷入局部最優(yōu),提升尋得最優(yōu)解的能力[10]。

綜合以上分析,本文研究一種基于粒子群算法的無人機滅火路徑規(guī)劃仿真方法,實現(xiàn)無人機滅火路徑的仿真規(guī)劃,獲得最優(yōu)最短路徑,為無人機高效滅火提供科學(xué)依據(jù)。

2 無人機滅火路徑規(guī)劃仿真方法研究

為了實現(xiàn)無人機滅火路徑規(guī)劃仿真,需先以現(xiàn)實無人機滅火環(huán)境為依據(jù)構(gòu)建無人機滅火路徑規(guī)劃仿真環(huán)境模型;再結(jié)合無人機滅火路徑長度代價、無人機航跡高程代價、無人機航跡水平轉(zhuǎn)角代價及滅火環(huán)境中障礙危險代價建立適應(yīng)度函數(shù);通過細菌覓食算法對基礎(chǔ)粒子群算法實施改進,獲得改進粒子群算法(PSO-BFA),定位檢測出滅火環(huán)境中的火點位置,并以此類火點位置作為規(guī)劃過程中的終極目標(biāo)點,通過改進粒子群算法運用所構(gòu)建的仿真環(huán)境模型與適應(yīng)度函數(shù)實現(xiàn)種群迭代進化尋優(yōu),獲得最優(yōu)無人機滅火路徑,完成無人機滅火路徑規(guī)劃仿真。

2.1 無人機滅火路徑規(guī)劃仿真環(huán)境建模

依據(jù)現(xiàn)實滅火環(huán)境構(gòu)建無人機滅火路徑規(guī)劃仿真環(huán)境模型,主要包含水平區(qū)域模型、障礙區(qū)域模型、危險區(qū)域模型,具體如下:

1)水平區(qū)域模型構(gòu)建:依據(jù)滅火環(huán)境地形的起伏狀態(tài)選用函數(shù)模擬法構(gòu)建水平區(qū)域模型,所構(gòu)建的水平區(qū)域模型可表示成

z1(x,y)=dsin(x)+sin(y+c)+ucos(y)+

(1)

式中,水平區(qū)域高程通過z1表示;水平區(qū)域的點坐標(biāo)通過(x,y)表示;數(shù)字地圖內(nèi)該區(qū)域的地表特征通過b、c、d、u、v系數(shù)表示。

2)障礙區(qū)域模型構(gòu)建:障礙區(qū)域模型重點針對滅火環(huán)境中的山體與樹木等障礙建模,所遵循的依據(jù)為已監(jiān)測所得的實際數(shù)據(jù)信息[11]。所構(gòu)建的障礙區(qū)域模型表示為

(2)

式中,樹木與山體的總數(shù)目通過m表示;第i棵樹木或第i座山體的控制坡度、高度分別通過li與hi表示;該樹木或山體的中心水平面投影點坐標(biāo)通過ei與fi表示;該區(qū)域高程通過z2表示。

3)危險區(qū)域模型構(gòu)建:該區(qū)域模型重點針對滅火環(huán)境中的雷達危險體區(qū)域?qū)嵤┓抡娼?選取半球體近似模擬該區(qū)域,則所構(gòu)建的危險區(qū)域模型可表示成

(3)

式中,危險區(qū)域的高程通過z3表示;第j個危險體的中心水平面投影點坐標(biāo)通過ej與fj表示;半球體的探測半徑通過r表示。

通過融合以上所構(gòu)建的水平區(qū)域模型、障礙區(qū)域模型及危險區(qū)域模型,獲得無人機滅火路徑規(guī)劃的整體仿真環(huán)境模型,可表示成

z(x,y)=max[z1(x,y),z2(x,y),z3(x,y)]

(4)

2.2 無人機滅火路徑規(guī)劃適應(yīng)度函數(shù)創(chuàng)建

適應(yīng)度函數(shù)是粒子群算法規(guī)劃無人機滅火路徑過程中種群迭代進化的根據(jù),對粒子群算法的執(zhí)行質(zhì)量與效率有著直接的影響作用[12],另外,通過適應(yīng)度函數(shù)能夠?qū)αＷ尤核惴ㄒ?guī)劃后所獲得的無人機滅火路徑的優(yōu)劣實施評價。因此,適應(yīng)度函數(shù)的創(chuàng)建是粒子群算法規(guī)劃無人機滅火路徑的基礎(chǔ)與關(guān)鍵。在此結(jié)合了無人機航跡高程代價、無人機航跡水平轉(zhuǎn)角代價、障礙危險代價與路徑長度代價共同創(chuàng)建適應(yīng)度函數(shù)。

設(shè)一共存在A條路徑,各條路徑均具備m個點,無人機航行環(huán)境內(nèi)所具備的障礙與危險區(qū)域總計k個。各代價如下:

1)路徑長度代價:作為評價無人機滅火路徑好壞的關(guān)鍵指標(biāo)之一的路徑長度,其值越低代表無人機由此路徑航行的耗能與用時越少。路徑長度代價可表示成

(5)

式中,路徑內(nèi)第i個節(jié)點坐標(biāo)通過(xi,yi,zi)表示;第n條路徑內(nèi)全部鄰近節(jié)點之間的間距之和通過Dn表示,其中,n=1,2,…,N。

(6)

(7)

式中,第g個危險或障礙區(qū)域半徑通過rg表示。

3)無人機航跡高程代價:無人機航跡高程即無人機平穩(wěn)航行時的高度,由于無人機平穩(wěn)航行高度能夠有效降低無人機操控系統(tǒng)的負擔(dān),以此節(jié)約航行燃料,減少耗能,故該指標(biāo)也是評價無人機滅火路徑好壞的重要指標(biāo)。無人機航跡高程代價可表示為

(8)

式中,路徑節(jié)點i的高度通過hi表示;路徑節(jié)點i下一個鄰近節(jié)點的高度通過hi+1表示。

4)無人機航跡水平轉(zhuǎn)角代價:除此之外,無人機航跡水平轉(zhuǎn)角也是評價路徑好壞的指標(biāo)之一。無人機航跡水平轉(zhuǎn)角代價可表示為

(9)

式中,無人機航行中的現(xiàn)實水平轉(zhuǎn)角通過β表示;預(yù)先設(shè)定的無人機最高水平轉(zhuǎn)角通過βmax表示。通過三角函數(shù)與向量可得出無人機的現(xiàn)實水平轉(zhuǎn)角β,將第n條路徑第j個路段的水平投影表示為

pn,j=(xn,j-xn,j-1,xn,m+j-xn,m+j+1)

(10)

則其當(dāng)前轉(zhuǎn)角運算式為

(11)

式中,矢量pn,j的長度通過‖pn,j‖表示。

將以上所得的路徑長度代價、障礙危險代價、無人機航跡高程代價及無人機航跡水平轉(zhuǎn)角代價相結(jié)合后,能夠得到路徑的適應(yīng)度函數(shù),可表示成

f=Dn×w1+δn×w2+Hn×w3+θn×w4

(12)

式中,w1～w4為對各代價間關(guān)系實施靈活配置的權(quán)重系數(shù),四個權(quán)重系數(shù)的總和為1。

2.3 基于細菌覓食改進粒子群算法的無人機滅火路徑規(guī)劃

在構(gòu)建的無人機滅火路徑規(guī)劃仿真環(huán)境模型基礎(chǔ)上,通過細菌覓食改進粒子群算法(PSO-BFA),獲得改進粒子群算法,對滅火環(huán)境中的火點位置實施定位檢測,以所檢測到的火點位置作為終極目標(biāo)點,通過改進粒子群算法運用所創(chuàng)建的適應(yīng)度函數(shù)當(dāng)作種群迭代進化的根據(jù)實現(xiàn)迭代尋優(yōu),獲得最優(yōu)無人機滅火路徑。

2.3.1 基于細菌覓食算法的改進粒子群算法

基礎(chǔ)粒子群算法是通過模擬鳥覓食過程而得的,將粒子種群內(nèi)各個粒子看成一只鳥,也就是一個可行路徑,各個粒子采取追蹤全局與個體兩種極值的方式,實現(xiàn)迭代更新,直至搜尋到最優(yōu)解,即最優(yōu)路徑為止[13]。粒子種群內(nèi)各個粒子速度與位置的更新方程式為

(13)

式中,慣性權(quán)重通過ω表示;第i代粒子的速度與位置分別通過Vi與Xi表示;其下一代粒子的速度與位置則分別通過Vi+1與Xi+1表示;s1與s2均為隨機數(shù);全局極值與個體極值分別通過X與X1表示;q1與q2均為學(xué)習(xí)因子。

基礎(chǔ)粒子群算法具有早期搜尋效率高的優(yōu)點,但因粒子速度太快導(dǎo)致此算法在搜尋過程中易錯失最優(yōu)解,同時,此算法中全部粒子的搜尋方向相同,導(dǎo)致種群過于單一,令此算法最終易陷入局部最優(yōu)且難以由局部最優(yōu)解中跳出來[14]。為解決基礎(chǔ)粒子群算法的以上問題,在此將細菌覓食算法融入到基礎(chǔ)粒子群算法內(nèi),獲得改進粒子群算法(PSO-BFA),通過該算法實現(xiàn)對無人機滅火路徑的。

細菌覓食算法主要包括趨向算子、復(fù)制算子及遷徙算子三個操作步驟[15],其表達公式為

(14)

式中,0～1之間隨機矩陣通過Rand表示;第i個細菌的第m個位置通過Xi,m表示;其第m次趨向方向通過Wi,m表示,其中,m=1,2,…,M1×M2×M3,復(fù)制、遷徙及趨向的最高循環(huán)次數(shù)依次通過M1、M2、M3表示;單位方向的向量通過Wd表示;隨機向量通過Δi,m表示;細菌走動時的步長通過Lm表示。此算法中的各個細菌可看作是路徑規(guī)劃中的各條路徑。通過細菌覓食算法的趨向算子可將基礎(chǔ)粒子群算法的局部搜尋性能有效提升,并解決基礎(chǔ)粒子群算法因粒子速度過快導(dǎo)致搜尋時錯失最優(yōu)解的問題;而細菌覓食算法的遷徙算子能夠擴大尋優(yōu)范圍,防止粒子群算法步入局部最優(yōu)。

2.3.2 滅火環(huán)境中火點定位檢測

運用實時采集的火災(zāi)現(xiàn)場圖片將火災(zāi)環(huán)境中火點相對無人機的位置運算得出,運算時所用到的火點定位圖如圖1所示。

圖1 火點定位圖

圖中的紅色標(biāo)記為火點,設(shè)火點的中心點O位于地面,C點為由O點經(jīng)過并與x軸平行的OC線同y軸的交點。無人機深度相機中深度信息已知FO、FC的長度,其中FC與OC垂直,依據(jù)勾股定理能夠得出OC的長度為

(15)

已知無人機的高度h,則O點至I點的間距為:

(16)

結(jié)合式(15)與式(16),能夠?qū)點至O點的間距獲得,可表示為:

(17)

綜合可得出火災(zāi)環(huán)境中火點的位置坐標(biāo)為(JO,CO,0),設(shè)無人機的位置坐標(biāo)為(x,y,z),那么火點相對無人機的相對位置坐標(biāo)則為(JO+x,CO+y,0+z)。

2.3.3 基于改進粒子群算法的無人機滅火路徑規(guī)劃過程

運用改進粒子群算法在所構(gòu)建的無人機滅火路徑規(guī)劃仿真環(huán)境中,依據(jù)所創(chuàng)建的適應(yīng)度函數(shù)實施迭代尋優(yōu),得到最優(yōu)無人機滅火路徑,實現(xiàn)無人滅火路徑規(guī)劃仿真。基于改進粒子群算法的無人機滅火路徑規(guī)劃過程為:

1)對所構(gòu)建的無人機滅火路徑規(guī)劃仿真環(huán)境實施初始化,將無人機滅火路徑規(guī)劃空間的邊界確準(zhǔn),以R=(xmax-xmin,ymax-ymin,zmax-zmin)表示,并提取出原始起點,以B(x0,y0,z0)表示,以定位檢測所得火點位置(JO+x,CO+y,0+z)作為終極目標(biāo)點。

2)以數(shù)條路徑構(gòu)成大小為Psize的粒子種群,每條路徑為一個粒子,其大小為psize,設(shè)置粒子的最高速度與最高迭代次數(shù)分別為Vmax與Gmax,其中最高速度等于0.1R,粒子的初始化速度可表示成

(18)

(19)

式中,s表示隨機數(shù),其取值區(qū)間為(0,1);第i個粒

5)對算子是否陷入局部最優(yōu)實施判別,若陷入局部最優(yōu),將遷徙算子融入對部分適應(yīng)度不好的粒子實施遷徙操作;若未陷入局部最優(yōu),即可繼續(xù)接下來的過程。

6)對整體規(guī)劃過程是否已到達最高迭代次數(shù),或者已達到終止條件實施判別,若未達到,即可向第(4)步返回,并令λ=λ+1;若已達到即可將所得最優(yōu)規(guī)劃結(jié)果輸出,獲得最優(yōu)無人機滅火路徑。

3 仿真結(jié)果分析

隨機選取某片戶外區(qū)域作為實驗滅火區(qū)域,并在其中分別設(shè)置6處模擬障礙、2處模擬危險體、3個規(guī)劃原始起點及3個模擬火點后,通過本文方法在等效地圖內(nèi)創(chuàng)建該實驗區(qū)域的無人機滅火路徑規(guī)劃仿真環(huán)境模型,在等效數(shù)字地圖下運用所創(chuàng)建的仿真環(huán)境模型完成實驗滅火區(qū)域中無人機滅火路徑規(guī)劃仿真,檢驗本文方法的應(yīng)用效果。其中,實驗滅火區(qū)域仿真環(huán)境模型中所設(shè)置的各個模擬障礙與危險體的關(guān)鍵參數(shù)、各個規(guī)劃原始起點的坐標(biāo)、經(jīng)本文方法定位所得各個模擬火點的坐標(biāo)以及本文方法中改進粒子群算法的設(shè)置參數(shù)詳見表1。

表1 實驗滅火區(qū)域仿真環(huán)境模型及本文方法關(guān)鍵參數(shù)

以3個規(guī)劃原始起點作為實驗滅火區(qū)域中無人機滅火路徑規(guī)劃的3處原始起點,3個模擬火點作為該區(qū)域無人機滅火路徑規(guī)劃的3處終極目標(biāo)點,通過本文方法在表1中參數(shù)的設(shè)置下,分別獲得實驗滅火區(qū)域仿真環(huán)境中3對起止點各自對應(yīng)的無人機最優(yōu)滅火路徑(A、B、C),如圖2所示。

圖2 本文方法規(guī)劃所得最優(yōu)無人機滅火路徑

由圖2可得出,本文方法能夠針對不同起點與目標(biāo)點(火點)實現(xiàn)無人機滅火路徑規(guī)劃,所得規(guī)劃路徑能夠有效避開全部模擬障礙與危險體,規(guī)劃效果理想。

為了更清晰地呈現(xiàn)出本文方法規(guī)劃所得最優(yōu)無人機滅火路徑的效果,現(xiàn)通過俯視圖的方式呈現(xiàn)出本文方法所得各條規(guī)劃路徑,如圖3所示。

通過圖3能夠看出,本文方法規(guī)劃所得各條路徑的長度均較短,且各條路徑均能夠與各個障礙物、危險體保持足夠的安全間距,無人機依據(jù)所規(guī)劃的各條路徑航行時,航跡水平轉(zhuǎn)角均較為平滑,由此可見,本文方法所得各條規(guī)劃路徑均較優(yōu),能夠滿足無人機滅火需求,規(guī)劃結(jié)果十分可靠。

將以上仿真重復(fù)50次,統(tǒng)計各條路徑規(guī)劃過程中的收斂迭代次數(shù)平均值、平均收斂用時、路徑長度平均值,以及無人機由各條規(guī)劃所得路徑航行用時平均值,依據(jù)所得統(tǒng)計結(jié)果分析本文方法的綜合性能。統(tǒng)計結(jié)果如表2所示。

表2 本文方法仿真中關(guān)鍵性能指標(biāo)統(tǒng)計結(jié)果

分析表2能夠得知,本文方法在規(guī)劃各條無人機滅火路徑的仿真中,三條規(guī)劃路徑的總體平均收斂迭代次數(shù)為123次,總體平均收斂用時為4.49s,原因是本文方法在規(guī)劃過程中將趨向與遷徙算子融入算法中,雖令運算中的迭代次數(shù)稍有增長,但整體收斂用時卻較低,提升了整個規(guī)劃過程的收斂速度;另外,本文方法規(guī)劃所得各條無人機滅火路徑長度較短,可降低無人機滅火航行用時。綜合以上結(jié)果可知,本文方法的綜合規(guī)劃性能較好,能夠快速獲得最短最優(yōu)滅火路徑,為無人機實現(xiàn)快速無碰撞滅火提供保障。

4 結(jié)論

本文針對一種基于粒子群算法的無人機滅火路徑規(guī)劃仿真方法展開研究,創(chuàng)建無人機滅火路徑規(guī)劃仿真環(huán)境模型與適應(yīng)度函數(shù),將細菌覓食算法內(nèi)的趨向算子與遷徙算子融入基礎(chǔ)粒子群算法內(nèi),得到改進粒子群算法,通過定位檢測出滅火環(huán)境中火點位置,運用改進粒子群算法結(jié)合所創(chuàng)建的仿真環(huán)境模型與適應(yīng)度函數(shù),以定位所得火點位置為滅火路徑規(guī)劃中的終極目標(biāo)點,對由數(shù)條路徑構(gòu)成的粒子種群實施迭代更新尋優(yōu),得出最優(yōu)無人機滅火路徑,實驗仿真結(jié)果表明,本文方法能夠針對所仿真的滅火環(huán)境實現(xiàn)無人機滅火路徑規(guī)劃,且所規(guī)劃的滅火路徑能夠避開全部模擬危險體與障礙物,路徑的長度短且水平轉(zhuǎn)角平滑度高,可有效降低無人機航行用時,整體規(guī)劃過程中可快速收斂,規(guī)劃結(jié)果理想可靠。