基于改進勢場蟻群算法的自動引導小車路徑規劃研究

王 雨，謝 峰，劉玉磊，朱 翔

（安徽大學 電氣工程與自動化學院，合肥 230601）

0 引言

自動引導小車（Automated Guided Vehicles，簡稱AGV）是一種無人駕駛的智能運輸車，廣泛的應用于現代工業自動化物流系統中[1]。AGV是指裝有諸如磁傳感器、攝像機等導航裝置，能夠行駛在提前規劃好的路徑，并且在車體上安裝有主控制器、定位裝置、安全保護裝置、通訊模塊、以及各種物料運載的車輛，是一種智能輪式機器人，被廣泛用于工廠自動化生產線、倉儲物流、機場和港口的物料傳送場景[2,3]。AGV路徑規劃是目前機器人領域中一個研究的熱點，即在未知的環境中，尋找到一條時間最短、路徑最短的安全無碰撞路徑。目前解決問題的方法主要有人工勢場法[4,5]、Dijkstra算法[6]、遺傳算法[7]以及蟻群算法[8]等，其中每種方法都存在著自身的優點和不足之處。

蟻群算法是由意大利學者Marco Dorigo于1992年提出的，其靈感來源于螞蟻在尋找食物過程發現路徑的行為。螞蟻在覓食的過程中會傾向于選擇信息素濃度大的路徑，同時更新自己的信息素，直到蟻群選擇同一條且信息素濃度最大的最優路徑。蟻群算法具有較強的適應性和魯棒性，但是也存在著許多問題，如蟻群算法是以螞蟻從當前點到目標點的距離作為啟發信息，不利于螞蟻對動、靜態障礙物的規避，而且螞蟻尋找目標是一個盲目搜索的過程，這樣就會產生較多的交叉路徑和螞蟻迷失現象[9]，造成蟻群算法過早的收斂、搜索路徑效率低下等情況。

人工勢場法是一種局部路徑規劃算法，它的本質是對AGV運行環境虛擬成一個抽象的勢場，在虛擬勢場中AGV受到障礙物的斥力和目標的吸引力形成的合力來確定運動方向和速度。人工勢場法可以保證得到一條安全的路徑，但可能并不是最優的一條，而且也存在著一些不足之處，該算法易造成目標不可以到達且在目標點附近打轉，或存在著局部最小區域，迫使AGV處于暫時停滯狀態[10]。

本文根據蟻群算法和人工勢場法兩者的優缺點，提出了一種改進的勢場蟻群算法。該算法利用AGV所受到人工勢場力以及到目標點的距離來重新構造啟發信息函數，根據動、靜態障礙物構造不同的勢場函數，并且引入障礙物對AGV的相對速度和方向，實時更新動態障礙物在柵格地圖中的位置，可以做到以較小的代價提前規避障礙物；人工勢場的加入使螞蟻盲目搜索變成有向的搜索，減少了蟻群搜索過程中的“迷失”現象，加快了收斂速度。

1 蟻群算法和人工勢場法的基本原理

為了更好地利用勢場蟻群算法解決自動化車間環境下AGV路徑規劃問題，本文將AGV工作環境視為二維空間，并采用柵格法建立柵格地圖，根據AGV小車的大小尺寸來進行柵格地圖網格大小的劃分，黑色表示障礙物，白色表示自由柵格，AGV作為一個質點運動，對障礙物進行膨脹處理，如占據局部柵格，按照整個柵格處理，以防止發生碰撞。AGV路徑規劃算法如下。

1.1 傳統蟻群算法

傳統的蟻群算法來決定螞蟻在t時刻行走路徑的原理是：某螞蟻（m）在第i個節點選擇下一個節點j的概率是根據柵格環境中各路徑上的信息素ij(t)和當前的啟發信息ij(t)的大小決定的，如式(1)所示。

螞蟻經過的路徑會留下信息素，但隨著時間的流逝會揮發一定的數量，需要對其按照式(2)進行局部更新：

蟻群算法完成一次迭代后，可找出當前螞蟻尋找到的最短、最優路徑，并對信息素通過式(3)和式(4)進行全局更新。

式中：Q為常量，ρ表示信息揮發參數，Lm表示螞蟻建立的最短路徑。

1.2 人工勢場法

人工勢場法的實質是對機器人運行環境虛擬一個抽象勢場，障礙物對機器人產生斥力Frep，目標點產生引力Fatt，合力Ftot指引機器人運動。

假設AGV在M點，目標對其引力勢場函數為Uatt(i)，如式(5)所示，障礙物對其斥力勢場函數為Urep(i)，如式(6)所示[11～13]。

式中：η和ξ分別是斥力勢場常量、引力勢場常量；d（M，O）為當前點到障礙物點的距離；d（M，G）為當前點到目標點的距離；dO表示斥場作用半徑。AGV在M點所受的引力和斥力分別為式(7)、式(8)所示。

根據幾何疊加原理得到所受合力為Ftot=Frep+Fatt，nMG為當前點到目標點的單位矢量。

2 勢場蟻群算法的改進

2.1 改進的人工勢場法

自動化車間環境經常會有人來回的進行走動，形成了動態的障礙物，人工勢場對于動態障礙物的環境，存在著躲避不及的問題，因此需在人工勢場法的基礎上加以改進，對勢場函數不僅要考慮其相對位置，還要考慮它們之間的相對速度。如圖1所示，以AGV小車為參照物，通過kinect視覺傳感器感知環境，得到障礙物t0到t1時間段的位置信息和移動角度，然后抽象為速度矢量三角形計算它們的相對速度大小v和方向。

圖1 求取障礙物相對速度示意圖

規定AGV移動逆時針為正，順時針為負，則障礙物移動的相對角度和距離為式(9)所示：計算出安全避碰最小角度和安全距離，并據此建立新的勢場函數。所改進的引力勢場函數和斥力勢場函數分別為式(10)和式(11)：

由此可求出障礙物和AGV的碰撞角

式中η和ξ是速度常數，v是AGV到障礙物的相對速度，vO為AGV到目標點的相對速度。

那么，AGV在此處受到的斥力和引力分別如式(12)和式(13)所示。

2.2 啟發信息的改進

螞蟻在柵格地圖上移動，傳統蟻群算法中螞蟻受到信息素濃度和距離的作用，當路徑短時，使螞蟻往返一次時間短，重復頻率快，每次行走都會留下信息素，吸引更多的螞蟻，增加路徑上的信息素濃度，這樣越來越多的螞蟻都聚集在最短路徑上。但在路徑規劃初期，信息素濃度較弱時，螞蟻搜索的隨機性較大，收斂速度變慢。而在傳統的人工勢場法中，螞蟻是通過所受勢場合力來進行路徑規劃，定義的啟發信息為：

式中，α為常數，θ為螞蟻行走方向和勢場合力方向的夾角。在啟發信息的作用下，螞蟻選擇θ最小的邊行走，有利于避免碰撞和有效的選擇最接近目標點路經行走。但當勢場合力為零時，AGV將會處于局部最小點，引力和斥力等價，陷入局部最優位置陷阱，為此，本文結合兩種算法的優點構成算法的啟發信息為：

式中，Nmax和N分別為最大迭代次數和當前迭代次數。從式(17)可以看出在勢場蟻群算法初期，信息素濃度較低，主要靠勢場力啟發信息使螞蟻快速找到目標點。隨著迭代次數的增加，降低了勢場力啟發信息的作用，加強了信息素的作用，使螞蟻主要集中在信息素濃度強的路徑上，從而增強了對最優路徑的搜索。最后還可以保障在人工勢場合力為零的情況下仍有效的進行到目標的最優路徑搜索，進而避免失去搜索方向。

2.3 路徑規劃步驟

步驟1：確定柵格地圖長度，障礙物的位置，AGV的起始點和終點；

步驟2：初始化勢場蟻群算法的參數，例如螞蟻數量、信息啟發因子、引力和斥力增益、信息素強度等；

步驟3：將螞蟻放在起點，判斷行走過程中有沒有動態障礙物，如果存在動態障礙物，算出安全距離和角度，更新柵格地圖中的障礙物位置，按照式(1)和勢場合力方向選擇下一個節點。當螞蟻到節點j后的，按式(2)對走過的路進行局部信息素更新，并刪除跟新的柵格地圖；若不存在動態障礙物，按照傳統勢場合力方向選擇下一個節點j，并將節點j加入禁忌表；

步驟4：重復步驟3，直到螞蟻到達目標點，保存所有螞蟻搜索到的路徑長度，并選擇最優路徑；

步驟5：按照式(3)對最短路徑進行信息素的全局更新，清空禁忌表；

步驟6：判斷是否達到最大迭代次數，若達到則終結，否則重復步驟3到步驟4。

3 AGV路徑規劃實驗驗證

為了驗證本文所提的路徑規劃算法的可行性，在Matlab環境下對該算法進行仿真，加以和常規的蟻群算法比較。本文用20×20的柵格環境和不同的障礙物設置來模擬真實環境，每個柵格的大小為一個單位長度。AGV起點設置為（1，20），終點設置為（20，1），黑色表格為障礙物，白色表格表示自由柵格。設定參數螞蟻數量為30，迭代次數為100，信息素濃度啟發因子α=1，能見度啟發因子β=5，信息素揮發系數ρ=0.7，信息素強度Q=1，引力系數η=2，斥力系數ζ=2，斥力作用半徑d0=2，可調參數ψ=0.1。

通過圖2可以看出，在復雜的自動化車間環境下，傳統蟻群算法沒有搜索到一條最優的路徑，而是找到了一條較長的路徑，因為盲目搜索和搜到啟發信息的影響，在中心復雜的環境中，螞蟻偏向于遠離障礙物，造成了較長的行走路徑，由于信息素的作用，以后的蟻群也會較大幾率選擇此路。改進的算法在勢場合力和信息素濃度的雙重作用下加快算法的收斂速度，并且避免了上述問題。從收斂曲線看，蟻群算法用了56次迭代收斂到34.549，本文改進的勢場蟻群算法只用了30次迭代就收斂到最優路徑30.364。

圖2 蟻群算法

圖3 改進勢場蟻群算法

圖4 動態障礙物的路徑規劃

對于動態障礙物，改進的人工勢場可以實時更新局部環境，根據計算得到的安全距離和角度來填充柵格地圖障礙物的位置。從上圖可以看出當運行到（8，14）時，有動態障礙物實時更新柵格地圖，從（8，12）開始添加障礙物，然后根據改進人工勢場算法在局部柵格地圖重新計算路徑。從圖4可以看出路徑變得更加復雜，用37次迭代收斂到31.269。

4 結論

本文針對復雜的自動化車間環境的路徑規劃問題，采用人工勢場算法和蟻群算法融合的辦法。將AGV在運動中受到的虛擬勢場合力作為螞蟻尋找目標點的部分啟發信息，引導AGV感知周圍障礙物，進行有效的避障和目標搜索。在感知到運動目標時，及時的在局部地圖上更新障礙物，在改進的新勢場函數引導下進行有效的避障，尋找到最優的安全避障距離和角度，結束后恢復原柵格地圖。通過仿真結果表明，本文所提出的改進勢場蟻群算法對自動化車間環境下路徑規劃的效果比較好，對動態障礙物也有很好的躲避效果。