基于改進蝙蝠算法的無人機三維路徑規劃

蘇 菲

(湖北商貿學院 人工智能學院，湖北 武漢 430079)

0 引言

近幾十年來，隨著無人機技術的快速發展及成熟，使得無人機在軍事行動中得到廣泛應用[1]。在軍事行動中，固定翼無人機常被用于情報收集、敵情偵察、物資補給，甚至武裝攻擊[2]。與有人駕駛飛機相比，無人機具有體積小、成本低、隱蔽性高和機動靈活等優勢，可以精確地完成重復性任務，且不受機組人員疲勞管理限制[3]。此外，無人機可以通過遠程控制，能在危及飛行安全的極端情況運行[4]。但目前無人機雖為無人駕駛，卻并沒有消除對飛行員的依賴，仍需要駕駛員遠程控制，難以實現自主駕駛[5-6]。

要實現無人機的自主駕駛，首先需要實現無人機的智能路徑規劃。當前，關于無人機路徑規劃的研究主要集中于連接起點和終點的最佳軌跡計算，且無人機軌跡必須符合無人機的動態約束，須對目標函數進行最小化處理，以實現最小化燃料消耗和最小化平均高度[7]。在早期的研究中，主要使用簡化的無人機模型及環境模型來表示，并依靠確定性算法計算最佳路徑[8-9]。但早期研究均依賴于在大量迭代中改進候選解，最終收斂到準最優解，計算工作量較大，在飛行中執行路徑規劃耗時太長[10]。

因此，為實現無人機自主駕駛及飛行，眾多專家學者針對無人機路徑規劃進行了大量研究。其中，文獻[11]提出了一種基于改進人工勢場的無人機動態避障路徑規劃方法，通過設置無人機與目標點的距離因子，調整斥力場系數，消除狹窄通道的軌跡振蕩。文獻[12]提出了一種基于改進A*算法的無人機路徑規劃方法，運用柵格法對無人機任務空間環境進行建模，提高了節點的搜索效率。但上述方法均屬于經典路徑規劃方法，算法運算時間較長，且容易陷入局部最優，實際應用效果不佳。文獻[13]提出了一種粒子群優化算法，通過考慮地形掩蔽、非各向同性雷達散射截面及無人機的動態約束等因素來確定路徑規劃。文獻[14]提出了一種混合灰狼路徑規劃優化算法，通過簡化計算階段加快收斂速度并保留種群探索能力，從而獲得有效的最佳飛行路徑。文獻[15]提出了一種基于蟻群優化算法的航跡規劃方法，在啟發函數中加入路徑偏移因子，降低了航跡搜索空間的復雜度。但上述方法均屬于元啟發法，需要強大的計算能力，導致消耗大量的計算時間，不利于無人機執行快速反應、機動靈活的作戰任務。

為此，針對上述研究問題，提出了一種融合黃金正弦和蝙蝠算法(Golden-Sine Bat Algorithm，GSBA)的無人機三維路徑規劃方法。首先，通過在傳統蝙蝠算法(Bat Algorithm,BA)中引入黃金正弦算法，提高蝙蝠個體尋優能力；采用平均種群位置對剩余個體進行引導，提高種群的多樣性。其次，引入刪除操作降低路徑的冗余度。最后，通過搭建仿真環境，驗證了所提方法的有效性。

1 模型構建

為了便于模型構建，假設突然發生泥石流或者其他的災害造成通往山區的公路無法通車，為了解決山區內居民生活物資問題，采用無人機進行物資的運送。假設山區空間大小為a1km×b1km×c1km，其中無人機運輸途中的障礙物主要為山體，即：

(1)

式中，Zi(x,y)為單個山體函數，即山體i上的某點(x,y)的高度；k1為表征山體形狀的系數；k2為表征山體大小的系數。山體i的中心點坐標為(xi,yi)，xpi，ypi分別對應山體i的x軸和y軸2個方向上的坡度。

無人機安全運輸的要求是能夠避開飛行途中的所有障礙物(即山體)，這也意味著在坐標點(xm,ym)處無人機的飛行高度要高于障礙物的高度，否則無人機將與山體相撞，即：

V(xm,ym)>Zi(xm,ym),xm∈Si,ym∈Si，

(2)

式中，V(xm,ym)為無人機在點(xm,ym)的飛行高度；Si為山體i在xy平面上的投影區域。

通常無人機具有一定的體積，如果單純使用無人機中心點計算無人機高度，可能會出現無人機邊緣撞擊山體的事故，所以還要考慮無人機機體與山體的距離是否會發生碰撞。因此，將UAV模型簡化為一個長方體，其長寬高分別用符號a，b，h表示，簡化后無人機與山體的位置關系如圖1所示。

圖1 長方體無人機與山體的位置關系Fig.1 Position relationship between the cuboid drone and the mountain

由圖1可知，如果根據式(1)和式(2)計算，在坐標(xm,ym)處，雖然無人機的飛行高度比該點山體要高，但是由于山體自身存在坡度，無人機在飛行過程中勢必還是會與山體相撞。這也意味著無人機與山體之間的避撞不僅與無人機體積有關，同時還與山體的陡峭程度有關，但是山體表面往往是非線性變化區域，因此對山體建模存在一定的困難。為了解決上述問題并避免無人機與山體發生碰撞，將無人機進一步簡化為球體，球體的直徑為無人機機體對角線最長部分，如圖2所示。

圖2 無人機球體模型Fig.2 UAV sphere model

其中，圖2也可以理解為將圖1中無人機簡化的長方體放置在一個球體中，球體半徑為：

(3)

為了對球體更好地進行描述，此處使用極坐標表示，該坐標系原點為無人機中心，即：

(4)

式中，R(x,y,z)表示球體R上的一個點，將R(x,y,z)與極點連成一條直線L，則θ表示z軸的正方向與L的夾角；將R(x,y,z)與z軸形成一個平面M，則φ為坐標系中z軸和x軸所形成的平面與平面M之間的夾角。

由此可以得到，如果球體R上的任意點(x,y,z)均在山體外部，則不會發生無人機碰撞山體事件，即：

R(xm,ym,z)>Zi(xm,ym),xm,ym∈Si。

(5)

此外，還要考慮無人機飛行高度超過限值導致的脫離無線控制信號范圍的問題，以及無人機飛行高度過低導致的可能與地面物體(如地表植物、石頭等)發生碰撞的問題，所以無人機飛行高度還應滿足：

Hmin≤Hi≤Hmax，

(6)

式中，Hmin為無人機飛行高度最小值；Hmax為無人機飛行高度最大值。

為了對無人機飛行的路徑質量進行評價，還需要構建以飛行路徑高度、長短和平滑度等為目標的評價指標。無人機飛行路徑中點i與點i+1之間的距離為：

(7)

式中，(xi,yi,zi)表示無人機飛行路徑點i在xzy三維坐標系中的坐標，此時無人機的飛行路徑總長度為：

(8)

式中，N表示無人機飛行過程中途經的點的總數。無人機飛行路徑中的轉角角度如圖3所示。

圖3 無人機飛行轉角Fig.3 UAV flight angle

從圖3可以看出，θ為無人機從路段AB轉至路段BC所需要轉的角度，故可以計算無人機飛行路徑的平均平滑度為:

(9)

式中，Ai為無人機飛行路徑中的點i與點i+1連接而成的向量。同時，因為無人機飛行高度越高能耗也越高，故無人機在安全飛行的前提下須盡量低空飛行。無人機從起點到終點飛行高度平均值為：

(10)

綜合式(7)～式(9)中的無人機路徑規劃目標，可得目標函數為：

minM=Lall+Q+Hall。

(11)

2 改進BA

2.1 傳統BA

BA是指根據蝙蝠的飛行行為而得到的一種啟發式算法[16]。首先，構建適應度函數并計算種群中個體的適應度值；其次，比較個體適應度值，并記錄其中適應度值最高的蝙蝠個體作為全局最優蝙蝠，同時根據此最優蝙蝠個體的信息對其他蝙蝠個體的位置和速度進行更新。然后對最優個體通過一定的局部搜索方法進行局部搜索，并更新其位置信息，不斷迭代此過程直到得到全局最優解。傳統BA更新過程為：

fi=fmin+(fmax-fmin)β，

(12)

(13)

(14)

全局搜索完成后可以得到全局最優蝙蝠個體，而后需要進一步通過局部搜索方法對該蝙蝠個體的周圍進行搜索，即在最優蝙蝠的周圍進行隨機游走，此時使用式(15)進行位置更新。

xnew=xold+εAt，

(15)

式中，xold為當前最優蝙蝠個體的位置；xnew為局部搜索更新后的最優蝙蝠個體位置；ε∈[-1,1]；At表示t次迭代中的種群平均響度。

當蝙蝠飛行過程中發現了獵物，為了更加準確地對獵物的位置進行定位，蝙蝠個體的聲波脈沖頻率會增加，響度會減小，位置更新為：

(16)

(17)

2.2 融合黃金正弦的BA

2.2.1 黃金正弦算法

黃金正弦算法(Golden-SA)為一種新型智能算法[17]，通過單位圓和sin函數的關系在算法迭代尋優的過程中進行全局搜索，同時使用黃金分割數對空間進行控制遍歷，實現個體的快速尋優，該算法計算簡單且迭代收斂快。

其位置更新為[18]：

(18)

a1=-π+(1-τ)2π，

(19)

a2=-π+2πτ，

(20)

2.2.2 種群平均位置

由于BA中的尋優是根據其中最優蝙蝠個體的引導而進行的，所以若全局最優蝙蝠個體并非種群最優個體且相差較大，則會導致算法陷入局部最優。針對此問題，為了避免蝙蝠個體引導方向錯誤，對于種群中蝙蝠個體的引導搜索還可以加入種群平均位置引導，進而極大可能地避免了局部最優問題。具體更新為：

(21)

(22)

式中，mt-1表示引入的t-1次迭代中的種群平均位置。

2.2.3 分階段局部搜索

在傳統的BA中通常是采用全維搜索方法，該方法雖然具有較強的局部搜索能力，卻忽略了單個維度值對算法適應度的影響。但是若采用單維度搜索算法，又會導致算法收斂速度慢，影響搜索效率。

考慮到上述因素，本文將全維搜索與單維搜索相結合形成互補的搜索方式，實現對最優蝙蝠個體的搜索。融合后的搜索方式為在每次迭代的前2/3過程中使用單維搜索，后1/3使用全維搜索，具體更新為：

(23)

式中，T表示最大迭代次數；d∈[1,D]。

2.2.4 刪除操作

由于路徑規劃中會存在冗余節點的問題，為了提高路徑平滑度、降低路徑長度，還需要刪除冗余節點，如圖4所示。

圖4 刪除操作示意Fig.4 Schematic diagram of delete operation

由圖4可知，在刪除操作之前算法規劃的路徑為1→2→3，將節點1和節點3相連接，如果可以避開障礙物，則1→3路徑可行且安全，那么可以對節點2進行刪除操作。

從第一個節點開始，依次連接后面的節點，如果連接的直線為無障礙路徑，則將2個節點中間的節點都刪除；如果不存在無障礙路徑，則從下個節點開始繼續搜索，直到最后一個節點。而后，重新對路徑適應度進行計算。通過刪除操作，一方面通過減少冗余節點縮短了路徑的長度，另一方面也提高了路徑的平滑度。

2.2.5 引入黃金正弦的BA

為了避免算法早熟，提出了一種改進BA，即引入黃金正弦思想。首先，將蝙蝠種群分成2個具有不同適應度的子種群，對于其中適應度較好的子種群，使用sin函數更新個體位置，進而使最優個體信息可以迅速引導影響其他個體，實現了算法的快速收斂，對于另外一個適應度較差的蝙蝠子群體，則通過種群平均位置避免了其他個體搜索方向的偏移，保證了算法多樣性，避免局部最優。此時，蝙蝠個體位置更新為：

(24)

算法全局搜索后，還要進行局部搜索，即通過全維搜索策略和單維搜索策略相結合分階段互補搜索，提高了算法的局部搜索能力。獲得最優解后，再通過刪除操作對其中的冗余節點進行刪除，最終得到了平滑度高、路徑長度短的最優路徑。

本文算法的流程如圖5所示，具體步驟如下：

圖5 本文所提算法的流程Fig.5 Flow chart of the algorithm proposed

② 對蝙蝠種群中每個蝙蝠個體的適應度進行計算，對其中最優的路徑x*進行記錄并保存，而后根據式(22)對蝙蝠種群的平均位置進行計算。

③ 根據式(24)更新最優蝙蝠個體位置，而后使用式(21)和式(14)對其他蝙蝠個體進行更新。

每次迭代中更新全局最優路徑，而后計算其適應度值。若t=T，那么刪除最優路徑中的冗余節點，輸出結果。若t

3 實驗結果分析

實驗中假設無人機需要向4個1 000 m×1 000 m×1 000 m的不同山區運送物資。將1 000 m×1 000 m×1 000 m的山區空間離散為109個坐標點，UAV的參數(a,b,c)=(0.5,0.6,0.5)m,Hmax為1 000 m,Hmin為10 m，算法中種群個體N為100，最大迭代次數T為100，脈沖頻率fmin=0.0,fmax=2.0，初始脈沖發射率r0=0.5，脈沖和響度調節參數為0.9。

山區1的起點坐標為(1,5,0)、終點坐標為(10,5,0)。山區2的起點坐標為(0,5,0)、終點坐標為(10,5,0)。山區3的起點坐標為(2,9,0)、終點坐標為(10,0.5,0)。山區4的起點坐標為(0.5,3.5,0)、終點坐標為(9.5,9.5,0)。為了驗證改進后的算法的性能，首先選取山區1進行算法迭代驗證，實驗中分別選取了傳統BA、Golden-SA以及本文所提改進算法對山區1優化路徑進行求解， 3種算法的飛行路徑如圖6所示。

圖6 3種算法對山區1規劃的無人機飛行路徑Fig.6 UAV flight path planned by the three algorithms for mountain area 1

由圖6可知，3種算法規劃的飛行路徑區別較大，山區1中3種算法的迭代圖如圖7所示。

由圖6和圖7可以看到，BA規劃的路徑長度和達到收斂的迭代次數與Golden-SA都較為接近，而改進后的算法在經過32次迭代后就得到最優飛行路徑，且路徑長度要明顯低于其他2種算法，由此也表明在融合了傳統BA和Golden-SA后，所得到的算法在性能上有了很大的提高。

圖7 山區1中3種算法迭代Fig.7 Three algorithm iterations in mountain area 1

為了驗證本文所提改進BA的有效性，選取了文獻[12]、文獻[13]和文獻[15]三種算法進行對比分析，分別對山區1～4進行無人機路徑規劃。4種算法的規劃路徑圖如圖8所示。

(a) 山區1

(b) 山區2

(c) 山區3

(d) 山區4圖8 山區1～4環境中4種對比算法規劃的路徑Fig.8 Paths planned by the four comparison algorithms in mountain 1～4 environments

從圖8可以看出，在山區1～4環境中本文所提算法的路徑要明顯比其他3種算法的短，且路徑更為平滑。4種算法在山區1環境下的算法迭代情況如圖9所示。從圖9中可以看出，所提算法在經過35次迭代后就獲得了最優路徑，其迭代速度明顯比其他3種算法快。為了更直觀地體現所提算法的性能，表1給出了4種算法的具體仿真參數，其中Min表示飛行路徑長度、Time表示算法迭代時間、Rate表示種群中個體的收斂率。

圖9 不同種算法在山區1路徑規劃中的迭代Fig.9 Iteration of different algorithms in mountain area 1 path planning

表1 不同算法路徑規劃指標比較Tab.1 Comparison of path planning indicators of different algorithms

4 結束語

針對當前無人機在高速動態環境中軌跡調整自主性低、響應速度慢的問題，提出了一種基于改進BA的無人機三維路徑規劃方法。實驗結果表明，本文所提算法在路徑長度、算法收斂時間以及種群收斂度方面有著良好的性能，能夠有效實現無人機的三維路徑規劃。但是需要注意的是，本文在路徑規劃方面的優勢需要建立在對飛行環境的精準建模基礎上，若建模出現誤差則可能會導致無人機墜毀，而對于復雜山體的建模仍然較為復雜，因此后續也將重點研究如何通過復雜山體模型構建來避免無人機與山體碰撞。