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

李銳君,董素鴿

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

1 引言

隨著科技的發展無人機已經逐步從單純的飛行設備轉變為多功能的智能系統,被大量應用在民用以及軍事等領域內[1]。在民用領域內,無人機被大量運用在關鍵區域火災滅火、建筑施工路線勘察及農情監測等方面,而在軍事領域內,無人機可被作為軍事武器應用于戰場上[2]。其中滅火無人機的應用與相關問題的研究已成為當下諸多學者的重點研究方向。無人機滅火方式可解決傳統人工滅火人員傷亡問題,大幅度降低火災環境中滅火人員的危險等級[3,4]。而對于無人機滅火方式而言,保障無人機在實際滅火環境中無碰撞、高效率完成滅火行為的關鍵即為最優滅火路徑的規劃問題,需通過研究恰當的無人機滅火路徑仿真規劃方法,獲得長度最短、耗時最低、水平轉角最平緩且可完全避開障礙與危險區域的路徑,為無人機滅火方式提供保障[5]。

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

綜合以上分析,本文研究一種基于粒子群算法的無人機滅火路徑規劃仿真方法,實現無人機滅火路徑的仿真規劃,獲得最優最短路徑,為無人機高效滅火提供科學依據。

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

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

2.1 無人機滅火路徑規劃仿真環境建模

依據現實滅火環境構建無人機滅火路徑規劃仿真環境模型,主要包含水平區域模型、障礙區域模型、危險區域模型,具體如下:

1)水平區域模型構建:依據滅火環境地形的起伏狀態選用函數模擬法構建水平區域模型,所構建的水平區域模型可表示成

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

(1)

式中,水平區域高程通過z1表示;水平區域的點坐標通過(x,y)表示;數字地圖內該區域的地表特征通過b、c、d、u、v系數表示。

2)障礙區域模型構建:障礙區域模型重點針對滅火環境中的山體與樹木等障礙建模,所遵循的依據為已監測所得的實際數據信息[11]。所構建的障礙區域模型表示為

(2)

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

3)危險區域模型構建:該區域模型重點針對滅火環境中的雷達危險體區域實施仿真建模,選取半球體近似模擬該區域,則所構建的危險區域模型可表示成

(3)

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

通過融合以上所構建的水平區域模型、障礙區域模型及危險區域模型,獲得無人機滅火路徑規劃的整體仿真環境模型,可表示成

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

(4)

2.2 無人機滅火路徑規劃適應度函數創建

適應度函數是粒子群算法規劃無人機滅火路徑過程中種群迭代進化的根據,對粒子群算法的執行質量與效率有著直接的影響作用[12],另外,通過適應度函數能夠對粒子群算法規劃后所獲得的無人機滅火路徑的優劣實施評價。因此,適應度函數的創建是粒子群算法規劃無人機滅火路徑的基礎與關鍵。在此結合了無人機航跡高程代價、無人機航跡水平轉角代價、障礙危險代價與路徑長度代價共同創建適應度函數。

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

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

(5)

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

(6)

(7)

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

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

(8)

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

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

(9)

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

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

(10)

則其當前轉角運算式為

(11)

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

將以上所得的路徑長度代價、障礙危險代價、無人機航跡高程代價及無人機航跡水平轉角代價相結合后,能夠得到路徑的適應度函數,可表示成

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

(12)

式中,w1～w4為對各代價間關系實施靈活配置的權重系數,四個權重系數的總和為1。

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

在構建的無人機滅火路徑規劃仿真環境模型基礎上,通過細菌覓食改進粒子群算法(PSO-BFA),獲得改進粒子群算法,對滅火環境中的火點位置實施定位檢測,以所檢測到的火點位置作為終極目標點,通過改進粒子群算法運用所創建的適應度函數當作種群迭代進化的根據實現迭代尋優,獲得最優無人機滅火路徑。

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

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

(13)

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

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

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

(14)

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

2.3.2 滅火環境中火點定位檢測

運用實時采集的火災現場圖片將火災環境中火點相對無人機的位置運算得出,運算時所用到的火點定位圖如圖1所示。

圖1 火點定位圖

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

(15)

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

(16)

結合式(15)與式(16),能夠將J點至O點的間距獲得,可表示為:

(17)

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

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

運用改進粒子群算法在所構建的無人機滅火路徑規劃仿真環境中,依據所創建的適應度函數實施迭代尋優,得到最優無人機滅火路徑,實現無人滅火路徑規劃仿真?；诟倪M粒子群算法的無人機滅火路徑規劃過程為:

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

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

(18)

(19)

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

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

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

3 仿真結果分析

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

表1 實驗滅火區域仿真環境模型及本文方法關鍵參數

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

圖2 本文方法規劃所得最優無人機滅火路徑

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

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

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

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

表2 本文方法仿真中關鍵性能指標統計結果

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

4 結論

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