基于自適應多態(tài)融合蟻群算法的無人機航跡規(guī)劃

甄然 張春悅 矯陽 吳學禮

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

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

中圖分類號：TP273;V279+.2 ? 文獻標志碼：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)代科學技術的不斷進步，無人機技術飛速發(fā)展。無人機的航跡規(guī)劃在軍事、民用等領域具有十分重要的研究意義和價值。隨著作戰(zhàn)環(huán)境與作戰(zhàn)任務的日益復雜，無人機自主作戰(zhàn)、集群協(xié)同作戰(zhàn)等將逐步成為現(xiàn)代戰(zhàn)爭重要的作戰(zhàn)樣式[1]，路徑規(guī)劃算法的性能直接影響規(guī)劃路徑的質(zhì)量，甚至影響后續(xù)作戰(zhàn)任務的順利進行。航跡規(guī)劃的實質(zhì)是為執(zhí)行任務的飛行器規(guī)劃出一條最安全的飛行航跡[2]。

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

1 蟻群算法基本原理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實驗結(jié)果和分析

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

實驗參數(shù)設置如下。

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

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

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

4 結(jié) 語

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

參考文獻/References：

[1] 黃克明，王濤，胡軍.無人機作戰(zhàn)仿真平臺設計及其關鍵技術研究[J].兵工自動化，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] 王俊，周樹道，朱國濤，等.無人機航跡規(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] 劉學芳，曾國輝，黃勃，等.基于改進蟻群算法的移動機器人路徑規(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)化算法的無人機航跡規(guī)劃[J].彈箭與制導學報，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] 王志中.基于改進蟻群算法的移動機器人路徑規(guī)劃研究[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圖的無人機航跡規(guī)劃[J].系統(tǒng)仿真學報，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] 韓攀，陳謀，陳哨東，等.基于改進蟻群算法的無人機航跡規(guī)劃[J].吉林大學學報（信息科學版），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] 夏亞梅，程渤，陳俊亮，等.基于改進蟻群算法的服務組合優(yōu)化[J].計算機學報，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] 王楠，張軍，解鵬.基于改進AG算法的機器人動態(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] 楊雅寧，藺勇.基于蟻群算法的一種無人機二維航跡規(guī)劃方法研究[J].電腦知識與技術，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] 何燕.基于動態(tài)加權(quán)A*算法的無人機航跡規(guī)劃[J].河北科技大學學報，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.