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

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

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

0 引 言

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

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

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

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

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

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

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

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

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

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

2 改進(jìn)蟻群算法

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

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

(1)

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

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

(2)

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

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

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

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

(3)

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

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

(4)

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

wj具體影響如下：

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

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

(3)wj是動(dòng)態(tài)值。可以實(shí)現(xiàn)不同階段對(duì)搜索準(zhǔn)確性及收斂速度快慢的動(dòng)態(tài)需求。

wj的計(jì)算公式如下：

(5)

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

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

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

(6)

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

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

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

(7)

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

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

(8)

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

當(dāng)ρ值較小時(shí)，信息素的殘留程度較高，信息素正反饋?zhàn)饔孟鄬?duì)較弱，算法搜索空間較大，搜索的隨機(jī)性較強(qiáng)；當(dāng)ρ值較大時(shí)，信息素的殘留程度較低，信息素正反饋?zhàn)饔孟鄬?duì)較強(qiáng)，搜索的隨機(jī)性較低，算法收斂速度較快。

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

(9)

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

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

(10)

改進(jìn)后的路徑信息素更新方法如下：

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

(11)

改進(jìn)后蟻群算法流程圖如圖3所示。

圖3 改進(jìn)后蟻群算法流程圖

3 仿真實(shí)驗(yàn)和分析

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

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

參考文獻(xiàn)(References):

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

[2] 陳 杰.基于蟻群算法的機(jī)器人路徑規(guī)劃研究[D].南京：南京理工大學(xué)自動(dòng)化學(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),等.動(dòng)態(tài)環(huán)境下基于模糊邏輯算法的移動(dòng)機(jī)器人路徑規(guī)劃[J].中南大學(xué)學(xué)報(bào)：自然科學(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] 王雪松,高 陽(yáng),程玉虎,等.知識(shí)引導(dǎo)遺傳算法實(shí)現(xiàn)機(jī)器人路徑規(guī)劃[J].控制與決策,2009,24(7):1043-1049.

[8] 趙娟平,高憲文,符秀輝,等.移動(dòng)機(jī)器人路徑規(guī)劃的改進(jìn)蟻群優(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] 宿 彪,黃向明,任瑩暉,等.基于蟻群算法的工程機(jī)械再制造優(yōu)化選配方法研究[J].機(jī)械工程學(xué)報(bào),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ó),等.移動(dòng)機(jī)器人路徑規(guī)劃方法研究[J].機(jī)器人,2008,30(2):97-101.

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