甄然 張春悅 矯陽(yáng) 吳學(xué)禮

摘 要：為解決傳統(tǒng)航跡規(guī)劃最短路徑算法易陷入局部最優(yōu)及復(fù)雜地形情況下的無(wú)人機(jī)航跡規(guī)劃問(wèn)題，提出了一種基于自適應(yīng)多態(tài)融合蟻群算法的航跡規(guī)劃方法。通過(guò)對(duì)航跡規(guī)劃問(wèn)題進(jìn)行描述， 建立數(shù)學(xué)模型， 將自適應(yīng)和蟻群算法相結(jié)合，與多態(tài)蟻群形成了全局、局部并行搜索模式，以提高算法尋找全局最優(yōu)值的能力;提出自適應(yīng)并行策略和自適應(yīng)信息更新策略，以提升其全局搜尋能力。仿真結(jié)果表明，自適應(yīng)多態(tài)融合蟻群算法較傳統(tǒng)蟻群算法和多態(tài)蟻群算法具備更好的性能，能有效地提高搜索路徑的長(zhǎng)度和收斂速度，從而避免在求解過(guò)程中陷入局部最優(yōu)，因此在求解最優(yōu)航跡規(guī)劃問(wèn)題上有很好的應(yīng)用前景。

關(guān)鍵詞：計(jì)算機(jī)仿真;無(wú)人機(jī);航跡規(guī)劃;多態(tài)蟻群;自適應(yīng)并行策略

中圖分類號(hào)：TP273;V279+.2 ? 文獻(xiàn)標(biāo)志碼：A ? doi：10.7535/hbkd.2019yx06010

Abstract：Aiming at the problem of traditional UAV trajectory planning which falls into local optimum easily， and the problem of UAV trajectory planning in complex terrain， a trajectory planning method based on adaptive polymorphic fusion ant colony algorithm is proposed. This study describes the problem of route planning， establishes a mathematical model， and combines the adaptive ant colony algorithm with the polymorphic ant colony algorithm to form a global and local parallel search mode， which improves the ability of the algorithm to find the global optimal value. An adaptive parallel strategy and an adaptive information update strategy are proposed to improve the global search ability. Simulation results show that this method has better performance than the other two traditional ant colony algorithm and polymorphic ant colony algorithms. It can effectively improve the length and convergence speed of the search path and avoid falling into local optimum in the solution process. Therefore， the adaptive polymorphic fusion ant colony algorithm has a good application prospect in solving the optimal track planning problem.

Keywords：computer simulation; UAV; track planning; polymorphic ant colony; adaptive parallel strategy

隨著現(xiàn)代科學(xué)技術(shù)的不斷進(jìn)步，無(wú)人機(jī)技術(shù)飛速發(fā)展。無(wú)人機(jī)的航跡規(guī)劃在軍事、民用等領(lǐng)域具有十分重要的研究意義和價(jià)值。隨著作戰(zhàn)環(huán)境與作戰(zhàn)任務(wù)的日益復(fù)雜，無(wú)人機(jī)自主作戰(zhàn)、集群協(xié)同作戰(zhàn)等將逐步成為現(xiàn)代戰(zhàn)爭(zhēng)重要的作戰(zhàn)樣式[1]，路徑規(guī)劃算法的性能直接影響規(guī)劃路徑的質(zhì)量，甚至影響后續(xù)作戰(zhàn)任務(wù)的順利進(jìn)行。航跡規(guī)劃的實(shí)質(zhì)是為執(zhí)行任務(wù)的飛行器規(guī)劃出一條最安全的飛行航跡[2]。

傳統(tǒng)的航跡規(guī)劃最短路徑算法主要包括Dijkstra算法[3]、Floyd算法和A*算法[4]。常用的隨機(jī)搜索算法包括遺傳算法、粒子群算法[5]、蟻群算法等智能優(yōu)化算法。本文根據(jù)文獻(xiàn)把路徑規(guī)劃算法分為網(wǎng)格圖法、路線圖法和人工勢(shì)場(chǎng)法[6-8]。基于各類智能算法，研究人員在路徑規(guī)劃方面已經(jīng)做了大量工作[9-12]。其中，文獻(xiàn)＼[9＼]動(dòng)態(tài)地提出了一種多信息素更新的蟻群算法。文獻(xiàn)＼[10＼]提出了基于混合動(dòng)力車輛路徑問(wèn)題的局部搜索問(wèn)題與傳統(tǒng)蟻群相結(jié)合的蟻群算法。文獻(xiàn)＼[11＼]針對(duì)路徑對(duì)準(zhǔn)問(wèn)題，提出了一種自適應(yīng)蟻群優(yōu)化算法。蟻群算法是一種用來(lái)尋找最優(yōu)路徑的智能優(yōu)化算法，具有強(qiáng)大的魯棒性和搜索更好解決方案的能力，但易陷入局部最優(yōu)，搜索時(shí)間長(zhǎng)，文獻(xiàn)＼[12＼]提出了自適應(yīng)并行蟻群算法來(lái)解決這一問(wèn)題。

1 蟻群算法基本原理

20世紀(jì)90年代初，意大利學(xué)者DORIGO等通過(guò)模擬螞蟻對(duì)自然界食物的集體搜索，提出了蟻群算法（ACA）。螞蟻覓食是一種基于群體的啟發(fā)式仿生算法，不是單一的螞蟻?zhàn)灾鲗ふ沂澄飦?lái)源。螞蟻在覓食時(shí)會(huì)利用特殊的感官能力，這些能力使它們始終能夠找到巢穴和食物來(lái)源之間的最短路徑。覓食行為取決于螞蟻和螞蟻之間或螞蟻個(gè)體與環(huán)境之間的交流，這是基于螞蟻產(chǎn)生的化學(xué)物質(zhì)（稱為信息素）的使用。螞蟻在走路時(shí)將信息素存放在地面上，并傾向于沿著信息素含量高的路徑行進(jìn)，孤立的螞蟻隨意移動(dòng)。然而，當(dāng)它遇到信息素的蹤跡時(shí)，遵循這條蹤跡的概率會(huì)增加。螞蟻的工作原理如下：首先，當(dāng)螞蟻到達(dá)它們必須決定向左或向右轉(zhuǎn)的決定點(diǎn)時(shí)，螞蟻會(huì)隨機(jī)選擇下一條路徑并將信息素存放在地面上，因?yàn)樗鼈儾恢滥膫€(gè)是最佳選擇。在短暫停頓選擇之后，兩條路徑上信息量的差異足以影響新的螞蟻進(jìn)入系統(tǒng)的決定，從此刻開(kāi)始，新的螞蟻將更有可能選擇信息量較多的路徑。因此，螞蟻可以聞到信息素的味道，并且很可能選擇強(qiáng)信息素濃度為標(biāo)志的路徑。蟻群算法具有正反饋、分布式計(jì)算和用于貪婪搜索的特點(diǎn)，因而具有較強(qiáng)的魯棒性和搜索性，目前已應(yīng)用于多個(gè)領(lǐng)域，例如：旅行商問(wèn)題（traveling salesman problem）[13]、工作流轉(zhuǎn)分配問(wèn)題、工作車間模式調(diào)度問(wèn)題[3]等。傳統(tǒng)蟻群算法和大部分改進(jìn)算法都是基于單種蟻群、單種信息素的算法，主要模擬了實(shí)際蟻群系統(tǒng)的一部分。在自然界當(dāng)中，真實(shí)螞蟻社會(huì)中的蟻群是有計(jì)劃、有組織的，類似于人類，不同種類的螞蟻群體具有不同的信息素控制機(jī)制，不同的控制機(jī)制對(duì)不同群體完成繁雜任務(wù)具有非常重要的作用。除此以外，蟻群算法還存在搜索時(shí)間長(zhǎng)、收斂速度慢、容易陷入局部最優(yōu)等缺點(diǎn)[14]。

2 自適應(yīng)多態(tài)融合蟻群算法路徑規(guī)劃

2.1 多態(tài)蟻群算法

根據(jù)傳統(tǒng)蟻群算法進(jìn)行具體分化的多態(tài)蟻群算法，這里面的“多態(tài)性”是指蟻群社會(huì)中各種形態(tài)的蟻群和信息素。螞蟻根據(jù)任務(wù)及分工的不同，分為偵察蟻、搜索蟻和工蟻，各種螞蟻各司其職[15]。其中，工蟻蟻群與路徑尋優(yōu)無(wú)關(guān)，所以就只需針對(duì)偵察蟻群和搜索蟻群，設(shè)計(jì)各自的信息素調(diào)節(jié)機(jī)制[15]，偵察蟻群負(fù)責(zé)局部偵察，搜索蟻群負(fù)責(zé)全局搜索。這種利用螞蟻種群的分工機(jī)制大大提高了螞蟻群體之間的合作效果，增強(qiáng)了算法的有效性[15]。

為了解決死鎖問(wèn)題，科學(xué)家采用早期死亡這種方法，該方法的主要思想是使陷入死鎖中的螞蟻死亡，從而停止更新已經(jīng)走過(guò)的路徑上的信息素。當(dāng)大量螞蟻處于死鎖狀態(tài)時(shí)，該方法不僅不利于全局尋優(yōu)，而且降低了路徑解的多樣性。文獻(xiàn)＼[18＼]用回退法解決這個(gè)問(wèn)題，當(dāng)螞蟻陷入死鎖時(shí)，不要讓它死去，而是允許它后退一步，繼續(xù)搜索。

本文研究的方向確定法是一種解決死鎖問(wèn)題的工具，當(dāng)螞蟻處于死鎖狀態(tài)時(shí)，對(duì)禁忌表進(jìn)行更新[19]，對(duì)死鎖邊緣的信息素進(jìn)行懲罰，使得螞蟻可以在原有位置上調(diào)整前進(jìn)方向，找到無(wú)障礙方向[20]，然后繼續(xù)前進(jìn)，這個(gè)方向如圖2中的箭頭所示。

該方法在解決死鎖問(wèn)題中的應(yīng)用目的是提高算法的全局搜索能力，有效地減少其他螞蟻在同一個(gè)位置陷入死鎖的可能性，它的信息素懲罰公式為τrs=（1-λ）τrs，（9）式中1-λ是相應(yīng)的懲罰系數(shù)。

自適應(yīng)多態(tài)融合蟻群算法無(wú)人機(jī)路徑規(guī)劃的具體步驟方法如下。

步驟1：采用網(wǎng)格法對(duì)初始環(huán)境進(jìn)行建模，設(shè)置常量q，c，n。

步驟2：將m偵察蟻分別放置在n路徑節(jié)點(diǎn)上，每個(gè)偵察蟻調(diào)查以其路徑節(jié)點(diǎn)為中心的其他（n-1）路徑節(jié)點(diǎn)，根據(jù)式（1）計(jì)算偵察要素，并將結(jié)果放置到sij中。

步驟3：根據(jù)式（2）設(shè)定初始時(shí)刻各路徑上的初始信息量。

步驟4：隨機(jī)選擇每個(gè)搜索螞蟻的初始位置，并將其放入相應(yīng)的禁忌表中。

步驟5：根據(jù)式（6）計(jì)算每只搜索螞蟻k下一步轉(zhuǎn)移的位置，將其設(shè)置為j;將前一位置設(shè)置為i，并將j放入搜索螞蟻k的相應(yīng)禁忌表中，直到每個(gè)搜索螞蟻完成一個(gè)周期以獲得解;如果螞蟻k在路徑搜索中陷入死鎖，那么采用方向確定法解決死鎖問(wèn)題。

步驟6：計(jì)算每個(gè)搜索螞蟻的路徑長(zhǎng)度Lk（k=1，2，…，m），并記錄當(dāng)前最優(yōu)解。

步驟7：如果已經(jīng)達(dá)到指定的迭代次數(shù)，或者所求的解在最近迭代中沒(méi)有明顯改善，則跳轉(zhuǎn)到步驟9;否則，根據(jù)式（8）修改每條路徑的信息素濃度。

步驟8：將i，j設(shè)置為0，清除禁忌表，將NC+1更新為NC，并返回步驟4。

步驟9：輸出最優(yōu)解。

3 實(shí)驗(yàn)結(jié)果和分析

為了驗(yàn)證基于自適應(yīng)多態(tài)融合蟻群算法的有效性，利用柵格法進(jìn)行仿真。在設(shè)置的柵格環(huán)境下，對(duì)傳統(tǒng)蟻群算法、多態(tài)蟻群算法和自適應(yīng)多態(tài)融合蟻群算法進(jìn)行仿真驗(yàn)證。無(wú)人機(jī)可移動(dòng)方向如圖3所示。

實(shí)驗(yàn)參數(shù)設(shè)置如下。

螞蟻數(shù)m=150，迭代次數(shù)n=210，信息素重要程度因子α=1，啟發(fā)函數(shù)重要程度因子β=5，信息素蒸發(fā)系數(shù)ρ=0.9，常數(shù)Q=100，初始時(shí)間c=3時(shí)每條路徑上的信息量，初始建模設(shè)置為22×22的柵格地形圖。

在圖4—圖6中獲得3個(gè)路徑中的最優(yōu)路徑長(zhǎng)度，從圖中可以發(fā)現(xiàn)，自適應(yīng)多態(tài)融合蟻群算法的路徑長(zhǎng)度要優(yōu)于傳統(tǒng)蟻群算法和多態(tài)蟻群算法。

根據(jù)表1的3種算法的數(shù)據(jù)對(duì)比可知，傳統(tǒng)蟻群算法和多態(tài)蟻群算法的最優(yōu)路徑長(zhǎng)度比改進(jìn)的自適應(yīng)多態(tài)融合蟻群算法路徑長(zhǎng)得多。在進(jìn)行的20次運(yùn)算中，前兩種算法分別小于或等于35 m的次數(shù)為7次和9次，第3種算法分別小于或等于35 m的次數(shù)有20次，結(jié)果都小于35 m，最優(yōu)路徑長(zhǎng)度為33.56 m。圖7—圖9為3種算法的迭代曲線。改進(jìn)后的算法在全局航跡計(jì)劃中實(shí)現(xiàn)了快速收斂，所找尋到的航跡長(zhǎng)度較短，航跡較為平滑。實(shí)驗(yàn)結(jié)果表明，在最優(yōu)航跡、收斂性和迭代效果方面，本文采用自適應(yīng)多態(tài)融合蟻群算法得到的路徑規(guī)劃效果要好于另外兩種算法。

4 結(jié) 語(yǔ)

為了在無(wú)人機(jī)有障礙的情況下尋找出最優(yōu)航跡，提出了一種自適應(yīng)多態(tài)融合蟻群算法。在多態(tài)蟻群算法的基礎(chǔ)上，引入了自適應(yīng)并行規(guī)則和偽隨機(jī)規(guī)則，避免了搜索過(guò)程中容易陷入局部最優(yōu)問(wèn)題。搜索螞蟻在搜索階段根據(jù)偽隨機(jī)規(guī)則進(jìn)行狀態(tài)轉(zhuǎn)移，同時(shí)采用自適應(yīng)并行策略確定狀態(tài)轉(zhuǎn)移函數(shù)中的最優(yōu)組合參數(shù)。用方向確定法來(lái)解決螞蟻在搜索過(guò)程中陷入死鎖問(wèn)題，提高了算法的全局搜索能力，有效地減少其他螞蟻在同一個(gè)位置陷入死鎖的可能性。對(duì)于不同分工的蟻群，分別進(jìn)行局部搜索和全局搜索，增強(qiáng)了算法的全局搜索能力，能有效避免陷入局部最優(yōu)，而且明顯提升了最優(yōu)路徑的長(zhǎng)度。本文只考慮了靜態(tài)障礙物的航跡規(guī)劃，在未來(lái)的研究中應(yīng)考慮動(dòng)態(tài)障礙物的航跡規(guī)劃，并在此算法的基礎(chǔ)上改進(jìn)動(dòng)態(tài)障礙物航跡規(guī)劃。

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

[1] 黃克明，王濤，胡軍.無(wú)人機(jī)作戰(zhàn)仿真平臺(tái)設(shè)計(jì)及其關(guān)鍵技術(shù)研究[J].兵工自動(dòng)化，2016，35（1）：90-95.

HUANG Keming， WANG Tao， HU Jun. Study on design of UAV combat simulation platform and its key techniques[J].Ordnance Industry Automation，2016，35（1）：90-95.

[2] 王俊，周樹(shù)道，朱國(guó)濤，等.無(wú)人機(jī)航跡規(guī)劃常用算法[J].火力與指揮控制，2012，37（8）：5-8.

WANG Jun， ZHOU Shudao， ZHU Guotao，et al. Research of common route planning algorithms for unmanned air vehicle[J].Fire Control & Command Control，2012，37（8）：5-8.

[3] GAN Rongwei，GUO Qingshun，CHANG Huiyou，et al.Improved ant colony optimization algorithm for the traveling salesman problems[J].Journal of Systems Engineering and Electronics，2010，21（2）： 329-333.

[4] 劉學(xué)芳，曾國(guó)輝，黃勃，等.基于改進(jìn)蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃研究[J].電子科技，2019，32（9）：5-9.

LIU Xuefang，ZENG Guohui，HUANG Bo，et al. Research on path planning of mobile robot based on improved ant colony algorithm[J].Electronic Science and Technology， 2019，32（9）：5-9.

[5] 陳冬，周德云，馮琦.基于粒子群優(yōu)化算法的無(wú)人機(jī)航跡規(guī)劃[J].彈箭與制導(dǎo)學(xué)報(bào)，2007，27（4）：340-342.

CHEN Dong， ZHOU Deyun， FENG Qi. Route planning for unmanned aerial vehicles based on particle swarm optimization[J].Journal of Projectiles Rockets，Missiles and Guidance，2007，27（4）：340-342.

[6] 王志中.基于改進(jìn)蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃研究[J].機(jī)械設(shè)計(jì)與制造，2018（1）：242-244.

WANG Zhizhong. Path planning for molile robot based on improved ant colony algorithm[J].Machinery Design & Manufacture，2018（1）：242-244.

[7] 趙文婷，彭俊毅.基于 VORONOI圖的無(wú)人機(jī)航跡規(guī)劃[J].系統(tǒng)仿真學(xué)報(bào)，2006，18（sup2）：159-162.

ZHAO Wenting，PENG Junyi.VORONOI diagram-based path planning for UAVs[J].Journal of System Simulation，2006，18（sup2）：159-162.

[8] 韓攀，陳謀，陳哨東，等.基于改進(jìn)蟻群算法的無(wú)人機(jī)航跡規(guī)劃[J].吉林大學(xué)學(xué)報(bào)（信息科學(xué)版），2013，31（1）：66-72.

HAN Pan，CHEN Mou，CHEN Shaodong，et al.Path planning for UAVs based on improved ant colony algorithm[J].Journal of Jilin University （Information Science Edition），2013，31（1）：66-72.

[9] 夏亞梅，程渤，陳俊亮，等.基于改進(jìn)蟻群算法的服務(wù)組合優(yōu)化[J].計(jì)算機(jī)學(xué)報(bào)，2012，35（2）：270-281.

XIA Yamei，CHENG Bo，CHEN Junliang，et al.Optimizing services composition based on improved ant colony algorithm[J].Chinese Journal of Computers，2012，35（2）：270-281.

[10] CHENG C T， FALLAHI K， LEUNG H，et al. An AUVs path planner using genetic algorithms with a deterministic crossover operator[C]//2010 IEEE International Conference on Robotics and Automation.Anchorage：IEEE，2010：5509335.

[11] ?Al-TAHARWA I， SHETA A，Al-WESHAH M. A mobile robot path planning using genetic algorithm in static environment[J].Journal of Computer Science，2008，4（4）：341-344.

[12] 王楠，張軍，解鵬.基于改進(jìn)AG算法的機(jī)器人動(dòng)態(tài)路徑規(guī)劃方法[J].河北工業(yè)科技，2018，35（3）：178-184.

WANG Nan， ZHANG Jun， XIE Peng. Robot dynamic path planning method based on improved AG algorithm[J]. Hebei Journal of Industrial Science and Technology，2018，35（3）：178-184.

[13] KOREN Y， BORENSTEIN J. Potential field methods and their inherent limitations for mobile robot navigation[C]//1991 IEEE International Conference on Robotics and Automation.Sacramento：IEEE，1991：131810.

[14] 楊雅寧，藺勇.基于蟻群算法的一種無(wú)人機(jī)二維航跡規(guī)劃方法研究[J].電腦知識(shí)與技術(shù)，2016，12（28）：188-191.

[15] MAVROVOUNIOTIS M， MLLER F M，YANG Shengxiang. Ant colony optimization with local search for dynamic traveling salesman problems[J].IEEE Transactions on Cybernetics，2017，47（7）：1743-1756.

[16] ZHAI Yahong，XU Longyan，YANG Yanxia. Ant colony algorithm research based on pheromone update strategy[C]//Proceedings of the 2015 7th International Conference on Intelligent Human-Machine Systems and Cybernetics. Washington DC： IEEE，2015：38-41.

[17] 何燕.基于動(dòng)態(tài)加權(quán)A*算法的無(wú)人機(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 Tech-nology， 2018，39（4）：349-355.

[18] WEN Naifeng，ZHAO Lingling，SU Xiaohong，et al.UAV online path planning algorithm in a low altitude dangerous environment[J].IEEE/CAA Journal of Automatica Sinica，2015， 2（2）：173-185.

[19] PHUNG M D，QUACH C H，DINH T H，et al.Enhanced discrete particle swarm optimization path planning for UAV vision-based surface inspection[J].Automation in Construction，2017，81（6）：25-33.

[20] QI Huang， ZHENG Guilin. Route optimization for autonomous container truck based on rolling window[J].International Journal of Advanced Robotic System，2016，13（3）：112-121.