何成偉，茅 健 HE Chengwei,MAO Jian

（上海工程技術(shù)大學(xué) 機(jī)械與汽車工程學(xué)院，上海 201620）

0 引言

AGV已是現(xiàn)代物流工廠重要的運(yùn)輸設(shè)備，在應(yīng)對越來越復(fù)雜的物流環(huán)境中，需要解決物流工程與任務(wù)復(fù)雜度的增加，AGV智能化的需求也越來越高，實現(xiàn)AGV的自主化也是國家實現(xiàn)2025計劃，工業(yè)4.0智能制造的重要部分。傳統(tǒng)的最優(yōu)路徑規(guī)劃方式有基于A*算法[1]，Dijkstra算法[2]，但是都有著計算量大，收斂速度慢，不具備實時性的弊端。近年來，神經(jīng)網(wǎng)絡(luò)[7]、蟻群算法[4]和遺傳算法[3]也陸續(xù)應(yīng)用到路徑規(guī)劃中。在這些方法中，神經(jīng)網(wǎng)絡(luò)因其具有良好的自適應(yīng)和學(xué)習(xí)優(yōu)化能力，但是其泛化能力弱，不具有普適性；遺傳算法有著較強(qiáng)的搜索能力，改進(jìn)遺傳算子，引入適用度權(quán)重系數(shù)[5]，可以很好地尋求全局最優(yōu)解，但是效率低；蟻群算法有著很強(qiáng)的啟發(fā)性和穩(wěn)定性，許多學(xué)者對蟻群算法有著深入的了解，使用蟻群算法結(jié)合Dijkstra算法規(guī)劃AGV初始路徑，引入節(jié)點隨機(jī)選擇機(jī)制得到最優(yōu)路徑[6]，或是通過更改啟發(fā)函數(shù)，算法中引入全局信息，得到全局的最優(yōu)解[7]。

本文針對單臺AGV在復(fù)雜物流車間運(yùn)輸過程中如何規(guī)劃最優(yōu)路徑的問題，研究了基于改進(jìn)蟻群算法的啟發(fā)函數(shù)和信息素?fù)]發(fā)系數(shù)，利用引入全局信息，設(shè)計避障因子和構(gòu)造路徑光滑參數(shù)三個方面進(jìn)行優(yōu)化。搜索到保證路徑光滑的情況下，得到的最短路徑。仿真結(jié)果表明，本算法具有較好的最優(yōu)路徑距離，且具有更好的避障能力，耗時較小，更適合于復(fù)雜的工廠環(huán)境。

1 構(gòu)造AGV作業(yè)環(huán)境

在AGV路徑規(guī)劃中，首先需要建立AGV運(yùn)輸環(huán)境模型。常有可視圖法，柵格法和無向網(wǎng)絡(luò)圖。根據(jù)實際物流車間運(yùn)輸?shù)那闆r，本文應(yīng)用MAKLINK無向網(wǎng)絡(luò)圖，按如下規(guī)則構(gòu)造AGV可移動路徑。

（1）將移動的AGV看作是質(zhì)點。

（2）將障礙物向各個方向膨脹，將其抽象為凸多邊形。即使是規(guī)劃的AGV沿著凸多邊形邊緣行走也不會與真實的障礙產(chǎn)生碰撞。

（3）每條自由連接線不能穿過障礙物。

（4）連接線的端點可以是障礙物的凸多邊形的頂點，或者是自由空間的邊界上的點。

（5）取每條連接線上的中點，作為AGV可行駛的節(jié)點。

圖1 構(gòu)造MALINK自由路徑

圖1中S—AGV行駛起點；T—AGV行駛終點；圖中細(xì)線封閉凸多邊形為障礙物。將節(jié)點相互兩兩相連，作為本文AGV路徑規(guī)劃的無向網(wǎng)絡(luò)圖。

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

根據(jù)傳統(tǒng)蟻群算法，第k只螞蟻從節(jié)點i出發(fā)到達(dá)下一個節(jié)點j轉(zhuǎn)移概率為：

式中：allow為節(jié)點i出發(fā)到其余所有的節(jié)點j的集合；為螞蟻在路徑i到j(luò)節(jié)點上留下的信息素濃度；ηij（t）為節(jié)點i到節(jié)點j的轉(zhuǎn)移期望值，是節(jié)點j的啟發(fā)函數(shù)；α為信息素濃度對轉(zhuǎn)移概率的影響因子；β節(jié)點i到節(jié)點j的期望值對轉(zhuǎn)移概率的影響因子。

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

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

若節(jié)點i和節(jié)點j的距離越短，啟發(fā)函數(shù)的值就越大，節(jié)點i到節(jié)點j的轉(zhuǎn)移概率也越大。

從上述分析來看，蟻群算法只考慮了相鄰節(jié)點與節(jié)點的距離，沒有考慮節(jié)點之間是否存在障礙。

2.1 引入避障因子和全局信息

當(dāng)兩個直線段有交點時，即認(rèn)為節(jié)點i和節(jié)點j之間有障礙物G存在。即當(dāng)xg2＞xa＞xg1，xi＞xa＞xj時，節(jié)點i和節(jié)點j存在障礙物。

計算直線方程lij各參數(shù)，計算得到直線lij,lg。

A點（xa,ya）是上述兩直線產(chǎn)生的交點，即可得：

各坐標(biāo)點的大小關(guān)系，構(gòu)造避障函數(shù) γij（t），γij（t）∈[0,1 ]。構(gòu)造 γij（t）的計算公式如下：

根據(jù)式（3） 可見，當(dāng)滿足節(jié)點i和節(jié)點j之間有障礙物時，的值為負(fù)；當(dāng)節(jié)點i和節(jié)點j之間無障礙物時，γij（t）的值為正。所以，當(dāng)存在障礙物時，可得啟發(fā)函數(shù)）的值比原來大幅減小，并通過啟發(fā)因子β放大，其轉(zhuǎn)移概率大幅下降，此時算法將選擇鄰近其他無障礙節(jié)點作為下一個路徑點。

式（4）中，djT為下一個節(jié)點到終點T的直線距離。ωj為引入的動態(tài)全局優(yōu)化因子，ωj∈ 0,[ ]1 。ωj的計算公式為：

式（5）中，Mcurrent為從起點運(yùn)動開始計算的已經(jīng)通過的自由空間中節(jié)點數(shù)；Mmax為所有自由空間中節(jié)點數(shù)量。

當(dāng)算法剛剛開始，通過計算當(dāng)前的節(jié)點數(shù)和所有節(jié)點數(shù)的比值，ωj的值很小，啟發(fā)函數(shù)ηij（t）的值很大，搜索范圍內(nèi)的轉(zhuǎn)移概率將被放大，可以提高算法的準(zhǔn)確性；當(dāng)蟻群算法逐漸搜索到后期，ωj的值逐漸變大，啟發(fā)函數(shù)）逐漸變小，使蟻群算法收斂速度增加。

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

2.2 路徑光滑因子

根據(jù)傳統(tǒng)蟻群算法運(yùn)算結(jié)果，規(guī)劃的AGV路徑存在有突變節(jié)點，即AGV在行駛中速度與加速度變化較大，行進(jìn)方向有較大突變。帶來的后果是按照不光滑路線行駛的AGV，時常需要改變較大的行駛角度，致使在轉(zhuǎn)動的過程中AGV損耗更多的電量和時間。由此，在改進(jìn)蟻群算法轉(zhuǎn)移概率目標(biāo)函數(shù)時，考慮將路徑光滑作為一個參數(shù)，構(gòu)造路徑光滑因子。

選取一條AGV行駛路徑，取其中三個連續(xù)的路徑節(jié)點A、B、C。如圖2所示，夾角φ為后一時刻AGV行駛線段的延長線與當(dāng)前路徑方向的夾角。

為了使規(guī)劃的路徑近似光滑，即是AGV方向轉(zhuǎn)角較小，所以φ的角度在0~90°之間。構(gòu)造路徑光滑參數(shù)λ和路徑光滑因子f，其計算公式如下：

圖2 路徑光滑示意圖

如式（7）所示，λ作為路徑光滑參數(shù)，反應(yīng)了前后兩個時刻的規(guī)劃路徑節(jié)點是否滿足近似光滑條件，即φ的值不超過0.5π，則λ∈[0,1] 。若前后兩個時刻規(guī)劃路徑節(jié)點不滿足近似光滑，即φ的值超過了0.5π，則λ的值超過1，認(rèn)為AGV行駛在這一節(jié)點不光滑。

式（8）為光滑因子f函數(shù)表達(dá)式，含有路徑光滑參數(shù)λ，光滑因子f的值決定了AGV已行駛路徑的光滑程度。當(dāng)f的值大于1時，說明路徑不光滑，將重新選擇路徑點；當(dāng)f的值小于1時，左右說明路徑較為光滑，平均每個節(jié)點的φi都小于90度，滿足路徑光滑條件。式中的Mcurrent是指這一條路徑上的已經(jīng)走過的節(jié)點數(shù)，即AGV行駛中需要變換方向的節(jié)點。

根據(jù)全局信息因子ω，避障因子γ和光滑因子λ，改進(jìn)的轉(zhuǎn)移概率計算公式如下：

避障因子（γij）t通過正負(fù)值差異來判斷是否在下一時刻有障礙物，為保證避障因子在整個轉(zhuǎn)移概率公式中起作用，即保證的分子不為雙數(shù)。如上式所示，在路徑不是很光滑的情況下，則f的值變大，的值就會變小，從而整個轉(zhuǎn)移概率在避障因子計算后，再通過比較大小得出最光滑的路徑。

2.3 信息素更新策略

原蟻群算法中，通過構(gòu)造關(guān)于信息素濃度和時間的函數(shù)關(guān)系來達(dá)到這一功能。原下一時刻信息素濃度的計算公式如下：

式 （10） 中，τij（t）為t時刻節(jié)點i到節(jié)點j路徑上的信息素濃度，τij（t+1 ）為t+1時刻節(jié)點i到節(jié)點j路徑上的信息素濃度；（1-ρ）為信息素殘留系數(shù)；ρ為信息素?fù)]發(fā)系數(shù)。

當(dāng)ρ的值較大時，信息素?fù)]發(fā)加快，對應(yīng)路徑上的信息素殘留濃度小；當(dāng)ρ的值較小時，信息素?fù)]發(fā)緩慢，對應(yīng)路徑上的信息素殘留濃度大。

針對信息素?fù)]發(fā)系數(shù)ρ，同樣引入避障函數(shù)γij（t），改進(jìn)更新的信息素?fù)]發(fā)系數(shù)ρ（t）為：

式（13）中，ρ0為初始信息度濃度；Ncurrent為當(dāng)前迭代次數(shù)；Nmax為算法最大迭代次數(shù)。

引入避障函數(shù)γij（t）之后，改進(jìn)的信息素?fù)]發(fā)系數(shù)ρ（t）在有障礙的路徑上揮發(fā)率大幅增加，使錯誤節(jié)點的信息素殘留少，降低了錯誤節(jié)點的轉(zhuǎn)移概率。

在算法開始初期，經(jīng)過的節(jié)點數(shù)較少，ρ（t）信息揮發(fā)系數(shù)較小，各節(jié)點上的信息素殘留濃度較大，降低了算法陷入局部最小值的概率；隨著算法到后期，經(jīng)過節(jié)點數(shù)增多，信息素?fù)]發(fā)系數(shù)增大，算法收斂加快。將式（13）代入式（10）中，得到改進(jìn)后的隨時間變化的信息素更新方法為：

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

3 仿真實驗分析

為了驗證改進(jìn)蟻群算法在AGV全局路徑規(guī)劃中的有效性，本文根據(jù)廣東某物流企業(yè)的實地生產(chǎn)線，構(gòu)建40m×50m的物流工廠環(huán)境模型，令A(yù)GV的起點為S（ 5,3 5 ），AGV的目標(biāo)點T（ 45,5）。在空間中含有4個凸多邊形作為障礙物。

在蟻群算法初始化中，設(shè)定信息素濃度Q=10，信息素?fù)]發(fā)系數(shù)初始值ρ0=0.1，信息素初始值τ0=0.004。蟻群中的螞蟻數(shù)量為20，啟發(fā)函數(shù)的啟發(fā)因子數(shù)β=5，信息素影響因子為α=1，最大迭代次數(shù)為Nmax=100。

基于上述初始化的參數(shù)設(shè)置，在應(yīng)用傳統(tǒng)蟻群算法之前先應(yīng)用A*算法，目的是利用A*算法為傳統(tǒng)蟻群算法先運(yùn)算出避開障礙的節(jié)點。

改進(jìn)蟻群算法分別進(jìn)行實驗，搜索得到的最優(yōu)化路徑分別如圖4、圖5和收斂速度曲線如圖6、圖7所示。

圖4和圖5中的粗實線為算法得到的最優(yōu)化路徑。改進(jìn)算法和傳統(tǒng)蟻群結(jié)合A*算法的路徑光滑因子f的值分別為0.20和2.4?？梢姡瑐鹘y(tǒng)蟻群算法路徑論光滑程度不如改進(jìn)蟻群算法的路徑，圖5中在節(jié)點P30、P6和P12處有突變，改進(jìn)蟻群算法路徑僅在節(jié)點P12處出現(xiàn)突變。由圖6和圖7可見，改進(jìn)蟻群算法在迭代次數(shù)為43左右收斂，而傳統(tǒng)蟻群算法在迭代次數(shù)60左右收斂。改進(jìn)算法收斂速度快于傳統(tǒng)算法。

所示的僅為一次實驗的結(jié)果，在初始化參數(shù)設(shè)置相同的情況下，對上述兩者分別進(jìn)行50次仿真實驗。得到實驗結(jié)果在圖8和圖9中所示，經(jīng)過計算，改進(jìn)蟻群算法的平均最優(yōu)路徑為60.31m，傳統(tǒng)蟻群算法為68.24m，改進(jìn)算法比傳統(tǒng)蟻群算法短；改進(jìn)蟻群算法的平均達(dá)到最優(yōu)路徑的迭代次數(shù)為46次，就已經(jīng)收斂，傳統(tǒng)蟻群算法為迭代75次后收斂，改進(jìn)算法比傳統(tǒng)蟻群算法達(dá)到最優(yōu)路徑的迭代次數(shù)較少。各評價系數(shù)平均值如表1所示：

4 結(jié)束語

本文提出了基于改進(jìn)蟻群算法中的AGV路徑規(guī)劃方法，在啟發(fā)函數(shù)中引入了避障條件，優(yōu)化路徑光滑，構(gòu)造全局信息因子，來應(yīng)對AGV面對的復(fù)雜地形，找尋避開障礙的光滑最優(yōu)路徑，達(dá)到保證安全、提高作業(yè)效率的目的。通過實驗仿真，驗證了該改進(jìn)算法不僅具備避開障礙的能力，且規(guī)劃的最優(yōu)路徑和迭代次數(shù)均優(yōu)于傳統(tǒng)蟻群算法結(jié)合A*算法。研究結(jié)果將提高AGV應(yīng)用的自動化程度，對未來AGV在應(yīng)對復(fù)雜物流環(huán)境有著一定的價值。

圖4 傳統(tǒng)蟻群結(jié)合A*算法規(guī)劃結(jié)果

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

圖6 傳統(tǒng)蟻群迭代次數(shù)

圖7 改進(jìn)蟻群算法迭代次數(shù)

表1 各評價參數(shù)平均值

圖8 兩種算法最優(yōu)路徑距離

圖9 兩種算法最優(yōu)迭代次數(shù)

[2] 湯紅杰，王鼎，皇攀凌,等.優(yōu)化Dijkstra算法在工廠內(nèi)物流AGV路徑規(guī)劃的研究[J].機(jī)械設(shè)計與制造，2018(5)：117-120.