改進(jìn)蟻群算法的無(wú)人機(jī)航跡規(guī)劃

王 瑤, 任安虎, 任洋洋

(西安工業(yè)大學(xué)電子信息工程學(xué)院,西安 710000)

0 引言

無(wú)人機(jī)航跡規(guī)劃需要考慮多方面的因素,包括環(huán)境信息、任務(wù)目標(biāo)等限制條件[1],以確保無(wú)人機(jī)能夠高效地完成任務(wù)。這些因素之間相互作用,需要在規(guī)劃過程中進(jìn)行綜合考慮和權(quán)衡,從而確定最優(yōu)的航跡方案。目前,常見的航跡規(guī)劃算法有粒子群算法[2]、遺傳算法[3]、神經(jīng)網(wǎng)絡(luò)算法[4]、人工勢(shì)場(chǎng)法[5]、蟻群算法[6]、A*算法[7]等。1991年,由DORIGO等[8]提出的蟻群算法相比于其他航跡規(guī)劃算法,具備高效的全局搜索能力、良好的正向反饋機(jī)制、較強(qiáng)的魯棒性以及實(shí)現(xiàn)簡(jiǎn)單[9]等優(yōu)點(diǎn)。但是在進(jìn)行航跡規(guī)劃時(shí)該算法具有易陷入局部最優(yōu)解、收斂速度較慢,容易造成航線質(zhì)量差以及規(guī)劃時(shí)間長(zhǎng)等缺點(diǎn)。

針對(duì)蟻群算法的不足,研究者們進(jìn)行了不同的改進(jìn)。文獻(xiàn)[10]融合改進(jìn)人工勢(shì)場(chǎng)法對(duì)模擬地圖進(jìn)行預(yù)搜索并引入重力勢(shì)能模擬無(wú)人機(jī)的高空飛行,提出新的信息素?fù)]發(fā)因子更新規(guī)則,提高了算法的隨機(jī)性。但是由于引入預(yù)先探索和信息素濃度更新的策略,增加了搜索的時(shí)間成本,從而降低了算法的搜索效率。為了提高算法的搜索效率,文獻(xiàn)[11]采用改進(jìn)局部搜索策略的方法,調(diào)整初始信息素的因子,并在啟發(fā)函數(shù)中引入路徑偏移因子,從而增強(qiáng)了算法在全局搜索方面的能力。但航跡規(guī)劃面對(duì)的環(huán)境具有復(fù)雜和多變的特征,在實(shí)際應(yīng)用中,依靠單一算法很難達(dá)到預(yù)期的結(jié)果。文獻(xiàn)[12]改進(jìn)了蟻群算法中信息素的更新規(guī)則,并將其與遺傳算法進(jìn)行融合。融合方案獲得的路徑長(zhǎng)度比遺傳算法和蟻群算法的都要短。針對(duì)蟻群算法收斂性差的問題,文獻(xiàn)[13]在傳統(tǒng)蟻群算法的基礎(chǔ)上引入了目標(biāo)節(jié)點(diǎn)信息素的引導(dǎo)因子,以引導(dǎo)螞蟻朝著目標(biāo)節(jié)點(diǎn)進(jìn)行搜索,從而降低搜索的盲目性。同時(shí),還采用了再激勵(lì)學(xué)習(xí)機(jī)制更新信息素,使得算法具有更快的收斂速度及更好的搜索效果。

從以上的改進(jìn)可以看出,研究者們都致力于使算法具有更快的收斂速度,讓無(wú)人機(jī)能夠在最短的時(shí)間內(nèi)到達(dá)目標(biāo)位置。基于以上啟發(fā),本文提出一種改進(jìn)的啟發(fā)式蟻群算法,該算法在保留了傳統(tǒng)蟻群算法的基本框架和優(yōu)點(diǎn)下,通過進(jìn)行初始信息素不均衡分配、優(yōu)化狀態(tài)轉(zhuǎn)移規(guī)則以及動(dòng)態(tài)調(diào)整信息素?fù)]發(fā)系數(shù),有效避免了蟻群算法易陷入局部最優(yōu)及收斂速度慢等問題。

1 無(wú)人機(jī)航跡規(guī)劃建模

1.1 二維環(huán)境建模

1.1.1 模型簡(jiǎn)化

航跡規(guī)劃是為了確保無(wú)人機(jī)在執(zhí)行任務(wù)時(shí)能夠按照規(guī)定的路徑安全、高效地飛行。在這個(gè)過程中,無(wú)人機(jī)應(yīng)該是在三維環(huán)境中執(zhí)行飛行任務(wù),但是,當(dāng)無(wú)人機(jī)在執(zhí)行某些特定的任務(wù)時(shí),不需要考慮高度的變化,只需保持在固定的飛行高度。因此,可以將航跡規(guī)劃問題從三維空間轉(zhuǎn)化為二維平面,以簡(jiǎn)化計(jì)算和優(yōu)化航跡規(guī)劃過程。本文對(duì)無(wú)人機(jī)在高速公路上穿越地形障礙,躲避禁飛區(qū)域進(jìn)行航跡規(guī)劃,將無(wú)人機(jī)的飛行環(huán)境做如下簡(jiǎn)化和假設(shè)[14]:1) 簡(jiǎn)化模型,將無(wú)人機(jī)簡(jiǎn)化為質(zhì)點(diǎn);2) 假設(shè)無(wú)人機(jī)在執(zhí)行任務(wù)時(shí),需要在規(guī)定的二維平面中保持固定的飛行高度和速度,并按照預(yù)設(shè)的航跡路線進(jìn)行移動(dòng);3) 假設(shè)地形障礙,禁飛區(qū)域已知,在進(jìn)行環(huán)境建模時(shí)用黑色代表地形障礙以及禁飛區(qū)。

1.1.2 建模

航跡規(guī)劃中常見的二維環(huán)境建模方法有可視圖法[15]、Voronoi圖法[16]和柵格圖法[17]。柵格圖法與其他兩種方法相比,在構(gòu)建環(huán)境模型時(shí)方法簡(jiǎn)單且易于修改。此外,柵格法具有良好的適應(yīng)性,并且易于計(jì)算機(jī)存儲(chǔ)和處理。故本文采用柵格圖法建立二維空間模型。

構(gòu)建圖1所示20×20的二維空間模型,0表示可通行的區(qū)域(即白色網(wǎng)格單元),1表示障礙物(即黑色網(wǎng)格單元)。

圖1 二維空間模型

1.2 三維環(huán)境建模

為了使研究結(jié)果更具有現(xiàn)實(shí)意義,不僅要在二維環(huán)境中對(duì)算法進(jìn)行對(duì)比驗(yàn)證,還應(yīng)該在三維環(huán)境中進(jìn)行仿真實(shí)驗(yàn)。本文采用柵格化的方法對(duì)三維環(huán)境進(jìn)行建模,首先將三維空間切片分層處理,然后再將每個(gè)切片劃分為若干個(gè)柵格。這種柵格化方法可以提高路徑規(guī)劃的效率和精度,同時(shí)減少無(wú)人機(jī)的碰撞風(fēng)險(xiǎn)。

三維空間劃分如圖2所示。

圖2 三維空間劃分

首先建立三維直角坐標(biāo)系O-XYZ。在三維直角坐標(biāo)系中構(gòu)造一個(gè)立體空間ABCD-EFGH,該立體空間的底面為ABCD,頂面為EFGH,表示無(wú)人機(jī)飛行的最高高度,其中,AB和AD的長(zhǎng)度分別等于飛行空間的長(zhǎng)度和寬度。將該立體空間沿著高度方向(Z軸)劃分為l個(gè)切片平面,接著,將l個(gè)切片平面劃分為m×n個(gè)柵格,從而將規(guī)劃空間劃分為n×m×l個(gè)柵格。

2 蟻群算法

2.1 轉(zhuǎn)移概率公式

在蟻群算法模型中,螞蟻根據(jù)狀態(tài)轉(zhuǎn)移公式選擇下一個(gè)可行的節(jié)點(diǎn),狀態(tài)轉(zhuǎn)移表示為

(1)

(2)

式中,dij為2個(gè)節(jié)點(diǎn)之間的歐氏距離。當(dāng)距離越小時(shí),啟發(fā)函數(shù)所提供的信息越詳盡豐富,即啟發(fā)信息量越大。距離與啟發(fā)信息量之間呈現(xiàn)反比例關(guān)系。

2.2 信息素更新規(guī)則

信息素更新規(guī)則表示為

(3)

(4)

式中:Q為信息素強(qiáng)度,是一個(gè)固定的常量,用于控制信息素增強(qiáng)的速度和程度;Lk為第k只螞蟻在一次循環(huán)中走過的總路徑長(zhǎng)度。

3 改進(jìn)蟻群算法

3.1 初始信息素濃度不均衡分配

在傳統(tǒng)蟻群算法中,初始信息素分布通常是均勻的,這意味著所有路徑上的信息素濃度都相等,這種情況下搜索初期所有路徑的被選擇概率相同,不利于算法搜索的多樣性,而且存在一定盲目性。為了加快算法的尋優(yōu)能力,本文采用有針對(duì)性的不均衡分配信息素的策略。利用A*算法快速的全局規(guī)劃能力且便于和其他算法相結(jié)合的優(yōu)勢(shì),首先利用A*算法規(guī)劃出一條較優(yōu)路徑,使該條路徑上的信息素濃度高于其他路徑,避免初期搜索的盲目性。

3.2 狀態(tài)轉(zhuǎn)移規(guī)則的改進(jìn)

無(wú)人機(jī)在飛行過程中,不僅要在最短時(shí)間內(nèi)到達(dá)目的地,還要保證其飛行距離最短。在初始路徑搜索階段,每條路徑上經(jīng)過的螞蟻數(shù)量較少,螞蟻在選擇下一節(jié)點(diǎn)時(shí)傾向于隨機(jī)選擇,為了防止螞蟻在搜索過程中選擇與目的地相反的方向從而影響算法的收斂速度,本文引入了一種啟發(fā)式因子δij(t),即

(5)

式中,θ(0≤θ≤π)為目標(biāo)的傾斜角度,表示螞蟻從當(dāng)前位置到下一節(jié)點(diǎn)與當(dāng)前位置到目標(biāo)點(diǎn)連線之間位移的夾角。改進(jìn)后的狀態(tài)轉(zhuǎn)移概率表示為

(6)

式中,γ為啟發(fā)式因子的重要程度。當(dāng)θ較小時(shí),δij(t)較大,狀態(tài)轉(zhuǎn)移概率就越大,螞蟻選擇該路徑的概率就越大。

3.3 信息素?fù)]發(fā)因子優(yōu)化

傳統(tǒng)蟻群算法在尋優(yōu)過程中,其信息素?fù)]發(fā)系數(shù)ρ通常是一個(gè)定值,但是蟻群算法的尋優(yōu)過程是一個(gè)正反饋的循序漸進(jìn)的過程,定量的揮發(fā)信息素滿足不了這一動(dòng)態(tài)過程的需求,而且蟻群算法本身容易陷入局部最優(yōu),因此,為了避免算法陷入局部最優(yōu)的同時(shí)提高算法的收斂速度,本文引入高斯函數(shù)設(shè)計(jì)了一種信息素?fù)]發(fā)系數(shù)的調(diào)整策略,表示為

(7)

(8)

式中:i為當(dāng)前迭代次數(shù);imax為最大迭代次數(shù);ε>1,為信息素衰減系數(shù)。信息素?fù)]發(fā)系數(shù)的調(diào)整策略是在搜索開始時(shí)具有較大的ρ,增加了算法的全局搜索能力,避免了算法過早陷入局部最優(yōu)。隨著迭代次數(shù)的增加,ρ在后期迅速下降,局部搜索能力變得更強(qiáng),有助于螞蟻找到最優(yōu)路徑。改進(jìn)后的信息素?fù)]發(fā)因子可以根據(jù)搜索進(jìn)行的不同程度,動(dòng)態(tài)地調(diào)整信息素?fù)]發(fā)系數(shù)的大小,提高了算法的性能,增加了蟻群算法的魯棒性。

3.4 算法步驟

改進(jìn)蟻群算法的航跡規(guī)劃步驟如下。

1) 環(huán)境建模。建立二維和三維環(huán)境模型,設(shè)置無(wú)人機(jī)的起始點(diǎn)和目標(biāo)點(diǎn)。

2) 設(shè)定初始的螞蟻系統(tǒng)和相關(guān)參數(shù)。設(shè)置螞蟻數(shù)量m,確定信息素權(quán)重因子α,確定啟發(fā)權(quán)重因子β,全局信息素?fù)]發(fā)系數(shù)ρ以及信息素強(qiáng)度Q等相關(guān)參數(shù)。

3) 利用A*算法規(guī)劃出一條較優(yōu)路徑,使得初始的信息素分布不均勻。

4) 將m只螞蟻放在起始位置上,開始進(jìn)行路徑搜索。

5) 選擇下一個(gè)節(jié)點(diǎn)。根據(jù)式(2)計(jì)算啟發(fā)式信息量,根據(jù)式(6)計(jì)算轉(zhuǎn)移概率,選擇下一個(gè)可行的節(jié)點(diǎn)。

6) 當(dāng)所有螞蟻完成一次迭代之后,根據(jù)式(7)調(diào)整信息素?fù)]發(fā)系數(shù),然后根據(jù)式(3)更新信息素含量,否則返回執(zhí)行步驟5)。

7) 判斷是否滿足收斂條件,如果滿足,則退出并輸出最終結(jié)果,否則返回執(zhí)行步驟3)。

4 仿真實(shí)驗(yàn)與結(jié)果分析

4.1 實(shí)驗(yàn)環(huán)境

本仿真實(shí)驗(yàn)運(yùn)行在一臺(tái)搭載有Intel Core i7-6600U處理器、主頻為2.60 GHz、內(nèi)存為8.00 GiB的計(jì)算機(jī)上。

4.2 參數(shù)設(shè)置

為保證仿真結(jié)果的準(zhǔn)確性,參與對(duì)比的算法均在相同的參數(shù)下進(jìn)行仿真測(cè)試,初始參數(shù)值設(shè)置如表1所示。

表1 參數(shù)設(shè)置

4.3 仿真實(shí)驗(yàn)結(jié)果分析

為了驗(yàn)證本文改進(jìn)蟻群算法在無(wú)人機(jī)航跡規(guī)劃問題中的可行性,本文分別在二維環(huán)境和三維環(huán)境下對(duì)傳統(tǒng)蟻群算法、本文算法、傳統(tǒng)A*算法、文獻(xiàn)[7]算法進(jìn)行仿真實(shí)驗(yàn)來(lái)評(píng)估改進(jìn)蟻群算法的性能。

4.3.1 二維環(huán)境仿真實(shí)驗(yàn)分析

二維環(huán)境下仿真結(jié)果如圖3所示。

圖3 二維環(huán)境下仿真結(jié)果

對(duì)于二維環(huán)境模型,4種算法的性能評(píng)估如表2所示。

表2 4種算法性能評(píng)估(二維環(huán)境)

上述實(shí)驗(yàn)是在障礙物較多的20×20的柵格地圖中進(jìn)行的。從圖3(a)和圖3(b)可以看出,傳統(tǒng)蟻群算法的收斂過程不穩(wěn)定,所規(guī)劃的航跡出現(xiàn)了較多的轉(zhuǎn)彎和拐點(diǎn),導(dǎo)致無(wú)人機(jī)頻繁地變更方向,增加了油耗和飛行時(shí)間,從而影響飛行效率;另外,拐點(diǎn)的出現(xiàn)也表明當(dāng)全局搜索空間增大時(shí),傳統(tǒng)蟻群算法的性能容易受到局部最優(yōu)解的影響。

從圖3(c)和圖3(d)可以看出,改進(jìn)后的蟻群算法可以減少航跡上的拐點(diǎn)和轉(zhuǎn)彎,使得飛行路線更加順暢和自然;而且本文算法在第12代就收斂得到最優(yōu)解,相比于傳統(tǒng)蟻群算法能夠快速地向最優(yōu)解靠近,算法的收斂速度得到了提升。從表2的仿真結(jié)果數(shù)據(jù)可以看出,本文算法航跡長(zhǎng)度較傳統(tǒng)蟻群算法縮短了12.05%,較傳統(tǒng)A*算法縮短了9.29%,較文獻(xiàn)[7]算法縮短了3.64%;同時(shí),與其他3種算法相比本文算法的拐點(diǎn)數(shù)目相對(duì)較少,得到的航跡更平滑。綜上所述,本文所提算法有效提升了航跡規(guī)劃的效果。

4.3.2 三維環(huán)境仿真實(shí)驗(yàn)分析

無(wú)人機(jī)的初始位置坐標(biāo)為(1 km,1 km,1 m),終點(diǎn)位置坐標(biāo)為(100 km,100 km,60 m)。三維環(huán)境下仿真結(jié)果如圖4所示。

圖4 三維環(huán)境下的仿真結(jié)果

對(duì)于三維環(huán)境模型,4種算法的性能評(píng)估如表3所示。

表3 4種算法性能評(píng)估(三維環(huán)境)

從圖4(b)和圖4(d)可以看出,在三維空間環(huán)境模型中,傳統(tǒng)蟻群算法在第36代左右得到最優(yōu)解,而本文算法在第4代就收斂得到最優(yōu)解,收斂速度提升了88.89%。從表3的數(shù)據(jù)可以看到,本文算法航跡長(zhǎng)度比傳統(tǒng)蟻群算法縮短了6.42%,比傳統(tǒng)A*算法縮短了6.16%,比文獻(xiàn)[7]算法縮短了1.39%。由此可知,本文所提的改進(jìn)算法可以有效提高蟻群算法的性能,在保證快速收斂的前提下,算法的搜索能力以及尋找最優(yōu)解的能力都得到提升,有效解決了其他算法收斂速度慢、易陷入局部最優(yōu)的問題。

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

基于傳統(tǒng)蟻群算法提出一種改進(jìn)的蟻群算法,旨在解決傳統(tǒng)蟻群算法容易受限于局部最優(yōu)、收斂速度緩慢等問題。通過對(duì)初始信息素進(jìn)行不均衡分配、狀態(tài)轉(zhuǎn)移規(guī)則以及信息素?fù)]發(fā)因子的優(yōu)化,進(jìn)行二維環(huán)境和三維環(huán)境的仿真實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果表明,改進(jìn)后的算法在搜索過程中能夠克服傳統(tǒng)蟻群算法在局部最優(yōu)解附近停滯的問題,能夠更加全面地搜索解空間,具有更快的收斂速度,可以有效避免算法陷入局部最優(yōu)。本文的研究主要是在靜態(tài)環(huán)境下進(jìn)行的,在接下來(lái)的工作中可以將優(yōu)化算法拓展應(yīng)用到動(dòng)態(tài)環(huán)境中。