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

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

0 引 言

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

傳統(tǒng)的路徑規(guī)劃方法如人工勢場法[3]、模擬退火算法[4]、模糊邏輯算法[5]等，普遍存在收斂速度慢、全局搜索能力差等缺陷。隨著智能控制技術的發(fā)展，神經網絡算法[6]、遺傳算法[7]、蟻群算法等智能算法逐漸被應用于解決路徑規(guī)劃問題[8]。其中：神經網絡算法具有自適應和自學習的能力，但是泛化能力差是其致命缺點；遺傳算法適用于全局路徑規(guī)劃，但是搜索空間大、運算效率不高、運行速度慢；蟻群算法(ACO)由于具有啟發(fā)性、并行性、強魯棒性等特點，而受到研究人員的廣泛關注。蟻群算法由意大利學者DORIGO M等[9]于1992年首先提出，是一種利用信息素正反饋的群智能算法，已經被應用于工程機械再制造選配[10]、遙感圖像分類[11]、車輛交通系統(tǒng)等方面[12]。近年來，國內外學者從不同角度研究了蟻群算法在路徑規(guī)劃方面的應用問題。CHAARI I等[13]將遺傳算法(GA)中的突變和交叉操作應用到蟻群算法中，設計了一種新的混合ACO-GA路徑規(guī)劃算法；GE B等[14]將蟻群算法每次迭代后的兩條較短路徑進行交叉組合產生新路徑，并更新其信息素，加快信息素的正反饋效應，提高了算法的收斂速度；ZHANG C等[15]在路徑規(guī)劃過程中結合免疫抑制和參數(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圖論法構建AGV運行環(huán)境模型，將環(huán)境中的障礙物依據AGV能無碰撞通過的最大尺寸進行膨脹化處理，轉化為廣義錐形或凸多邊形等基本幾何圖形，將環(huán)境劃分為障礙空間和自由空間，AGV運行環(huán)境模型如圖1所示。

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

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

圖2 無向網絡圖p1,p2,p3,...,p14—MAKLINK線

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

2 改進蟻群算法

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

2.1 轉移概率的改進

(1)

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

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

(2)

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

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

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

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

(3)

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

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

(4)

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

wj具體影響如下：

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

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

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

wj的計算公式如下：

(5)

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

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

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

(6)

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

信息素更新包括實時信息素更新和路徑信息素更新[20]。實時信息素更新是指螞蟻每經過一個路徑節(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]。

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

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

(9)

式中：ρ0—信息素揮發(fā)系數(shù)初始值，ρ0∈[0,1]；Ncurrent—算法當前迭代次數(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ī)劃中的有效性，筆者構建30 m×30 m的工廠環(huán)境模型，設定AGV起始點S坐標為(5,3)，目標點T坐標為(26,25)，定義4個多邊形作為工廠中的障礙物。由Dijkstra算法規(guī)劃出的初始路徑經過的MAKLINK線依次為p10,p11,p12,p14，Mmax=4。筆者將p10,p11,p12,p14均等分為20段，等分點作為蟻群算法路徑規(guī)劃中AGV的可行節(jié)點。

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

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

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

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

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

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

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

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

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

從表1實驗數(shù)據對比可以看出：改進后蟻群算法搜索到的最優(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 結束語

針對AGV在工廠環(huán)境中進行快速路徑規(guī)劃，得到兩點間最短距離的問題，本研究提出了基于改進蟻群算法的路徑規(guī)劃方法，該算法融合動態(tài)權重目標導向原理，增加了可選路徑節(jié)點距目標點的啟發(fā)信息，加快算法的收斂速度；信息素更新時，引入動態(tài)調整信息素揮發(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].南京：南京理工大學自動化學院,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].中南大學學報：自然科學版,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] 王雪松,高 陽,程玉虎,等.知識引導遺傳算法實現(xiàn)機器人路徑規(guī)劃[J].控制與決策,2009,24(7):1043-1049.

[8] 趙娟平,高憲文,符秀輝,等.移動機器人路徑規(guī)劃的改進蟻群優(yōu)化算法[J].控制理論與應用,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].機械工程學報,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版.北京：北京航空航天大學出版社,2015.