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

李喜剛, 蔡遠(yuǎn)利

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

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

李喜剛, 蔡遠(yuǎn)利

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

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

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

0 引言

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

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

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

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

1 搜索空間建模

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

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

(1)

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

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

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

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

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

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

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

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

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

圖3 機(jī)場(chǎng)某條離場(chǎng)航線示意圖Fig.3 Diagram of an illustrative departure route in airport

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

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

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

2.1 改進(jìn)螞蟻的移動(dòng)規(guī)則

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

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

2.2 改進(jìn)全局信息素的更新策略

2.2.1 改進(jìn)信息素?fù)]發(fā)系數(shù)的更新方式

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

(2)

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

2.2.2 改進(jìn)信息素增量的更新方式

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

(3)

(4)

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

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

(5)

(6)

2.3 雙向搜索機(jī)制

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

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

圖6中可能出現(xiàn)兩種情況。情況一:螞蟻k1的當(dāng)前位置為p3,螞蟻k2的當(dāng)前位置為p4,則兩只螞蟻不會(huì)相遇,但此時(shí)程序檢測(cè)到p3已經(jīng)被螞蟻k2訪問(wèn)過(guò),所以直接聯(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},考慮到無(wú)人機(jī)的最大轉(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ù)相遇檢測(cè)算法,兩只螞蟻在途中相遇了。此時(shí),根據(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對(duì)改進(jìn)的ACO算法進(jìn)行兩組仿真試驗(yàn),除出發(fā)角為θs和終止角為θe不同外,其余參數(shù)完全一致。仿真參數(shù)為:螞蟻數(shù)量M=50只;信息啟發(fā)因子α=1;ρ=0.95;期望啟發(fā)因子β=5;Q=1;θm=45°;搜索次數(shù)50次。仿真試驗(yàn)1的θs=0°,θe=180°,起始節(jié)點(diǎn)編號(hào)為65,目標(biāo)節(jié)點(diǎn)編號(hào)為1021,仿真結(jié)果如圖7所示。仿真試驗(yàn)2的θs=-90°,θe=135°,起始節(jié)點(diǎn)編號(hào)為65,目標(biāo)節(jié)點(diǎn)編號(hào)為990,仿真結(jié)果如圖8所示。

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

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

[1] 譚寶成,王培.A*路徑規(guī)劃算法的改進(jìn)與實(shí)現(xiàn)[J].西安工業(yè)大學(xué)學(xué)報(bào),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] 戴青.基于遺傳和蟻群算法的機(jī)器人路徑規(guī)劃研究[D].武漢:武漢理工大學(xué),2009.

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

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

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

[8] 王強(qiáng),張安,吳忠杰.改進(jìn)人工勢(shì)場(chǎng)法與模擬退火算法的無(wú)人機(jī)航路規(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] 曹文鋒.基于改進(jìn)蟻群算法的飛行器航跡規(guī)劃研究[D].重慶:重慶大學(xué),2011.

[11] 盧江松.基于改進(jìn)蟻群算法的多機(jī)協(xié)同突防航跡規(guī)劃方法研究[D].長(zhǎng)沙:國(guó)防科學(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;

時(shí)間:2016-11-01 16:48

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

李喜剛(1988-)，男，甘肅靜寧人，碩士研究生，研究方向?yàn)闊o(wú)人機(jī)建模及路徑規(guī)劃。

V279

A

1002-0853(2017)01-0052-05