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

姚曉通，李致遠，程 曉

(蘭州交通大學(xué)電子與信息工程學(xué)院，甘肅 蘭州 730070)

1 引言

目前，機器人在各個領(lǐng)域的應(yīng)用越來越廣泛，機器人路徑規(guī)劃在其中占有很重要的地位。所謂路徑規(guī)劃，是機器人從起始位置到目標點位置這兩點之間，以一定的優(yōu)化準則(如行走路徑最短)，找到一條可以躲避障礙物的最優(yōu)路徑或次優(yōu)路徑，指導(dǎo)機器人去逼近找到的路徑，完成任務(wù)[1]。對于機器人路徑規(guī)劃的研究，涉及很多傳統(tǒng)的全局路徑規(guī)劃算法，其中包括A*算法，D*算法，人工勢場法，以及C空間法[2]。但是在面對比較復(fù)雜的障礙物環(huán)境時，以上算法的效果不佳。隨后，一些研究人員根據(jù)自然界生物行為的啟發(fā)，又相繼提出了應(yīng)用在路徑規(guī)劃方面的智能算法，如粒子群算法，遺傳算法，神經(jīng)網(wǎng)絡(luò)法，以及蟻群算法[3]。其中，蟻群算法和以上其它智能算法相比，具有信息正反饋，分布式計算及全局求解能力強的特點，所以在機器人路徑規(guī)劃領(lǐng)域中，其作為一種很有效的規(guī)劃算法，應(yīng)用很廣泛。

蟻群算法是意大利學(xué)者M.Dorigo于20世紀90年代通過對螞蟻覓食行為的觀察研究后，受到啟發(fā)，而提出來的一種仿生模擬算法[4]。該算法首先成功的解決了旅行商問題(TSP問題)，在求解旅行商路徑最短問題上取得了比較理想的效果。后續(xù)，有學(xué)者便將蟻群算法應(yīng)用到路徑規(guī)劃方面，雖然相比于其它智能算法，其具有一定的優(yōu)勢。但是基本蟻群算法還是存在一定的缺陷和不足，因此許多研究人員對基本蟻群算法進行了改進。文獻[5]提出了將環(huán)境中局部的機器人路徑信息引入到蟻群信息素的初始化和路徑選擇概率中，提高了蟻群算法的收斂速度，但路徑質(zhì)量不是很理想。文獻[6]將遺傳算法算子引入到了蟻群算法中，缺點是運算復(fù)雜，效率低。文獻[7]提出了使用混合型信息素更新策略，提高了收斂速度并能夠避免局部最優(yōu)，但在最優(yōu)路徑距離上效果不是很好。文獻[8]通過根據(jù)螞蟻迭代次數(shù)手動設(shè)置信息素增強系數(shù)去達到提高算法收斂速度的目的，但是容易陷入局部最優(yōu)。文獻[9]提出了一種基于改進蟻群算法的自適應(yīng)蟻群算法，該方法針對二維環(huán)境的路徑規(guī)劃效果較好，在三維環(huán)境中收斂緩慢，而且容易陷入局部最優(yōu)。

上述方法雖然在避免陷入局部最優(yōu)問題和提高蟻群算法的收斂速度上取得一定的效果，但是仍存在全局路徑效果不佳且搜索到的路徑長度偏長的問題。為了更好地解決這些問題，得到更優(yōu)質(zhì)量的路徑。本文提出了改進的蟻群算法，在蟻群狀態(tài)轉(zhuǎn)移策略中引入了基于hocaoglu算法思想的引導(dǎo)函數(shù)，引導(dǎo)螞蟻更好地逼近最優(yōu)解。在信息素更新規(guī)則中，設(shè)計了一種自適應(yīng)信息素揮發(fā)因子更新方法，避免蟻群陷入局部最優(yōu)解。

2 基本蟻群算法概述

2.1 蟻群算法的思想

自然界的單個螞蟻的行為比較簡單，但是蟻群整體卻可以體現(xiàn)一些智能的行為。螞蟻在尋找食物的過程中會在經(jīng)過的路徑上釋放一種被稱作信息素的化學(xué)物質(zhì)，以便其它后來的螞蟻可以感知[10]。在剛開始時，由于路徑上沒有螞蟻經(jīng)過，不會存在信息素，螞蟻會隨機選擇遇到的路徑。隨著時間的推移，距離短的路徑經(jīng)過的螞蟻會越來越多，從而會使路徑上累積的信息素濃度越來越高，后續(xù)的螞蟻選擇此路徑的概率也會增大，最終螞蟻群會找到一條到達目標點的最優(yōu)路徑。

2.2 蟻群算法的數(shù)學(xué)模型

1)狀態(tài)轉(zhuǎn)移概率

螞蟻根據(jù)信息素濃度去選擇下一個需要移動的節(jié)點。同時，還要受到當(dāng)前節(jié)點與周圍節(jié)點之間的期望信息的影響。對于螞蟻的狀態(tài)轉(zhuǎn)移規(guī)則如式(1)所示[11]

(1)

2)信息素更新規(guī)則

由上可知，禁忌表tabuk用來記錄在當(dāng)前迭代中螞蟻走過的節(jié)點，直到完成本次迭代，否則不能再次訪問禁忌表記錄的節(jié)點。當(dāng)所有螞蟻完成對所有節(jié)點的訪問后，在禁忌表中便記錄每只螞蟻所走過的節(jié)點，構(gòu)成路徑的可行解。之后，要對之前的路徑信息素進行削弱，對新引入的信息素進行加強，規(guī)則如下

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

(2)

(3)

(4)

3 改進蟻群算法

3.1 改進蟻群算法引導(dǎo)函數(shù)

針對基本蟻群算法中螞蟻搜索路徑存在一定的盲目性且逼近目標點的效果不理想的問題，本文提出了一種基于hocaoglu算法思想的引導(dǎo)函數(shù)。hocaoglu算法是一種多尺度路徑規(guī)劃算法，其原理如圖1所示[12]。

圖1 hocaoglu算法原理圖

在上圖中，s為起始點，e為目標點。顯然可知，從s到e的最短路徑是它們之間的直線段。若在se之間有障礙物，則做se的垂直平分線ab，那么sb、be就是為到達目標點所規(guī)劃的路徑。當(dāng)sb之間也存在障礙物時，繼續(xù)做sb的垂直平分線，就可以找到sc、cb、be的可達路徑。以此類推，最后一定可以找到一條不經(jīng)過障礙物的路徑?？梢园l(fā)現(xiàn)，越靠近se附近的節(jié)點，節(jié)點與起始點和目標點的距離之和越小，路徑越短，反之，則路徑越長?；诖?，本文設(shè)計了帶有權(quán)重調(diào)節(jié)因子的引導(dǎo)函數(shù)，如式5所示

(5)

(6)

其中Dis為當(dāng)前節(jié)點與起始節(jié)點的距離，die為與目標節(jié)點的距離。引導(dǎo)函數(shù)的值與節(jié)點到目標點的距離和到起始點的距離之和有關(guān)，也和節(jié)點與目標點的距離有關(guān)。由式(5)可知，在se附近的節(jié)點且越靠近目標點的節(jié)點，且引導(dǎo)函數(shù)的值越大，相應(yīng)的路徑距離越小。同時，對引導(dǎo)函數(shù)設(shè)置調(diào)節(jié)因子λ，在搜索前期λ大于0.5，更偏向于se附近的節(jié)點，在搜索后期λ小于0.5，更側(cè)重于靠近目標點的節(jié)點，這樣有助于螞蟻在后期更快的找到目標點。Ns為當(dāng)前節(jié)點所在節(jié)點的次序，Nm為搜索的中期節(jié)點的次序。所以改進后的算法的狀態(tài)轉(zhuǎn)移規(guī)則如式7所示

(7)

γ為啟發(fā)引導(dǎo)因子，表示引導(dǎo)函數(shù)的重要程度。

3.2 自適應(yīng)信息素揮發(fā)因子的設(shè)計

相比于其它參數(shù)，信息素揮發(fā)因子ρ對算法性能的影響最大。當(dāng)ρ過小時，信息素揮發(fā)慢，導(dǎo)致路徑上的信息素濃度差異小，螞蟻會充分搜索地圖上的每條路徑，但是收斂速度會變慢[13]；而ρ過大時，路徑上的信息素揮發(fā)速度過快，之前信息素濃度低的路徑，信息素濃度會更低，信息素濃度差異變大，會出現(xiàn)強烈的正反饋效果，這樣雖然會加快算法的收斂速度，但是很容易陷入局部最優(yōu)。面對信息素揮發(fā)因子很難找到一個特定的值去適應(yīng)螞蟻搜索迭代的整個周期，本文提出了一種自適應(yīng)的信息素揮發(fā)因子的方法。對于ρ的區(qū)間范圍為[0，1]，將ρ的初始值設(shè)置為0.95，若連續(xù)10次迭代中相鄰兩次最優(yōu)解的差值小于等于0.1%時，ρ自動調(diào)節(jié)為原來的0.9倍；當(dāng)ρ小于0.2時，強制設(shè)置ρ為0.2，表達式如式8所示

(8)

式(8)中，約束條件的設(shè)定，某種程度上可以防止螞蟻在搜索過程中陷入局部最優(yōu)，同時既可以信息素 揮發(fā)因子過大，又可以防止過小，對算法性能產(chǎn)生壞的影響?；谝陨?，改進后的蟻群算法流程圖如圖2所示。

圖2 改進后的蟻群算法流程圖

4 實驗結(jié)果與分析

為了驗證改進算法的有效性，本文在matlab2016a環(huán)境下搭建仿真地圖并進行對比實驗。相比于可視圖法、節(jié)點法和自由空間法，柵格法具有規(guī)劃空間表達一致，便于計算機建模、存儲、處理更新和分析等優(yōu)點，故采用柵格法對環(huán)境地圖進行建模。為了排除地圖環(huán)境因素的影響，建立了兩種不同的障礙物仿真地圖：一種是簡單的障礙物環(huán)境地圖(規(guī)格為10*10)，另一種是復(fù)雜障礙物環(huán)境地圖(規(guī)格為20 *20)。由于蟻群算法參數(shù)較多，采用控制變量，利用單一參數(shù)對算法性能的影響來確定最佳參數(shù)值，其它參數(shù)的選取則都是在已經(jīng)確定的之前參數(shù)的最佳值的基礎(chǔ)上進行實驗的。本文對最佳參數(shù)的選取(以平均路徑長度和平均迭代次數(shù)為評判準則)，進行了10次實驗，每次迭代的次數(shù)為100，然后再取10次實驗最佳值的平均值。最終參數(shù)確定如下：螞蟻數(shù)目m=35，信息啟發(fā)因子α=4，期望啟發(fā)因子β=5，引導(dǎo)啟發(fā)因子γ=3，信息素強度系數(shù)Q=100，路徑初始信息素濃度τ0=0.3，信息素揮發(fā)因子ρ=0.95，最大迭代次數(shù)NCmax=100。

路徑規(guī)劃的兩種地圖環(huán)境模型，它們的起始點都為(1，1)，目標點分別為(10，10)，(20，20)，其中黑色為障礙物，白色為可規(guī)劃路徑地圖。在簡單環(huán)境地圖模型下，基本蟻群算法和改進后的蟻群算法路徑規(guī)劃仿真運行圖，如圖3、4所示，它們的迭代收斂曲線圖，如圖5、6所示。

圖3 基本蟻群算法路徑規(guī)劃圖

圖4 改進蟻群算法路徑規(guī)劃圖

圖5 基本蟻群算法收斂圖

圖6 改進蟻群算法收斂圖

由圖3、圖4、圖5和圖6可知，改進蟻群算法規(guī)劃的最優(yōu)路徑的長度明顯小于基本蟻群算法規(guī)劃的路徑距離，本文改進算法的收斂長度為15.95，且在第28代就開始收斂；而基本蟻群算法的路徑收斂長度為19.32，收斂代數(shù)為52代，顯然改進蟻群算法在最優(yōu)路徑長度和收斂速度要優(yōu)于傳統(tǒng)蟻群算法。

圖7、圖8為另一種復(fù)雜環(huán)境地圖下蟻群算法的路徑規(guī)劃仿真運行圖。

圖7 基本蟻群算法路徑規(guī)劃圖

圖8 改進蟻群算法路徑規(guī)劃圖

圖9、10為復(fù)雜地圖環(huán)境下基本蟻群算法和改進蟻群算法的收斂曲線圖。

圖9 基本蟻群算法收斂圖

圖10 改進蟻群算法收斂圖

由圖9、圖10分析可知，在復(fù)雜障礙物環(huán)境下，改進蟻群算法的性能也是要優(yōu)于基本蟻群算法的。改進蟻群算法在42代就收斂到最優(yōu)路徑，路徑長度為30.56，而基本蟻群算法最優(yōu)路徑長度為34.23，收斂的代數(shù)為68。在兩種地圖環(huán)境下，可以看出改進蟻群算法通過引入引導(dǎo)函數(shù)，加強精英螞蟻的路徑信息素濃度和對信息素揮發(fā)因子的自適應(yīng)調(diào)節(jié)使其全局尋優(yōu)能力和收斂速度都好于基本蟻群算法，使螞蟻的尋優(yōu)效率更高，更有目的性，而且不易陷入局部最優(yōu)。

5 結(jié)論

本文提出了一種基于改進蟻群算法的機器人路徑規(guī)劃方法。針對傳統(tǒng)蟻群算法路徑規(guī)劃中存在的一些問題，提出了相應(yīng)的改進。首先，在蟻群狀態(tài)轉(zhuǎn)移策略中引入基于hocaoglu算法思想的引導(dǎo)函數(shù)并對其設(shè)置調(diào)節(jié)因子；其次，在蟻群信息素更新規(guī)則中采用自適應(yīng)的信息素揮發(fā)因子；最后在matlab環(huán)境下對所提方法進行仿真驗證，結(jié)果表明改進的蟻群算法在尋優(yōu)能力和收斂速度上具有明顯優(yōu)勢，求解最優(yōu)解更有目的性，在提高收斂速度的同時又可以避免陷入局部最優(yōu)，能找到更優(yōu)質(zhì)量的路徑，具有實際工程意義。