改進蟻群算法在移動機器人路徑規(guī)劃上的應用

陳 志，韓興國

(桂林航天工業(yè)學院 機械工程學院，廣西 桂林 541000)

0 引 言

傳統(tǒng)的移動機器人路徑規(guī)劃算法主要包括人工勢場法、網(wǎng)格法等[1,2]，但傳統(tǒng)路徑規(guī)劃算法目標不可達性和局部最小點的問題容易導致路徑規(guī)劃的失敗，且隨著路徑環(huán)境復雜性的增加，存在數(shù)據(jù)存儲空間大、計算速度慢、實時決策差等缺陷[3,4]。

蟻群算法是由M.Dorigo等學者提出的分布式智能仿生算法[5]。該算法模擬了螞蟻合作覓食行為的性質(zhì)。它具有正反饋、高穩(wěn)健性和并行性的優(yōu)點，但是該算法存在搜索空間大、局部最優(yōu)、搜索效率低、計算量大等問題[6,7]。張原藝等[8]提出一種改進的多步長蟻群算法。將蟻群每次迭代產(chǎn)生的最優(yōu)路徑作為引導徑，利用路徑引導搜索策略確定多步長的移動路徑，提高搜索范圍的多樣性，該算法有效提高了算法跳出局部最優(yōu)的能力，但改進算法在算法的收斂速度方面還有待改善。張強等[9]針對傳統(tǒng)人工勢場算法存在死鎖及局部路徑欠優(yōu)等問題，對其進行改進。利用障礙物檢測算法識別出有效障礙物和有效路徑中間點，通過引力場和邊界條件規(guī)劃出起點到中間點的局部路徑，將中間點置為新的起點進行反復迭代，直至起點與目標點重合則規(guī)劃完成，解的質(zhì)量明顯提高，但仍存在尋優(yōu)過程中搜索時間較長的問題。王慧等[10]利用粒子群算法個體加權(quán)平均值并加入慣性權(quán)重提出了一種改進粒子群路徑優(yōu)化算法，但該算法搜索到最優(yōu)解時迭代次數(shù)較多，搜索時間較長。

鑒于此，提出了一種改進的蟻群算法。該算法根據(jù)中間節(jié)點與起始終端線之間的距離關(guān)系設置不均勻分布的初始信息素，減少了初始階段的盲目性問題；將衰減因子引入啟發(fā)函數(shù)，隨著迭代次數(shù)的增加，啟發(fā)式信息在路徑選擇中的作用逐漸減弱，從而加快了收斂速度；使用偽隨機狀態(tài)轉(zhuǎn)移概率規(guī)則，并根據(jù)迭代次數(shù)和該迭代的最優(yōu)解計算狀態(tài)轉(zhuǎn)移概率值，以自適應地調(diào)整確定選擇和隨機選擇的比例。對于死鎖問題，根據(jù)路徑上丟失的螞蟻數(shù)量，對不完整路徑的最后兩步進行處罰，以減少丟失螞蟻的數(shù)量，確保算法的多樣性。仿真實驗在不同的移動環(huán)境中進行，實驗結(jié)果表明，改進的蟻群算法在性能指標上有顯著提高。

1 基本蟻群算法

蟻群算法模擬了螞蟻“探索”的行為特征，即螞蟻將使用前螞蟻在覓食過程中留下的信息素，根據(jù)一定的概率選擇路徑或探索新的路徑并同時分泌信息素。路徑上的信息素會積累、揮發(fā)和擴散，并影響下面的螞蟻。螞蟻傾向于選擇具有高信息素濃度的路徑并最終尋找最佳路徑[11]，蟻群算法的兩個最重要的步驟就是路徑選擇和信息素更新。

假設螞蟻k在t時刻位于節(jié)點i，則路徑轉(zhuǎn)換的概率可由式(1)表示，然后利用輪盤賭模型選擇下一個節(jié)點

(1)

式中：C為螞蟻允許在下一步選擇的節(jié)點集；τij為路徑(i，j)的信息素值；α為信息素激勵因子，它反映了信息素濃度對路徑選擇的重要性，α越大則信息素對于路徑選擇越重要，螞蟻將更傾向于選擇大多數(shù)螞蟻采取的路徑；β是預期的啟發(fā)因子，它反映了啟發(fā)式信息在路徑上的重要性。β越大則螞蟻越傾向于選擇最短路徑；ηij(t)為啟發(fā)式值，表示螞蟻從節(jié)點j轉(zhuǎn)移到目標節(jié)點g的期望程度，如式(2)所示

(2)

式中：djg是節(jié)點j和目標節(jié)點g之間的歐幾里德距離。每個螞蟻在使用路徑上的信息素的同時也會不斷分泌信息素，因此路徑上的信息素將不斷積累。為了防止過多的信息素導致啟發(fā)信息泛濫，在每個螞蟻采取一步或完成一個周期之后更新路徑上的信息素，并且從t+1時刻獲得路徑上的信息素，如式(3)所示

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

(3)

式中：ρ為信息素揮發(fā)系數(shù)，主要模擬螞蟻信息素隨時間的自然揮發(fā)；1-ρ為信息素殘留因子；Δτij(t)為循環(huán)路徑(i，j)上信息素的增量。當信息素更新策略時，有不同的計算方法。如式(4)所示為螞蟻循環(huán)模型計算方式

(4)

式中：Q為信息素的強度；Lk為螞蟻在此循環(huán)中所采用路徑的總長度。

2 改進蟻群算法

2.1 改善初始信息素

基本蟻群算法的信息素值在算法的初始階段是固定的，螞蟻在初始路徑搜索中有一些盲目性，因此算法的搜索時間將會增加。鑒于此本文提出了一種改進的信息素方法，該方法根據(jù)當前節(jié)點、下一節(jié)點和起始點連接之間的相對距離計算初始信息素，如式(5)所示

(5)

其中，dSE為從起點到終點的歐幾里德距離；dSi為從起點到當前節(jié)點的歐幾里德距離；dij為當前節(jié)點和下一個節(jié)點之間的歐幾里德距離；djE為從下一個節(jié)點到終點的歐幾里德距離；C為下一個節(jié)點的集合；a0為常數(shù)。從式(5)中可以看出，當dSi+dij+djE越小，路徑上的初始信息素越大。針對這一現(xiàn)象，根據(jù)位置關(guān)系設置了不均勻分布的初始信息素，避免了算法初始搜索的盲目性，進一步提高了搜索速度。

2.2 改進啟發(fā)式信息功能

基本蟻群算法的啟發(fā)式信息值與從下一個節(jié)點到目標點的距離成反比，從而驅(qū)動螞蟻選擇短距離路徑。然而在不考慮當前節(jié)點和下一節(jié)點的位置的情況下，所選路徑不一定是最短路徑，并且在后期搜索階段，為了加快收斂速度，啟發(fā)式信息對路徑選擇的影響將會削弱。因此本文提出了一種通過引入阻尼系數(shù)來改進啟發(fā)式信息函數(shù)的方法，如式(6)所示

(6)

其中

(7)

式中：NCmax為最大迭代次數(shù)；NC為當前的迭代次數(shù)。

2.3 改進信息素更新規(guī)則

信息素更新主要用于模擬天然螞蟻信息素隨時間的積累和自然揮發(fā)。目前對于信息素的更新主要有本地更新和全局更新兩種方式，本文結(jié)合最大-最小蟻群系統(tǒng)(MMAS)[12]的基本模型和精英蟻群算法，對信息素更新規(guī)則進行了改進。

在一個螞蟻完成循環(huán)后，可根據(jù)式(3)、式(4)實現(xiàn)本地更新路徑。在所有螞蟻完成迭代后，所有路徑上的信息素都會更新，且所有完整路徑都可以找到最佳解決方案和最差解決方案如式(8)所示，通過該式可有效增強當前最優(yōu)解對后續(xù)迭代的指導作用。另外，對最差解決方案的懲罰可用于減少最差路徑對后續(xù)迭代的誤導效應，從而該算法將收斂速度加速到全局最優(yōu)解

(8)

式中：Lbest是當前最佳路徑的長度；Lworst是當前完整路徑中最差路徑的長度。為了避免算法停滯，將信息素的范圍設置為[τmin，τmax]，如式(9)所示

(9)

2.4 改進狀態(tài)轉(zhuǎn)換規(guī)則

為了提高搜索效率和算法質(zhì)量，使用偽隨機狀態(tài)轉(zhuǎn)換規(guī)則。設螞蟻k在t時刻位于節(jié)點i，則在t+1時刻螞蟻k的位置為

(10)

其中，q0為轉(zhuǎn)換率，范圍為(0,1)，q為隨機數(shù)，當q≤q0時，下一個節(jié)點直接由信息素濃度最大值和啟發(fā)式信息來確定。

q0的值決定了確定性選擇和隨機選擇模式的比率。如果q0值很大，則路徑移位更可能是確定性模式，從而加速了收斂速度，但這種情況下會降低全局搜索能力。相反，如果q0的值較小，則路徑移位更傾向于輪盤賭模式，這增加了路徑選擇的隨機性并進一步增加了全局搜索能力。因此，q0值的設置對收斂速度和全局搜索能力有重要影響。本文提出了一種新的自適應計算q0的方法，通過迭代次數(shù)NC和當前最佳路徑長度Lbest來確定q0值，如式(11)所示，其中b為(0,1)之間的常數(shù)。

(11)

為了進一步防止過早收斂到局部最優(yōu)解并停滯，建立迭代次數(shù)閾值N0。當?shù)螖?shù)NC小于N0時，q0值為b；否則自適應地計算q0的值。

2.5 解決死鎖問題

當環(huán)境更加復雜時，螞蟻可能會陷入無路的狀態(tài)，即死鎖。如圖1所示，環(huán)境中的P1位置是一個“陷阱”，當螞蟻走進那里時，它無法移動到另一個位置。雖然在P2位置沒有明顯的陷阱，但如果螞蟻按圖片路徑行走最終也會出現(xiàn)死鎖。

圖1 死鎖狀態(tài)

針對僵局問題，在圖1中P1位置需要后退兩步才能擺脫它，計算復雜性將成倍增加。在本文中，使用了一種折衷方法，它可以殺死處于死鎖狀態(tài)的螞蟻，并計算進入同一死鎖點的螞蟻數(shù)量nLost(i，j)，不完整路徑的最后兩步將由式(12)懲罰

(12)

式中：λ為懲罰因子，其值為(0,1)之間的常數(shù)。很容易看出，同一條路徑中的螞蟻越多，對路徑的懲罰就越大，后續(xù)螞蟻通過這條路徑的概率就越小，從而大大減少了失去的螞蟻數(shù)量。

3 改進的蟻群算法在路徑規(guī)劃中的應用

將改進的蟻群算法應用于路徑規(guī)劃。具體步驟如下：

步驟1 初始化參數(shù)。其中包括起始位置S，目標位置G，螞蟻數(shù)m，最大迭代次數(shù)NCmax，迭代次數(shù)NC，信息素強度Q，信息素啟發(fā)式因子α，期望啟發(fā)式因子β，死鎖懲罰因子λ。其中，初始化目標位置S、目標位置G由實驗網(wǎng)格環(huán)境決定，螞蟻數(shù)m=50，最大迭代次數(shù)NCmax=100，信息素強度Q=100，α、β、λ作為變量根據(jù)實驗對象分別進行設置。

步驟2 計算初始信息素。其中常數(shù)a0=0.5，將起點到當前節(jié)點的歐幾里德距離dSi、當前節(jié)點和下一個節(jié)點之間的歐幾里德距離dij、下一個節(jié)點到終點的歐幾里德距離djE分別代入式(5)中計算初始信息素。

步驟3 路徑選擇。假設螞蟻k在t時刻位于節(jié)點i處，則利用式(1)由路徑(i，j)的信息素值τij、信息素激勵因子α計算出螞蟻選擇下一節(jié)點的概率，然后利用式(10)計算螞蟻在t+1時刻的路徑選擇。

步驟4 更新信息素和啟發(fā)式信息。當螞蟻建立完整路徑時，對信息素和啟發(fā)式信息進行更新，其中信息素可將信息揮發(fā)系數(shù)ρ、信息素殘留因子1-ρ、信息素的增量Δτij(t)代入式(3)中進行更新，其中信息素的增量Δτij(t)由式(4)計算得到，啟發(fā)式信息可由式(6)更新。

步驟5 死鎖解決方案。當螞蟻創(chuàng)建一條不完整的路徑時，此時需要對所創(chuàng)建的死鎖路徑上的信息素利用懲罰因子λ進行懲罰，根據(jù)死鎖發(fā)生的具體路徑位置利用式(12)進行懲罰，當死鎖被懲罰后轉(zhuǎn)到步驟3并繼續(xù)循環(huán)執(zhí)行直到完成搜索。

步驟6 信息素的全局更新。在所有螞蟻完成搜索之后，需要找到該迭代中所有完整路徑的最佳路徑和最差路徑，并根據(jù)式(3)和式(8)增強最佳路徑上的信息素，削弱最差路徑上的信息素。

步驟7 自適應調(diào)整q0。當?shù)螖?shù)Nc大于迭代閾值N0時，可由當前最佳路徑長度Lbest、最大迭代次數(shù)NCmax、從起點到終點的歐幾里德距離dSE通過式(11)計算新的狀態(tài)轉(zhuǎn)移率q0以更新狀態(tài)轉(zhuǎn)移規(guī)則。

步驟8 搜索結(jié)束。確定是否滿足結(jié)束條件，如果滿足，則輸出最佳路徑長度，否則清除禁忌清單，讓NC=NC+1，然后轉(zhuǎn)到步驟3并繼續(xù)循環(huán)執(zhí)行，直到滿足結(jié)束條件或達到最大迭代次數(shù)。如圖2所示為基于改進蟻群算法的路徑規(guī)劃的具體過程。

圖2 改進蟻群算法的路徑規(guī)劃的具體過程

4 模擬實驗和分析

為驗證所述改進勢場蟻群算法的有效性，在Matlab R2010a中進行仿真實驗，計算機操作系統(tǒng)為Windows 7，CPU為core i5-650，內(nèi)存為8 GB，仿真環(huán)境分別為10×10、20×20、30×30的平面柵格環(huán)境。同時，為了驗證本文算法的優(yōu)越性，在相同環(huán)境中將本文算法所得結(jié)果分別與文獻[13]和文獻[14]中改進蟻群算法的結(jié)果進行比較。

4.1 模擬環(huán)境的建立

為了便于蟻群算法搜索最優(yōu)路徑，本文采用網(wǎng)格法建立二維移動環(huán)境空間，網(wǎng)格按從上到下，從左到右的順序編號。其中障礙網(wǎng)格稱為不可行網(wǎng)格，無障礙網(wǎng)格稱為可行網(wǎng)格。為了便于算法的實現(xiàn)，螞蟻在行進過程中當遇到障礙網(wǎng)格時，算法默認將其標注為“1”，無障礙網(wǎng)格標注為“0”，從而將網(wǎng)格圖轉(zhuǎn)換為0和1分布的二維電子地圖，如圖3所示。

圖3 網(wǎng)格圖和相應的電子地圖

通過式(13)確定網(wǎng)格編號與坐標之間的數(shù)學對應關(guān)系

(13)

其中，r為網(wǎng)格的比例，由機器人的幾何尺寸決定；n為網(wǎng)格號；R為網(wǎng)格的行數(shù)；mod函數(shù)為余數(shù)函數(shù)；ceil函數(shù)是向右舍入函數(shù)。

4.2 參數(shù)優(yōu)化選擇

蟻群算法的參數(shù)選擇直接決定了算法的性能，常用的方法有遺傳算法，粒子群算法(PSO)，三步法，經(jīng)驗和實驗方法等。但到目前為止，還沒有完美的方法直接確定參數(shù)的最優(yōu)組合。為了降低算法的復雜度，本文采用經(jīng)驗和實驗方法，通過設置不同的參數(shù)進行仿真實驗，分析實驗結(jié)果的優(yōu)缺點，選擇最優(yōu)參數(shù)組合。

測試方法為每個參數(shù)設置一組值，在每個實驗中，只有一個參數(shù)被更改，其它參數(shù)為常量。分別測試迭代次數(shù)，最佳路徑長度和丟失的螞蟻數(shù)量。本文僅介紹啟發(fā)式因子α，期望啟發(fā)式因子β，揮發(fā)系數(shù)ρ和死鎖懲罰因子λ的最優(yōu)組合。其它參數(shù)可以以相同的方式執(zhí)行。

使用環(huán)境1(如圖3(a))作為組合實驗的測試環(huán)境，參數(shù)設置如下：

m=50，NCmax=100，Q=100，β=6，ρ=0.2，λ=0.2，N0=5，q0=0.3。當α=0.8，α=0.9，…，α=2.0時，分別測試算法的迭代次數(shù)，最佳路徑長度和丟失的螞蟻數(shù)量，實驗結(jié)果如圖4所示。實驗結(jié)果表明，當α很小時，改進的蟻群算法無法搜索全局最優(yōu)解；當α∈[1,1.2]時，它具有更好的收斂速度和搜索全局最優(yōu)解的能力。隨著α的進一步增加，算法的收斂速度逐漸增大，但全局搜索能力逐漸減弱，更容易陷入局部最優(yōu)解。總體而言，與基本蟻群算法相比，本文改進的蟻群算法大大提高了收斂速度、全局最優(yōu)解搜索能力和丟失螞蟻數(shù)的性能指標。

圖4 啟發(fā)式因子與迭代次數(shù)、最佳路徑長度、丟失螞蟻數(shù)的關(guān)系

在同一環(huán)境中，設置如下參數(shù)：m=50，NCmax=100，Q=100，α=1.1，ρ=0.2，λ=0.2，N0=5，q0=0.3。當β=1，β=2，…，β=9時進行一系列實驗。實驗結(jié)果如圖5所示。實驗結(jié)果表明，無論β如何變化，它都具有更快的收斂速度和更少的螞蟻損失，并且當β∈[4,7]時，有最佳的性能指標。最小迭代次數(shù)為8.7次，最佳路徑長度為13.898，丟失的螞蟻數(shù)為28.2。

當ρ=0.1，ρ=0.2，…，ρ=0.9時，分別測試算法的迭代次數(shù)，最佳路徑長度和丟失的螞蟻數(shù)。實驗結(jié)果如圖6所示。當ρ增加時，收斂速度更快，失去的螞蟻更少，但路徑更長。當ρ在[0.1,0.2]之間時，算法具有最佳性能指標。全局最優(yōu)路徑長度為13.898，迭代次數(shù)為9.6，丟失螞蟻數(shù)為58.4。

當λ=0.1，λ=0.2，λ=0.3……，λ=0.9時，進行相同的實驗。實驗結(jié)果如圖7所示。結(jié)果表明當λ∈[0.2，0.5]時，具有最佳性能指標，最小迭代次數(shù)為7.9，最佳路徑長度為13.898，丟失螞蟻數(shù)為39.3?？傊?，改進的蟻群算法大大提高了基本蟻群算法的性能指標。當α∈[1,1.2]，β∈[4,7]，ρ∈[0.1,0.2]，λ∈[0.2，0.5]時，有更好的綜合性能指標。

圖5 預期啟發(fā)式因子與迭代次數(shù)、最佳路徑長度、丟失螞蟻數(shù)的關(guān)系

圖6 信息素揮發(fā)系數(shù)與迭代次數(shù)、最佳路徑長度、丟失螞蟻數(shù)的關(guān)系

圖7 懲罰因子與迭代次數(shù)、最佳路徑長度、丟失螞蟻數(shù)的關(guān)系

4.3 與其它算法進行比較

4.3.1 20×20情況(環(huán)境2)

為了驗證所提出的算法的有效性與優(yōu)越性，將其與文獻[13]的算法在環(huán)境2(如圖8(a))情況下進行對比實驗，實驗參數(shù)設置為：m=50，NCmax=100，Q=100，α=1.1，ρ=0.2，β=7，λ=0.2，N0=5，q0=0.3。如圖8所示為對比實驗仿真結(jié)果，圖8(a)中的實線是本文算法的規(guī)劃路徑，虛線是參考文獻[13]中的算法路徑。為避免偶然情況，重復了10次實驗，表1為平均結(jié)果。從圖8和表1可以看出，文獻[13]中的算法比本文算法具有更快的收斂速度和更少的運行時間，但本文算法在最優(yōu)路徑搜索的性能指標上具有更大的優(yōu)勢，且丟失的螞蟻數(shù)量更少。本文算法的最優(yōu)路徑長度收斂到30.968，而文獻[13]中算法的平均路徑長度為35.6573，這進一步說明了本文的算法更穩(wěn)定。

4.3.2 30×30情況(環(huán)境3)

為了驗證復雜環(huán)境的有效性和優(yōu)越性，將其與文獻[14]的算法在環(huán)境3(如圖9(a))情況下進行對比實驗，仿真結(jié)果如圖9所示。圖9(a)中的實線是本文算法的規(guī)劃路徑，虛線是文獻[14]中算法的規(guī)劃路徑，表2給出了在相同參數(shù)下重復10次實驗的平均值。

圖8 兩種算法在路徑規(guī)劃中的比較結(jié)果

表1 兩種算法在路徑規(guī)劃中的比較結(jié)果

從實驗結(jié)果上來看，在復雜的環(huán)境中本文算法仍然可以快速搜索最優(yōu)路徑。文獻[14]中算法的最佳路徑長度為48.425，而本文的最佳路徑長度為44.522，路徑長度縮短3.903；文獻[14]中的平均迭代次數(shù)為59次，本文算法的平均迭代次數(shù)為22.1次，收斂速度提高了近3倍且丟失的螞蟻數(shù)量僅占文獻[14]中算法的三分之一。在運行時間上，本文算法較文獻[14]中的算法更長，但考慮到算法的性能指標，本文算法可以在運行時間上做出一點犧牲，從而獲得更好的路徑長度和更快的收斂速度。

圖9 兩種算法在路徑規(guī)劃中的比較結(jié)果

表2 兩種算法在路徑規(guī)劃中的比較結(jié)果

綜上所述，本文將改進的蟻群算法與文獻[13]、文獻[14]的算法進行了比較。本文提出的改進算法能夠自適應地調(diào)整了偽隨機狀態(tài)轉(zhuǎn)移比例基數(shù)，以改進路徑選擇規(guī)則，啟發(fā)式信息函數(shù)和信息素更新規(guī)則，進一步提高了收斂速度和全局搜索能力，大大減少了螞蟻丟失的數(shù)量，具有很大的優(yōu)越性和實用性。

5 結(jié)束語

路徑規(guī)劃是當前機器人在復雜環(huán)境下行進的關(guān)鍵技術(shù)，蟻群算法作為一種仿生算法能夠有效實現(xiàn)機器人的路徑規(guī)劃。針對基本蟻群算法在路徑規(guī)劃中存在的收斂速度慢、搜索效率低的問題提出了一種改進的蟻群算法。實驗中將改進的蟻群算法應用于機器人路徑規(guī)劃，并通過實驗和經(jīng)驗方法確定算法參數(shù)的最優(yōu)組合。通過模擬多個移動環(huán)境，并與其它算法進行比較，實驗結(jié)果表明改進的蟻群算法有效解決了算法初期盲目搜索的問題，提高了收斂速度，驗證了該算法的有效性和優(yōu)越性。