自適應(yīng)多啟發(fā)蟻群算法的無人機(jī)路徑規(guī)劃

尹雅楠 甄然 武曉晶 張春悅 吳學(xué)禮

摘 要：為了解決蟻群算法在無人機(jī)實(shí)現(xiàn)路徑規(guī)劃中容易陷入局部最優(yōu)的問題，提出改進(jìn)的蟻群算法。對信息素的揮發(fā)因子以及信息素進(jìn)行上、下限設(shè)置，防止由于較短路徑上的信息素過高以及較長路徑上的信息素過低，使螞蟻陷入局部最優(yōu)，同時(shí)在多啟發(fā)因素的影響下，將路徑的整體長度作為決定狀態(tài)轉(zhuǎn)移概率的一個(gè)自適應(yīng)啟發(fā)函數(shù)因子，當(dāng)路徑長度很大時(shí)，自適應(yīng)啟發(fā)函數(shù)因子較小，使得蟻群選擇該路徑的概率減小。實(shí)驗(yàn)結(jié)果表明，改進(jìn)的算法在路徑長度上減少了6.4%，最優(yōu)路徑長度方差降低了85.78%，增加了對環(huán)境整體性的考慮，縮短了路徑長度，降低了迭代次數(shù)，跳出局部最優(yōu)。在環(huán)境復(fù)雜度加大的情況下，引入自適應(yīng)啟發(fā)函數(shù)因子之后的算法可以有效地選擇較好的路徑，為無人機(jī)路徑規(guī)劃提供了理論依據(jù)。

關(guān)鍵詞：航空、航天科學(xué)技術(shù)基礎(chǔ)學(xué)科其他學(xué)科;無人機(jī);蟻群算法;路徑規(guī)劃;啟發(fā)因素

中圖分類號：TP301.6;V279?文獻(xiàn)標(biāo)識(shí)碼：A

文章編號：1008-1542（2021）01-0038-10

隨著現(xiàn)代科技的發(fā)展，無人機(jī)可執(zhí)行的任務(wù)逐漸增多，例如無人機(jī)可以承擔(dān)起運(yùn)輸醫(yī)療救援包等應(yīng)急物資的任務(wù)[1]。為了使無人機(jī)能夠更好地在實(shí)際中應(yīng)用，學(xué)者對無人機(jī)的路徑規(guī)劃進(jìn)行了大量的研究，提出了很多算法來提高路徑規(guī)劃的效率，目前有人工勢場法[2]、A*算法[3]、蟻群算法[4]、遺傳算法[5]、粒子群算法[6]、蝙蝠算法[7]、模擬退火法[8]、快速擴(kuò)展隨機(jī)樹算法[9]、D*算法[10]、人工魚群算法[11]、蝗蟲算法[12]以及螢火蟲算法[13]等。遺傳算法是用編碼來表示問題的解，在編碼進(jìn)行選擇、交叉、變異等操作之后，將適應(yīng)度函數(shù)的值作為進(jìn)化的評價(jià)依據(jù)，最后得到最優(yōu)的種群，也就是問題的解[14]。蟻群算法與遺傳算法在選擇最優(yōu)解時(shí)，操作相似。蟻群算法也是通過迭代尋找最優(yōu)解，但是蟻群算法在選擇最優(yōu)解時(shí)沒有交叉和變異這2個(gè)操作，所以求解更簡單。

蟻群算法是一種基于啟發(fā)的搜索算法，是由DORIGO等于20世紀(jì)90年代初通過模擬螞蟻群在環(huán)境中的覓食行為而提出的算法[15]。蟻群算法具有正反饋、并行計(jì)算、魯棒性好等特點(diǎn)[16]，許多學(xué)者在研究路徑規(guī)劃方面的問題時(shí)，將蟻群算法應(yīng)用其中，并且得到了較好的結(jié)果。蟻群算法搜索范圍廣，有較快的收斂速度，可以應(yīng)用在離散優(yōu)化的問題上[17]，但是由于該算法具有正反饋特性，可能會(huì)造成局部路徑上的信息素堆積，從而存在陷入局部最優(yōu)等問題[18-19]。蟻群算法通過將當(dāng)前位置與下一位置之間的距離作為啟發(fā)信息，當(dāng)遇到障礙物時(shí)，在提前躲避障礙物方面還存在一些問題[16]。對于蟻群算法的不足，許多學(xué)者對算法本身的不足進(jìn)行改進(jìn)。隨著研究的不斷深入，結(jié)合路徑規(guī)劃的特性，學(xué)者將如何提高算法的搜索效率作為研究的重點(diǎn)[20]。

路徑平滑能夠降低無人機(jī)的飛行風(fēng)險(xiǎn)，HUANG等[21]引入K度平滑方法，生成光滑的路徑。TAO等[22]因當(dāng)前節(jié)點(diǎn)與多個(gè)相鄰節(jié)點(diǎn)的距離完全相等，導(dǎo)致在選擇下一個(gè)節(jié)點(diǎn)時(shí)啟發(fā)不能發(fā)揮重要作用，于是提出將起始點(diǎn)與目標(biāo)點(diǎn)之間的最短距離作為路徑搜索的引導(dǎo)，通過計(jì)算當(dāng)前節(jié)點(diǎn)和下一個(gè)待走節(jié)點(diǎn)的距離和下一個(gè)待走節(jié)點(diǎn)到最短路徑的垂直距離的加權(quán)和的倒數(shù)，加快了算法的搜索。孫功武等[23]設(shè)計(jì)了一種自適應(yīng)啟發(fā)函數(shù)，該啟發(fā)函數(shù)引入了當(dāng)前柵格與待走柵格的距離以及待走柵格到目標(biāo)柵格的距離選擇較好的節(jié)點(diǎn)，但是該自適應(yīng)啟發(fā)函數(shù)只考慮當(dāng)前柵格以及待走柵格到目標(biāo)柵格的距離。黃心等[24]根據(jù)多尺度路徑搜索的思路，提出了改進(jìn)后的引導(dǎo)因子，該引導(dǎo)因子考慮了節(jié)點(diǎn)到目標(biāo)點(diǎn)的距離以及節(jié)點(diǎn)到起始點(diǎn)的距離，同時(shí)通過地形的高度決定無人機(jī)的飛行，但只局部考慮了啟發(fā)函數(shù)的引導(dǎo)作用。李理等[25]在路徑平滑問題上，將轉(zhuǎn)彎次數(shù)引入啟發(fā)函數(shù)中，對改進(jìn)的啟發(fā)函數(shù)進(jìn)行影響，同時(shí)對信息素的更新方式也進(jìn)行了改進(jìn)，路徑平滑性得到較大提高，收斂性和全局搜索能力都較好，但是轉(zhuǎn)移概率只受信息素和啟發(fā)函數(shù)的影響，迭代次數(shù)較大，容易陷入局部最優(yōu)。

文獻(xiàn)[21]在對路徑平滑問題上引入K度平滑方法，而文獻(xiàn)[25]不僅將平滑問題考慮到啟發(fā)函數(shù)中，還將路徑的轉(zhuǎn)彎次數(shù)考慮到啟發(fā)函數(shù)中;文獻(xiàn)[22]對轉(zhuǎn)移概率進(jìn)行了改進(jìn)，保證了算法的收斂速度，以提高算法的性能，但是所得到的路徑長度不是最短的;文獻(xiàn)[23]根據(jù)當(dāng)前柵格與目標(biāo)柵格的距離設(shè)計(jì)了自適應(yīng)啟發(fā)函數(shù)，但是只考慮了路徑長度這一因素，文獻(xiàn)[25]的啟發(fā)函數(shù)考慮了多個(gè)啟發(fā)因素;文獻(xiàn)[24]將節(jié)點(diǎn)的引導(dǎo)因子引入到轉(zhuǎn)移概率中進(jìn)行改進(jìn)，但是沒有對啟發(fā)因素進(jìn)行改進(jìn)。文獻(xiàn)[25]在使路徑盡可能短的同時(shí)，對路徑的轉(zhuǎn)彎次數(shù)以及路徑平緩性進(jìn)行考慮，進(jìn)而提出了將距離修正函數(shù)、安全性函數(shù)以及平滑性函數(shù)這3種因素考慮到啟發(fā)函數(shù)中的多啟發(fā)因素蟻群算法。在螞蟻尋找最優(yōu)路徑時(shí)，以多啟發(fā)因素為基礎(chǔ)選擇路徑。

但是文獻(xiàn)[25]中的路徑因素只考慮了當(dāng)前柵格的各個(gè)鄰接?xùn)鸥竦侥繕?biāo)柵格的距離，沒有從路徑的整體性考慮。本文在多啟發(fā)因素的作用下，從路徑的整體性考慮，將文獻(xiàn)[24]的引導(dǎo)因子引入轉(zhuǎn)移概率中，并對啟發(fā)函數(shù)、信息素和信息素?fù)]發(fā)因子進(jìn)行處理，增加算法的準(zhǔn)確性。仿真結(jié)果表明，該方法提高了路徑搜索效率，降低了迭代次數(shù)，路徑長度得到改善。

1?環(huán)境建模

本文采用二維柵格法[26]對路徑環(huán)境建模?？紤]到無人機(jī)的安全問題，將無人機(jī)路徑與柵格障礙物之間的距離定為柵格長度的一半。每個(gè)柵格有8個(gè)鄰接?xùn)鸥馵27]可以走，如圖1所示。dis（i，j）表示當(dāng)前柵格i到其第j個(gè)鄰接?xùn)鸥竦木嚯x。

螞蟻選擇下一柵格的流程如下。

2?多啟發(fā)因素

文獻(xiàn)[25]基于路徑規(guī)劃需要路徑長度短、轉(zhuǎn)彎的次數(shù)不宜過多、路徑盡量平緩以及適應(yīng)環(huán)境性等問題，提出將距離修正函數(shù)、安全性函數(shù)以及平滑性函數(shù)這3種因素考慮到啟發(fā)函數(shù)中。距離修正函數(shù)使當(dāng)前柵格的各個(gè)鄰接?xùn)鸥竦侥繕?biāo)柵格的距離差值增大，在選擇下一個(gè)待走柵格時(shí)，增加路徑長度對螞蟻的啟發(fā)。安全性函數(shù)對無人機(jī)飛行中的轉(zhuǎn)彎有一定的引導(dǎo)作用，當(dāng)無人機(jī)當(dāng)前的方向與上一時(shí)刻的方向相同時(shí)，該方向的安全性函數(shù)值就較大。平滑性函數(shù)會(huì)給無人機(jī)選擇平緩路徑的啟發(fā)。

2.1?距離修正函數(shù)

2.2?安全性函數(shù)

在無人機(jī)飛行過程中，如果規(guī)劃的路徑轉(zhuǎn)彎次數(shù)較多，不僅使無人機(jī)飛行的路徑距離增加，還會(huì)增加無人機(jī)飛行的危險(xiǎn)程度。盡可能地減少無人機(jī)的轉(zhuǎn)彎次數(shù)，對路徑規(guī)劃來說是有必要的。

式中：j∈allowedi;rij（t）為安全性函數(shù);u為啟發(fā)常數(shù);θ表示安全性的重要程度;visitedi為第t次迭代過程中，第k只螞蟻?zhàn)叩疆?dāng)前第i號柵格時(shí)所走過的柵格號的集合;v為當(dāng)前第i號柵格的上一個(gè)柵格的標(biāo)號，v=visitedi（end-1）;J（allowedi）表示當(dāng)前柵格的可行鄰接?xùn)鸥竦臄?shù)量;drvi（t）表示在第t次迭代時(shí)，從第v號到第i號柵格的方向轉(zhuǎn)向;drij（t）表示在第t次迭代時(shí)，從第i號到第j號柵格的方向轉(zhuǎn)向。通過drvi（t）和drij（t）的比較，如果兩者相同，則會(huì)增大下一步沿同一個(gè)方向走的可能性，從而使路線能夠較好地保持直線。

2.3?平滑性函數(shù)

式中：hmax為當(dāng)前第i個(gè)柵格的高度與其鄰接?xùn)鸥竦母叨戎畹淖畲笾?hmin為當(dāng)前第i個(gè)柵格的高度與其鄰接?xùn)鸥竦母叨戎畹淖钚≈?h（i）為柵格高度。

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

本文讓蟻群在構(gòu)建的柵格圖中根據(jù)信息素、啟發(fā)函數(shù)以及轉(zhuǎn)移概率，從當(dāng)前柵格的8個(gè)相鄰柵格中選擇下一個(gè)要走的柵格，尋找一條從起始點(diǎn)到目的點(diǎn)最近的路徑。在蟻群開始尋找路徑之前每柵格的信息素是相同的，螞蟻通過轉(zhuǎn)移概率選擇下一個(gè)待走柵格行走，走過的路徑會(huì)留下信息素，沒有走過的路徑的信息素會(huì)在迭代中不斷減少。同時(shí)間內(nèi)，較短路徑上的螞蟻很快就找到食物，而較長路徑上的螞蟻找到食物較慢。因此，較短路徑上螞蟻留下的信息素總和較多，從而吸引更多的螞蟻來走這條路徑，也就找到了最短路徑。

3.1?轉(zhuǎn)移概率

蟻群算法的轉(zhuǎn)移概率受啟發(fā)函數(shù)和螞蟻留下的信息素這2個(gè)因素影響。在實(shí)際環(huán)境中有障礙物存在，多啟發(fā)函數(shù)可以使螞蟻對障礙物進(jìn)行躲避、選擇較短的路徑以及減少轉(zhuǎn)彎次數(shù)等。存在較多信息素的路徑會(huì)引導(dǎo)許多螞蟻選擇該路徑，當(dāng)過多的螞蟻從同一條路徑行走時(shí)，在螞蟻沒有找到最優(yōu)路徑的情況下，認(rèn)為當(dāng)前路徑為全局最優(yōu)，從而使螞蟻陷入局部最優(yōu)。

3.1.1?自適應(yīng)啟發(fā)函數(shù)因子

為了能夠提高螞蟻搜索路徑的效率，跳出局部最優(yōu)，本文在轉(zhuǎn)移概率中引入了自適應(yīng)啟發(fā)函數(shù)因子，見式（5）。自適應(yīng)啟發(fā)函數(shù)因子是待走柵格到起始柵格的距離與待走柵格到目的柵格的距離和的加權(quán)倒數(shù)。在待走柵格與目標(biāo)柵格距離的基礎(chǔ)上，再加上待走柵格到起始柵格的距離，即在考慮該待走柵格是否為最佳待走柵格時(shí)，將自適應(yīng)啟發(fā)函數(shù)因子作為轉(zhuǎn)移概率的影響因素之一，增加對環(huán)境的整體性考慮。

式中：μij為自適應(yīng)啟發(fā)函數(shù)因子;dAj為起始點(diǎn)與待走柵格的距離;A為起始點(diǎn);j為待走柵格標(biāo)號;djE為待走柵格與目的點(diǎn)的距離;E為目的點(diǎn);a，b為權(quán)重系數(shù)。待走柵格與起始點(diǎn)以及待走柵格與目的點(diǎn)的距離越小，自適應(yīng)啟發(fā)函數(shù)因子越大，轉(zhuǎn)移概率相應(yīng)地越大，從而能較好地選擇較短的路徑。

通過對轉(zhuǎn)移概率引入自適應(yīng)啟發(fā)函數(shù)因子，使得螞蟻盡可能地選擇最短路徑，加快搜索路徑的效率。

3.1.2?改進(jìn)的轉(zhuǎn)移概率

改進(jìn)后的轉(zhuǎn)移概率：

式中：k為螞蟻的標(biāo)號;i為當(dāng)前柵格號;j為將要走的下一個(gè)柵格號;t為當(dāng)前的迭代次數(shù);τ為信息素強(qiáng)度;η為啟發(fā)函數(shù);α為信息素重要程度因子;β為啟發(fā)因子;allowedk為螞蟻k下一步可以選擇的柵格。后面的螞蟻會(huì)根據(jù)前面螞蟻留下的信息素來其行走進(jìn)行引導(dǎo)，路徑越短，螞蟻留下的信息素越多，信息素同時(shí)也會(huì)蒸發(fā)，信息素的更新方式如下：

3.2?啟發(fā)函數(shù)

在啟發(fā)函數(shù)中加入當(dāng)前柵格到其鄰接?xùn)鸥竦臍W式距離，作為影響啟發(fā)函數(shù)因素之一。通過距離修正函數(shù)，在當(dāng)前柵格的鄰接?xùn)鸥裰羞x一個(gè)距離目標(biāo)柵格最近的鄰接?xùn)鸥瘛．?dāng)前柵格到其鄰接?xùn)鸥竦木嚯x不完全相同，為了能夠更加準(zhǔn)確地考慮路徑長度對蟻群選擇下一柵格的影響，在啟發(fā)函數(shù)中加入當(dāng)前柵格到其鄰接?xùn)鸥竦臍W式距離d（i，j）。當(dāng)d（i，j）距離較大時(shí)，[SX（]1d（i，j）[SX）]的值則會(huì)減小，使得多啟發(fā)函數(shù)值ηij（t）減小，進(jìn)而影響轉(zhuǎn)移概率的值，構(gòu)成了一個(gè)閉環(huán)反饋。啟發(fā)函數(shù)見式（12）。

4?算法仿真

4.1?算法流程

步驟1：對柵格地圖進(jìn)行構(gòu)建，設(shè)置起始點(diǎn)A和目的點(diǎn)E的坐標(biāo)。

步驟2：初始化參數(shù)，將所有螞蟻放在起始點(diǎn)上，構(gòu)建禁忌表。

步驟3：根據(jù)式（12）計(jì)算啟發(fā)函數(shù)以及根據(jù)式（6）計(jì)算轉(zhuǎn)移概率來確定螞蟻下一個(gè)要走的柵格，將走過的柵格號放禁忌表中。當(dāng)螞蟻到達(dá)目的點(diǎn)時(shí)，即完成一次搜索，記錄本次迭代的最優(yōu)路徑。

步驟4：根據(jù)式（9）對信息素進(jìn)行更新。

步驟5：對各次迭代的最優(yōu)路徑進(jìn)行比較，確定目前最優(yōu)路徑。

步驟6：判斷迭代次數(shù)是否達(dá)到最大，若達(dá)到最大，則輸出結(jié)果，否則繼續(xù)進(jìn)行迭代。

根據(jù)以上步驟的描述，給出部分改進(jìn)蟻群算法的偽代碼如下：

算法流程圖見圖4。

4.2?參數(shù)設(shè)定

為了能夠更好地進(jìn)行數(shù)據(jù)對比，本文參數(shù)的選取是在對比算法所采用參數(shù)的基礎(chǔ)上進(jìn)行的更改，并根據(jù)經(jīng)驗(yàn)不斷地運(yùn)行調(diào)試，找到合適的數(shù)值。初始化參數(shù)見表1。

4.3?仿真比較

為了提高轉(zhuǎn)移概率的可靠性，本文對轉(zhuǎn)移概率進(jìn)行了改善，引入了自適應(yīng)啟發(fā)函數(shù)因子，并將當(dāng)前柵格到其鄰接?xùn)鸥竦臍W式距離作為啟發(fā)函數(shù)的影響因素之一。

由于本文采用的算法是一種啟發(fā)式隨機(jī)優(yōu)化方法，為了驗(yàn)證

算法改進(jìn)之后的有效性，本文用MATLAB7將改進(jìn)的算法與文獻(xiàn)[25]進(jìn)行了30次的仿真比較，研究的地形環(huán)境分別在10×10以及30×30的柵格障礙物地圖上。

4.3.1?10×10柵格環(huán)境下的仿真

如圖5所示，虛線為文獻(xiàn)[25]的最優(yōu)路徑，實(shí)線為本文改進(jìn)蟻群算法的最優(yōu)路徑，從圖中可看出路徑大部分是重疊的。但是從路徑整體效果來看，實(shí)線的轉(zhuǎn)彎次數(shù)為4次，虛線轉(zhuǎn)彎次數(shù)為6次。在虛線第4次轉(zhuǎn)彎時(shí)，實(shí)線保持原路徑方向繼續(xù)前進(jìn)，路徑的平滑性較好。

圖6為不同迭代次數(shù)時(shí)最優(yōu)路徑長度的比較。在開始時(shí)，實(shí)線的路徑長度比虛線的路徑長度長，但是在進(jìn)行迭代之后，實(shí)線較快地找到了較短路徑，而虛線在相同迭代次數(shù)下，找到的路徑長度并不是最佳的。

圖7為不同迭代次數(shù)時(shí)最優(yōu)路徑的高度均方差的比較。開始時(shí)，實(shí)線與虛線的初始值相同，隨著迭代次數(shù)的增加，可以看出實(shí)線的高度均方差在迭代5次以內(nèi)達(dá)到穩(wěn)定值，而虛線在迭代5次以外達(dá)到穩(wěn)定值。

圖8為不同迭代次數(shù)時(shí)最優(yōu)路徑的轉(zhuǎn)彎次數(shù)的比較。從圖8中可以看出，實(shí)線和虛線初始在同一迭代次數(shù)下，轉(zhuǎn)彎次數(shù)是相同的，當(dāng)?shù)螖?shù)大于5時(shí)，隨著迭代次數(shù)的增加，引入自適應(yīng)啟發(fā)函數(shù)因子的實(shí)線得到一個(gè)新的較少的轉(zhuǎn)彎次數(shù)，而虛線保持原來的轉(zhuǎn)彎次數(shù)，表明改進(jìn)的蟻群算法增加了蟻群對路徑環(huán)境的整體性考慮，跳出了局部最優(yōu)。

圖9為不同迭代次數(shù)時(shí)最優(yōu)路徑的綜合指標(biāo)以及平均綜合指標(biāo)的比較，綜合指標(biāo)即為距離修正函數(shù)、安全性函數(shù)以及平滑性函數(shù)的綜合評價(jià)，指標(biāo)越低則算法越優(yōu)。從圖9可以看出，本文改進(jìn)算法最優(yōu)路徑的綜合指標(biāo)在初始時(shí)的值較大，隨著迭代次數(shù)的增加，較快地收斂到穩(wěn)定值。

通過表2可以看出，本文的改進(jìn)算法降低了迭代次數(shù)，綜合指標(biāo)相對較小。為了減少算法隨機(jī)性對實(shí)驗(yàn)結(jié)果帶來的影響，本文在運(yùn)行30次的情況下，對最優(yōu)解的平均值以及方差進(jìn)行了計(jì)算，如表2中的最優(yōu)路徑長度平均值以及最優(yōu)路徑長度方差所示。對于最優(yōu)路徑長度平均值之間的比較，從數(shù)據(jù)上看，差別不太大，為了更充分地體現(xiàn)差別，同時(shí)考慮到實(shí)際無人機(jī)飛行環(huán)境是復(fù)雜的，所以繼續(xù)加大復(fù)雜程度，將環(huán)境建立在30×30的柵格環(huán)境中。

4.3.2?30×30柵格環(huán)境下的仿真

如圖10所示，虛線為文獻(xiàn)[25]的最優(yōu)路徑，實(shí)線為本文改進(jìn)算法的最優(yōu)路徑。從圖10可看出，在第二次轉(zhuǎn)彎的地方，虛線的路徑為直線，而實(shí)線的路徑為斜線，實(shí)線的路徑長度較短。從路徑整體效果來看，實(shí)線的轉(zhuǎn)彎次數(shù)為19次，虛線轉(zhuǎn)彎次數(shù)為16次。從路徑的整體性考慮，雖然轉(zhuǎn)彎次數(shù)增加了，但是路徑的長度減少了。

圖11為不同迭代次數(shù)時(shí)最優(yōu)路徑的長度比較。從圖11中可以看出，在引入自適應(yīng)啟發(fā)函數(shù)因子的情況下，開始迭代時(shí)，本文改進(jìn)算法的路徑長度較短，經(jīng)過迭代后，很快找到較短路徑并且達(dá)到穩(wěn)定值。從結(jié)果可以得出，本文算法增加了螞蟻考慮路徑整體性的能力，并且提高了螞蟻搜索路徑的效率。

圖12為不同迭代次數(shù)時(shí)最優(yōu)路徑的高度均方差的比較。開始時(shí)刻，實(shí)線與虛線的初始值相同，隨著迭代次數(shù)的增加，可以看出實(shí)線的高度均方差在迭代次數(shù)10以內(nèi)達(dá)到穩(wěn)定值，而虛線在迭代次數(shù)10以外達(dá)到穩(wěn)定值，而且實(shí)線達(dá)到穩(wěn)定值的速度較快。

圖13為不同迭代次數(shù)時(shí)最優(yōu)路徑的轉(zhuǎn)彎次數(shù)的比較。從圖13可以看出，由于引入自適應(yīng)啟發(fā)函數(shù)因子，螞蟻選擇路徑時(shí)考慮路徑整體性，所以實(shí)線較為平緩，波動(dòng)不太大。

圖14為不同迭代次數(shù)時(shí)最優(yōu)路徑的綜合指標(biāo)以及平均綜合指標(biāo)的比較，指標(biāo)越低則算法越優(yōu)。從圖14可以看出，本文改進(jìn)算法最優(yōu)路徑的綜合指標(biāo)曲線整體較為平緩，并且隨著迭代次數(shù)的增加，較早地趨于穩(wěn)定值。

通過表3中路徑長度、高度均方差、轉(zhuǎn)彎次數(shù)、綜合指標(biāo)以及路徑長度的迭代次數(shù)等數(shù)據(jù)結(jié)果可以看出，改進(jìn)的蟻群算法找到的路徑長度相對較短，并且在路徑長度的迭代次數(shù)上，改進(jìn)的蟻群算法的迭代次數(shù)相對較少。

5?結(jié)?語

螞蟻在柵格環(huán)境中尋找路徑時(shí)，當(dāng)前柵格到其鄰接?xùn)鸥竦木嚯x不完全相同。

為了能夠更加準(zhǔn)確地考慮路徑長度對蟻群選擇下一柵格的影響，本文在啟發(fā)函數(shù)中加入當(dāng)前柵格到其鄰接?xùn)鸥竦臍W式距離，增加了啟發(fā)函數(shù)的影響因素，構(gòu)成了一個(gè)閉環(huán)反饋，同時(shí)在轉(zhuǎn)移概率中引入自適應(yīng)啟發(fā)函數(shù)因子，即將起始點(diǎn)到待走柵格再到目的點(diǎn)的距離作為螞蟻選擇下一個(gè)柵格的轉(zhuǎn)移概率影響因素之一，增加了對環(huán)境整體的考慮，并對信息素以及信息素?fù)]發(fā)因子進(jìn)行改善，減小因路徑上過多或過少的信息素對螞蟻選擇路徑產(chǎn)生的影響，避免螞蟻在搜索路徑過程中陷入局部最優(yōu)。

本文改進(jìn)算法提高了螞蟻搜索路徑的效率，實(shí)驗(yàn)結(jié)果表明，改進(jìn)算法減少了路徑的長度，降低了迭代次數(shù)，路徑更平緩，得到的曲線較為平穩(wěn)，能夠較快地達(dá)到穩(wěn)定值。自適應(yīng)多啟發(fā)蟻群算法使得無人機(jī)路徑規(guī)劃的綜合指標(biāo)以及平均綜合指標(biāo)均有所降低。

本文將無人機(jī)的三維環(huán)境投影到二維進(jìn)行研究，簡化了飛行環(huán)境，未來還需增加飛行環(huán)境的復(fù)雜度，以提升算法的實(shí)際應(yīng)用性。

參考文獻(xiàn)/References：

[1]?唐立，郝鵬， 張學(xué)軍. 基于改進(jìn)蟻群算法的山區(qū)無人機(jī)路徑規(guī)劃方法[J]. 交通運(yùn)輸系統(tǒng)工程與信息， 2019， 19（1）： 158-164.

TANG Li， HAO Peng， ZHANG Xuejun. An UAV path planning method in mountainous area based on an improved ant colony algorithm[J]. Journal of Transportation Systems Engineering and Information Technology， 2019， 19（1）： 158-164.

[2]?CHEN Yongbo， LUO Guanchen， MEI Yuesong， et al. UAV path planning using artificial potential field method updated by optimal control theory[J]. International Journal of Systems Science， 2016， 47（6）： 1407-1420.

[3]?何燕.基于動(dòng)態(tài)加權(quán)A*算法的無人機(jī)航跡規(guī)劃[J].河北科技大學(xué)學(xué)報(bào)，2018，39（4）：349-355.

HE Yan.UAV route planning based on improved dynamic weighted A* algorithm[J].Journal of Hebei University of Science and Technology，2018，39（4）：349-355.

[4]?甄然， 張春悅， 矯陽， 等. 基于自適應(yīng)多態(tài)融合蟻群算法的無人機(jī)航跡規(guī)劃[J].河北科技大學(xué)學(xué)報(bào)， 2019， 40（6）： 526-532.

ZHEN Ran， ZHANG Chunyue， JIAO Yang， et al. Research on UAV route planning based on adaptive polymorphic ant colony algorithm[J]. Journal of Hebei University of Science and Technology， 2019， 40（6）： 526-532.

[5]?王琪， 馬璐， 鄧會(huì)亨. 基于遺傳算法的UAV自適應(yīng)航跡規(guī)劃[J]. 計(jì)算機(jī)系統(tǒng)應(yīng)用， 2013， 22（1）： 200-203.

WANG Qi， MA Lu， DENG Huiheng. Adaptive path planning of the UAV based on genetic algorithm[J]. Computer Systems & Applications， 2013， 22（1）： 200-203.

[6]?熊華捷， 蔚保國， 何成龍. 基于改進(jìn)粒子群算法的UAV航跡規(guī)劃方法[J]. 計(jì)算機(jī)測量與控制， 2020， 28（2）： 144-147.

XIONG Huajie， YU Baoguo， HE Chenglong. UAV path planning method based on improved PSO[J]. Computer Measurement & Control， 2020， 28（2）： 144-147.

[7]?WANG G G，CHU H E，MIRJALILI S.Three-dimensional path planning for UCAV using an improved bat algorithm[J].Aerospace Science and Technology，2016，49：231-238.

[8]?MIAO Hui， TIAN Yuchu. Dynamic robot path planning using an enhanced simulated annealing approach[J]. Applied Mathematics and Computation， 2013， 222： 420-437.

[9]?武曉晶， 許磊， 甄然， 等. 動(dòng)態(tài)步長BI-RRT的無人機(jī)航跡規(guī)劃算法[J]. 河北科技大學(xué)學(xué)報(bào)， 2019， 40（5）： 414-422.

WU Xiaojing， XU Lei， ZHEN Ran， et al. Dynamic step BI-RRT UAV path planning algorithm[J]. Journal of Hebei University of Science and Technology， 2019， 40（5）： 414-422.

[10]趙娟. 啟發(fā)點(diǎn)引導(dǎo)D*算法擴(kuò)展的無人機(jī)航跡規(guī)劃策略[J]. 機(jī)械設(shè)計(jì)與制造， 2020（2）： 153-157.

ZHAO Juan.Unmanned air vehicle route planning strategy based on D* algorithm extension guided by inspiration point[J]. Machinery Design & Manufacture， 2020（2）： 153-157.

[11]許江波， 劉琳嵐. 基于改進(jìn)人工魚群算法的無人機(jī)三維航跡規(guī)劃[J]. 計(jì)算機(jī)工程與設(shè)計(jì)， 2019， 40（2）： 540-544.

XU Jiangbo， LIU Linlan. 3D trajectory planning for UAV based on improved artificial fish swarm algorithm[J]. Computer Engineering and Design， 2019， 40（2）： 540-544.

[12]程澤新， 李東生， 高楊. 基于蝗蟲算法的無人機(jī)三維航跡規(guī)劃[J]. 飛行力學(xué)， 2019， 37（2）： 46-50.

CHENG Zexin， LI Dongsheng， GAO Yang. UAV three-dimensional path planning based on the grasshopper algorithm[J]. Flight Dynamics， 2019， 37（2）： 46-50.

[13]余勝東， 吳洪濤， 馬金玉. 應(yīng)用混沌螢火蟲算法的無人機(jī)航跡規(guī)劃[J]. 機(jī)械設(shè)計(jì)與制造， 2018（11）： 113-116.

YU Shengdong， WU Hongtao， MA Jinyu. Path planning for unmanned air vehicle based on chaotic glowworm swarm optimization[J]. Machinery Design & Manufacture， 2018（11）： 113-116.

[14]陸天和， 劉莉， 賀云濤， 等. 多無人機(jī)航跡規(guī)劃算法及關(guān)鍵技術(shù)[J]. 戰(zhàn)術(shù)導(dǎo)彈技術(shù)， 2020（1）： 85-90.

LU Tianhe， LIU Li， HE Yuntao， et al. Multi-UAV path planning algorithm and key technology[J]. Tactical Missile Technology， 2020（1）： 85-90.

[15]肖作林，王鵬，冷淑香，等.多無人作戰(zhàn)飛機(jī)雙精度航跡規(guī)劃技術(shù)[J].戰(zhàn)術(shù)導(dǎo)彈技術(shù)，2016（3）：53-57.

XIAO Zuolin，WANG Peng，LENG Shuxiang，et al.Research on the double precision mission planning in multi-UCAV system[J].Tactical Missile Technology，2016（3）：53-57.

[16]朱莉凱，沈朝萍，沈?qū)殗?，?無人機(jī)航跡規(guī)劃群智能優(yōu)化算法綜述[J].數(shù)字技術(shù)與應(yīng)用，2019，37（8）：126.

ZHU Likai，SHEN Chaoping，SHEN Baoguo，et al.A survey of intelligent optimization algorithms for UAV route planning group[J].Digital Technology and Application，2019，37（8）：126.

[17]王輝， 胡曉陽. 基于蟻群算法的無人機(jī)航跡規(guī)劃研究[J]. 科技資訊， 2020， 18（10）： 29-30.

[18]劉蓉，楊帆，張衡.基于改進(jìn)混沌蟻群算法的無人機(jī)航路規(guī)劃[J].指揮信息系統(tǒng)與技術(shù)，2018，9（6）：41-48.

LIU Rong，YANG Fan，ZHANG Heng.Path planning for UAV based on improved chaotic ant colony algorithm （CACA）[J].Command Information System and Technology，2018，9（6）：41-48.

[19]張松燦， 普杰信， 司彥娜， 等. 蟻群算法在移動(dòng)機(jī)器人路徑規(guī)劃中的應(yīng)用綜述[J]. 計(jì)算機(jī)工程與應(yīng)用， 2020， 56（8）： 10-19.

ZHANG Songcan， PU Jiexin， SI Yanna， et al. Survey on application of ant colony algorithm in path planning of mobile robot[J]. Computer Engineering and Applications， 2020， 56（8）： 10-19.

[20]王瓊， 劉美萬， 任偉建， 等. 無人機(jī)航跡規(guī)劃常用算法綜述[J]. 吉林大學(xué)學(xué)報(bào)（信息科學(xué)版）， 2019， 37（1）： 58-67.

WANG Qiong， LIU Meiwan， REN Weijian， et al. Overview of common algorithms for UAV path planning[J]. Journal of Jilin University（Information Science Edition）， 2019， 37（1）： 58-67.

[21]HUANG Liwei， QU Hong， JI Peng， et al. A novel coordinated path planning method using k-degree smoothing for multi-UAVs[J]. Applied Soft Computing， 2016， 48： 182-192.

[22]TAO Jihua， WANG Yinqiu， YANG Huanhuan， et al. Three-dimensional path planning of unmanned aerial vehicle under complicated environment[C]//第28屆中國控制與決策會(huì)議論文集（下）.?[S.l.]：[s.n.]，2016： 1498-1503.

[23]孫功武，蘇義鑫，顧軼超， 等. 基于改進(jìn)蟻群算法的水面無人艇路徑規(guī)劃[J/OL]. 控制與決策.

[2019-11-04]. https：//doi.org/10.13195/j.kzyjc.2019.0839.

SUN Gongwu， SU Yixin， GU Yichao， et al. Path planning for unmanned surface vehicle based on improved ant colony algorithm[J/OL]. Control and Decision. [2019-11-04].https：//doi.org/10.13195/j.kzyjc.2019.0839.

[24]黃心，向煜. 基于改進(jìn)蟻群算法的無人機(jī)航跡規(guī)劃仿真研究[J]. 城市勘測，2019（1）：83-87.

HUANG Xin， XIANG Yu. Simulation research on UAV route planning based on improved ant colony algorithm[J]. Urban Geotechnical Investigation & Surveying， 2019（1）： 83-87.

[25]李理，李鴻，單寧波.多啟發(fā)因素改進(jìn)蟻群算法的路徑規(guī)劃[J].計(jì)算機(jī)工程與應(yīng)用，2019，55（5）：219-225.

LI Li，LI Hong，SHAN Ningbo.Path planning based on improved ant colony algorithm with multiple inspired factor[J].Computer Engineering and Applications，2019，55（5）：219-225.

[26]陳勁峰，黃衛(wèi)華，王肖，等.基于改進(jìn)蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃[J].高技術(shù)通訊，2020，30（3）：291-297.

CHEN Jinfeng，HUANG Weihua，WANG Xiao，et al.Research on path planning based on an improved ant colony algorithm for mobile robot[J].Chinese High Technology Letters，2020，30（3）：291-297.

[27]KHALED A， FARID K. Mobile robot path planning using an improved ant colony optimization[J]. International Journal of Advanced Robotic Systems， 2018， 15（3）： 1-7.