基于改進蟻群算法的AGV路徑研究

何成偉，茅 健 HE Chengwei,MAO Jian

（上海工程技術大學 機械與汽車工程學院，上海 201620）

0 引言

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

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

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

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

（1）將移動的AGV看作是質點。

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

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

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

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

圖1 構造MALINK自由路徑

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

2 改進蟻群算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

將式（4）代入式（1）中，得到改進后的蟻群算法轉移概率計算公式：

2.2 路徑光滑因子

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

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

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

圖2 路徑光滑示意圖

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

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

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

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

2.3 信息素更新策略

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

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

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

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

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

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

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

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

3 仿真實驗分析

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

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

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

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

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

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

4 結束語

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

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

圖5 改進蟻群算法規(guī)劃結果

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

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

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

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

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

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