基于改進蟻群算法的機器人全局路徑規劃研究*

曹新亮，王智文，馮 晶，查 敏，王宇航

(1.廣西科技大學電氣與信息工程學院，廣西 柳州 545006； 2.廣西科技大學計算機科學與通信工程學院,廣西 柳州 545006； 3.廣西師范大學多源信息挖掘與安全重點實驗室，廣西 桂林 541004； 4.廣西師范大學計算機科學與信息工程學院，廣西 桂林 541004 )

1 引言

隨著科技的快速發展以及機器人的大量應用，人們對機器人的要求也越來越高，尤其表現在對機器人的智能化方面的要求，而機器人自主路徑規劃是實現機器人智能化的重要步驟，路徑規劃是指規劃機器人從起點位置出發，無碰撞、安全到達指定目標位置的最優路徑。迄今為止，國內外很多學者圍繞機器人路徑規劃開展了大量研究，如傳統算法有迪杰斯特拉算法[1]、A*算法[2,3]、人工勢場法[4]等。隨著研究的深入，傳統算法已經無法很好地解決問題，對此許多學者提出了一系列的智能算法，如遺傳算法、花朵授粉算法[5]、粒子群算法[6]、螢火蟲算法[7]、蟻群算法[8]等，不同的算法在不同的限定條件下有著其特有的優勢，但是也存在不足之處。

蟻群算法是由意大利學者Maro Dorigo首次提出的，是一種分布式仿生算法，本身具有較強的魯棒性，但也存在著收斂速度慢、容易陷入局部最優的問題。為了解決這些問題，國內外許多學者對傳統的蟻群算法進行了相應的改進。Lee[9]改進蟻群算法轉移概率函數和信息素更新規則，提高了算法的尋優能力；Mouhcine等人[10]通過獲取動態數據，代理協作獲取最優路徑，優化蟻群算法，提高了算法全局尋優性能，避免了陷入局部最優；Jiao等人[11]在多態蟻群算法中引入了自適應策略和自適應信息更新策略，避免了死鎖問題，提高其全局搜索能力；Wang等人[12]通過應用禁忌表和網絡權重表，縮小了算法的搜索范圍，提高了搜索效率；Luo等人[13]使用偽隨機狀態轉移規則選擇路徑，提高了算法的全局搜索能力和收斂速度；王志中[14]提出了螞蟻相遇策略，提高了算法的搜索效率，改進后的算法具有更快的收斂速度；趙峰等人[15]提出了一種自適應搜索半徑蟻群算法規劃路徑，提高了環境適應能力和收斂速度；黃于欣等人[16]改進路徑啟發函數，并引入動態參數調整機制，優化蟻群搜索和開發機制，有效避免算法陷入局部最優，同時提高了算法收斂速度；鄭延斌等人[17]通過引入反向學習方法對螞蟻位置進行初化分布來改進蟻群算法，提高了算法的全局搜索能力，同時利用粒子群算法中的自適應慣性權重因子調節信息素濃度Q值，使其自適應變化，避免陷入局部最優。

本文針對傳統蟻群算法收斂速度慢進行改進，建立新的數學模型，使初始信息素濃度不均勻分布，并通過仿真實驗與傳統的蟻群算法比較，以驗證改進前后算法的效果。實驗結果表明，本文改進的算法能夠有效地提高蟻群算法的收斂速度。

2 傳統蟻群算法

2.1 蟻群算法基本原理

蟻群算法是根據蟻群覓食行為提出的一種仿生智能算法，螞蟻在尋找食物的過程中會在經過的路徑上留下信息素，而遺留下來的信息素能夠被其他螞蟻感知到，螞蟻根據信息素濃度選擇路徑，優先選擇信息素濃度較高的路徑，這樣逐漸形成一種正反饋現象。螞蟻趨向選擇較短的路徑，經過的螞蟻越多，表明信息素濃度越高，該路徑上的信息素濃度就越大，其它螞蟻選擇這條路徑的幾率就越大，螞蟻就是通過這種信息傳遞的方式選擇1條較優路徑進行覓食。蟻群算法中的路徑選擇概率和信息素濃度的更新是2個至關重要的因素，決定著算法的尋優效果。

2.2 蟻群算法模型

(1)

信息素會在螞蟻完成1次循環后進行更新，根據式(2)～式(4)來調整信息素。

τij(t+1)=(1-ρ)τij(t)+Δτij

(2)

(3)

(4)

3 改進的蟻群算法

針對傳統蟻群算法存在收斂速度慢的問題，本文提出對初始信息素進行差異化設置，防止非最優路徑上的信息素對螞蟻產生誤導，從而實現快速收斂的效果。

3.1 蟻群算法的具體改進

傳統蟻群算法初始信息素濃度是均勻分配的，這樣算法初期搜索具有較強的盲目性，進而導致收斂速度慢等問題。螞蟻通常根據路徑上信息素濃度的差異來尋找最優路徑，在信息素的引導下選擇1條從起始點到目標點的完整路徑，由于初始信息素濃度是相同的，而且初期搜索具有很強的盲目性，這樣就會出現誤導，無法選擇最優路徑，容易使算法陷入局部最優，影響算法尋優能力。為了避免因信息素導致算法陷入局部最優，減少錯誤的啟發信息對螞蟻的誤導，提高其尋優能力，考慮機器人移動過程中的實際工作環境，本文構造新的數學模型，對初始信息素濃度進行預先的差異化設置，以達到快速尋優的效果。如圖1所示，由于最優路徑多集中在起始點S和目標點E的連線L附近區域，同時受環境中障礙物的影響。首先根據起始點和目標點在柵格地圖上選取出優選區域，預設優選區域外的初始信息素的值τ0，同時在優選區域內預設初始信息素值C，并為優選區域內的點設定不同的增量，具體設置方法如圖2所示：在優選區域內，節點j是螞蟻下一步移動的節點，根據起始點與目標點的直線距離X與節點j到起始點和目標點的距離和的比值設置節點j的信息素濃度增量，對該區域的初始信息素進行差異化增加，使得對初始信息素濃度的差異化設置更符合實際求解問題的要求。

Figure 1 Mathematical model diagram of initial pheromone setting 圖1 初始信息素設置數學模型圖

Figure 2 Initial pheromone differentiation setting圖2 初始信息素差異化設置

假設蟻群算法尋找選擇節點j時，節點j到起始點S的距離為X1,到目標點E的距離為X2，X1+X2的值越小，則認為該點越優。在該點設定的初始信息素濃度越高，越能滿足實際需求。如圖1和圖2所示，優選區域內各位置的初始信息素濃度增量是根據建立的數學模型進行設置的，以起始點S和目標點E為焦點可以得到無數個橢圓，這樣就可以將優選區域劃分成多個部分，每個部分分別具有不同的信息素濃度增量，但在優選區域中會存在一系列信息素相同的節點。考慮存在障礙物的因素，為了避免算法在尋優時選擇跨越性較大，應盡量靠近上一個節點。所以，選擇節點j時，先判斷上一節點在橢圓中的位置，再對比X1、X2的值的大小。若上一個節點靠近起始點S的位置，即當X1X2時，選擇節點j,這樣避免了優化不穩定性。

節點j的初始信息素濃度值計算如式(5)所示：

(5)

其中，τ0為優選區域以外柵格地圖節點的信息素值，C為優選區域內節點信息素值，R為優選區域內節點集合，λ[X/(X1+X2)]為優選區域內柵格地圖位置的信息素增量，λ為信息素增量系數，X為理想最優路徑SE的長度，X1為節點j到起始點S的距離長度，X2為節點j到目標點E的距離長度。

3.2 改進算法步驟

本文提出的改進蟻群算法的實施步驟分為5個階段:

(1) 設置蟻群算法基本參數：螞蟻總量M、信息啟發系數α、期望啟發系數β、信息素揮發系數ρ、調整系數δ、最大迭代次數Nmax。

(2) 利用柵格法對環境地圖進行建模，根據起始點和目標點選出優選區域，增加其信息素初始值，并根據節點與起始點和目標點的距離之和和起始點與目標點之間距離的比例對信息素進行差異化增量設置。

(3) 尋找路徑，對禁忌表進行初始化并將起點加入其中，根據狀態轉移概率(如式(1)所示) 尋找下一可達節點，直到螞蟻選取的節點為目標點時，停止搜索。

(4) 判斷循環迭代次數是否達到設定值，如果達到，則保存信息，否則繼續進行路徑搜索。

(5) 得到最優路徑，算法終止。

4 仿真實驗與結果分析

4.1 實驗環境建模

在實際工作環境中，移動機器人工作環境是復雜多變的，且為三維空間。為了便于研究，本文對環境進行簡化建模。柵格法是一種常用的環境表示方法，因其簡單方便(二維環境)，環境建模的復雜性小，因而本文環境建模采用柵格法[18]。在柵格地圖中，工作環境被劃分為很多柵格，其中包括有障礙物和無障礙的柵格，在仿真程序中用 0 表示此柵格無障礙物，機器人可以通過此柵格，用1表示柵格有障礙物，機器人無法通過，需選擇其他柵格。柵格的尺寸大小可根據工作環境中的障礙物尺寸以及安全距離進行設置。為了實現程序仿真，需要對柵格進行標識，如圖 3 所示，以10×10的柵格環境為例來說明。

Figure 3 Relationship between raster map and number圖3 柵格地圖與編號的關系

如圖3所示，白色柵格表示無障礙物的柵格，黑色柵格則表示有障礙物的柵格，在地圖中對每個柵格編號，不同序號的柵格在坐標系中的坐標可用式(6)來表示。

(6)

其中，mod為取余運算，ceil表示向后取整，Ni是對應柵格的標號，N表示每一列的柵格數量，取柵格中心位置作為柵格在坐標系中的坐標。

這樣機器人全局路徑規劃的問題就轉變成了利用算法在柵格地圖上尋找由起始點S到目標點E的有序的柵格子集，這些柵格子集的中心連線便是算法尋找的路徑。

4.2 實驗結果及分析

蟻群算法是一種概率型算法，具有一定隨機性，算法的性能可以依據算法運行一次得到最優解的可能性大小來判斷。在20×20的地圖環境中將傳統蟻群算法和本文改進的蟻群算法各運行 20 次進行分析，其中螞蟻的規模M設置為50，迭代次數為100，信息啟發式因子α為1，期望啟發式因子β為7，信息素揮發系數ρ為0.3，參數Q為1，C為0.5。對于蟻群算法的參數選取，是基于大量的實驗仿真得到的，C設置為0.5，效果更優。

Table 1 Algorithm simulation results in 20×20 environment 表1 20×20環境中算法仿真結果

由圖4～圖6及表1可知，在20×20環境下，改進后的蟻群算法收斂速度較快，主要原因是傳統蟻群算法的初始信息素濃度設置的值是相同的，導致算法在迭代初期具有很大的搜索盲目性，進而會收斂較慢，而改進后的算法在初期就劃定全局最優區域，并賦予一個較小的初值，同時在優選區域中，根據新的初始信息素濃度設置模型，對柵格地圖中各點初始信息素濃度進行差異化設置，避免了前期搜索的盲目性，能更快地尋找最優路徑，提高了算法的收斂速度。本文改進的蟻群算法收斂速度要快于傳統蟻群算法。

5 結束語

傳統蟻群算法存在著收斂速度慢的不足，尋優效果差，本文提出了一種改進蟻群算法，通過不均勻設置初始信息濃度，使得算法在開始尋優時，能避免尋優盲目性，優選區域的存在，使得尋優初期就在一個較好的范圍內，大大提高算法的收斂速度和尋優效果。考慮到研究機器人全局路徑問題時，障礙物多是靜態的，為了降低空間復雜度，將三維空間降維為二維空間，本文采用柵格地圖對環境建模，并建立了新的模型，通過Matlab仿真實驗，驗證了本文改進蟻群算法對解決機器人路徑規劃問題的有效性和可行性。本文只是針對蟻群算法其中一點不足做出改進，后期將對算法的其他性能做進一步研究，希望本文做出的改進能為后續工作提供幫助，同時為其他研究者提供一些參考。

Figure 4 Path planning results and convergence curves of the algorithm in 20×20 environment (1)圖4 20×20環境(1)中算法的路徑規劃結果及收斂曲線

Figure 5 Path planning results and convergence curves of the algorithm in 20×20 environment (2)圖5 20×20環境(2)中算法的路徑規劃結果及收斂曲線

Figure 6 Path planning results and convergence curves of the algorithm in 20×20 environment (3)圖6 20×20環境(3)中算法的路徑規劃結果及收斂曲線