融合柵格地圖模型的改進AGV路徑規劃算法研究

顧文斌，陳澤宇，吳亞偉，苑明海

(1.河海大學 機電學院，江蘇 常州 213022；2.常州工程職業技術學院，江蘇 常州 213022)

0 引 言

自動引導小車(automated guided vehicle，AGV)最早出現于二十世紀五十年代，是一種智能化物料自動搬運設備，其特點在于自動化程度高、易于控制、節省勞動力、提高運輸效率、占地空間小等，因此，AGV在眾多生產制造物流行業中得到了廣泛應用。在汽車制造行業中，物流領域自動化設備應用是大勢所趨，使用AGV替代人力能夠降低汽車制造企業的運輸成本，提升服務質量[1]。對煙草、醫藥、食品和化工等行業而言，業內對搬運任務有清潔、無排放污染、安全等要求，AGV能夠較好地勝任。在倉儲業中，AGV使用程度更為廣泛，因為AGV有較強自動化水平和較高柔性，在倉儲物流行業中能夠降低人力成本，提高運輸效率[2]。在AGV的使用中，進行合理的路徑規劃對于降低企業運營成本，提高利潤率有重大作用，因此AGV的路徑規劃問題十分值得研究。

為了計算得到全局最優路徑，目前采用的方法主要有遺傳算法[3-4]、粒子群算法[5-6]、快速擴展隨機樹尋路算法[7]和蟻群算法[8-9]。之后的研究主要針對這幾種算法進行改進，文獻[1]提出的改進遺傳算法減少了最短路徑的路程，文獻[2]對傳統遺傳算法進行改進，提高了算法的收斂速度和效率。文獻[5]提出的改進粒子群算法提高了在AGV在規避障礙時搜得解的精度。文獻[7]提出的改進快速擴展隨機樹尋路算法使得在復雜環境下機器人的運行更加平穩，且在一定程度上縮短了路徑長度。文獻[8]提出的融合粒子群與蟻群算法提升了蟻群算法的整體性能。對于傳統蟻群算法收斂性差，容易陷入局部最優，結果不穩定的缺點，則考慮在對螞蟻和迭代質量的評估之后，對每一次尋路的信息素進行區別更新，有利于擴大算法前期的搜索范圍，加強算法后期的收斂性，提高算法的穩定性。

以上文獻所用方法是目前解決AGV路徑規劃問題中普遍認可的，較優的算法，但是傳統算法存在容易進入局部最優解，收斂性較差和搜尋結果穩定性差的問題。基于此，該文提出了改進型蟻群算法，使用兩次評估來合理區分蟻群，根據區分結果使用不同的信息素更新方式，以此實現提高算法解的多樣性、收斂性和穩定性的目標。此外使用蜂巢柵格建立地圖模型，使得模型更加實際可靠，能提高AGV小車行駛時的平穩性，并降低避險路徑的長度。

1 環境模型建立

對于研究AGV的路徑規劃問題，建立其空間移動環境模型是基礎，常用的方法有可視圖法[10]、傳統柵格法[11]和人工勢場法[12]。柵格法(grid method)具有簡單，易于表達和靈活等優點，所以采用柵格法建立AGV空間環境模型，并在傳統的柵格基礎上，模擬蜂巢建立起正六邊形的柵格，對AGV行駛環境進行分割。

1.1 蜂巢柵格模型建立

圖1 蜂巢型柵格

1.2 蜂巢型柵格和傳統柵格的對比分析

圖2 蜂巢柵格移動方向

圖3 避險路徑對比

圖4 最短路徑對比

綜上，蜂巢柵格在行駛的平穩性和避險路徑的長度方面都優于傳統的正方形柵格，因此后文的改良蟻群算法將在蜂巢柵格的背景下進行求解。

2 基于動態分級制度的改進型蟻群算法

2.1 傳統蟻群算法

在傳統的蟻群算法中，螞蟻會根據路徑上的信息素濃度選擇自己的路徑，并且根據路徑的質量留下新的信息素，每一次迭代后所有路徑上的信息素都會消散一部分，使得路徑尋找不會過早地進入局部最優。選擇方法如下。

(1)

(2)

(3)

式中，ρ∈(0,1)，為信息素在一次迭代中的揮發系數；Δτij為信息素的增量；K為螞蟻總數；Q為一常數。

2.2 選擇機制的改進

在傳統的蟻群算法中，路徑啟發因子ηij(t)是根據路徑(i，j)所確定的，但是這樣容易陷入局部最優解。為了獲得全局優解，在改進的算法中使用ηij(t)=1/d(i,s)，其中d(i,s)為螞蟻此時距離目標點的距離，同時將allowedk改為螞蟻k相鄰可選擇的點，將柵格矩陣做鄰接處理，螞蟻k只能選擇所得鄰接矩陣中值不為0的點做下一目標點，以減少不必要的計算。

2.3 對蟻群進行評估分類

對于傳統的蟻群算法，信息素的更新完全根據路徑長度，也有學者研究了改良的信息素更新規則[13]來優化蟻群算法，但是在算法前期多樣性和后期的收斂性方面還有待提高。針對這個問題，文中在考慮螞蟻的動態分級[9]之上，考慮每一次迭代的質量，將每一次的迭代性質分為尋優和偵察，不同性質的迭代采用不同的信息素更新規則，以提高前期解的多樣性和后期解的收斂性。

具體來說，受到人工蜂群算法[14]的啟發，先將螞蟻分為偵察蟻和尋優蟻。首先根據該螞蟻在一次迭代中所搜索到的路徑Lk與此次迭代中所搜索到的最短路徑Lmin相比較，得到該螞蟻的屬性值，該值設置為：Tk=Lmin/Lk。之后設置屬性值的閾值，記為T0。比較屬性值和閾值來區分偵察蟻和尋優蟻，當Tk>T0時，說明該螞蟻搜得結果與最優解相近，為尋優蟻，則該螞蟻在更新信息素時，將更新的參數調整使得余留更多的信息素。反之當Tk≤T0時，說明該螞蟻搜得路徑與最短路徑之間的差距較大，為偵察蟻，則該螞蟻在更新信息素時，將參數調整使得余留更少的信息素。所以T0設置的值需要重點研究，如果T0太大容易導致更少的螞蟻成為尋優蟻而導致算法最終不能很好地收斂，如果T0太小容易使更多的螞蟻成為尋優蟻而導致蟻群容易陷入局部最優解。經過多次仿真，發現將T0設置為0.68時能得到很好的結果。

2.4 信息素更新規則

根據上文對蟻群的評估結果，將算法中的螞蟻分為了四種情況，對于四種螞蟻將采取不同的信息素更細規則。

首先對于尋優蟻和偵察蟻，兩者在信息素更新時，滿足以下關系：

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

(4)

(5)

(6)

式(5)、式(6)中，ω為螞蟻質量系數，其中ω1>ω2>0，Q為一常數，Tk為螞蟻的屬性值，T0為螞蟻屬性值的閾值。在此更新規則下，尋優蟻的信息素余留要高于偵察蟻的信息素余留，這樣在進行全局搜素時，確保了較優路徑上有高濃度的信息素，但是ω1和ω2之間的差值不能過大，否則容易在算法初期就陷入局部最優。經過實驗仿真，將ω1設置為5，ω2設置為3，能夠有效防止陷入局部最優且最后收斂較好。

關于迭代質量，由于在算法初期，螞蟻搜索范圍大，路徑長短參差不齊且相差較大，此時這一代螞蟻的信息素更新策略采用式(7)。

τij(t+1)=(1-ρ)τij(t)+pm·Δτij,pm≤p0(7)

式中，pm為迭代的質量值；Δτij則根據上述內容先判斷該螞蟻是尋優蟻還是偵察蟻。

在這種機制下，算法初期過于發散的搜尋結果將不會留下過濃的信息素，而其中接近最優路徑的螞蟻則根據尋優蟻余留更多信息素的特點，將較優路徑先行區分開來，到達算法后期，一次迭代中大部分螞蟻都是接近最優路徑后，則使用式(4)進行信息素更新，使結果收斂于最優路徑。

綜上所述，改進型蟻群算法信息素更新滿足以下規則。

(8)

2.5 算法流程

將蜂巢柵格和改進的蟻群信息素更新規則融入傳統蟻群算法，得到的基于蜂巢柵格的改良蟻群算法如下(見圖5):

圖5 改進蟻群算法流程

(1)全局初始化，將環境矩陣鄰接化得到鄰接矩陣，得到初始螞蟻總數，迭代總數，起點終點位置。

(2)螞蟻根據概率公式(1)對路徑節點進行選擇。

(3)判斷螞蟻是否到達終點，若是，記錄此路徑長度并對該螞蟻的屬性進行評估，當所有螞蟻執行完此步，迭代數加1。若不是則重復步驟(2)。

(4)當所有螞蟻完成步驟(3),對迭代質量進行評估。

(5)根據螞蟻屬性和迭代質量，對信息素進行區別更新。

(6)判斷是否到達最大迭代數，若是，則輸出最優路徑，算法結束；若不是，則重復步驟(2)～(5)，直到算法結束。

3 仿真分析

使用MATLAB軟件對傳統蟻群算法和改進型蟻群算法進行仿真。前文已經論述了蜂巢柵格的優點，所以兩種算法都在25×25的蜂巢柵格的背景下進行計算。各個參數設置為：α=1,β=7,ρ=0.3,Q=1螞蟻數K=100，迭代數M=150。算法性能從算法的收斂性、路徑多樣性進行證明。

3.1 算法收斂性證明

圖6為根據改進型蟻群算法所得出的最短路徑圖。圖7為兩種算法的最短路徑長度的曲線收斂圖。從圖7的對比中可以看出，改進型算法在前期效果并非十分明顯，因為要保證初期路徑的多樣性，而到了算法中后期，進行有針對地尋找最優路徑時，改進型蟻群算法能體現出良好的收斂性。

圖6 最優路徑圖

為了證明算法的穩定性，并和傳統算法進行對比，將兩種算法各運行10次并統計數據結果，如表1所示。

表1 算法結果對比

從表中可知，傳統算法下搜得最短路徑長度為36，而改進型算法下搜得最短路徑為35，并且根據10次運算的平均值和標準差可以看出，傳統的算法搜得最終結果差別較大，相比之下改進型蟻群算法出現此類問題的次數會少很多，根據收斂代數也可以看出，改進型蟻群算法由于信息素更新與傳統蟻群有區別，所以算法后期收斂性更強。

3.2 路徑多樣性證明

為了證明改進型蟻群算法在路徑多樣性方面的優越性，和王槐彬等人提出的動態分級蟻群算法[15]進行了實驗數據結果對比。

在同時采用蜂巢柵格的基礎上，改進型蟻群算法和動態分級蟻群算法在路徑多樣性方面的對比如圖8所示。實驗設計150次迭代，在前半段迭代中，由于迭代質量不佳，螞蟻殘留的信息素濃度根據更新規則會相應減少，可以看到改進型蟻群算法的路徑多樣性要高于動態分級蟻群算法，達到避免進入局部最優的效果，證明了改進型蟻群算法在路徑多樣性方面的優越性。并且在算法后半段，迭代質量提升，螞蟻逐漸向整體最優路徑靠攏，根據信息素更新規則留下的信息素會增加使得蟻群準確地找到最優解。在圖中可以看出，最后改進型蟻群算法能夠使大部分螞蟻都找到最優解，也證明了改進型蟻群算法的收斂性要優于動態分級蟻群算法。

圖8 路徑種類對比

從每一次迭代結果的路徑長度標準差分析，如圖9所示，動態分級蟻群算法整體上能實現算法前期避免進入局部最優，后期結果實現收斂，但是通過比較可以看出改進型蟻群算法在前期的發散程度和后期的收斂程度都要高于動態分級蟻群算法。如果考慮標準差到達一個閾值可以認為蟻群已經找到整體最優解，那么改進型蟻群算法相比于動態分級蟻群算法能夠更快得到結果，解決算法效率低的問題，證明改進型蟻群算法整體上優于動態分級蟻群算法。

圖9 路徑長度標準差對比

4 結束語

對于AGV的路徑規劃問題，在傳統的柵格模型上進行改變，使用轉向角度小，避險路徑和原路徑比值小的蜂巢柵格對AGV行駛環境進行模型建立。在算法方面，由于傳統蟻群算法效率低，根據螞蟻和迭代的評估值對其進行信息素區別更新。在新的更新規則下，根據仿真結果可以得出，相比于傳統算法，改進型算法在前期的路徑多樣性，后期的算法收斂性方面都更加優良，并且最終結果的準確性、穩定性也要優于傳統的蟻群算法，證明了改進型蟻群算法整體優于傳統蟻群算法。