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

姜偉楠，楊理柱，李秀華，侯阿臨

(長春工業大學計算機科學與工程學院，吉林 長春 130012)

1 引言

近年來，自主移動機器人在工業、農業、醫藥、航天等領域發揮了重要作用，具有廣闊的應用前景。路徑規劃算法一直是移動機器人技術領域的核心和熱點問題。其研究目標是找到一條連接起點和目標點最優或次最優的路徑[1]。目前，國內外在路徑規劃方面取得了大量的研究成果，包括傳統的Dijkstra算法、A*算法和粒子群算法、人工神經網絡算法、蟻群算法等智能優化算法。

蟻群優化算法(ACO)具有較強的魯棒性和良好的搜索能力，但也存在搜索效率低、容易陷入局部最優解等缺點[2]。

針對蟻群算法存在的問題，Jiao Z等人提出采用自適應狀態轉移策略和自適應信息更新策略，避免多態蟻群算法陷入局部優化[3]。Cao J提出了動態調整信息素蒸發率改進全局最優性和收斂速度。同時改進啟發式函數和狀態轉移規則，以盡快找到最優解，并改變信息素更新策略，以避免過早收斂[4]。王曉燕等人結合人工勢場方法構造啟發式信息函數的同時采用了初始信息素不平衡原理和動態調節信息素蒸發速率的方法，加速了算法收斂，避免了局部最優[5]。朱艷等人改進蟻群算法啟發式函數使其自適應調整，并添加方向信息以提高算法的搜索效率的同時通過動態調整權重系數目標點的方向信息的影響，以平衡收斂速度和全局最優性[6]。

本文提出了一種基于最大最小蟻群系統(MMAS)的改進算法。結合改進的APF算法降低ACO算法初始路徑規劃的盲目性和復雜性。改進啟發函數，并采用啟發式信息遞增函數來避免蟻群算法的局部最優問題，同時保證算法的收斂速度。蟻群算法的信息素更新機制以及改進更新規則，保證收斂速度和路徑的多樣性。同時，增加長度，角度等因素作為評價標準改善路徑評價函數，提高算法的全局最優性，使獲得的路徑更符合實際應用。通過改進狀態轉移規則并自適應地調整狀態轉移函數的閾值，可以提高算法的運行效率，同時可以增加解的多樣性。仿真結果表明，該算法不僅可以有效提高算法收斂速度，而且可以提高最優解的質量。

2 相關基本算法

2.1 最大最小蟻群系統

MMAS算法是蟻群算法的最佳改進算法之一，與傳統的ACO算法相比，主要改進了信息素更新機制、總濃度極限和初始濃度。該算法有兩個關鍵步驟：概率選擇和信息素更新[7-8]。

(1)

(2)

其中，α為信息素啟發因子，表征信息素重要程度的參數，其值越大，螞蟻越傾向于選擇信息素濃度大的路徑;β為期望啟發式因子，表征啟發信息重要程度的參數，其值越大，螞蟻越傾向于選擇距離目標點近的節點;djg為待選節點j到目標節點g的歐氏距離。ηij為期望啟發式函數，離目標點越近，期望啟發信息越大。

螞蟻在經過路徑時釋放信息素，同時信息素會隨著時間的推移而蒸發，因此信息素需要更新。傳統的MMAS算法只允許當代最優解的螞蟻路徑在所有螞蟻完成迭代后進行信息素更新，信息素通過以下公式進行全局更新

(3)

(4)

2.2 改進的人工勢場算法

Milad N等人提出了一種改進的APF算法，以在柵格地圖環境中找到起點和目標點之間的所有可行路徑[9]。該算法通過三個節點列表構造新的勢場圖。這三個列表中，open表中是所有未分配勢場值的節點；temp表中是已分配勢場值但其相鄰節點未分配勢場值的節點；closed表中是其本身與相鄰節點都分配好勢場值的節點。算法通過三個列表按照相應步驟生成勢場圖，為所有節點分配勢場值。

改進的APF算法從起始點開始，在每次迭代中選擇具有最大勢場值的相鄰可行節點。重復迭代多次，直到相鄰可行節點中存在目標點。由此，可以在勢場圖得到初始路徑。在某些情況下，節點的鄰近節點中可能不止一個節點具有最大勢場值，在此處節點路徑將會被劃分成多個子路徑，每個子路徑繼續延伸尋找終點，也就是說在勢場圖上可能會得到多條子路徑。

在本文中，通過改進的APF算法獲得多個子路徑，然后統計路徑中的所有節點。將統計節點用于簡化初始地圖，將不屬于統計節點的節點設置為障礙物，縮小了ACO算法要探索的地圖的范圍。因此，提高了ACO算法的效率和最優性。

3 蟻群算法改進

3.1 改進啟發函數

傳統的MMAS轉移概率由信息素和啟發函數組成，兩者都是由距離長度來判斷的。事實上在實際應用中，除了距離之外，路徑的程度也受到諸如路徑曲折程度等因素的影響。本文在借鑒A*算法的自適應啟發函數思想的同時，綜合考慮轉折角度重新構造啟發函數，同時設計啟發函數遞增函數，增大算法前期的解的多樣性，避免陷入局部最優，在后期增大算法收斂性，以加快算法的運行速度。

A*算法的基本原理是利用當前節點、可選節點和目標節點的位置關系自適應構造估價函數，估價函數是當前節點S與可選節點的成本以及可選節點到目標節點E的成本的總和，公式如下

f(n)=g(n)+h(n)

(5)

其中，g(n)表示節點S到可選節點n的代價，h(n)表示從可選節點n到目標節點E的代價。

本文綜合考慮上式與轉折角度等因素設計的啟發式函數如下

(6)

ζ=min(0.1+ξ1*log2(1+NC/NCmax)，ζmax)

(7)

其中，dij表示當前節點i和可選節點j之間的歐氏距離，djg表示可選節點j與目標節點g之間的歐幾里德距離，thita表示前一節點與當前節點i和可選節點j之間的角度.w1，w2和w3代表三個啟發因子的權重。通過多次實驗測試將它們設定為0.15，0.75和0.1。ζ表示啟發式信息的遞增函數，ζ函數的調整系數ξ1決定了函數的遞增速度。 隨著迭代次數的增加，遞增函數逐漸增大。到達最大閾值ζmax后，函數將停止變化。多次實驗測試后，設置最大閾值為3。

3.2 改進狀態轉移規則

傳統的最大最小蟻群算法使用輪盤賭規則選擇下一節點，本文采用偽隨機比例原則選擇下一個節點位置，即

(8)

其中，選擇概率qo為(0，1)的常量，q為(0，1)的符合均勻分布的隨機數，當q≤qo時，按[τij]α[ηij]β的最大值確定性搜索，否則，按照輪盤賭規則選擇下一節點，如果沒有可選節點，設螞蟻提前死亡。

文獻[10]對于蟻群算法的各項參數進行研究分析，發現選擇概率qo對算法規劃出路徑的結果影響最大。當qo越小時，算法的收斂性越慢，同時會增加解的多樣性，因此本文在自適應調節qo的方面進行研究，避免算法陷入局部最優的同時保證其收斂性。

設定一個迭代閾值R(設為迭代次數的1/3)，當迭代次數小于等于R時，qo由大變小，且遞減速度較快，算法在前期注重全局最優性的同時保證了一定的收斂性。當迭代次數大于R時，qo再次由大變小，且遞減速度較慢，此時算法的中后期注重收斂速度，維持蟻群一定的隨機搜索。qo的自適應調節公式如下

qo=

(9)

其中，qmax表示最大選擇概率的值，qmin表示最小選擇概率的值，ξ2、ξ3表示早期，中后期選擇概率的遞減函數的系數。經過多次實驗，設定ξ2、ξ3為2和0.5。

3.3 改進信息素更新規則

為了提高所提算法的全局最優性，參考排序螞蟻系統算法更新排名前n的當代路徑的信息素。同時，改進了路徑評價函數和信息素分配規則。越優秀的路徑余留的信息素越大，提升算法的收斂性。平衡更新多條路徑帶來的算法收斂速度問題。

本文綜合考慮路徑的長度、轉折數以及轉折角度來改進路徑的評價函數評價最優路徑，是得到的路徑更符合實際應用情況。評價值越大，路徑越差。路徑評價函數如下

fit(n)=w4Ln+w5sumthitan+w6sumbentn

(10)

其中，Ln表示當前路徑的長度，sumthitan表示當前路徑的總轉折數，sumbentn表示當前路徑的總轉折角度，w4，w5和w6表示路徑評估中的三個評價因素所占的權重，基于三者在路徑評價中的重要程度的適當的設置值。在論文中，根據仿真環境和多次測試設置，w4，w5和w6為0.75，0.15和0.1。

通過式(10)獲得排名前n個路徑，然后用式(11)更新信息素

(11)

其中，f表示當前路徑的評價值，fbad表示歷史最差路徑評價值，fbest表示歷史最優路徑評價值，通過上式對不同路徑進行信息素分配，使得更優秀的路徑能夠得到更多的信息素。

對于歷史最優路徑，使用以下公式計算信息素增量

iffg>fbest

(12)

其中，fg代表該次迭代的局部最佳路徑，當局部最優路徑的評價值大于歷史最優路徑時，對歷史最優路徑的信息素采用式(12)更新，減輕了由更新前n個最佳路徑引起的收斂速度問題。

3.4 改進算法具體步驟

根據上述方法，改進的ACO算法的流程圖如圖1所示。

圖1 改進蟻群算法流程

4 仿真結果及分析

為了驗證本文算法在機器人路徑規劃上的可行性和有效性，本文進行了大量的仿真，將本文算法與最大最小蟻群算法以及文獻[6]中改進的蟻群算法進行比較，體現算法的優越性。本文的仿真環境為：Windows7 64 bit；MATLAB R2017；處理器為Intel(R) Core(TM) i3-3100M；主頻2.4 GHz；內存6GB；本文采用8叉樹柵格法建立機器人運行環境。蟻群算法通常通過經驗選取參數，本文算法在一系列測試的情況下，選取參數如表1。

表1 參數設置

本文采用改進人工勢場法對30×30地圖進行了初始規劃后仿真結果如下。初始地圖如圖2所示，簡化后地圖如圖3所示。

圖2 初始地圖 圖3 簡化后地圖

上圖所示，仿真結果表明算法消減了初始地圖的范圍，減小了螞蟻需要探索的地圖區域，減少了算法初期螞蟻的盲目搜索，可以減少螞蟻的數量而不影響算法的全局最優性，提高了算法的搜索效率與收斂速度。

本文構建一個30×30規模的的柵格地圖用于仿真。本文算法由于對地圖環境進行過初始規劃，故可以消減螞蟻數量提升收斂速度而不影響最優結果，設螞蟻數量為35，而其它兩種算法在消減螞蟻數量的情況下不能保證算法的最優結果，故設螞蟻數量為50，三種算法最大迭代次數為100。三種算法在地圖進行仿真結果如圖4及表2所示。

圖4 30×30地圖仿真結果

表2 30×30地圖20次仿真后平均結果

表2為三種算法在30×30的仿真地圖下以以481為起點(即圖中第16行第1列的點)，終點為30(即圖中第1行第30列的點)進行20次仿真結果對比表。在圖4(a)、圖4(b)中實線代表本文算法，虛線代表最大最小蟻群算法，點劃線代表文獻[6]算法。圖4(a)是三種算法的路徑規劃結果圖。4(b)是三種算法的收斂趨勢圖，每一點表示算法當前迭代的最優路徑值。仿真結果表明，從路徑的平均轉彎次數以及平均轉彎角度的結果上來看，本文算法比起最大最小蟻群算法以及文獻算法[6]規劃出的路徑要更加的平滑，更符合實際應用情況，同時也是最短路徑。平均迭代次數結果上表明本文算法具有更好的收斂速度，所需的程序運行時間明顯優于其它兩種算法，具有良好的運行效率與尋優能力，滿足了機器人路徑規劃的實時性要求。因此，綜合評價算法效果，本文算法更具優勢，仿真的結果驗證了算法的正確性和有效性。

5 結論

本文在全局靜態環境下，基于柵格法對移動機器人進行環境建模。采用改進APF算法減小初始地圖縮小蟻群搜索的范圍。在啟發函數、信息素更新以及路徑評價函數中加入長度、轉折性、平滑性三種因素的影響，從而讓算法尋找出各方面都較優的路徑，同時改進信息素更新機制以增加算法的全局最優性。為了在保證收斂速度的條件下提高算法的全局搜索能力，提出了自適應狀態轉移函數選擇概率。

仿真結果從路徑長度、平滑度，算法收斂速度以及算法實時性等方面證明了本文改進的蟻群算法能夠更有效地規劃出最優路徑。本文是在靜態環境下進行的實驗，下一步研究結合動態避障方面的內容，提高路徑規劃能力。