改進蝙蝠算法的無人機路徑規劃

丁元明,侯孟珂

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

0 引言

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

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

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

1 飛行空間模型與目標函數

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

1.1 飛行空間模型

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

圖1 山地仿真地圖

由于在實際飛行過程中,環境是變化的,該山地模型中的山峰隨機產生,增加了環境隨機性,對路徑規劃算法的健壯性、普適性有更加嚴格的要求。其數學模型為:

(1)

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

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

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

(2)

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

1.2 目標函數

UAV飛行路徑是指在約束條件下生成最優飛行路線,其目標是在合理的時間、成本內找到UAV的最優飛行路線。在飛行過程中,要考慮飛行成本。飛行成本主要分為3個部分:飛行路徑長度成本、威脅區成本和飛行高度成本?？偝杀竞瘮涤肳表示。最小成本函數Wmin可以表示為

Vmin=k1VL+k2VT+k3JH

(3)

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

飛行路徑長度成本為

(4)

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

威脅代價VT為

(5)

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

飛行高度代價JH為

(6)

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

2 改進蝙蝠算法

2.1 經典算法

2.1.1經典粒子群算法

PSO是一種基于種群的智能隨機算法,PSO模擬種群行為在搜索空間中進行全局搜索和局部開發,并根據目標函數得出當前搜索周期內的全局最優gbest和個體最優pbest;并根據前一代的gbest、pbest決定下一代粒子,最終得出最優解。粒子的速度和位置更新公式為

(7)

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

2.1.2基本蝙蝠算法

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

fi=fmin+(fmax-fmin)×β

(8)

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

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

(9)

(10)

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

xnew=xold+εAk

(11)

3) 參數更新。接受新解,則代表著更進一步靠近最優解,則降低響度,并不斷增加回聲發射速率ri,其更新公式為

(12)

(13)

2.2 改進蝙蝠算法

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

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

圖2 PSOBA搜素示意圖

在PSO中有明確的全局最優和個體最優的定義。由PSO中個體最優的定義出發改進BA,則PSOBA在隨機全局搜索的速度與位置迭代模型為

(14)

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

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

(15)

式(15)中:R2為0～1服從均勻分布的隨機數;k為當前迭代次數;K為最大迭代數;C(-1,0)是服從標準柯西分布的隨機數,范圍為-1到0;N(0,1)是服從高斯分布的隨機數,范圍為0到1。

2.3 最優成功率策略動態調整慣性權值

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

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

(16)

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

進而,將最優成功率策略用于動態調節慣性權值w,這使得慣性權重與種群的最佳成功率相關。最優成功率策略動態調節的自適應慣性權重為

(17)

(18)

(19)

OS-PSOBA通過最優成功率策略動態的調整w,使得種群按照k-1代的搜索結果進行收斂搜索,或是靠近全局最優和個體最優進行發散搜索,并在搜索過程中維持種群搜索的多樣性,整個搜索路徑的過程形成一個外部穩定,核心自適應動態調整的整體。

2.4 改進蝙蝠算法的無人機路徑規劃流程

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

圖3 PSOBA算法流程圖

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

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

步驟2根據目標函數,即式(3)計算種群各個個體的適應度。

步驟3按照個體適應度進行對比,找出個體最優解pbest以及全局最優解gbest。

步驟4判斷最優解的隨機數R1是否大于脈沖發射頻率r。若R1>r,則將在最優解附近隨機飛行;若R1

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

步驟7如未達到結束條件(通常為足夠好的適應值或達到一個預設的最大迭代數),則返回步驟2,直至達到結束條件,找出最優路徑。

3 模擬實驗與討論

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

3.1 二維空間下的仿真實驗

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

表1 PSOBA算法參數

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

圖4 二維空間下UAV路徑規劃

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

3.2 三維空間下的仿真實驗

3.2.1隨機變換三維空間下仿真實驗

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

圖5 隨機三維環境下仿真

3.2.2復雜三維空間下避障仿真實驗

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

圖6 復雜三維環境下避障仿真實驗

3.3 三維環境下對比實驗

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

表2 對比實驗參數設置

對比實驗進行5次,以避免偶然性對實驗結果產生影響。每次將對比實驗結果的路徑長短、路徑搜索時間、目標函數收斂情況和任務成功率作為比較參數。對比實驗認為路徑中無碰撞、無斷點,軌跡平滑,且從目標點成功到達目標點即為成功,運行結果如圖7所示。

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

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

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

圖8 算法路徑長度統計圖

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

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

圖9 目標函數值收斂曲線比較圖

4 結論

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

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

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

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