基于改進蟻群算法的自動導(dǎo)引運輸車全局路徑規(guī)劃方法研究*

梁建剛，劉曉平，王 剛，韓 松

(北京郵電大學(xué) 自動化學(xué)院，北京 100876)

0 引 言

由于具有運輸效率高、人力成本低、安全可靠等諸多優(yōu)點，自動導(dǎo)引運輸車(AGV)成為當(dāng)代物流自動化裝備的重要組成部分[1]。AGV路徑規(guī)劃是指在具有一定障礙物的環(huán)境中，給定起始點和目標(biāo)點，按照某些評價標(biāo)準，在運行環(huán)境中搜索一條最優(yōu)的無碰撞路徑[2]。

傳統(tǒng)的路徑規(guī)劃方法如人工勢場法[3]、模擬退火算法[4]、模糊邏輯算法[5]等，普遍存在收斂速度慢、全局搜索能力差等缺陷。隨著智能控制技術(shù)的發(fā)展，神經(jīng)網(wǎng)絡(luò)算法[6]、遺傳算法[7]、蟻群算法等智能算法逐漸被應(yīng)用于解決路徑規(guī)劃問題[8]。其中：神經(jīng)網(wǎng)絡(luò)算法具有自適應(yīng)和自學(xué)習(xí)的能力，但是泛化能力差是其致命缺點；遺傳算法適用于全局路徑規(guī)劃，但是搜索空間大、運算效率不高、運行速度慢；蟻群算法(ACO)由于具有啟發(fā)性、并行性、強魯棒性等特點，而受到研究人員的廣泛關(guān)注。蟻群算法由意大利學(xué)者DORIGO M等[9]于1992年首先提出，是一種利用信息素正反饋的群智能算法，已經(jīng)被應(yīng)用于工程機械再制造選配[10]、遙感圖像分類[11]、車輛交通系統(tǒng)等方面[12]。近年來，國內(nèi)外學(xué)者從不同角度研究了蟻群算法在路徑規(guī)劃方面的應(yīng)用問題。CHAARI I等[13]將遺傳算法(GA)中的突變和交叉操作應(yīng)用到蟻群算法中，設(shè)計了一種新的混合ACO-GA路徑規(guī)劃算法；GE B等[14]將蟻群算法每次迭代后的兩條較短路徑進行交叉組合產(chǎn)生新路徑，并更新其信息素，加快信息素的正反饋效應(yīng)，提高了算法的收斂速度；ZHANG C等[15]在路徑規(guī)劃過程中結(jié)合免疫抑制和參數(shù)切換策略，使算法準確性得到了提高；CHEN X等[16]基于氣味滲透原理，提出了一種用于機器人路徑規(guī)劃的快速兩階段蟻群算法；GIGRAS Y等[17]提出了混合ACO-PSO算法用于機器人路徑規(guī)劃。

本研究提出一種基于改進蟻群算法的AGV全局路徑規(guī)劃方法。

1 AGV工作環(huán)境建模

路徑規(guī)劃問題包括環(huán)境建模和搜索算法兩部分。常用的環(huán)境建模方法有可視圖法、柵格法和MAKLINK圖論法等。MAKLINK圖論法又稱為自由空間法，由HABIB M K和ASAMA H于1991年提出[18]。

為了簡化問題，本研究在處理問題過程中，將AGV模型簡化為點狀機器人。利用MAKLINK圖論法構(gòu)建AGV運行環(huán)境模型，將環(huán)境中的障礙物依據(jù)AGV能無碰撞通過的最大尺寸進行膨脹化處理，轉(zhuǎn)化為廣義錐形或凸多邊形等基本幾何圖形，將環(huán)境劃分為障礙空間和自由空間，AGV運行環(huán)境模型如圖1所示。

圖1 AGV運行環(huán)境模型黑色區(qū)域—障礙空間；其余—自由空間

MAKLINK圖論法中，不與障礙物相交的前提下，兩個障礙物頂點之間的連線以及障礙物頂點到空間邊界的垂線段稱為MAKLINK線。初始時刻，取MAKLINK中點作為AGV的可行節(jié)點，連接各個MAKLINK線的中點及起始點S和目標(biāo)點T，構(gòu)成用于初始路徑規(guī)劃的無向網(wǎng)絡(luò)圖如圖2所示。

圖2 無向網(wǎng)絡(luò)圖p1,p2,p3,...,p14—MAKLINK線

基于該環(huán)境模型，路徑規(guī)劃問題可以描述為：AGV從起始點S出發(fā)，避開空間中的障礙物，通過若干MAKLINK線，到達目標(biāo)點T的最優(yōu)路徑問題。

2 改進蟻群算法

為了解決AGV路徑規(guī)劃的問題，本研究在起始點S循環(huán)釋放人工螞蟻，當(dāng)螞蟻到達目標(biāo)點T時，通過在其經(jīng)過的路徑上添加信息素來引導(dǎo)其他螞蟻的走向，循環(huán)多次，從而達到全局路徑尋優(yōu)的目的。

2.1 轉(zhuǎn)移概率的改進

(1)

式中：J—從節(jié)點i出發(fā)所有可選路徑節(jié)點j的集合；τij(t)—路徑(i,j)的信息素濃度；ηij(t)—節(jié)點j的啟發(fā)函數(shù)；α—信息素濃度τij(t)對轉(zhuǎn)移概率的影響因子；β—啟發(fā)函數(shù)ηij(t)對轉(zhuǎn)移概率的影響因子。

啟發(fā)函數(shù)ηij(t)的計算公式如下：

(2)

式中：dij—節(jié)點i與節(jié)點j之間的距離值。

dij值越小，節(jié)點j的啟發(fā)函數(shù)值越大，節(jié)點j被選擇的概率越大。

A*算法是一種典型的啟發(fā)式搜索算法[19]，被廣泛應(yīng)用于路徑規(guī)劃領(lǐng)域。算法中引入評估路徑節(jié)點n價值的估價函數(shù)f(n)，其計算公式如下：

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

(3)

式中：g(n)—從起始點S到達節(jié)點n的實際行駛距離；h(n)—從節(jié)點n到達目標(biāo)點T的預(yù)估行駛距離。

采用A*算法規(guī)劃路徑時，選擇當(dāng)前節(jié)點的鄰居節(jié)點中估價函數(shù)f(n)值最小的點作為下一路徑節(jié)點，使路徑規(guī)劃具有了目標(biāo)導(dǎo)向性。

(4)

式中：djT—節(jié)點j與目標(biāo)點T之間的直線距離，作為節(jié)點j距目標(biāo)點的啟發(fā)信息；wj—節(jié)點j距目標(biāo)點的啟發(fā)信息對路徑規(guī)劃影響的權(quán)重，wj∈[0,1]。

wj具體影響如下：

(1)wj=0。路徑規(guī)劃與節(jié)點j距目標(biāo)點的啟發(fā)信息無關(guān)，啟發(fā)函數(shù)蛻化為傳統(tǒng)蟻群算法的啟發(fā)函數(shù)，算法收斂速度慢；

(2)wj是固定正值。當(dāng)wj值較小時，算法搜索空間大，搜索側(cè)重于廣度優(yōu)先，搜索的準確性提高，收斂速度慢，當(dāng)wj值較大時，算法搜索空間小，搜索側(cè)重于深度優(yōu)先，搜索的準確性降低，收斂速度快；

(3)wj是動態(tài)值?？梢詫崿F(xiàn)不同階段對搜索準確性及收斂速度快慢的動態(tài)需求。

wj的計算公式如下：

(5)

式中：Mmax—路徑規(guī)劃通過的MAKLINK線總數(shù)；Mcurrent—將依次經(jīng)過的MAKLINK線以1為起始數(shù)值，按從小到大的次序逐個編號，該值為當(dāng)前所處MAKLINK線編號值。

隨著路徑規(guī)劃過程的進行，wj值逐漸增大，搜索前期側(cè)重搜索的準確性，搜索后期側(cè)重收斂的快速性。

將式(4)代入式(1)中，得到改進后的轉(zhuǎn)移概率計算公式為：

(6)

2.2 變系數(shù)信息素更新策略

信息素更新包括實時信息素更新和路徑信息素更新[20]。實時信息素更新是指螞蟻每經(jīng)過一個路徑節(jié)點后即更新其信息素濃度：

τij(n+1)=(1-ρ)τij(n)+ρτ0

(7)

路徑信息素更新是指蟻群完成一次搜索后，更新最優(yōu)路徑上每個節(jié)點的信息素濃度：

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

(8)

式中：τ0—信息素初始值；Δτij=Q/Lbest；Q—信息素濃度的常量；Lbest—本次搜索中最優(yōu)路徑長度；(1-ρ)—信息素的殘留程度；ρ—信息素揮發(fā)系數(shù)，ρ∈[0,1]。

當(dāng)ρ值較小時，信息素的殘留程度較高，信息素正反饋作用相對較弱，算法搜索空間較大，搜索的隨機性較強；當(dāng)ρ值較大時，信息素的殘留程度較低，信息素正反饋作用相對較強，搜索的隨機性較低，算法收斂速度較快。

為了提高路徑規(guī)劃效率，采用動態(tài)調(diào)整信息素揮發(fā)系數(shù)策略。規(guī)劃過程中，隨著迭代次數(shù)的增加，逐漸增大信息素揮發(fā)系數(shù)ρ′，計算公式為：

(9)

式中：ρ0—信息素揮發(fā)系數(shù)初始值，ρ0∈[0,1]；Ncurrent—算法當(dāng)前迭代次數(shù)；Nmax—算法最大迭代次數(shù)。

路徑規(guī)劃初始過程，由于信息素揮發(fā)系數(shù)較小，盡可能多的搜索到較優(yōu)路徑，降低了算法陷入局部最優(yōu)的概率；隨著迭代次數(shù)的增加，信息素揮發(fā)系數(shù)逐漸增大，算法收斂速度加快。將公式(9)代入式(7，8)得到改進后的實時信息素更新方法：

(10)

改進后的路徑信息素更新方法如下：

τij(n+1)=(1-ρ′)τij(n)+ρ′Δτij

(11)

改進后蟻群算法流程圖如圖3所示。

圖3 改進后蟻群算法流程圖

3 仿真實驗和分析

為了驗證改進蟻群算法在AGV全局路徑規(guī)劃中的有效性，筆者構(gòu)建30 m×30 m的工廠環(huán)境模型，設(shè)定AGV起始點S坐標(biāo)為(5,3)，目標(biāo)點T坐標(biāo)為(26,25)，定義4個多邊形作為工廠中的障礙物。由Dijkstra算法規(guī)劃出的初始路徑經(jīng)過的MAKLINK線依次為p10,p11,p12,p14，Mmax=4。筆者將p10,p11,p12,p14均等分為20段，等分點作為蟻群算法路徑規(guī)劃中AGV的可行節(jié)點。

蟻群算法中，設(shè)定信息素影響因子α=1，啟發(fā)函數(shù)影響因子β=2，信息素濃度常數(shù)Q=6，信息素揮發(fā)系數(shù)初始值ρ0=0.1，種群中螞蟻個數(shù)為10，算法最大迭代次數(shù)Nmax=200，信息素初始值τ0=0.000 3。

基于以上參數(shù)設(shè)置，傳統(tǒng)蟻群算法和改進后蟻群算法搜索到的最優(yōu)路徑結(jié)果圖如圖4(a)、5(a)所示。收斂速度曲線如圖4(b)、5(b)所示。

圖4 傳統(tǒng)蟻群算法路徑規(guī)劃仿真結(jié)果

圖5 改進后蟻群算法路徑規(guī)劃仿真結(jié)果

圖中粗實線表示最優(yōu)路徑。從圖中可知，傳統(tǒng)蟻群算法在迭代次數(shù)達到110左右收斂到最優(yōu)路徑，而改進后蟻群算法在迭代次數(shù)為60左右就收斂到了最優(yōu)路徑，其收斂速度可達傳統(tǒng)蟻群算法的2倍。

以上僅為一次仿真結(jié)果的對比，為消除偶然因素對算法的影響，參數(shù)設(shè)置同上，本研究對兩種算法均獨立進行50次路徑規(guī)劃實驗。實驗結(jié)果中，傳統(tǒng)蟻群算法及改進蟻群算法的最優(yōu)路徑對比曲線如圖6(a)所示。收斂速度對比曲線如圖6(b)所示。

圖6 傳統(tǒng)及改進蟻群算法仿真結(jié)果對比曲線

根據(jù)50次路徑規(guī)劃仿真實驗的結(jié)果，筆者計算最優(yōu)路徑平均值和收斂到最優(yōu)路徑的迭代次數(shù)平均值，計算結(jié)果如表1所示。

表1 傳統(tǒng)蟻群算法與改進蟻群算法仿真結(jié)果對比

從表1實驗數(shù)據(jù)對比可以看出：改進后蟻群算法搜索到的最優(yōu)路徑平均值為31.171 1 m，小于傳統(tǒng)蟻群算法的31.172 0 m，說明改進后蟻群算法降低了搜索陷入局部最優(yōu)的概率。改進后蟻群算法的迭代次數(shù)平均達58次時收斂到最優(yōu)路徑，而傳統(tǒng)蟻群算法為107次，其收斂速度基本為傳統(tǒng)蟻群算法的2倍，收斂速度顯著提升。

4 結(jié)束語

針對AGV在工廠環(huán)境中進行快速路徑規(guī)劃，得到兩點間最短距離的問題，本研究提出了基于改進蟻群算法的路徑規(guī)劃方法，該算法融合動態(tài)權(quán)重目標(biāo)導(dǎo)向原理，增加了可選路徑節(jié)點距目標(biāo)點的啟發(fā)信息，加快算法的收斂速度；信息素更新時，引入動態(tài)調(diào)整信息素揮發(fā)系數(shù)策略，隨著路徑規(guī)劃的進行，逐漸增大信息素揮發(fā)系數(shù)，在前期降低陷入局部最優(yōu)的概率，后期加快算法收斂速度，提高了路徑規(guī)劃效率。

通過仿真實驗分析對比，證明了該算法在解決AGV路徑規(guī)劃問題時，具有更快的收斂速度、更高的規(guī)劃效率。

參考文獻(References):

[1] 李遠儀，佃松宜，駱瑞森.基于便攜式PC控制器的小型AGV系統(tǒng)[J].兵工自動化，2016，35(12)：26-29.

[2] 陳 杰.基于蟻群算法的機器人路徑規(guī)劃研究[D].南京：南京理工大學(xué)自動化學(xué)院,2009.

[4] MIAO H, TIAN Y C. Dynamic robot path planning using an enhanced simulated annealing approach[J].AppliedMathematics&Computation,2013,222(5):420-437.

[5] 李 擎,張 超,韓彩衛(wèi),等.動態(tài)環(huán)境下基于模糊邏輯算法的移動機器人路徑規(guī)劃[J].中南大學(xué)學(xué)報：自然科學(xué)版,2013,44(s2):104-108.

[6] LV Z, CAO J. Path planning methods of mobile robot based on new neural network[C]. Control Conference, Xi’ an: IEEE,2013.

[7] 王雪松,高 陽,程玉虎,等.知識引導(dǎo)遺傳算法實現(xiàn)機器人路徑規(guī)劃[J].控制與決策,2009,24(7):1043-1049.

[8] 趙娟平,高憲文,符秀輝,等.移動機器人路徑規(guī)劃的改進蟻群優(yōu)化算法[J].控制理論與應(yīng)用,2011,28(4):457-461.

[9] COLORNI A, DORIGO M, MANIEZZO V. Distributed optimization by ant colonies[C]. Ecal91-European Conference on Artificial Life, Paris: Elsevier Publishing,1991.

[10] 宿 彪,黃向明,任瑩暉,等.基于蟻群算法的工程機械再制造優(yōu)化選配方法研究[J].機械工程學(xué)報,2017,53(5):60-68.

[11] WANG M, WAN Y, YE Z, et al. Remote sensing image classification based on the optimal support vector machine and modified binary coded ant colony optimization algorithm[J].InformationSciences,2017,402(1):50-68.

[12] JABBARPOUR M R, MALAKOOTI H, NOOR R M, et al. Ant colony optimisation for vehicle traffic systems: applications and challenges[J].InternationalJournalofBio-InspiredComputation,2014,6(1):32-56.

[13] CHAARI I, KOUBAA A, TRIGUI S, et al. SmartPATH: an efficient hybrid ACO-GA algorithm for solving the global path planning problem of mobile robots[J].InternationalJournalofAdvancedRoboticSystems,2014,11(1):1.

[14] GE B, SHENG H. Ant colony optimization based on combined optimization for path planning[C]. International Conference on Logistics Engineering, Management and Computer Science, Paris: Atlantis Press,2015.

[15] ZHANG C, LI Q, CHEN P, et al. Ant colony optimization combined with immunosuppression and parameters switching strategy for solving path planning problem of landfill inspection robots[J].InternetionalJournalofAdvancedRobotrcSystems,2016,13(3):1.

[16] CHEN X, KONG Y, FANG X, et al. A fast two-stage ACO algorithm for robotic path planning[J].NeuralComputing&Applications,2013,22(2):313-319.

[17] GIGRAS Y, CHOUDHARY K, GUPTA K, et al. A hybrid ACO-PSO technique for path planning[C]. International Conference on Computing for Sustainable Global Development, New Delhi: IEEE,2015.

[18] HABIB M K, ASAMA H. Efficient method to generate collision free paths for an autonomous mobile robot based on new free space structuring approach[C]. IEEE/RSJ International Workshop on Intelligent Robots and Systems, Intelligence for Mechanical Systems, Osaka: IEEE,1991.

[19] 曲道奎,杜振軍,徐殿國,等.移動機器人路徑規(guī)劃方法研究[J].機器人,2008,30(2):97-101.

[20] 郁 磊.Matlab智能算法30個案例分析[M].2版.北京：北京航空航天大學(xué)出版社,2015.