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

李喜剛, 蔡遠利

(西安交通大學(xué) 電子與信息工程學(xué)院, 陜西 西安 710049)

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

李喜剛, 蔡遠利

(西安交通大學(xué) 電子與信息工程學(xué)院, 陜西 西安 710049)

針對傳統(tǒng)無人機路徑規(guī)劃算法存在規(guī)劃效率低以及無法滿足特定任務(wù)需求的缺點,提出了基于改進蟻群優(yōu)化算法的無人機路徑規(guī)劃算法。首先,將待規(guī)劃區(qū)域柵格化,給每一個網(wǎng)格按順序編號;其次,在路徑搜索時引入了一種雙向搜索機制,對信息素的更新規(guī)則和下一步節(jié)點的選擇方法做出改進;最后,提出了一種新的方法來整合兩組螞蟻生成的路徑,并給出了若干仿真試驗結(jié)果。結(jié)果表明,所提算法相比傳統(tǒng)算法更能有效避免過早陷入局部最優(yōu),收斂速度加快,生成滿足任務(wù)約束的最短路徑。

蟻群優(yōu)化算法; 無人機路徑規(guī)劃; 雙向搜索

0 引言

無人機在整個航空領(lǐng)域扮演著越來越重要的角色。為了完成各種民用和軍事任務(wù),無人機控制系統(tǒng)面臨許多難題,比如多機任務(wù)協(xié)同、路徑規(guī)劃、路徑跟蹤等,其中路徑規(guī)劃是無人機導(dǎo)航和控制的核心技術(shù)。

對路徑規(guī)劃的研究始于20世紀60年代,國內(nèi)外學(xué)者提出了大量的路徑規(guī)劃算法,包括A*算法[1]、Voronoi圖算法[2]、動態(tài)規(guī)劃方法[3]、仿生學(xué)算法[4]等。由于路徑規(guī)劃問題具有高時間復(fù)雜度,所以,問題的求解時間會隨著問題的規(guī)模呈指數(shù)型增長,尤其在復(fù)雜環(huán)境或者搜索空間比較大的情況下,上述所有算法的計算成本會急劇增加。由此,提出了新的啟發(fā)式算法和混合式算法用于無人機路徑規(guī)劃,典型代表有模糊控制[5]、神經(jīng)網(wǎng)絡(luò)[6]、蟻群優(yōu)化算法[7]、模擬退火-人工勢場法[8]和粒子群算法[9]。

蟻群優(yōu)化算法(Ant Colony Optimization,ACO)是基于生物界螞蟻的群體行為習(xí)性提出的一種仿生學(xué)搜索算法。為了使規(guī)劃出來的路徑能夠滿足特定的任務(wù)要求,需要對傳統(tǒng)蟻群算法進行一定的改進。其中一種方法是改變蟻群的搜索機制,比如文獻[10-11]提出的雙向搜索。然而,文獻[10]沒有對路徑的轉(zhuǎn)彎角度作限制,也沒有無人機的飛行性能約束,而文獻[11]的搜索效率也不高。一般來講,無人機從機場起飛后要經(jīng)過一系列轉(zhuǎn)彎過程才能加入航線,因此無人機離開出發(fā)點空域時有角度約束,同時,無人機可能要以特定的角度進入目標空域執(zhí)行任務(wù),顯然傳統(tǒng)的ACO算法不能滿足任務(wù)需要。

本文針對無人機路徑規(guī)劃問題的特殊性,對傳統(tǒng)ACO算法進行了改進。首先,將無人機的工作區(qū)域劃分為一系列具有二值信息的網(wǎng)格單元,在柵格圖中進行路徑規(guī)劃時考慮無人機的最大轉(zhuǎn)彎角度限制,以及起始區(qū)域和終點區(qū)域的角度約束;然后改進了螞蟻信息素的更新規(guī)則,根據(jù)每只螞蟻所求解的質(zhì)量不同,對螞蟻經(jīng)過路徑上的信息素增量自適應(yīng)地更新,信息素揮發(fā)系數(shù)ρ也隨著迭代次數(shù)的增加而相應(yīng)地改變,使得算法在一定程度上避免陷入局部最優(yōu);最后,提出了一種雙向搜索機制,在任務(wù)起點和終點同時放出兩組螞蟻進行路徑搜索,并分別討論了搜索過程中螞蟻的相遇問題,提出了一種路徑整合方法,充分利用了搜索方向相對的兩只螞蟻各自的信息,加快了路徑生成的速度。

1 搜索空間建模

本文無人機的搜索空間為一張32×32的柵格地圖,每一個網(wǎng)格都被賦予從1到1024的一個編號。由蟻群優(yōu)化算法最終生成的無人機路徑是一個數(shù)集,如{1,2,13,25,…, 991},其中1為柵格地圖上的起點編號,991為柵格地圖上的終點編號。

柵格地圖從左到右、自上而下的編號為:第一行從左至右依次為1,2,3,…,32,第二行從左至右依次為33,34,…,64,依此類推。柵格地圖的網(wǎng)格編號和任務(wù)區(qū)域的坐標對應(yīng)關(guān)系為:

(1)

式中:(xm,ym)為柵格地圖中節(jié)點的坐標;(xr,yr)為真實任務(wù)區(qū)域的相對坐標;δ為無人機在單位時間內(nèi)實際飛行的距離;f(x,δ)為x除以δ;H為柵格地圖的高度;I為網(wǎng)格的編號。

在柵格地圖中,障礙物占一個或多個柵格,當(dāng)不滿一個柵格時,算一個柵格。值為1代表該網(wǎng)格是障礙物,可能是雷達威脅或地形威脅,值為0代表無人機可以通過該區(qū)域,如圖1所示。

在實際場景中,無人機的飛行路徑還受到最大轉(zhuǎn)彎角度和任務(wù)區(qū)域角度的約束。

圖1 柵格地圖(黑色方塊代表禁飛區(qū))Fig.1 Grid map(black squares indicating no-fly zones)

1.1 最大轉(zhuǎn)彎角度

無人機在轉(zhuǎn)彎機動時,由于性能限制轉(zhuǎn)彎角度不能超過最大轉(zhuǎn)彎角θm。也就是說,無人機在轉(zhuǎn)彎時其角度變化范圍不能超過[θ0-θm,θ0+θm],θ0為無人機當(dāng)前的飛行角度,如圖2所示。

圖2 最大轉(zhuǎn)彎角度約束示意圖Fig.2 Diagram of maximum turning angle constraint

1.2 任務(wù)區(qū)域角度約束

通常情況下,機場的飛機離場圖規(guī)定飛機必須按照特定的路線離開機場空域,飛機從跑道起飛后需要進行一系列的轉(zhuǎn)彎機動,經(jīng)過規(guī)定的導(dǎo)航臺后才能加入航線,離開機場空域。這就要求從機場開始進行路徑規(guī)劃時,必須考慮無人機離開機場空域的起始角度。圖3展示的是機場的其中一條離場航線示意圖。同樣地,任務(wù)的終點區(qū)域可能由于地形或者威脅限制了無人機的進近角度和方向,如圖4所示。這樣在作路徑規(guī)劃時,必須考慮無人機離開起始區(qū)域的角度θs和進入終點區(qū)域的角度θe。

圖3 機場某條離場航線示意圖Fig.3 Diagram of an illustrative departure route in airport

圖4 任務(wù)終點角度示意圖Fig.4 Diagram of approaching angle

2 改進的ACO路徑規(guī)劃算法

盡管ACO算法有著諸多的優(yōu)勢,但是它的缺點仍然不容忽視,例如收斂速度慢、易陷入局部最優(yōu)、不能滿足特定任務(wù)的需求等。為了解決這些問題,同時滿足特定的任務(wù)約束,本文提出了一種改進的ACO算法。

2.1 改進螞蟻的移動規(guī)則

在傳統(tǒng)ACO算法中,每只螞蟻在走完一步后要在鄰接的節(jié)點中選擇下一步要走的節(jié)點,候選節(jié)點數(shù)量將直接影響到計算狀態(tài)轉(zhuǎn)移概率的時間和內(nèi)存消耗。在1.2節(jié)中提到,無人機最大轉(zhuǎn)彎角限制了螞蟻在選擇下一節(jié)點時,不能把當(dāng)前時刻它周圍的8個節(jié)點都看作是候選節(jié)點,只有3個節(jié)點(如果它們不在禁飛區(qū)的話)才能算作是候選節(jié)點,且這3個節(jié)點和當(dāng)前節(jié)點的連線與螞蟻的前進方向夾角為θm∈{45°,0°,-45°},如圖5所示。圖中,黑色實線為螞蟻已經(jīng)走過的路徑。

圖5 可供螞蟻選擇的候選節(jié)點示意圖Fig.5 Diagram of potential nodes for ants to choose

2.2 改進全局信息素的更新策略

2.2.1 改進信息素揮發(fā)系數(shù)的更新方式

通常情況下,ACO算法信息素的正反饋機制能夠得到路徑規(guī)劃問題的全局最優(yōu)解,但有時ACO算法會過早陷入局部優(yōu)化。為了解決這個問題,本文首先對信息素揮發(fā)系數(shù)ρ的更新規(guī)則作了改進,使其可以隨著迭代次數(shù)的增加自適應(yīng)地改變。

(2)

式中:n為當(dāng)前迭代的次數(shù);N為設(shè)定迭代的總次數(shù)。

2.2.2 改進信息素增量的更新方式

通過引入信息素增量調(diào)節(jié)因子λ,根據(jù)每只螞蟻所求解的優(yōu)劣程度調(diào)節(jié)信息素的增量為：

(3)

(4)

通過引入信息素增量調(diào)節(jié)因子λ,使得在短時間內(nèi)可以通過信息素增量來判斷路徑的優(yōu)劣程度,可以將次優(yōu)路徑和其他路徑分開,在較大程度上加快了算法的收斂速度,提高了算法的全局搜索能力。

綜上所述,t+n時刻在螞蟻的路徑點(i,j)上的信息素更新法則如下:

(5)

(6)

2.3 雙向搜索機制

在傳統(tǒng)ACO算法中,一條路徑的生成通常是從起點開始,到終點結(jié)束,沒有充分發(fā)揮螞蟻群體協(xié)作的特性,因此影響了算法的效率和收斂速度,而且不一定滿足任務(wù)的角度約束,雙向搜索機制能夠有效解決這個問題。將兩組螞蟻(A組和B組)分別放在起點和終點區(qū)域,然后兩組螞蟻同時以對方的出發(fā)點為目的地尋找最短路徑。A組的螞蟻出發(fā)角為θs,終止角為θe,而B組的螞蟻正好相反。

螞蟻在尋找路徑的過程中,尋路方向不同的兩只螞蟻可能會在途中相遇。這兩只螞蟻分別攜帶了它們各自的路徑信息,通過整合它們的信息,可以快速得到一條新的可行路徑,從而加快了算法的收斂速度。當(dāng)螞蟻移動到下一個節(jié)點后,就開始檢測當(dāng)前節(jié)點是否在對向螞蟻的路徑上,如果是,則通過整合機制將兩條路徑整合為一條新的可行路徑;如果不是,則檢測是否與對向來的螞蟻相遇,當(dāng)兩只螞蟻相遇時,也可以通過路徑整合得到一條新的路徑。

圖6中可能出現(xiàn)兩種情況。情況一:螞蟻k1的當(dāng)前位置為p3,螞蟻k2的當(dāng)前位置為p4,則兩只螞蟻不會相遇,但此時程序檢測到p3已經(jīng)被螞蟻k2訪問過,所以直接聯(lián)合螞蟻k1的路徑path1={1,12,23,24,25,36,46,56}和螞蟻k2的路徑path2={98,89,79,69,58,57,56,55,54,53}生成新的路徑path={1,12,23,24,25,36,46,56,57,58,69,79,89,98},考慮到無人機的最大轉(zhuǎn)彎角限制,在路徑結(jié)合處做平滑處理,最終得到新路徑path—new={1,12,23,24,25,36,46,57,58,69,79,89,98}。情況二:螞蟻k1的當(dāng)前位置為p1,螞蟻k2的當(dāng)前位置為p2或者p3,根據(jù)相遇檢測算法,兩只螞蟻在途中相遇了。此時,根據(jù)螞蟻k1和k2的已有路徑,考慮到路徑結(jié)合處的最大轉(zhuǎn)彎角度限制,直接生成一條滿足約束條件的可行路徑path—meet={1,12,23,24,25,36,46,57,58,69,79,89,98}。

圖6 雙向搜索算法示意圖Fig.6 Diagram of bidirectional searching

3 仿真結(jié)果及分析

本文采用Matlab對改進的ACO算法進行兩組仿真試驗,除出發(fā)角為θs和終止角為θe不同外,其余參數(shù)完全一致。仿真參數(shù)為:螞蟻數(shù)量M=50只;信息啟發(fā)因子α=1;ρ=0.95;期望啟發(fā)因子β=5;Q=1;θm=45°;搜索次數(shù)50次。仿真試驗1的θs=0°,θe=180°,起始節(jié)點編號為65,目標節(jié)點編號為1021,仿真結(jié)果如圖7所示。仿真試驗2的θs=-90°,θe=135°,起始節(jié)點編號為65,目標節(jié)點編號為990,仿真結(jié)果如圖8所示。

圖7 仿真試驗1路徑規(guī)劃結(jié)果Fig.7 Path planning in simulation 1

圖8 仿真試驗2路徑規(guī)劃結(jié)果Fig.8 Path planning in simulation 2

試驗中,將傳統(tǒng)的和改進的ACO算法的仿真結(jié)果進行了對比,結(jié)果如表1所示。圖9和圖10為兩種算法最短路徑收斂曲線對比圖。

表1 仿真結(jié)果對比

圖9 試驗1最短路徑收斂曲線Fig.9 Convergence curves of shortest path in simulation 1

圖10 仿真試驗2最短路徑收斂曲線Fig.10 Convergence curves of shortest path in simulation 2

仿真結(jié)果表明,改進的ACO算法能夠以更快的收斂速度規(guī)劃出最短路徑。圖7和圖8表明，傳統(tǒng)ACO算法雖然能規(guī)劃出一條從起點到終點的路徑,但無法保證規(guī)劃出來的路徑滿足任務(wù)的約束條件。圖9和圖10表明，改進的ACO算法的收斂速度和全局最優(yōu)性都得到了較大提高。

4 結(jié)束語

本文提出了一種基于改進蟻群優(yōu)化算法的無人機路徑規(guī)劃算法。該算法限制了螞蟻在搜索路徑時的“視野”,在一定程度上提高了算法的搜索效率。提出的螞蟻相遇策略充分發(fā)揮了蟻群之間相互協(xié)作的群體特性,大大提升了生成路徑的速度。

傳統(tǒng)蟻群算法和改進蟻群算法收斂曲線對比結(jié)果表明,改進算法比傳統(tǒng)算法具有更快的收斂速度,能夠更快、更有效地獲得可行路徑。在接下來的工作中,可以將本優(yōu)化算法拓展到三維空間和更復(fù)雜、更真實的應(yīng)用場景中。

[1] 譚寶成,王培.A*路徑規(guī)劃算法的改進與實現(xiàn)[J].西安工業(yè)大學(xué)學(xué)報,2012,32(4):325-329.

[2] Pehilivanoglu Y V.A new vibrational genetic algorithm enhanced with a Voronoi diagram for path planning of autonomous UAV[J].Aerospace Science and Technology,2012,16(1):47-55.

[3] Jennings A L,Ordonez R,Ceccarelli N.Dynamic programming applied to UAV way point path planning in wind[C]//IEEE Multi-conference on Systems and Control.San Antonio,Texas:IEEE,2008:215-220.

[4] 戴青.基于遺傳和蟻群算法的機器人路徑規(guī)劃研究[D].武漢:武漢理工大學(xué),2009.

[5] 付宜利,顧曉宇,王樹國.基于模糊控制的自主機器人路徑規(guī)劃策略研究[J].機器人,2004,26(6):548-552.

[6] 樊長虹,陳衛(wèi)東,席裕庚.未知環(huán)境下移動機器人安全路徑規(guī)劃的一種神經(jīng)網(wǎng)絡(luò)方法[J].自動化學(xué)報,2004,30(6):816-823.

[7] 段海濱.蟻群算法原理及其應(yīng)用[M].北京:科學(xué)出版社,2005.

[8] 王強,張安,吳忠杰.改進人工勢場法與模擬退火算法的無人機航路規(guī)劃[J].火力與指揮控制,2014,39(8):70-73.

[9] WU Xianxiang, MING Yan, WANG Juan. An improved path planning approach based on particle swarm optimization[C]//International Conference on Hybrid Intelligent Systems (HIS).Meacca:IEEE,2011:157-161.

[10] 曹文鋒.基于改進蟻群算法的飛行器航跡規(guī)劃研究[D].重慶:重慶大學(xué),2011.

[11] 盧江松.基于改進蟻群算法的多機協(xié)同突防航跡規(guī)劃方法研究[D].長沙:國防科學(xué)技術(shù)大學(xué),2011.

(編輯：方春玲)

UAV path planning based on improved ant colony algorithm

LI Xi-gang, CAI Yuan-li

(School of Electronic and Information Engineering, Xi’an Jiaotong University,Xi’an 710049, China)

Traditional intelligent optimization algorithms have lots of disadvantages in UAV path planning, and they rarely take mission constraints into consideration. In order to obtain an optimal path that meets the mission constraints with higher efficiency, an improved ant colony optimal (ACO) algorithm is proposed in this paper. First of all, searching space was modeled as a grid map and each grid was labeled by sequential number. Secondly, a bidirectional searching method was used in the path searching, pheromone updating rules and the method to select next node were also improved. Finally, a new method was presented to combine and smooth the paths generated by those two group ants. Simulation results show that the improved ACO algorithm is capable to generate a feasible path that meets the mission constraints, and the improved ACO algorithm can help the solutions escape from their local optimization and find better path at higher convergence speed.

ant colony optimization algorithm; UAV path planning; bidirectional searching

2016-03-30;

2016-10-21;

時間:2016-11-01 16:48

國家自然科學(xué)基金資助(61308120)

李喜剛(1988-)，男，甘肅靜寧人，碩士研究生，研究方向為無人機建模及路徑規(guī)劃。

V279

A

1002-0853(2017)01-0052-05