喻俊松,王　琪,徐蓉瑞

(南昌航空大學信息工程學院,南昌　330063)

基于改進人工魚群算法的無人機路徑規(guī)劃*

喻俊松,王琪,徐蓉瑞

(南昌航空大學信息工程學院,南昌330063)

摘要:針對使用基于網(wǎng)格劃分策略的改進人工魚群算法計算無人機路徑規(guī)劃問題中尋優(yōu)精度與算法計算量的矛盾,提出一種改進人工魚群算法,該算法引入自適應步長和執(zhí)行概率自適應分段網(wǎng)格遍歷策略。算法前期用較大步長全局搜索較優(yōu)路徑,后期用較小步長及網(wǎng)格分段遍歷策略在較優(yōu)解附近進行局部遍歷得到更精確最優(yōu)解。仿真結(jié)果表明所提改進人工魚群算法比原始魚群算法和自適應步長人工魚群算法結(jié)果更精確、穩(wěn)定,較基于簡單網(wǎng)格劃分策略的人工魚群算法計算量更小。

關(guān)鍵詞:路徑規(guī)劃;人工魚群算法;網(wǎng)格劃分策略;分段遍歷

0引言

飛行器航跡規(guī)劃就是在綜合考慮飛行器到達時間油耗威脅以及飛行區(qū)域等因素的前提下,為飛行器規(guī)劃出一條最優(yōu)或者是滿意的飛行航跡,以保證能夠圓滿完成飛行任務[1]。由于無人機在較高的高度高速巡航飛行,因此不考慮航跡的高度問題,可以將三維的航跡規(guī)劃轉(zhuǎn)化為二維的航路規(guī)劃問題。無人機的路徑規(guī)劃問題的本質(zhì)是多目標多約束的最優(yōu)化問題。文獻[2]使用遺傳算法來解決無人機路徑規(guī)劃問題。文獻[3]使用內(nèi)圓角的方法對無人機進行路徑規(guī)劃。文獻[4]是基于多邊形的無人機路徑規(guī)劃。由于人工魚群算法具有較強的全局尋優(yōu)能力,適合應用于路徑規(guī)劃問題,然而原始人工魚群算法和簡單步長自適應人工魚群算法在無人機路徑規(guī)劃中由于算法迭代后期人工魚的步長過大或覓食中的隨機行為導致尋優(yōu)結(jié)果精度不高,而文獻[5]中的基于網(wǎng)格劃分策略的改進人工魚群算法雖然尋優(yōu)結(jié)果精度高,但應用于無人機路徑規(guī)劃這類多維向量尋優(yōu)問題時計算量太大。

為了解決計算量與尋優(yōu)精度的矛盾,文中同時采用了自適應步長策略和概率自適應分段網(wǎng)格遍歷策略的人工魚群算法,將迭代后期較優(yōu)路徑附近的局部區(qū)域網(wǎng)格化,以分段遍歷局部網(wǎng)格所能組成的路徑作為反饋行為,仿真結(jié)果表明改進人工魚群算法在沒有明顯增加計算量的前提下有效的提高了尋優(yōu)精度。

1建模

1.1　無人機飛行環(huán)境建模

假設無人機從坐標原點出發(fā),前往目的地,途中任意的設置了若干個半徑大小不一的圓形威脅區(qū)域。無人機需要在繞過所有威脅區(qū)域的前提下以最短的路程到達目的地。文中借鑒了文獻[6]中的無人機路徑規(guī)劃的建模方式,使用多維向量代表路徑,再根據(jù)起點與目的地間的距離、威脅區(qū)域半徑的大小和結(jié)果精度的要求,將整條路徑分n-1步到達,路徑點的坐標是二維的,形如(xi,yi),為了減少每條人工魚的復雜度,將X軸上起點到終點間的距離n-1等分為x1,x2,…,xn-1,xn分別以它們作為各個路徑點的橫坐標,路徑優(yōu)化過程中只要為每個路徑點尋找符合要求的垂直坐標yi即能達到路徑規(guī)劃的目的。

1.2　尋優(yōu)目標函數(shù)

無人機路徑規(guī)劃的主要內(nèi)容包括規(guī)避威脅和盡量使飛行路程最短。合理的設計目標函數(shù)才能使得人工魚群算法的最后結(jié)果符合要求,得到最優(yōu)路徑。

采用計算路線中各路徑點間的距離之和作為整條路徑的長度或燃油代價。無人機飛行路程長度的目標函數(shù)為:

(1)

由于路徑中的x坐標被n等分,所以其中xi+1-xi是一個常數(shù)。其值由具體問題具體得出。

另外,為了規(guī)避威脅區(qū)域,將各個路徑點距各威脅中心的距離與各威脅的半徑作比較。此問題中如果相鄰兩路徑點間距較長,需要相應的增加步數(shù)以避免產(chǎn)生單步中兩端的路徑點在威脅區(qū)外而兩路徑點間的路徑經(jīng)過威脅區(qū)域的現(xiàn)象。然而步數(shù)的增加會大大增加運算量,降低運算效率,因此在規(guī)避威脅區(qū)域時還可以將相鄰兩路徑點間的中點、四分點甚至是多分點與各威脅中心點的距離和各威脅區(qū)域的半徑作比較以達到規(guī)避威脅區(qū)域的目的。當今世界,雷達和防空導彈系統(tǒng)越來越先進,為了嚴格禁止無人機飛進威脅區(qū)域,假設無人機進入威脅區(qū)域就意味著被擊落,使得無人機永遠無法到達目的地,飛行路程無限長,即:Obj=∞。

因此目標函數(shù)為:

(2)

式中:ri為各路徑點(或各路徑點和各相鄰路徑點間的多分點)到各威脅中心的距離;Ri為各威脅區(qū)域的半徑。由此目標函數(shù)值越小越好,路過威脅區(qū)的路線尤其不可取。

2自適應策略和分段網(wǎng)格遍歷策略

人工魚群算法是由李曉磊在2002年首次提出的一種新型群智能優(yōu)化算法[7]。算法通過執(zhí)行每條人工魚的覓食、聚群、追尾等行為來達到尋優(yōu)的目的。文中針對無人機路徑規(guī)劃問題,更是引入了步長自適應策略和概率自適應分段網(wǎng)格遍歷策略來改進魚群算法,使算法的尋優(yōu)精度和穩(wěn)定性得到進一步的提升。

2.1　自適應策略

文中兩次使用到了自適應策略,兩次自適應策略分別是隨著迭代次數(shù)的上升降低人工魚群的步長和提高執(zhí)行分段網(wǎng)格遍歷行為的概率。

其中引入步長自適應策略可以加快算法的收斂速度,提高算法精度。迭代初期以較大的步長迅速在大范圍內(nèi)尋優(yōu)。迭代后期步長變小,使得人工魚能夠在較優(yōu)值附近尋找更優(yōu)值,避免陷入局部極值。而引人概率自適應分段遍歷策略較簡單網(wǎng)格遍歷策略可以降低算法計算量,提高算法運算速度。避免在迭代前期遠遠還沒有找到最優(yōu)值的時候進行大計算量的網(wǎng)格遍歷行為,但在迭代的后期,執(zhí)行分段網(wǎng)格遍歷行為的概率變高,可以在尋優(yōu)結(jié)果趨于一個較為平穩(wěn)值的時候遍歷最優(yōu)人工魚的鄰域,進一步尋找附近的更優(yōu)解,使算法結(jié)果更精確。

2.2　分段網(wǎng)格遍歷策略

雖然步長自適應魚群算法后期人工魚步長變小,但由于人工魚覓食行為中隨機貪心尋優(yōu)的不確定性,導致結(jié)果精度仍有欠缺。這就需要采用網(wǎng)格遍歷策略提高尋優(yōu)精度。

2.2.1　無人機路徑規(guī)劃中的基本網(wǎng)格遍歷策略

假設人工魚的當前狀態(tài)為Yi,由于每條人工魚代表一條飛行路徑,所以Yi是一個由路徑點數(shù)個(包括起點和終點)元素組成的n維向量,每個元素代表該路徑點的垂直坐標,形如Yi(y1,y2,…,yn)。文中的網(wǎng)格遍歷是指在當前人工魚的附近范圍[YL,YU]按精度需求進行網(wǎng)格劃分,由于路徑的起點和終點不參與網(wǎng)格遍歷,所以YL=(y2L,y3L,…,y(n-1)L),YU=(y2U,y3U,…,y(n-1)U)。

網(wǎng)格劃分如圖1所示,劃分為m×(n-2)個網(wǎng)格,其中YL、YU和m的大小由尋優(yōu)精度的需求決定,n-2為除去起點和終點的路徑點個數(shù)。

圖1　無人機路徑規(guī)劃的網(wǎng)格劃分

然而如果只是單純的如此進行網(wǎng)格劃分,雖然尋優(yōu)結(jié)果會更精確,但當路徑點數(shù)目較多,n較大時,每次網(wǎng)格遍歷的計算任務將極其繁重,需要遍歷m(n-2)種網(wǎng)格可能組成的路徑,且需要將每種路徑代入目標函數(shù)計算路程的長短優(yōu)劣。所以文中引入分段網(wǎng)格遍歷策略以降低算法的運算量。

2.2.2　無人機路徑規(guī)劃中的分段網(wǎng)格遍歷策略

分段網(wǎng)格遍歷策略是文中針對無人機路徑規(guī)劃問題提出的在不明顯增加運算量的前提下提高尋優(yōu)精度的有效方法。分段網(wǎng)格遍歷策略包括兩個部分,即分段遍歷和各段之間的連接。

3基于改進算法的無人機路徑規(guī)劃

文中采用改進魚群算法進行無人機路徑規(guī)劃,并對解決此問題中人工魚的個體行為和算法步驟進行說明。

3.1　單條魚的個體行為

3.1.1　覓食行為

人工魚在步長(文中設置人工魚視野等于步長)范圍內(nèi)為除了起點和終點外每一個路徑點隨機的選取一個值組成Yi滿足yminFj,則使人工魚從Yi移動到Y(jié)j,否則不改變當前人工魚的狀態(tài)。試探既定次數(shù)后,就以該步長內(nèi)貪心覓食既定次數(shù)后得到的最優(yōu)路徑作為覓食行為的結(jié)果。覓食行為采取自適應步長覓食,隨魚群算法迭代次數(shù)的上升步長逐漸下降,即ymax-ymin逐漸下降,這樣可以得到一個較原始魚群算法更精確的解。

3.1.2　聚群行為

把視野內(nèi)人工魚的當前狀態(tài)向量Yi相加后除以視野內(nèi)人工魚群數(shù)目就得到視野內(nèi)人工魚的中心位置Yc,再分別把各人工魚位置與中心位置進行比較,如果人工魚的中心位置具有較高的食物濃度且不太擁擠,則人工魚從當前位置向人工魚中心位置移動。無人機航跡規(guī)劃問題為求解最小值問題,所以當滿足目標函數(shù)值Fi>Fc和Fc×n>δ×Fi時,表示距離中心位置最近的人工魚的位置較好且不會太擁擠,其中n表示視野內(nèi)人工魚的數(shù)目,δ表示人工魚擁擠度因子。如果不滿足以上條件則執(zhí)行人工魚的覓食行為。

3.1.3　追尾行為

假設人工魚的當前狀態(tài)為Yi,在視野范圍內(nèi)與所有的人工魚進行比較,找出目標函數(shù)最小的人工魚及其位置Yk。如果滿足目標函數(shù)值Fi>Fk且Fk×n<δ×Fi,則表示追尾目標人工魚的位置較好且不會太擁擠,人工魚向Yk方向移動。如果不能滿足以上條件則執(zhí)行人工魚的覓食行為。

3.1.4　隨機行為

隨機行為是指在視野范圍內(nèi)隨機地找一條線路,此行為的目的是防止尋優(yōu)過程陷入局部極值。

3.2　算法實現(xiàn)步驟

1)人工魚初始化、公告牌初始化、設置隨機行為概率初始值、人工魚群數(shù)目、最大迭代次數(shù)、概率衰減因子、步長線性變化率等。

2)對所有的人工魚依次執(zhí)行追尾行為、覓食行為、聚群行為和隨機行為,然后對執(zhí)行后的結(jié)果進行評價。如果行為評價后所得人工魚路程更短則執(zhí)行步驟4)。

3)如果行為評價后不能得到更優(yōu)結(jié)果則產(chǎn)生一個隨機數(shù),如果該隨機數(shù)大于分段網(wǎng)格遍歷行為概率,則執(zhí)行遍歷行為。

4)公告牌更新最優(yōu)路徑。

5)更新步長Step=Stepmax-t·θ。式中Stepmax為人工魚初始步長,t為已迭代的次數(shù),θ為步長線性變化率。

更新分段網(wǎng)格遍歷行為概率P=?·P。式中?為概率衰減因子。

6)判斷是否滿足終止條件,不滿足則執(zhí)行步驟2)。

4仿真實例

為了證明算法的優(yōu)越性,采用三種方案進行對比。方案A為原始魚群算法,人工魚數(shù)目為10,路徑點數(shù)目為13,最大迭代次數(shù)為1 000。方案B為簡單步長自適應魚群算法,最大步長為110,步長線性變換率為0.1,其他參數(shù)與方案A相同。方案C為所提出的改進魚群算法,概率衰減因子為0.96,YL、YU中各元素與當前人工魚相應元素差的絕對值為4,網(wǎng)格劃分數(shù)量m為5,分成每段包含3個路徑點的3段進行遍歷,其他參數(shù)與方案B相同。本實驗設置6個半徑大小不一的威脅,路徑起始點為(0,0),終點為(180,68)。每種算法做30次仿真,尋優(yōu)結(jié)果為路徑長度,越小越好。分別采用三種人工魚群算法進行無人機路徑規(guī)劃仿真(見圖2),三種算法仿真結(jié)果見表1和表2。

圖2　三種人工魚群算法的無人機路徑規(guī)劃

算法方案A方案B方案C平均值208.3238208.2737202.5241

表2　標準差對比

通過比較仿真圖和仿真結(jié)果可以發(fā)現(xiàn):所提改進人工魚群算法路徑規(guī)劃結(jié)果更為平滑,30次仿真規(guī)劃路徑平均長度較原始魚群算法和步長自適應魚群算法更短更精確,且尋優(yōu)結(jié)果標準差更小,算法尋優(yōu)更穩(wěn)定。這主要是因為迭代后期分段網(wǎng)格遍歷行為開始介入。

另外,本實驗也使用了基于普通網(wǎng)格劃分策略的魚群算法進行路徑規(guī)劃,但由于用該算法進行一次仿真的計算時間過長,所提改進魚群算法計算量優(yōu)勢明顯,所以未將其仿真數(shù)據(jù)納入對比中。

5結(jié)論

文中針對無人機路徑規(guī)劃問題中使用原始魚群算法或簡單步長自適應魚群算法局部尋優(yōu)精度有所欠缺,而使用基于網(wǎng)格策略的改進魚群算法計算精度和計算量不能兼得的矛盾,引入自適應步長和自適應分段網(wǎng)格遍歷策略,提出一種改進人工魚群算法。仿真結(jié)果表明該算法較原始魚群算法或簡單步長自適應魚群算法精度更高;較基于網(wǎng)格策略的人工魚群算法,尤其在路徑點較多時,計算量有明顯降低。

參考文獻:

[1]J F Gilmore. Autonomous vehicle planning analysis methodology [C]∥ The Proceedings of Association for Unmanned Vehicles Systems Conference. Washington, D.C. 1991.

[2]Miles B Pellazar. Vehicle route planning with constraints using genetic algorithms [C]∥In IEEE Nationgal Aerospace and Electronics Conference, 1994: 111-119.

[3]Chandler P R, Rasmussen S. UAV cooperative path planning, AIAA-2000-4370-CP [R]. 2000.

[4]Sridhar B, Chatterji G, Grabbe S, et al. Integration of traffic flow management decision [C]∥AIAA Paper 2002: 1-9.

[5]黃光球, 王西鄧, 劉冠. 基于網(wǎng)格劃分策略的改進人工魚群算法 [J]. 微電子學與計算機, 2007, 24(7): 83-86.

[6]袁麟博, 章衛(wèi)國, 李廣文. 一種基于遺傳算法—模式搜索法的無人機路徑規(guī)劃 [J]. 彈箭與制導學報, 2009, 29(3): 279-282.

[7]李曉磊, 邵之江, 錢積新. 一種基于動物自治體的尋優(yōu)模式: 魚群算法 [D]. 杭州: 浙江大學, 2002.

收稿日期:2014-06-06

作者簡介:喻俊松(1991-),男,江西南昌人,碩士研究生,研究方向:導航、制導與控制,通信與信息系統(tǒng)。

中圖分類號:V279

文獻標志碼:A

UAV Path Planning Based on Improved Artificial Fish-swarm Algorithm

YU Junsong,WANG Qi,XU Rongrui

(School of Information Engineering, Nanchang Hangkong University, Nanchang 330063, China)

Abstract:To resolve the conflict between precision and workload in path planning of an UAV with artificial fish-swarm algorithm based on gridding method, an improved artificial fish-swarm algorithm was presented. The proposed algorithm introduces adaptive step length method and adaptive gridding segmented traversal method. In early iteration, the proposed algorithm calculates with large step length, later calculates with narrowed step length and gridding segmented traversal method to find a better solution around a defective solution. The simulation result shows that the proposed artificial fish-swarm algorithm is more accurate and more stable than basic artificial fish-swarm algorithm or adaptive step length artificial fish-swarm algorithm and has large advantage on workload over artificial fish-swarm algorithm based on gridding method.

Keywords:path planning; artificial fish-swarm algorithm; gridding method; segmented traversal