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

李喜剛, 蔡遠利

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

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

李喜剛, 蔡遠利

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

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

蟻群優化算法; 無人機路徑規劃; 雙向搜索

0 引言

無人機在整個航空領域扮演著越來越重要的角色。為了完成各種民用和軍事任務,無人機控制系統面臨許多難題,比如多機任務協同、路徑規劃、路徑跟蹤等,其中路徑規劃是無人機導航和控制的核心技術。

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

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

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

1 搜索空間建模

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

柵格地圖從左到右、自上而下的編號為:第一行從左至右依次為1,2,3,…,32,第二行從左至右依次為33,34,…,64,依此類推。柵格地圖的網格編號和任務區域的坐標對應關系為:

(1)

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

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

在實際場景中,無人機的飛行路徑還受到最大轉彎角度和任務區域角度的約束。

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

1.1 最大轉彎角度

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

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

1.2 任務區域角度約束

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

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

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

2 改進的ACO路徑規劃算法

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

2.1 改進螞蟻的移動規則

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

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

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

2.2.1 改進信息素揮發系數的更新方式

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

(2)

式中:n為當前迭代的次數;N為設定迭代的總次數。

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

通過引入信息素增量調節因子λ,根據每只螞蟻所求解的優劣程度調節信息素的增量為：

(3)

(4)

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

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

(5)

(6)

2.3 雙向搜索機制

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

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

圖6中可能出現兩種情況。情況一:螞蟻k1的當前位置為p3,螞蟻k2的當前位置為p4,則兩只螞蟻不會相遇,但此時程序檢測到p3已經被螞蟻k2訪問過,所以直接聯合螞蟻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},考慮到無人機的最大轉彎角限制,在路徑結合處做平滑處理,最終得到新路徑path—new={1,12,23,24,25,36,46,57,58,69,79,89,98}。情況二:螞蟻k1的當前位置為p1,螞蟻k2的當前位置為p2或者p3,根據相遇檢測算法,兩只螞蟻在途中相遇了。此時,根據螞蟻k1和k2的已有路徑,考慮到路徑結合處的最大轉彎角度限制,直接生成一條滿足約束條件的可行路徑path—meet={1,12,23,24,25,36,46,57,58,69,79,89,98}。

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

3 仿真結果及分析

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

圖7 仿真試驗1路徑規劃結果Fig.7 Path planning in simulation 1

圖8 仿真試驗2路徑規劃結果Fig.8 Path planning in simulation 2

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

表1 仿真結果對比

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

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

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

4 結束語

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

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

[1] 譚寶成,王培.A*路徑規劃算法的改進與實現[J].西安工業大學學報,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] 戴青.基于遺傳和蟻群算法的機器人路徑規劃研究[D].武漢:武漢理工大學,2009.

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

[6] 樊長虹,陳衛東,席裕庚.未知環境下移動機器人安全路徑規劃的一種神經網絡方法[J].自動化學報,2004,30(6):816-823.

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

[8] 王強,張安,吳忠杰.改進人工勢場法與模擬退火算法的無人機航路規劃[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] 曹文鋒.基于改進蟻群算法的飛行器航跡規劃研究[D].重慶:重慶大學,2011.

[11] 盧江松.基于改進蟻群算法的多機協同突防航跡規劃方法研究[D].長沙:國防科學技術大學,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

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

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

V279

A

1002-0853(2017)01-0052-05