摘 要：針對傳統(tǒng)蟻群算法在機器人路徑規(guī)劃中路徑不是最短距離、運行時間長以及收斂速度慢等問題，提出多鄰域蟻群算法（multi-neighborhood ant colony algorithm，ACO-MN）。為了解決路徑不是最短距離的問題，引入多鄰域搜索，使得搜索鄰域擴大，機器人的路徑距離減小；為了解決運行時間長的問題，在快速判斷的基礎上運用象限概率和象限概率控制參數(shù)，使得算法運行加快；為了解決收斂速度慢的問題，結合步長和鄰域夾角改進啟發(fā)函數(shù)，使得算法在后期的收斂速度加快。最后，在不同大小、不同復雜程度的柵格地圖下，將ACO-MN與傳統(tǒng)蟻群算法和其他改進算法進行仿真對比實驗。實驗表明，在小規(guī)模簡單環(huán)境下ACO-MN的收斂速度相比于傳統(tǒng)蟻群算法加快了76.19%，在大規(guī)模復雜環(huán)境下ACO-MN的運行時間相比于其他改進算法縮短了49.84%，最短路徑縮短了5.6%，驗證了該算法的有效性和優(yōu)越性。

關鍵詞：蟻群算法；路徑規(guī)劃；多鄰域；啟發(fā)函數(shù)；象限概率控制參數(shù)；機器人

中圖分類號：TP242

文獻標志碼：A

收稿日期：2023-09-06

基金項目：湖南省自科基金（2022JJ50205）；湖南省教育廳科研項目（21B0682，21B0676，21C0599）；湖南省科技計劃項目（2016TP1023）；邵陽學院研究生科研創(chuàng)新項目（CX2023SY083）

作者簡介：唐宏偉，男，教授， 博士，主要從事智能機器人導航及自動控制研究工作；E-mail：125474096@qq.com

羅佳強，男，碩士研究生，從事移動機器人路徑規(guī)劃研究工作；E-mail：1443741855@qq.com

Robot path planning based on multi-neighborhood ant colony algorithm

TANG Hongwei， LUO Jiaqiang

（Hunan Provincial Key Laboratory of Grids Operation and Control on Multi-Power Source Area， Shaoyang University， Shaoyang 422000， China）

Abstract： Aiming at the problems of traditional ant colony algorithm in robot path planning， such as the path was not the shortest distance， long running time， and slow convergence speed， a multi-neighborhood ant colony algorithm （ACO-MN） was proposed. In order to solve the problem that the path was not the shortest distance， multi-neighborhood search was introduced to expand the search field and reduce the path distance of the robot; in order to solve the problem of long running time， quadrant probability and quadrant probability control parameters were used on the basis of rapid judgment， which made the algorithm run faster; in order to solve the problem of slow convergence speed， the heuristic function was improved by combining the step size and the angle between fields， so that the convergence speed of the algorithm was accelerated in the later stage. Finally， the multi-neighborhood ant colony algorithm was simulated and compared with the traditional ant colony algorithm and other improved algorithms under different size and complexity grid maps. The experiments show that the convergence speed of this algorithm is 76.19% faster higher than the traditional ant colony algorithm in small-scale simple environment， and the running time of the algorithm is 49.84% less than other improved algorithms in large-scale complex environment， and the shortest path is 5.6% shorter， which verifies the effectiveness and superiority of the algorithm.

Key words： ant colony algorithm; path planning; multi-neighborhood; heuristic function; quadrant probability control parameters; robot

唐宏偉，羅佳強：基于多鄰域蟻群算法的機器人路徑規(guī)劃

機器人的開發(fā)是一個重要并且具有挑戰(zhàn)的課題。傳統(tǒng)的路徑規(guī)劃算法如A*算法［1］和人工勢場法［2］等，已經(jīng)取得了極大的成功。隨著計算機的快速發(fā)展，開始新興起一種模仿生物群體行為規(guī)律的智能群算法如粒子群算法［3］、人工蜂群算法［4］和蟻群算法［5-10］。智能群算法在解決大規(guī)模復雜地形問題時有較大優(yōu)勢，近年來研究比較多。

由于蟻群算法具有計算簡單、參數(shù)少等特點，其廣泛運用于機器人路徑規(guī)劃。然而傳統(tǒng)蟻群算法存在規(guī)劃的路徑不是最短距離、運行時間長及收斂速度慢等問題，針對這些缺點，文獻［11-13］提出人工勢場法與蟻群算法相結合，該算法在復雜地形下性能優(yōu)越，但是規(guī)劃的路徑不是最短距離。徐菱等［14］提出改變傳統(tǒng)蟻群算法的搜索方式，變成16方向24鄰域的搜索方式，有效地減小了路徑長度，但是收斂速度緩慢。曾明如等［15］提出多步長蟻群算法，使得螞蟻可以找到一條最短路徑，但是運行時間較長。LI等［16］提出基于特征點，采用不等分配信息素和雙向并行策略，縮短算法運行時間，但是規(guī)劃的路徑距離較長。蒲興成等［17］提出一種新的回退策略，通過該策略處理U型障礙死鎖問題，但是收斂速度慢。陳青楨等［18］提出U型障礙物多方向多層填充，有效地解決了路徑死鎖問題，但需要對地圖進行預處理，增加了算法運行時間。

上述改進算法，都以犧牲一些性能為基礎去解決某些問題。本文為同時解決路徑不是最短距離、運行時間長及收斂速度慢等問題，提出多鄰域蟻群算法（multi-neighborhood ant colony algorithm，ACO-MN），ACO-MN提出增加鄰域的方法，使得螞蟻在路徑搜索時有比傳統(tǒng)蟻群算法更長的步長，有效地減小路徑長度和拐點個數(shù)。引入象限概率控制參數(shù)，來控制螞蟻的搜索范圍，減小運行時間。引入一種新的基于鄰域夾角和步長的啟發(fā)函數(shù)，加快算法收斂速度。最后，通過仿真實驗結果，驗證了ACO-MN的先進性。

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

蟻群算法模仿螞蟻的生物特性，即螞蟻在覓食過程中分泌的一種具有吸引力的信息素，從而形成正反饋，讓螞蟻快速找到一條距離食物最近的路徑。

標準蟻群算法選擇下一節(jié)點j的概率公式Pkij如下：

Pkij=τijtαηijtβ∑s∈Allowedτijtαηijtβ0，jAllowed（1）

式中：τijt為螞蟻在t時刻從i節(jié)點到j節(jié)點路徑上的信息素濃度值；ηijt為啟發(fā)函數(shù)螞蟻在t時刻從i節(jié)點到j節(jié)點的直線距離；α為信息素啟發(fā)因子；β為期望啟發(fā)因子，為常數(shù)。Allowed為螞蟻從i節(jié)點可以到達下一個所有節(jié)點的集合。信息素更新公式τijt+1如下：

τijt+1=1－pτijt+pΔτij（t）（2）

Δτij（t）=∑Mk=1τkij（3）

式中：p為信息素揮發(fā)因子；Δτij（t）為在本次循環(huán)中所有從i節(jié)點到j節(jié)點螞蟻留下的信息素濃度的和；M為本次循環(huán)中可以從i節(jié)點到j節(jié)點的螞蟻總數(shù)。

2 改進蟻群算法

針對傳統(tǒng)蟻群算法存在的一些問題，對螞蟻的搜索方式進行改進，并對螞蟻鄰域的數(shù)量進行調(diào)整。

2.1 環(huán)境感知

本文提出一種對角探索方式，在時間上更加迅速。探索原理為遇到障礙物就停止該方向的探索。

對角探索方式具體操作為：螞蟻從當前點沿著水平和垂直方向爬行，遇到障礙物停止該方向搜索，然后回到當前點，沿著對角線向外移動一個柵格，一直重復該操作，直到沿著對角線向外移動一個柵格是障礙物，這條對角線探索完成。螞蟻爬行的柵格范圍，代表最終螞蟻可以感知到的最大范圍（圖1），其中灰色柵格表示未探索范圍。對于沒有探索到的柵格，全部按障礙物處理（圖2）。

2.2 環(huán)境決策

在螞蟻探索的范圍內(nèi)，仍然有些區(qū)域不可到達，現(xiàn)對環(huán)境做出決策找到探索范圍內(nèi)的全部可行柵格。以螞蟻當前位置為原點，把環(huán)境劃分為8個高度對稱區(qū)域，每個區(qū)域內(nèi)，邊界障礙物柵格距離對角線最近的頂角稱為臨界點（圖3），其中，臨界點用空心小圓表示。由于8個區(qū)域高度對稱，現(xiàn)以區(qū)域1為例介紹決策原理，其他區(qū)域類似。

決策原理為：把螞蟻當前柵格中心點和當前臨界點連接并延長線段，延長線段與被影響那列柵格中心的垂直線相交于一點，這點為極限點（圖4），其中，黑色小圓點表示極限點，在垂直線的基礎上，向遠離螞蟻當前位置移動一定距離，一定會和當前臨界點的障礙物柵格相撞。

為方便計算出極限點精確位置，以螞蟻當前柵格中心位置為坐標原點建立直角坐標系。極限點到Y軸距離已知，但是到X軸距離位置未知，需要進行公式推導。

極限點到X軸距離SX計算公式如下：

SX=SYiXiY（4）

式中：SY為極限點到Y軸的距離；iX為臨界點到X軸的距離；iY為臨界點到Y軸的距離。

由柵格地圖知道每個柵格對應的行數(shù)和列數(shù)，對式（4）進行進一步的展開。

SY=jL-ALa，jL∈Gather（5）

iX=iH-AHa（6）

iY=iL-ALa（7）

式中：jL為極限點柵格列數(shù)；iL為當前臨界點柵格的列數(shù)；iH為當前臨界點柵格的行數(shù)；AL為螞蟻當前點列數(shù)；AH為螞蟻當前點的行數(shù)；a為一個小柵格的邊長；Gather為當前臨界點可以影響列的集合。

由于柵格法特性，螞蟻只可以從一個柵格中心到達另一個柵格中心［19］。但是極限點位置可能不在柵格中心。運用公式把極限點轉(zhuǎn)化為柵格中心形式。

c=floor（SXa）（8）

式中：c為螞蟻在該列可行柵格的個數(shù)；floor為取下整函數(shù)。

2.3 快速判斷

根據(jù)兩點之間線段最短，如果螞蟻鄰域中存在終點，則不用再對全部鄰域運用輪盤賭法進行下一節(jié)點選擇，螞蟻直接快速判斷終點為下一節(jié)點。改進算法可以進行快速判斷，先決條件是上文對環(huán)境的決策和感知使得鄰域數(shù)量急劇上升，增加了終點出現(xiàn)在當前節(jié)點鄰域的概率。

2.4 改進參數(shù)

2.4.1 象限概率

隨著搜索精度的提高，螞蟻會存在很多鄰域，提出象限概率，在不減少路徑多樣性的情況下，減少鄰域的判斷，以縮短算法收斂時間。以螞蟻當前點為坐標原點，建立直角坐標系，終點所屬象限概率為0.5，相鄰的兩象限概率都為0.2，對角象限概率為0.1。螞蟻在眾多鄰域中選擇下一節(jié)點時，螞蟻會根據(jù)象限概率，只選擇其中一個象限里的鄰域運用輪盤賭法進行選擇。

2.4.2 象限概率控制參數(shù)

本文根據(jù)文獻［14］提出的控制參數(shù)思想，提出象限概率控制參數(shù)δ∈0，1，通過對δ的取值來控制象限選擇策略。

螞蟻在進行象限選擇前，產(chǎn)生一個自適應參數(shù)μ

μ=e－tT（9）

式中：μ∈0，1；t為當前迭代次數(shù)；T為算法最大迭代次數(shù)。當μ≥δ時，螞蟻運用象限概率來選擇需要的象限；反之，當μlt;δ時，螞蟻直接選擇終點所在的象限。

2.5 改進啟發(fā)函數(shù)

隨著鄰域的增加，改進后的蟻群算法不再適用于傳統(tǒng)蟻群算法的啟發(fā)函數(shù)，本文基于步長和鄰域夾角提出一種新的啟發(fā)函數(shù)公式。

鄰域夾角θ∈0°，180°，從當前節(jié)點位置向終點和鄰域中心點作出兩條線段的夾角，如圖5所示，其中左上角為螞蟻當前位置，右下角為終點。

以θ和步長（螞蟻當前位置到下一鄰域的歐式距離）為變量的啟發(fā)函數(shù)公式如下：

ηij=dεijθβij（10）

式中：θij為當前節(jié)點到下一節(jié)點的鄰域夾角；dij為當前節(jié)點到下一節(jié)點的步長；β為一個常數(shù)，表示鄰域夾角啟發(fā)因子；ε為一個常數(shù)，表示步長啟發(fā)因子。

2.6 算法步驟

改進后的蟻群算法流程圖見圖6，步驟如下。

Step1使用柵格法構造地圖，初始化相關參數(shù)：起點位置、終點位置、障礙物面積占整個地圖面積的比例w、迭代次數(shù)N、螞蟻數(shù)量M、信息素啟發(fā)因子α、步長啟發(fā)因子ε、鄰域夾角啟發(fā)因子β、象限概率控制參數(shù)δ、信息素揮發(fā)系數(shù)p。并且初始化禁忌表［20］。

Step2 M只螞蟻從起點出發(fā)，通過探索周圍環(huán)境做出決策，找到全部可行鄰域。

Step3 對全部可行鄰域進行快速判斷。判斷成功，該螞蟻搜索完成，進行下一只螞蟻的鄰域選擇；判斷不成功，該螞蟻繼續(xù)進行鄰域選擇。

Step4 隨機生成μ，判斷μ和象限概率控制參數(shù)δ大小，選擇螞蟻下一鄰域的所屬象限。

Step5 計算鄰域的選擇概率pkij，根據(jù)概率選擇下一節(jié)點，并更新禁忌表。

Step6 M只螞蟻全部完成搜索后，更新信息素。

Step7 循環(huán)步驟2到步驟5，直到達到迭代次數(shù)N，最后輸出路徑。

3 仿真與分析

為了驗證ACO-MN的優(yōu)越性，先通過MATLAB R2016b對ACO-MN提出的新參數(shù)進行仿真實驗并分析數(shù)據(jù)，找到最優(yōu)參數(shù)值，然后將本文ACO-MN與傳統(tǒng)蟻群算法和文獻［11］的改進蟻群算法在不同大小、不同復雜程度地圖下進行對比分析。實驗基本參數(shù)設置見表1，左上角設置為起點，右下角設置為終點。

3.1 與傳統(tǒng)蟻群算法進行仿真對比實驗

為了驗證本文改進算法的優(yōu)越性，在20×20、60×60柵格地圖下將本文改進算法與傳統(tǒng)4鄰域蟻群算法（ant colony algorithm in 4 neighborhood，ACO-4N）和傳統(tǒng)8鄰域蟻群算法（ant colony algorithm in 8 neighborhood，ACO-8N）進行仿真實驗，在本實驗中，環(huán)境相對簡單，δ取0.6，給出20×20、60×60兩種地圖的收斂速度（圖7、圖8）和路徑搜索軌跡（圖9、圖10），其中每個小柵格大小為1 m×1 m。

從圖10可知：

1）針對路徑平滑度，ACO-4N性能最差，因為ACO-4N使得螞蟻搜索方向只有4個，不僅容易出現(xiàn)多次拐點，在復雜環(huán)境4個搜索方向更容易使得螞蟻陷入死鎖狀態(tài)。隨著地圖的擴大，ACO-MN性能逐漸提高，在兩種地圖下，ACO-MN搜索到的最短路徑拐點個數(shù)比ACO-8N搜索到的最短路徑拐點個數(shù)分別減少了33.33%和57.57%。

2）針對最短路徑，隨著地圖的擴大，ACO-4N會存在找不到路徑的情況，如在60×60地圖下沒有產(chǎn)生路徑。隨著地圖的擴大，ACO-MN搜索路徑距離的性能也逐步提高，ACO-MN搜索到的最短路徑比ACO-8N搜索到的最短路徑分別縮短了2.12%和10.32%。ACO-MN的性能隨著地圖的擴大而提高是因為象限概率控制參數(shù)對啟發(fā)函數(shù)的改進，使得螞蟻具有一種較遠鄰域優(yōu)先原則，地圖越大，步長也就越大，導致最短路徑越小。

3）針對收斂速度，ACO-MN完全優(yōu)于傳統(tǒng)蟻群算法。ACO-MN相對于ACO-8N，在小地圖20×20下，差距更大，收斂速度加快了76.19%。

3.2 與文獻［11］算法進行仿真對比

3.2.1 20×20小型復雜地圖下仿真對比

ACO-MN與傳統(tǒng)算法在簡單環(huán)境中進行了對比實驗，為了進一步體現(xiàn)本文改進蟻群算法的優(yōu)越性，采用文獻［11］提供的20×20小型復雜柵格地圖，在該地圖下進行仿真對比實驗。在本實驗中，環(huán)境相對復雜，δ取0.4，結果對比見表2，最優(yōu)路徑軌跡對比見圖11。

根據(jù)表2和圖11可知：

1）針對搜索到的最短路徑，ACO-MN最短路徑為30.142，比文獻［11］最短路徑減小了14.0%。

2）針對平滑度，ACO-MN的性能高于文獻［11］，ACO-MN只有12個拐點，比文獻［11］算法拐點個數(shù)減少了20.0%。

3）針對運行時間，ACO-MN運行時間為2.5 s，比文獻［11］算法運行時間縮短了51.9%。

3.2.2 30×30大型復雜地圖下仿真對比

為了驗證ACO-MN在大型復雜地圖下的優(yōu)越性是否會下降，采用文獻［11］中的30×30大型復雜柵格地圖。在本實驗中，地圖尺寸大并且環(huán)境相對復雜，δ取0.2，在該地圖下進行仿真對比實驗。實驗結果對比見表3，最優(yōu)路徑軌跡對比見圖12。

根據(jù)表3和圖12可知：

1）隨著地圖復雜程度提高和尺寸的擴大，從圖12可以看出，文獻［11］極易陷入局部最優(yōu)，并且螞蟻在該位置多次轉(zhuǎn)折才可以跳出局部最優(yōu)地區(qū)；然而當ACO-MN在機器人進入容易發(fā)生局部最優(yōu)地區(qū)（障礙物相對較多地區(qū)）時，機器人并不會陷入局部最優(yōu)，因為ACO-MN算法的多鄰域策略導致螞蟻的多樣性增加，并且搜索范圍更廣，使得螞蟻不會陷入局部最優(yōu)（即使陷入也可以快速逃離局部最優(yōu)），綜上，得到ACO-MN最短路徑為42.58 m，比文獻［11］算法最短路徑縮短了5.6%。

2）在地形復雜地形中，文獻［11］算法在整個路徑規(guī)劃中隨著地圖的擴大，螞蟻從起點到終點判斷的鄰域總數(shù)急劇增加，導致算法運行時間緩慢，使得ACO-MN運行時間比文獻［11］算法縮短49.84%，導致這個現(xiàn)象的原因是ACO-MN的象限概率和象限概率控制參數(shù)使算法在大尺寸地圖中，不需對很多鄰域進行判斷。綜上原因?qū)е铝薃CO-MN 運行時間更短。

3）從表3可以發(fā)現(xiàn)，ACO_MN的拐點個數(shù)比文獻［11］算法的拐點個數(shù)減少了75%，因為隨著地圖的擴大，運用多鄰域螞蟻的步長也就更大，從而導致螞蟻在路徑規(guī)劃中轉(zhuǎn)折點更少。

綜上表明，ACO-MN在最短路徑、運行時間以及拐點個數(shù)上更加適合大型復雜地形。

4 結論

ACO-MN打破傳統(tǒng)固定鄰域的搜索方式，提出在未知環(huán)境下的多鄰域搜索，通過對環(huán)境感知和決策，增加鄰域。通過快速搜索，減少不必要的判斷。最后通過仿真對比實驗，驗證了本文改進算法的優(yōu)越性。但是本文算法只是應用于障礙物靜止狀態(tài)下的情況，下一步將結合動態(tài)障礙物進行路徑規(guī)劃。

參考文獻：

［1］陳曉冬， 王福威. 基于改進A*算法的AGV路徑規(guī)劃［J］. 計算機系統(tǒng)應用， 2023， 32（3）： 180-185.

［2］XIU C J. Application of gaussian artificial potential field algorithm in obstacle avoidance for autonomous vehicles［C］//中國汽車工程學會（China Society of Automotive Engineers）. 2019中國汽車工程學會年會論文集（1）. 機械工業(yè)出版社， 2019： 5.

［3］趙迪， 何克勤， 趙祖高. 基于改進粒子群優(yōu)化算法的移動機器人路徑規(guī)劃［J］. 傳感器與微系統(tǒng)， 2023， 42（6）： 150-153.

［4］王鄭拓， 馮振禮， 葉國云， 等. 基于人工蜂群算法的雙機器人路徑規(guī)劃分析［J］. 焊接學報， 2015， 36（2）： 97-100， 118.

［5］LIU J H， YANG J G， LIU H P， et al. An improved ant colony algorithm for robot path planning［J］. Soft Computing， 2017， 21： 5829-5839.

［6］李志錕， 黃宜慶， 徐玉瓊. 改進變步長蟻群算法的移動機器人路徑規(guī)劃［J］. 電子測量與儀器學報， 2020， 34（8）： 15-21.

［7］左大利， 聶清彬， 張莉萍， 等. 移動機器人路徑規(guī)劃中的蟻群優(yōu)化算法研究［J］. 現(xiàn)代制造工程， 2017（5）： 44-48.

［8］徐興， 錢譽欽， 趙蕓， 等. 基于改進蟻群算法的立體倉庫三維空間路徑優(yōu)化［J］. 計算機集成制造系統(tǒng)， 2021， 27（1）： 206-213.

［9］梁江濤， 王慧琴. 基于改進蟻群算法的建筑火災疏散路徑規(guī)劃研究［J］. 系統(tǒng)仿真學報， 2022， 34（5）： 1044-1053.

［10］WU T， JING X J. Exploration of multiple access interference suppression based on multi-user detection［J］. Chinese Journal of Electronics， 2019， 28（4）： 835-840.

［11］許凱波， 魯海燕， 黃洋， 等. 基于雙層蟻群算法和動態(tài)環(huán)境的機器人路徑規(guī)劃方法［J］. 電子學報， 2019， 47（10）： 2166-2176.

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

［13］李濤， 趙宏生. 基于進化蟻群算法的移動機器人路徑優(yōu)化［J］. 控制與決策， 2023， 38（3）： 612-620.

［14］徐菱， 付文浩， 江文輝， 等. 基于16方向24鄰域改進蟻群算法的移動機器人路徑規(guī)劃［J］. 控制與決策， 2021， 36（5）： 1137-1146.

［15］曾明如， 徐小勇， 羅浩， 等. 多步長蟻群算法的機器人路徑規(guī)劃研究［J］. 小型微型計算機系統(tǒng)， 2016， 37（2）： 366-369.

［16］LI E C， QI K K. Ant colony algorithm for path planning based on grid feature point extraction［J］. Journal of Shanghai Jiaotong University （Science）， 2023， 28（1）： 86-99.

［17］蒲興成， 宋欣琳. 分組教學蟻群算法改進及其在機器人路徑規(guī)劃中應用［J］. 智能系統(tǒng)學報， 2022， 17（4）： 764.

［18］陳青楨， 龔家寶， 于瀟雁， 等. U型障礙物多方向多層填充的移動機器人改進蟻群算法［J/OL］. 機械科學與技術： 1-8［2023-11-21］.https：//doi.org/10.13433/j.cnki.1003-8728.20220259.

［19］袁福龍， 朱建平. 基于改進蟻群算法的移動機器人最優(yōu)路徑規(guī)劃［J］. 現(xiàn)代制造工程， 2021， 490（7）： 38-47， 65.

［20］鄒敢， 游長莉， 唐成章. 基于改進禁忌算法的地址編碼小車路徑規(guī)劃［J］. 北部灣大學學報， 2023， 38（4）： 62-67.