布升強 梅淼 李瓊瓊 楊家富 王大明

摘 要：蟻群算法是解決森林防火機器人軌跡尋蹤問題的有效方法，針對傳統(tǒng)蟻群算法收斂速度慢、容易陷入局部最優(yōu)解的不足，本文設計一種自適應的蟻群算法。信息素啟發(fā)因子α與期望啟發(fā)因子β共同起引導螞蟻搜索的作用，動態(tài)調(diào)整兩者在搜索過程中的取值，提高收斂速度;基于地圖位置信息設計改進型的啟發(fā)式函數(shù)，提高前期搜索效率;依據(jù)螞蟻的行進意圖擴展禁忌表內(nèi)容，避免路徑交叉，減少螞蟻的迷失數(shù)量;在信息素更新函數(shù)中導入轉角指標，并通過信息素濃度對比試驗確定權重系數(shù)的最優(yōu)取值，使路徑更平滑;基于Matlab平臺搭建林區(qū)仿真地圖，對比測試自適應蟻群算法性能。試驗結果表明，自適應蟻群算法具有自適應調(diào)節(jié)能力、不會出現(xiàn)交叉路徑，與傳統(tǒng)蟻群算法相比，在收斂速度與搜索結果方面有著較好的改善。

關鍵詞：森林防火機器人;蟻群算法;軌跡尋蹤

Abstract：Ant colony algorithm is an effective method to solve the problem of track tracking of forest fire protection robot. Aiming at the shortcomings of traditional ant colony algorithm， such as slow convergence speed and easy to fall into the local optimum， an adaptive ant colony algorithm is proposed in this paper to solve these problems. Pheromone heuristic factor α and expectation heuristic factor β work together to guide the ant search. To accelerate the convergence rate， the value of α and β in the search process is dynamically adjusted. The heuristic function based on the information of location is designed to improve the efficiency of early ant search. Based on ants intention， the tabu table is expanded to avoid path crossing and reduce the number of lost ants. The corner performance index is added to the update function of pheromone to smooth the search path， and the optimal value of the weight coefficient is determined by the contrast test of pheromone concentration. The simulation map of forest region is built based on Matlab， and the performance of adaptive ant colony algorithm is. Experimental results show that the algorithm has the ability of self-adaptive adjustment， and does not appear cross path. Compared with the traditional ant colony algorithm， the algorithm has better convergence speed and better search results.

Keywords：Forest fireproof robot; ant colony algorithm; track tracing

0 引言

森林火災是一種突發(fā)性強、破壞力大的自然災害。森林火災事發(fā)突然，蔓延速度快，火災的撲滅也顯得格外困難。及時發(fā)現(xiàn)和清理隱燃的余火，特別是肉眼難以發(fā)現(xiàn)的無煙隱燃火，才能夠有效地避免發(fā)生余火復燃。長期以來，一直采用人工進行森林余火探測與清理，該方式效率低下并且危險系數(shù)很高。為了提高探測余火的效率和安全系數(shù)，需要一種有效的、快速的余火探測及清理移動消防機器人，該消防機器人能夠在森林地形條件下進行火災探測和清理等消防作業(yè)[1-4]。本文主要討論在全局環(huán)境信息已知的基礎上，林區(qū)防火機器人的軌跡尋蹤研究。

軌跡尋蹤技術是人工智能領域中的一個重要分支，主要用于引導移動機器人在已知環(huán)境內(nèi)快速搜索出一條從起始點與到目標點的可行路徑。軌跡尋蹤的算法大致可分為：基于勢場的搜索算法[5-6]，基于采樣的搜索算法[8-9]，基于仿生學的搜索算法[7]。其中，基于勢場的搜索算法與基于采樣的算法優(yōu)點在于能夠在短時間內(nèi)快速搜索出可行路徑，缺點是在大范圍復雜路況下搜索時，易陷入局部最優(yōu)甚至導致搜索失敗。相比之下，基于仿生學的搜索算法，能有效地求解出路徑最優(yōu)解，并表現(xiàn)出良好的自組織、自管理能力。本文選用基于仿生學的搜索算法作為該環(huán)境下的軌跡尋蹤算法。

在基于仿生學的搜索算法中，最具代表性的有蟻群算法（ACO）、粒子群算法（PSO）、細菌覓食法（BFO）、人工蜂群算法（ABC）和螢火蟲算法（FA）等，其中，蟻群算法（ACO）的啟發(fā)機制與反饋機制能保證算法的可靠性[10-13]，但傳統(tǒng)的蟻群算法存在收斂速度過慢和易陷入局部最優(yōu)點等不足。針對基本蟻群算法的這些缺點，國內(nèi)外學者們進行了相關研究，并提出了大量的改進方法，改進的思想可分為兩類：第一類是圍繞蟻群算法自身的結構和參數(shù)進行優(yōu)化，結構優(yōu)化的思想主要有最大最小蟻群系統(tǒng)[14-17]、精英螞蟻優(yōu)化策略[18]和雙向搜索策略[19]等，參數(shù)優(yōu)化的思想主要包括多要素的啟發(fā)式搜索策略[20]、帶賞罰機制的搜索策略[21]等;第二類是多算法融合的優(yōu)化思想，如多群落混合的搜索策略[22]、模擬退火的搜索策略[23]等。

林區(qū)環(huán)境中存在的障礙物種類主要以靜態(tài)障礙物為主，可將林區(qū)環(huán)境視為具有復雜路況的地圖。本文主要基于第一類優(yōu)化思想設計了自適應的蟻群算法，包括混合型的啟發(fā)式函數(shù)與復合型的信息素更新策略的設計，以及兩者權重系數(shù)的動態(tài)調(diào)整，同時擴增了禁忌表的內(nèi)容。

1 傳統(tǒng)蟻群算法

蟻群算法最初由意大利學者Marco Dorigo等于1991年提出[7]。在求解路徑規(guī)劃問題中，計算可行路徑處的轉移概率pmi，j（t），根據(jù)輪盤賭法選擇螞蟻下一步的移動位置。

轉移概率pmi，j（t）的具體公式為：

2 自適應改進型蟻群算法

2.1 參數(shù)α、β基于迭代次數(shù)的自適應改進

迭代初期，各路徑上的信息濃度大致相同，啟發(fā)式信息在搜索過程起引導作用。隨著算法迭代，路徑上的信息素逐漸累積，信息素替代啟發(fā)式信息在搜索過程中起引導作用。當某一路徑上的信息素濃度遠超過其他路徑上的信息素濃度時，為防止螞蟻因信息素累積而陷入局部最優(yōu)解的情況，需要減弱信息素的作用。由上述分析得出，α在迭代過程中呈現(xiàn)先增后減的變化趨勢，而β的變化趨勢與α“互鎖”，即先減后增的變化趨勢。在傳統(tǒng)的蟻群算法中，α和β通常取某個固定值，算法缺乏自適應能力。為描述參數(shù)α與β在迭代過程中的變化趨勢，本文選用幅度衰減的三角函數(shù)，見公式（3）和公式（4）。在不改變其他參數(shù)的基礎上，測試衰減幅度對算法性能的影響，見表1。當衰減程度為30%，搜索效果較好。

2.2 混合改進型啟發(fā)式函數(shù)

啟發(fā)式函數(shù)可視為搜索導向信息，引導螞蟻的搜索。傳統(tǒng)蟻群算法中，計算當前位置距離終點的最短距離，取該距離的倒數(shù)作為啟發(fā)式函數(shù)的取值，見公式（5）和公式（6）。這是一種貪心策略，螞蟻會因貪圖當前路徑而錯過全局最優(yōu)路徑，且容易在復雜路況下迷失。

2.3 信息素更新策略

蟻群算法中，更新信息素的方法[6]主要有：Ant-Cycle模型、Ant-Density模型和Ant-Quantity模型。傳統(tǒng)的蟻群算法常選擇Ant-Cycle模型作為信息素的更新策略，但是Ant-Cycle模型僅考慮路徑的最短距離，忽略了路徑的平滑程度。在機器人的應用領域，需要考慮轉彎角度的影響，因此本研究加入了轉角θcost指標，要求機器人搜索出一條轉角有限的平滑路徑。如圖2所示，A、B、C、D為路徑節(jié)點，start、goal則對應路徑的起點、終點，路徑的轉向角分別為φ1與φ2。

2.4 禁忌表優(yōu)化

傳統(tǒng)的蟻群算法中，為避免螞蟻重復搜索，螞蟻在確定移動位置后，便將當前位置加入禁忌表中，后續(xù)的螞蟻在選取移動路徑時，會參考禁忌表中的信息，避免出現(xiàn)“倒退”的情況，但“不倒退”的策略在面對“凹陷”的區(qū)域時，容易迷失在其中。螞蟻在“凹陷”區(qū)域內(nèi)搜索路徑，常會出現(xiàn)路線“相交”的情況。本文將“相交”路徑視為螞蟻陷入“凹陷”區(qū)域的標志，在此基礎上，把上一位置的鄰域加入禁忌表中以改善路徑“相交”的情況。

根據(jù)螞蟻移動情況，將螞蟻“后方”的位置加入禁忌表，確保螞蟻“前向”選擇路徑，圖4與圖5表示螞蟻往某一方向直行或轉彎后可行路徑的情況，在原始禁忌表的基礎上，將起始柵格（is，js）的相鄰點（is+signi，js+signj）加入禁忌表，其中signi與signj為位置增量標志，根據(jù)螞蟻具體的行進情況取值0、1。

3 仿真實驗

常見的地圖模型有：拓撲地圖、柵格地圖和四叉樹模型等，其中柵格地圖實現(xiàn)與維護簡單，常用于表示環(huán)境信息。本研究采用柵格法建立二維的地圖模型，林區(qū)存在的障礙物大多形狀不規(guī)則且分布不均，需對柵格地圖中的障礙物膨脹處理直至填滿柵格并記為1。

3.1 地圖模型

本研究采用柵格法建立二維的地圖模型，地圖中的柵格位置通過序號法表示，見公式：

3.2 算法流程

蟻群算法的參數(shù)選取一般根據(jù)經(jīng)驗取值，并通過實驗擇優(yōu)。迭代次數(shù)與螞蟻數(shù)量的取值過小影響算法的收斂結果，取值過大時效性差，通常將螞蟻數(shù)量設置為30～50只、迭代為100～150次。為突顯信息素對搜索過程的影響，蒸發(fā)系數(shù)設置為0.2～0.5。本研究選用20×20的柵格地圖，參數(shù)取值見表2。

3.3 結果分析

在20×20的柵格地圖上，分別測試原始蟻群算法，尤海龍等[7]基于迭代次數(shù)改進的蟻群算法（以下簡稱為改進蟻群算法），本文的自適應蟻群算法（以下簡稱為自適應蟻群算法）。對比測試不同算法間的差異，由于螞蟻遵循賭輪盤法的規(guī)則選取路徑，算法存在一定的隨機性，每一次執(zhí)行都可能得出不同的結果，因此，重復試驗10次，并記錄平均值。

（1）障礙物隨機分布地圖下的仿真實驗

在20×20的柵格地圖上，通過隨機函數(shù)生成障礙物的分布情況，設置障礙物數(shù)量占柵格總數(shù)量的35%。在此情況下，重復多次試驗并對所得試驗結果取均值。3種算法的路徑性能指標的對比結果見表3，路線情況如圖7所示。

在表3中，螞蟻迷失率等于搜索失敗的螞蟻數(shù)量比螞蟻的總數(shù)量，迭代穩(wěn)定次數(shù)取決路徑收斂的最小迭代次數(shù)并取整。結果表明，3種算法的搜索路徑長度相差不大，對比其余路徑指標，自適應蟻群算法與改進算法均優(yōu)于原始算法。自適應蟻群算法與改進算法在迷失率和迭代穩(wěn)定次數(shù)上差距不大，但在運行時間上自適應蟻群算法優(yōu)化了8.9%。

在圖6中，圓形標記代表本文的自適應蟻群算法，菱形標記代表改進蟻群算法，方形標記代表原始算法，3種算法的后半程搜索路線情況基本一致，差別集中在前半程路徑。自適應蟻群算法的搜索路徑在光滑程度方面要優(yōu)于傳統(tǒng)算法與改進蟻群算法。由圖7可知，自適應蟻群算法與改進蟻群算法的收斂情況均優(yōu)于原始算法，同時，自適應蟻群算法的收斂次數(shù)與最小路徑長度皆優(yōu)于改進蟻群算法。

4 結束語

根據(jù)森林防火機器人的軌跡尋蹤需求，基于原始蟻群算法，提出了一種自適應的蟻群算法。為降低螞蟻前期搜索的盲目性，在啟發(fā)式函數(shù)中加入了位置分布信息，引導螞蟻在搜索前期有針對性地進行搜索，提高了算法的收斂速度;動態(tài)調(diào)整α、β兩種參數(shù)的取值，優(yōu)化了算法的自適應能力;在信息素更新函數(shù)中導入轉角指標，要求螞蟻搜索出一條轉角較少的平滑路徑，同時驗證了轉角指標對信息素濃度分布的影響;擴增了禁忌表的內(nèi)容，以確保螞蟻前向搜索，有效地回避交叉路徑;在仿真試驗平臺下，驗證了算法的可行性與有效性，為森林防火機器人的軌跡尋蹤技術提供了理論基礎，但是本文主要針對靜態(tài)環(huán)境下復雜路徑規(guī)劃的研究，在動態(tài)性能方面，算法的搜索效率不高，還有待進一步的研究。

【參 考 文 獻】

[1]蔣敬， 郭會玲， 蔣霄然. 我國2005—2016年森林火災案件大數(shù)據(jù)分析[J]. 林業(yè)經(jīng)濟， 2019， 41（7）： 106-109.

JIANG J， GUO H L， JIANG X R. Big data analysis on chinas forest fire cases from 2005 to 2016[J]. Forestry Economics， 2019， 41（7）： 106-109.

[2]邸雪穎， 劉暢， 孫建， 等. 森林火災損失評估技術研究[J]. 森林工程， 2015， 31（2）： 42-45.

DI X Y， LIU C， SUN J， et al. Technical study on forest fire loss assessment[J]. Forest Engineering， 2015， 31（2）： 42-45.

[3]魏娜，肖冰，才麗華，等.基于GIS的森林安全防火系統(tǒng)的研究[J].林業(yè)機械與木工設備，2019，47（12）：16-19.

WEI N， XIAO B， CAI L H， et al. Research on forest safety fire prevention system based on GIS[J]. Forestry Machinery & Woodworking Equipment， 2019， 47（12）：16-19.

[4]陳越， 趙亞琴， 蔣林權，等. 森林火災火焰像素檢測的背景減除算法[J]. 林業(yè)工程學報， 2018， 3（4）：131-136.

CHEN Y， ZHAO Y Q， JIANG L Q. Background subtraction algorithms for detecting flame pixels of forest fire[J]. Journal of Forestry Engineering， 2018， 3（4）：131-136.

[5]劉志榮， 姜樹海. 基于強化學習的移動機器人路徑規(guī)劃研究綜述[J]. 制造業(yè)自動化， 2019， 41（3）：90-92.

LIU Z R， JIANG S H. Review of mobile robot path planning based on reinforcement learning[J]. Manufacturing Automation， 2019， 41（3）： 90-92.

[6]施楊洋，楊家富，布升強，等. 基于RRT改進的智能車輛路徑規(guī)劃算法[J]. 計算技術與自動化， 2019， 38（4）： 143-148.

SHI Y Y， YANG J F， BU S Q， et al. Improved intelligent vehicle pathing planning algorithm based on RRT[J]. Computing Technology and Automation， 2019， 38（4）： 143-148.

[7]尤海龍， 魯照權. 參數(shù)α、β和ρ自適應調(diào)整的快速蟻群算法[J]. 制造業(yè)自動化， 2018， 40（6）： 99-102.

YOU H L， LU Z Q. A fast ant colony algorithm for α， β and ρ adaptive adjustment[J]. Manufacturing Automation， 2018， 40（6）： 99-102.

[8]張瑋， 馬焱， 趙捍東， 等. 基于改進煙花-蟻群混合算法的智能移動體避障路徑規(guī)劃[J]. 控制與決策， 2019， 34（2）： 335-343.

ZHANG W， MA Y， ZHAO H D， et al. Obstacle avoidance path planning of intelligent mobile based on improved fireworks-ant colony hybrid algorithm[J]. Control and Decision， 2019， 34（2）： 335-343.

[9]RAJPUT U， KUMARI M. Mobile robot path planning with modified ant colony optimisation[J]. International Journal of Bio-Inspired Computation， 2017， 9（2）： 106.

[10]PATLE B K， BABU L G， PANDEY A， et al. A review： On path planning strategies for navigation of mobile robot[J]. Defence Technology， 2019， 15（4）： 582-606.

[11]康冰， 王曦輝， 劉富. 基于改進蟻群算法的搜索機器人路徑規(guī)劃[J]. 吉林大學學報（工學版）， 2014， 44（4）： 1062-1068.

KANG B， WANG X H， LIU F. Path planning of searching robot based on improved ant colony algorithm[J]. Journal of Jilin University （Engineering and Technology Edition）， 2014， 44（4）： 1062-1068.

[12]卜新蘋， 蘇虎， 鄒偉， 等. 基于復雜環(huán)境非均勻建模的蟻群路徑規(guī)劃[J]. 機器人， 2016， 38（3）： 276-284.

BU X P， SU H， ZOU W， et al. Ant colony path planning based on non-uniform modeling of complex environment[J]. Robot， 2016， 38（3）： 276-284.

[13]黃艷國，宋峰華.遺傳蟻群算法在公路隧道照明設計中的應用[J].公路工程，2018，43（4）：39-43.

HUANG Y G， SONG F H. Application of genetic ant colony algorithm in lighting design of highway tunnel[J]. Highway Engineering， 2018， 43（4）：39-43.

[14]BANERJEE A， CHATTOPADHYAY S， GHEORGHE G， et al. Minimization of reliability indices and cost of power distribution systems in urban areas using an efficient hybrid meta-heuristic algorithm[J]. Soft Computing， 2019， 23（4）： 1257-1281.

[15]劉建華， 楊建國， 劉華平， 等. 基于勢場蟻群算法的移動機器人全局路徑規(guī)劃方法[J]. 農(nóng)業(yè)機械學報， 2015， 46（9）： 18-27.

LIU J H， YANG J G， LIU H P， et al. Robot global path planning based on ant colony optimization with artificial potential field[J]. Transactions of the Chinese Society for Agricultural Machinery， 2015， 46（9）： 18-27.

[16]宋廣虎，馮全，海洋，等.采用深度學習法優(yōu)化的葡萄園行間路徑檢測[J].林業(yè)機械與木工設備，2019，47（7）：23-27.

SONG G H，F(xiàn)ENG Q，HAI Y，et al.Vineyard Inter-row Path Detection Based on Deep Learning[J].Forestry Machinery & Woodworking Equipment，2019，47（7）：23-27.

[17]王曉燕， 楊樂， 張宇， 等. 基于改進勢場蟻群算法的機器人路徑規(guī)劃[J]. 控制與決策， 2018， 33（10）： 1775-1781.

WANG X Y， YANG L， ZHANG Y， et al. Robot path planning based on improved ant colony algorithm with potential field heuristic[J]. Control and Decision， 2018， 33（10）： 1775-1781.

[18]方朋朋， 楊家富， 施楊洋， 等. 基于梯度下降法和改進人工勢場法的無人車避障方法[J]. 制造業(yè)自動化， 2018， 40（11）： 81-84.

FANG P P， YANG J F， SHI Y Y， et al. Gradient descent method and improved artificial potential field method for obstacle avoidance of unmanned vehicle[J]. Manufacturing Automation， 2018， 40（11）：81-84.

[19]DAI X L， LONG S， ZHANG Z W， et al. Mobile robot path planning based on ant colony algorithm with A* heuristic method[J]. Frontiers in Neurorobotics， 2019， 13： 15.

[20]TAHERI E， FERDOWSI M H， DANESH M. Closed-loop randomized kinodynamic path planning for an autonomous underwater vehicle[J]. Applied Ocean Research， 2019， 83： 48-64.

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

[22]孫瓊， 李林. 旅游路線規(guī)劃蟻群算法的偽隨機比例規(guī)則優(yōu)化[J]. 科技通報， 2016， 32（1）： 175-178.

SUN Q， LI L. Optimized pseudo-random proportion rule of ant colony algorithm for tourist routes planning[J]. Bulletin of Science and Technology， 2016， 32（1）： 175-178.

[23]CASTILLO O， NEYOY H， SORIA J， et al. A new approach for dynamic fuzzy logic parameter tuning in Ant Colony Optimization and its application in fuzzy control of a mobile robot[J]. Applied Soft Computing， 2015， 28： 150-159.