蟻群優(yōu)化算法的無人機(jī)室內(nèi)航跡規(guī)劃

馬肇祥　朱慶偉　張俊　屈乾龍

摘要：由于室內(nèi)無人機(jī)導(dǎo)航較為復(fù)雜，針對(duì)現(xiàn)有的傳統(tǒng)（基本）蟻群算法存在早期盲目搜索、易陷入局部最優(yōu)和收斂速度慢等問題，探索一種高效、準(zhǔn)確的航跡規(guī)劃方法意義重大。為提高收斂速度使其避免陷入局部最優(yōu)等算法缺陷，提出一種改進(jìn)蟻群算法的室內(nèi)無人機(jī)三維航跡規(guī)劃方法，該方法設(shè)計(jì)初始信息素的調(diào)節(jié)因子，增強(qiáng)蟻群搜索的方向性;設(shè)計(jì)啟發(fā)概率函數(shù)，改進(jìn)狀態(tài)轉(zhuǎn)移規(guī)則，有效提高蟻群可見性精度;改進(jìn)算法的信息素更新方式，增加信息素?fù)]發(fā)率的動(dòng)態(tài)調(diào)整策略，提高算法的收斂速度，擴(kuò)大搜索空間，有效避免其陷入局部最優(yōu)。通過仿真實(shí)驗(yàn)進(jìn)行算法適應(yīng)性驗(yàn)證，結(jié)果表明：改進(jìn)蟻群算法有效提高全局搜索能力，減少收斂迭代次數(shù)，得到的最優(yōu)路徑長(zhǎng)度比傳統(tǒng)蟻群算法平均縮短38.6%，平均用時(shí)減少3.8%，顯著提高蟻群優(yōu)化算法的適應(yīng)性，體現(xiàn)出在特定應(yīng)用場(chǎng)景下的優(yōu)越性。

關(guān)鍵詞：無人機(jī);蟻群算法;室內(nèi)環(huán)境;三維航跡規(guī)劃;較優(yōu)路徑

中圖分類號(hào)：TP 24文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1672-9315（2022）02-0307-10

DOI：10.13800/j.cnki.xakjdxxb.2022.0215開放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

Ant colony optimization algorithm for UAV

indoor trajectory planningMA Zhaoxiang，ZHU Qingwei，ZHANG Jun，QU Qianlong

（College of Geomatics，Xian University of Science and Technology，Xian 710054，China）

Abstract：Due to the complicated indoor drone navigation，there is an early blind search for the existing traditional（basic）ant colony algorithm，which is easy to fall into a problem such as local optimization and slow convergence speed.Explore an efficient and accurate track planning method significance. In order to improve the convergence speed，it is proposed to improve the three-dimensional airline planning method for improving the ant colony algorithm.The method designs the adjustment factor of the initial pheromone，enhances the directionality of the ant colony search.The design inspiration probability function，improve the state transfer rules，effectively improve the visibility of ant colony.The updated methods of the algorithm pheromones are improved，with their dynamic adjustment strategies promoted，thus increasing the convergence speed of the algorithm，expanding search space，and effectively avoiding its topical optimal.The algorithm adaptation verification is performed by simulation experiments， and the results show that the improved ant colony algorithm effectively improves global search capabilities，reducing the number of convergence iterations，the optimal path length is less than 38.6% more than the traditional ant colony algorithm， nd the average time reduces by 3.8%.Significantly improve the adaptability of the ant colony optimization algorithm，indicating the superiority of a particular application scenario.

Key words：unmanned aerial vehicle（UAV）;ant colony algorithm;indoor environment;three-dimensional trajectory planning;better path

0引言

無人機(jī)因其操作簡(jiǎn)便、機(jī)動(dòng)性能好等特點(diǎn)，已經(jīng)被廣泛應(yīng)用于各個(gè)領(lǐng)域。將無人機(jī)用于執(zhí)行室內(nèi)災(zāi)害救援任務(wù)時(shí)，可以減少救援人員的安全風(fēng)險(xiǎn)，提高救援工作效率。航跡規(guī)劃是無人機(jī)完成自主飛行的關(guān)鍵技術(shù)之一，在室內(nèi)救援時(shí)，尋找一條安全、可靠的飛行航跡是保證救援任務(wù)能否完成的關(guān)鍵。無人機(jī)室內(nèi)飛行面臨的挑戰(zhàn)是室內(nèi)空間狹小、障礙物較多，高度有限，使無人機(jī)飛行受到一定條件的限制。在室內(nèi)，由于環(huán)境信息是未知的，航跡規(guī)劃要滿足避障要求，規(guī)劃一條合理路徑。

目前，各國(guó)學(xué)者已提出許多種無人機(jī)航跡規(guī)劃算法。常用到的算法有：可視圖法、D*算法[1]、A*算法[2]、人工勢(shì)場(chǎng)法[3]、神經(jīng)網(wǎng)絡(luò)算法[4]、快速搜索隨機(jī)樹（RRT）算法[5]、遺傳算法[6]、粒子群算法[7]、蟻群算法[8-10]、模擬退火算法[11]、強(qiáng)化學(xué)習(xí)算法[12]等。其中，蟻群算法在求解較優(yōu)航跡方面較其他算法具有顯著優(yōu)勢(shì)。對(duì)蟻群算法進(jìn)行改進(jìn)應(yīng)用于航跡規(guī)劃的研究，國(guó)內(nèi)外學(xué)者作了大量的研究工作。陳俠等提出的算法為使蟻群算法能更好適用于無人機(jī)三維航跡規(guī)劃，對(duì)算法存在的收斂速度慢、易陷入局部最優(yōu)的問題，進(jìn)行了相應(yīng)改進(jìn)，將三維航跡規(guī)劃分解成二維平面規(guī)劃和高度規(guī)劃2部分，運(yùn)用幾何優(yōu)化法增強(qiáng)蟻群的引導(dǎo)方向性，根據(jù)無人機(jī)航跡點(diǎn)與障礙物之間的距離，對(duì)飛行高度進(jìn)調(diào)整，利用自適應(yīng)變化閾值參數(shù)法提高了蟻群在全局中的搜索能力，從而達(dá)到求解多樣性的效果[13]。針對(duì)蟻群算法所含有的空間復(fù)雜性高、收斂速度慢的缺陷，魏江等提出的算法改進(jìn)部分對(duì)局部搜索策略和初始信息素調(diào)節(jié)因子進(jìn)行優(yōu)化，在啟發(fā)函數(shù)中加入路徑偏移因子，有效降低空間搜索復(fù)雜性，提高了路徑規(guī)劃效率[14]。徐玉瓊等針對(duì)傳統(tǒng)蟻群算法在路徑規(guī)劃中對(duì)魯棒性缺乏的問題，提出改進(jìn)自適應(yīng)蟻群算法，在概率轉(zhuǎn)移規(guī)則中引入加權(quán)因子，以提高算法收斂速度，并按解的分布狀況適應(yīng)性地對(duì)信息素進(jìn)行更新，同時(shí)在步長(zhǎng)選擇策略中選擇最優(yōu)步長(zhǎng)，增強(qiáng)算法全局搜尋能力，從而提高機(jī)器人路徑規(guī)劃效率[15]。李憲強(qiáng)等將人工勢(shì)場(chǎng)法與蟻群算法融合組成新的融合算法。由于蟻群算法易陷入局部最優(yōu)，引入人工勢(shì)場(chǎng)法對(duì)初始信息素進(jìn)行分配。并且引入勢(shì)場(chǎng)引導(dǎo)函數(shù)對(duì)蟻群算法的狀態(tài)轉(zhuǎn)移函數(shù)進(jìn)行相應(yīng)改進(jìn)，從而避免算法因忽視周圍障礙物信息而陷入長(zhǎng)時(shí)間進(jìn)行路徑選擇的問題[16]。這些研究都將蟻群算法用到具體的環(huán)境[17-22]，取得良好的效果，然而，對(duì)于文中研究的室內(nèi)無人機(jī)航跡規(guī)劃，并不適用。因?yàn)檫@些算法應(yīng)用于室外環(huán)境，且算法規(guī)劃速度較慢，搜索時(shí)間較長(zhǎng)，難以滿足室內(nèi)災(zāi)害救援及其他室內(nèi)飛行任務(wù)的要求。

由于室內(nèi)環(huán)境分布著大量障礙物，且障礙物分布不均以及其高度、形狀、大小都各不相同[23-25]。而無人機(jī)在室內(nèi)進(jìn)行搜救或者自主導(dǎo)航時(shí)，室內(nèi)環(huán)境信息并不能保證都了解。筆者結(jié)合室內(nèi)環(huán)境特點(diǎn)及蟻群算法存在的缺陷，對(duì)空間做離散化處理，降低其空間復(fù)雜度。針對(duì)搜索初期，因信息素的缺乏，會(huì)導(dǎo)致搜索的盲目性，采用信息素調(diào)節(jié)因子，同時(shí)根據(jù)算法存在收斂速度慢和易陷入局部最優(yōu)的缺點(diǎn)，設(shè)計(jì)啟發(fā)概率，并改進(jìn)信息素更新規(guī)則和采用動(dòng)態(tài)信息素?fù)]發(fā)策略。最后，通過實(shí)驗(yàn)測(cè)試對(duì)改進(jìn)后的算法性能進(jìn)行驗(yàn)證和分析。

1空間離散化

室內(nèi)環(huán)境中隨機(jī)分布著很多障礙物，且空間環(huán)境處于連續(xù)狀態(tài)。當(dāng)發(fā)生災(zāi)害時(shí)，室內(nèi)障礙物和突發(fā)的各種不確定因素給航跡規(guī)劃帶來巨大挑戰(zhàn)。因此，對(duì)室內(nèi)三維空間環(huán)境進(jìn)行離散化處理，則在航跡規(guī)劃時(shí)可以直接獲得空間節(jié)點(diǎn)集。即在空間節(jié)點(diǎn)集中找到組成路徑規(guī)劃的總成本代價(jià)最小的節(jié)點(diǎn)。

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

在基本蟻群算法中，概率選擇并不能總是保證最優(yōu)解，有時(shí)在優(yōu)化的早期，算法會(huì)進(jìn)行盲目搜索、易陷入局部最優(yōu)，而且由于啟發(fā)式搜索的局限性，導(dǎo)致算法收斂速度很慢，為提高基本蟻群算法的性能并克服其缺點(diǎn)，做出以下改進(jìn)：改進(jìn)初始信息素調(diào)節(jié)因子，有效增強(qiáng)蟻群算法的搜索方向性;設(shè)計(jì)啟發(fā)概率并改進(jìn)狀態(tài)轉(zhuǎn)移概率函數(shù)，從而擴(kuò)展蟻群搜索視野和提高可見性精度;對(duì)信息素更新規(guī)則進(jìn)行改進(jìn)和增加信息素?fù)]發(fā)率的動(dòng)態(tài)調(diào)整策略，有效提升算法的收斂速度、擴(kuò)大搜索空間。

2.1初始信息素的改進(jìn)

由于基本蟻群算法的初始信息素均勻分布于空間中，因此在算法搜索初期，螞蟻選擇任意節(jié)點(diǎn)位置的概率都相同，從而出現(xiàn)蟻群盲目搜索的現(xiàn)象，同時(shí)也耗費(fèi)大量的時(shí)間。

為避免螞蟻在算法搜索初期的盲目性，在起始點(diǎn)和目標(biāo)點(diǎn)連線的區(qū)域中，通過起始點(diǎn)到當(dāng)前節(jié)點(diǎn)的距離和待選節(jié)點(diǎn)到目標(biāo)點(diǎn)距離的變化量來影響初始信息素?；鞠伻核惴ǖ某跏夹畔⑺厥且粋€(gè)固定常數(shù)值，改進(jìn)蟻群算法通過確定起始點(diǎn)、當(dāng)前節(jié)點(diǎn)、待選節(jié)點(diǎn)以及且標(biāo)點(diǎn)之間的距離，使蟻群盡可能沿著起始點(diǎn)和目標(biāo)點(diǎn)連線的附近進(jìn)行路徑搜索，從而縮小路徑搜索范圍，因此對(duì)初始信息素調(diào)節(jié)因子進(jìn)行了如下設(shè)計(jì)。

式中D為室內(nèi)空間中起始點(diǎn)與目標(biāo)點(diǎn)連線的歐式距離;τ′₀為固定的信息素常數(shù);d_si為蟻群所走路徑的起始點(diǎn)與當(dāng)前節(jié)點(diǎn)的距離（因?yàn)橄伻核惴ㄋ阉骶哂须S機(jī)性，這里的dsi為蟻群所搜索的路徑，這一距離大于起始點(diǎn)到當(dāng)前節(jié)點(diǎn)的直線距離），d_ij為蟻群所走路徑的當(dāng)前節(jié)點(diǎn)與下一待選節(jié)點(diǎn)的距離，d_je為待選節(jié)點(diǎn)與目標(biāo)點(diǎn)的距離。由公式（4）可知，d_si+d_ij+d_je的值越大，則路徑（i，j）間的初始信息素越大;反之，初始信息素的值越小。

通過對(duì)上述信息素調(diào)節(jié)因子的設(shè)計(jì)使改進(jìn)算法達(dá)到增強(qiáng)蟻群搜索方向性的效果。

2.2啟發(fā)概率

ST是組合運(yùn)算，啟發(fā)概率設(shè)計(jì)了讓螞蟻更容易選擇最好的下一個(gè)空間網(wǎng)格（將室內(nèi)空間按單位長(zhǎng)度等分為大小相等的多個(gè)空間網(wǎng)格），所選網(wǎng)格必須是一個(gè)可行的網(wǎng)格，有多個(gè)可行通道抵達(dá)目標(biāo)。這個(gè)概率取決于網(wǎng)格周圍障礙物的數(shù)量。因此，空間網(wǎng)格周圍的障礙物越少，概率就越大，網(wǎng)格就越有吸引力。需要做以下組合。

在三維空間中，無人機(jī)在搜索時(shí)，有27個(gè)搜索方向，去掉無人機(jī)本身的所占據(jù)的位置，因此剩于26個(gè)方向，即N（26，M_obs），它表示圍繞一個(gè)確定的網(wǎng)格j，其周圍障礙物可能分布的數(shù)量，即表征一個(gè)可行網(wǎng)格節(jié)點(diǎn)周圍有多少障礙物，且障礙物數(shù)量為[0，26]，如圖1所示。

2.3改進(jìn)信息素更新規(guī)則

信息素的數(shù)量是選擇經(jīng)過最短路徑上的最佳空間網(wǎng)格的必要因素之一，然而，它含有一定強(qiáng)度的劣質(zhì)信息素，這是由最差的螞蟻所產(chǎn)生的，它會(huì)使其他螞蟻移動(dòng)到難以接近目標(biāo)點(diǎn)的位置上，或者會(huì)導(dǎo)致算法過早求解，為了獲得良好的尋優(yōu)性能，在每次迭代中，可使用以下更新規(guī)則增加最佳局部路徑上的信息素濃度并降低最差局部路徑上的信息素濃度。因此，對(duì)信息素更新規(guī)則公式改進(jìn)為

2.4設(shè)置動(dòng)態(tài)信息素?fù)]發(fā)策略

在基本蟻群算法中，信息素?fù)]發(fā)率ρ是（0，1）范圍內(nèi)的常數(shù)，直接影響著算法全局搜素能力和收斂速度，如果ρ太小，信息素?fù)]發(fā)的較慢，會(huì)降低全局搜索能力，使算法陷入局部收斂。如果ρ過大，全局搜索能力會(huì)得到一定程度的提高，但收斂速度會(huì)降低。

為確保能在擴(kuò)大搜索空間和加快收斂速度兩者間取得良好的平衡，對(duì)信息素?fù)]發(fā)率進(jìn)行動(dòng)態(tài)調(diào)整。其中，在算法開始時(shí)，將揮發(fā)率設(shè)置為較大的值，來改善全局搜索能力，然后揮發(fā)率將按如下公式進(jìn)行改變

3算法改進(jìn)與實(shí)現(xiàn)

3.1改進(jìn)蟻群算法的步驟

具體改進(jìn)蟻群算法流程如圖2所示。

3.2仿真實(shí)驗(yàn)環(huán)境構(gòu)建與有效性分析

3.2.1仿真實(shí)驗(yàn)環(huán)境的構(gòu)建

為驗(yàn)證改進(jìn)的蟻群算法在室內(nèi)三維航跡規(guī)劃的有效性，在三維柵格地圖中對(duì)改進(jìn)蟻群算法進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)仿真平臺(tái)為MATLAB2018a，考慮到一架無人機(jī)和室內(nèi)環(huán)境模型特點(diǎn)，且無人機(jī)可以向環(huán)境中任意方向運(yùn)動(dòng)飛行。該實(shí)驗(yàn)的規(guī)劃空間分為10 m×10 m×10 m柵格，20 m×20 m×20 m柵格和30 m×20 m×15 m柵格，實(shí)驗(yàn)搭建的三維模型如圖3所示，為更真實(shí)的接近室內(nèi)場(chǎng)景，空間中隨機(jī)設(shè)置障礙物。規(guī)定沒有障礙物的空間柵格可以通過，有障礙物的空間柵格不可通過。

在室內(nèi)航跡規(guī)劃中，算法參數(shù)設(shè)置如下：螞蟻數(shù)量m=100，信息素濃度啟發(fā)因子α=1，能見度啟發(fā)因子β=2，揮發(fā)系數(shù)ρ=0.7，信息素強(qiáng)度Q=10，迭代次數(shù)n=50。

3.2.2改進(jìn)算法的實(shí)現(xiàn)及有效性驗(yàn)證

在不同空間規(guī)模的條件下，采用改進(jìn)算法和基本算法在室內(nèi)環(huán)境1（規(guī)模為10 m×10 m×10 m）、室內(nèi)環(huán)境2（規(guī)模為20 m×20 m×20 m）和室內(nèi)環(huán)境3（規(guī)模為20 m×30 m×15 m）中各進(jìn)行20次重復(fù)航跡規(guī)劃，然后從路徑長(zhǎng)度，收斂時(shí)間等角度來比較2種算法的實(shí)驗(yàn)效果，并對(duì)得到的結(jié)果進(jìn)行對(duì)比和分析。為便于統(tǒng)計(jì)計(jì)算，對(duì)實(shí)驗(yàn)的相關(guān)結(jié)果保留至小數(shù)點(diǎn)后3位。3種室內(nèi)空間規(guī)模中基本算法和改進(jìn)算法所規(guī)劃的路徑以及最佳個(gè)體適應(yīng)度變化情況分別如圖4～圖6所示。

圖4～圖6的實(shí)驗(yàn)結(jié)果表明，改進(jìn)蟻群算法在3種不同的室內(nèi)環(huán)境中經(jīng)過計(jì)算迭代后，均能搜索到一條較優(yōu)路徑，并且搜索到的較優(yōu)路徑比基本蟻群算法的路徑長(zhǎng)度更短，如圖4（b）、圖5（b）、圖6（b）中的藍(lán)色路徑相較于紅色路徑更短。這是因?yàn)樵谒惴ㄋ阉鞒跗?，基本蟻群算法因缺乏初始信息素，?duì)空間進(jìn)行盲目搜索，使得所找尋到的路徑較長(zhǎng)。而改進(jìn)算法對(duì)初始信息素調(diào)節(jié)因子進(jìn)行改進(jìn)，增強(qiáng)朝目標(biāo)點(diǎn)方向的信息素濃度，避免算法出現(xiàn)盲目搜索的狀況，從而找尋到一條較短路徑，有效節(jié)約搜索時(shí)間。同時(shí)，在環(huán)境1中，障礙物的高度不一，分布也不均勻，改進(jìn)算法所規(guī)劃的路徑選擇離目標(biāo)點(diǎn)距離近且周圍障礙物少的路徑通道，基本蟻群算法按傳統(tǒng)的啟發(fā)式規(guī)則隨機(jī)選擇可行通道，有時(shí)選擇的可行通道節(jié)點(diǎn)離目標(biāo)點(diǎn)較遠(yuǎn)。產(chǎn)生這2種結(jié)果的原因是改進(jìn)算法中新設(shè)計(jì)的啟發(fā)式概率有效擴(kuò)展蟻群搜索視野并提高了蟻群可見性精度。

如圖4（c）、圖5（c）、圖6（c）為3組實(shí)驗(yàn)的側(cè)視圖。圖4（d）、圖5（d）、圖6（d）所反映的是最佳個(gè)體適應(yīng)度值變化趨勢(shì)，可以得出改進(jìn)算法（藍(lán)色曲線）比基本算法（紅色曲線）的收斂迭代速度快，且當(dāng)適應(yīng)度值達(dá)到穩(wěn)定后，改進(jìn)算法所得到的適應(yīng)度值比基本算法的小，并且改進(jìn)算法的適應(yīng)度值在算法前期搜索階段，快速下降，出現(xiàn)這種結(jié)果是由于算法改進(jìn)了信息素更新規(guī)則并采用信息素?fù)]發(fā)率動(dòng)態(tài)調(diào)整策略，從而加快算法的收斂速度，同時(shí)也擴(kuò)大蟻群搜索范圍，有效解決基本蟻群算法易陷入局部最優(yōu)極值的問題。在環(huán)境1中，基本算法經(jīng)過33次迭代后，其最佳個(gè)體的適應(yīng)度值趨于穩(wěn)定，且達(dá)到最優(yōu)，而改進(jìn)算法在迭代15次后，最佳個(gè)體的適應(yīng)度值達(dá)到最優(yōu)，如圖4（d）所示。并且基本算法經(jīng)過后續(xù)的多次迭代后，其最佳個(gè)體的適應(yīng)度值仍高于改進(jìn)算法相對(duì)應(yīng)的值。從圖5（d）可以看出，改進(jìn)算法和基本算法分別經(jīng)過19次、43次迭代后，適應(yīng)度值達(dá)到最小。圖6（d）中，改進(jìn)算法和基本算法分別經(jīng)過6次、8次迭代后，適應(yīng)度值達(dá)到最小。圖4室內(nèi)環(huán)境1中2種算法仿真對(duì)比

對(duì)2種蟻群算法在3種不同室內(nèi)環(huán)境中重復(fù)實(shí)驗(yàn)得到的20條路徑長(zhǎng)度和算法所用時(shí)長(zhǎng)進(jìn)行統(tǒng)計(jì)比較，見表1。由表1可知，改進(jìn)蟻群算法搜索的20條最優(yōu)路徑長(zhǎng)度效率分別提高：11.8%，46.9%，57.2%，路徑長(zhǎng)度平均值效率分別提高17.7%，54.9%，62.7%。改進(jìn)蟻群算法平均用時(shí)相較基本蟻群算法而言，提升較小。具體來說，在室內(nèi)空間規(guī)模較小的環(huán)境1中，2種算法都能較快搜索到最優(yōu)解，搜索到的路徑長(zhǎng)度平均值和算法用時(shí)兩方面的效率百分比相差不大。

伴隨著室內(nèi)空間范圍擴(kuò)大，改進(jìn)算法的各項(xiàng)性能逐漸顯現(xiàn)，同時(shí)路徑長(zhǎng)度效率提升趨勢(shì)與算法用時(shí)效率提升趨勢(shì)呈一升一降2種相反的變化結(jié)果。分析可知，這是由于改進(jìn)算法在尋找較優(yōu)路徑時(shí)，隨著空間范圍的增大，相應(yīng)地空間搜索計(jì)算量也增大，從而導(dǎo)致所用時(shí)間增大，算法用時(shí)的提升效率也隨之降低。

3.2.3算法適應(yīng)性驗(yàn)證

為驗(yàn)證所提出的改進(jìn)算法在不同場(chǎng)景下的適應(yīng)性，在不同障礙物和目標(biāo)位置點(diǎn)中分別進(jìn)行3組實(shí)驗(yàn)，每次實(shí)驗(yàn)運(yùn)行多次并使結(jié)果保留至小數(shù)點(diǎn)后3位。圖7～圖9顯示3組實(shí)驗(yàn)的路徑規(guī)劃圖。其中圖7（b）在圖7（a）基礎(chǔ)上改變目標(biāo)點(diǎn)位置，圖8（b）與圖8（a）為相同起始點(diǎn)和目標(biāo)點(diǎn)條件下的室內(nèi)不同障礙物環(huán)境，圖9（a）和圖9（b）為完全不同的室內(nèi)環(huán)境和目標(biāo)點(diǎn)。

從圖7可以看出，實(shí)驗(yàn)更改無人機(jī)所要到達(dá)的目標(biāo)位置，規(guī)劃的路徑仍能夠安全避開障礙物并準(zhǔn)確到達(dá)目標(biāo)點(diǎn)，由于圖7（a）和圖7（b）起始點(diǎn)坐標(biāo)都為（1，1，1），圖7（a）目標(biāo)點(diǎn)坐標(biāo)是（9，10，7），圖7（b）目標(biāo)點(diǎn)坐標(biāo)是（10，9，8），所以圖7（b）實(shí)驗(yàn)得到的路徑規(guī)劃長(zhǎng)度、算法計(jì)算用時(shí)、迭代次數(shù)都大于圖7（a）的值。圖8（a）與圖8（b）因障礙物差異較大，且圖8（a）中的無人機(jī)直接通過第2、第3個(gè)障礙物下方的通道到達(dá)目標(biāo)點(diǎn)，但在圖8（b）中，由于第2個(gè)障礙物是一個(gè)類似U型的障礙物，則無人機(jī)需要先不斷沿y軸方向搜索，再轉(zhuǎn)向x軸方向搜索到達(dá)目標(biāo)點(diǎn)，最終導(dǎo)致改進(jìn)算法搜索到的最優(yōu)路徑長(zhǎng)度、算法用時(shí)、收斂迭代次數(shù)不同。在第3組實(shí)驗(yàn)中，由于室內(nèi)空間范圍由圖9（a）的20 m×20 m×12 m擴(kuò)展為圖9（b）的20 m×20 m×14 m，使得圖9（b）中采用改進(jìn)算法所規(guī)劃的路徑長(zhǎng)度比圖9（a）的路徑長(zhǎng)度更長(zhǎng)。表2為圖7～圖9這3組實(shí)驗(yàn)得到的數(shù)據(jù)結(jié)果。

表2結(jié)果說明，改變不同的條件，所提出的改進(jìn)算法在不同的場(chǎng)景下有著很好的適應(yīng)性，同時(shí)通過實(shí)驗(yàn)驗(yàn)證改進(jìn)算法的路徑規(guī)劃性能指標(biāo)與無人機(jī)起始點(diǎn)和目標(biāo)點(diǎn)的距離大小、空間復(fù)雜度大小、空間范圍大小這3種因素有關(guān)。

4結(jié)論

1）針對(duì)傳統(tǒng)蟻群算法存在初期盲目搜索、易陷入局部最優(yōu)、收斂速度慢等問題，提出一種優(yōu)化蟻群算法，通過改進(jìn)初始信息素調(diào)節(jié)因子，進(jìn)而增強(qiáng)蟻群搜索的方向性。

2）設(shè)計(jì)一種啟發(fā)概率函數(shù)，擴(kuò)展蟻群搜索視野并提高可見性，使得最優(yōu)路徑長(zhǎng)度比基本蟻群算法縮短38.6%，平均用時(shí)減少3.8%。

3）對(duì)信息素更新規(guī)則進(jìn)行改進(jìn)，增添信息素?fù)]發(fā)動(dòng)態(tài)調(diào)整策略，從而加快算法收斂迭代速度，有效驗(yàn)證改進(jìn)算法在復(fù)雜環(huán)境中的良好適應(yīng)性。

參考文獻(xiàn)（References）：

[1]張飛，白偉，喬耀華，等.基于改進(jìn)D*算法的無人機(jī)室內(nèi)路徑規(guī)劃[J].智能系統(tǒng)學(xué)報(bào)，2019，14（4）：662-669.ZHANG Fei，BAI Wei，QIAO Yaohua，et al.UAV indoor path planning based on improved D* algorithm[J].CAAI Transactions on Intelligent Systems，2019，14（4）：662-669.

[2]MANDLOI D，ARYA R，VERMA A K.Unmanned aerial vehicle path planning based on A* algorithm and its variants in 3D environment[J].International Journal of System Assurance Engineering and Management，2021，12（5）：990-1000.

[3]諶海云，陳華胄，劉強(qiáng).基于改進(jìn)人工勢(shì)場(chǎng)法的多無人機(jī)三維編隊(duì)路徑規(guī)劃[J].系統(tǒng)仿真學(xué)報(bào)，2020，32（3）：414-420.CHEN Haiyun，CHEN Huazhou，LIU Qiang.Multi-UAV 3D formation path planning based on improved artificial potential field[J].Journal of System Simulation，2020，32（3）：414-420.

[4]朱大奇，劉雨，孫兵，等.自治水下機(jī)器人的自主啟發(fā)式生物啟發(fā)神經(jīng)網(wǎng)絡(luò)路徑規(guī)劃算法[J].控制理論與應(yīng)用，2019，36（2）：183-191.ZHU Daqi，LIU Yu，SUN Bing，et al.Autonomous underwater vehicles path planning based on autonomous inspired Glasius bio-inspired neural network algorithm[J].Control Theory & Applications，2019，36（2）：183-191.

[5]GAN Y，ZHANG B，KE C，et al.Research on robot motion planning based on RRT algorithm with nonholonomic constraints[J].Neural Processing Letters，2021，53（4）：3011-3029.

[6]XIN J，ZHONG J，YANG F，et al.An improved genetic algorithm for path-planning of unmanned surface vehicle[J].Sensors，2019，19（11）：1-23.

[7]SHAO S，PENG Y，HE C，et al.Efficient path planning for UAV formation via comprehensively improved particle swarm optimization[J].ISA Transactions，2020，97：415-430.

[8]韓鵬，張冰玉.基于改進(jìn)蟻群算法的無人機(jī)安全航路規(guī)劃研究[J].中國(guó)安全科學(xué)學(xué)報(bào)，2021，31（1）：24-29.HAN Peng，ZHANG Bingyu.Safety route planning of UAV based on improved ant colony algorithm[J].China Safety Science Journal，2021，31（1）：24-29.

[9]陳超，張莉.基于改進(jìn)蟻群算法的三維路徑規(guī)劃[J].計(jì)算機(jī)工程與應(yīng)用，2019，55（20）：192-196.CHEN Chao，ZHANG Li.Three-dimensional path planning based on improved ant colony algorithm[J].Computer Engineering and Applications，2019，55（20）：192-196.

[10]LUO Q，WANG H，ZHENG Y，et al.Research on path planning of mobile robot based on improved ant colony algorithm[J].Neural Computing and Applications，2020，32（6）：1555-1566.

[11]HUO L，ZHU J，WU G，et al.A novel simulated annealing based strategy for balanced UAV task assignment and path planning[J].Sensors，2020，20（17）：4769.

[12]BAE H，KIM G，KIM J，et al.Multi-robot path planning method using reinforcement learning[J].Applied Sciences，2019，9（15）：3057.

[13]陳俠，艾宇迪，梁紅利.基于改進(jìn)蟻群算法的無人機(jī)三維航跡規(guī)劃研究[J].戰(zhàn)術(shù)導(dǎo)彈技術(shù)，2019（2）：59-66，105.CHEN Xia，AI Yudi，LIANG Hongli，et al.Research on three-dimensional path planning of UAV based on improved ant colony algorithm[J].Tactical Missile Technology，2019（2）：59-66，105.

[14]魏江，王建軍，王健，等.基于改進(jìn)蟻群算法的三維航跡規(guī)劃[J].計(jì)算機(jī)工程與應(yīng)用，2020，56（17）：217-223.WEI Jiang，WANG Jianjun，WANG Jian，et al.3D path planning based on improved ant colony algorithm[J].Computer Engineering and Applications，2020，56（17）：217-223.

[15]徐玉瓊，婁柯，李婷婷，等.改進(jìn)自適應(yīng)蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃[J].電子測(cè)量與儀器學(xué)報(bào)，2019，33（10）：89-95.XU Yuqiong，LOU Ke，LI Tingting，et al.Path planning of mobile robot based on improved adaptive ant colony algorithm[J].Journal of Electronic Measurement and Instrumentation，2019，33（10）：89-95.

[16]李憲強(qiáng)，馬戎，張伸，等.蟻群算法的改進(jìn)設(shè)計(jì)及在航跡規(guī)劃中的應(yīng)用[J].航空學(xué)報(bào)，2020，41（S2）：213-219.LI Xianqiang，MA Rong，ZHANG Shen，et al.Improved design of ant colony algorithm and its application in path planning[J].Acta Aeronautica et Astronautica Sinica，2020，41（S2）：213-219.

[17]唐立，郝鵬，張學(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.

[18]WANG H，GUO F，YAO H，et al.Collision avoidance planning method of USV based on improved ant colony optimization algorithm[J].IEEE Access，2019，7：52964-52975.

[19]LI B，QI X，YU B，et al.Trajectory planning for UAV based on improved ACO algorithm[J].IEEE Access，2019，8：2995-3006.

[20]LIU W，ZHENG X.Three-dimensional multi-mission planning of UAV using improved ant colony optimization algorithm based on the finite-time constraints[J].International Journal of Computational Intelligence Systems，2021，14（1）：79-87.

[21]YUE L，CHEN H.Unmanned vehicle path planning using a novel ant colony algorithm[J].Eurasip Journal on Wireless Communications and Networking，2019，2019（1）：1-9.

[22]SANGEETHA V，KRISHANKUMAR R，RAVICHANDRAN K S，et al.Energy-efficient green ant colony optimization for path planning in dynamic 3D environments[J].Soft Computing，2021，25（6）：4749-4769.

[23] MIAO C，CHEN G，YAN C，et al.Path planning optimization of indoor mobile robot based on adaptive ant colony algorithm[J].Computers & Industrial Engineering，2021，156：107230.

[24]LI F，ZLATANOVA S，KOOPMAN M，et al.Universal path planning for an indoor drone[J].Automation in Construction，2018，95：275-283.

[25]ZHANG X，WANG J，F(xiàn)ANG Y，et al.Multilevel humanlike motion planning for mobile robots in complex indoor environments[J].IEEE Transactions on Automation Science and Engineering，2018，16（3）：1244-1258.