一種基于改進蟻群算法的AGV小車三維路徑規劃研究

金 鑫 鑫

(亳州學院電子與信息工程系 安徽 亳州 236800)

0 引 言

智能倉儲系統是指以信息化手段實現對倉庫的實時監視和全面管理的信息系統，該系統能夠實時掌握倉庫容量、了解貨物所存放位置、實現自主貨物轉移等[1-2]。在智能倉儲系統中，貨物轉移快慢直接關系到其管理效率，通常執行貨物轉移作業的設備主要為AGV小車，如果要提高貨物轉移的速度，就需要對AGV小車的行駛路徑進行規劃[3]。

當前針對倉儲系統中AGV小車的路徑優化算法包括人工勢場法、遺傳算法、蟻群算法等。其中遺傳算法雖然全局搜索能力強，但存在產生無效路徑的問題；人工勢場法在勢場合力為零時會出現停滯狀態，容易陷入局部最優；相比之下，蟻群算法具有正反饋、高穩健性和并行性的優點，已成功地用于智能倉儲AGV小車的行駛路徑規劃等問題[4]。

蟻群算法最早是由Dorigo等學者提出的分布式智能仿生算法，該算法模擬了螞蟻合作覓食行為的性質[5]。從算法原理上來看，蟻群算法主要存在搜索空間大、局部最優、搜索效率低、計算量大等問題。近年來，國內外眾多專家學者致力于利用蟻群算法解決全局路徑規劃問題。文獻[6]通過重新定義蟻群算法中的轉移概率，對蟻群算法進行改進，從而加快了算法的尋優速度，但是其轉移概率自適應調整能力較差。文獻[7]為了避免蟻群在面對凹型障礙物時易陷入死鎖狀態的問題，通過采用廣義信息素更新原則，代替傳統蟻群算法的信息素更新，從而找到最優解，但是該算法易陷入局部最優。文獻[8]提出了雙層蟻群算法，大大提高了路徑規劃的效率，但雙蟻群的信息素作用會相互干擾，影響尋優結果。文獻[9]提出一種基于自適應調整信息素的改進蟻群算法，根據人工螞蟻所獲得解的情況，動態調整路徑上的信息素，從而使得算法跳離局部最優解，但是該方法未能考慮較優路徑重要路段上的信息素強度，使得算法搜索效率不高。

智能倉儲系統中的AGV小車路徑規劃是當前研究的熱點和難點。針對AGV路徑規劃，文獻[10]在路徑優化的方法中增加了對時間和能耗的考慮，實現了倉儲系統貨物轉移作業中的能耗和效率之間的有效平衡。文獻[11]通過利用交通規則和預約表解決倉儲物流機器人集群在運行時發生的碰撞和死鎖問題，并根據所設定的協同機制，減少機器人無任務的待機狀態，平衡各機器人之間的工作量，最終實現在保證系統安全運行的基礎上縮短系統運行時間的目的。文獻[12]在倉儲系統貨物轉移作業的工作中，為平衡行駛距離、行駛時間、作業載重等因素，建立了多因子的路徑優化模型，并通過集成學習優化算法降低模型的復雜度，實現了倉儲系統貨物轉移作業時間效率的優化。

從當前的研究現狀來看，AGV路徑規劃的研究主要針對二維平面避障、二維路徑優化等，但是不適用于貨架式倉儲系統中的三維折線路徑規劃[10]，且大多數路徑規劃算法運行效率低，容易陷入局部最優。鑒于此，本文提出了一種基于改進蟻群算法的AGV小車三維路徑規劃方法。首先，通過構建三維倉庫模型來確定不同目標的三維坐標，并根據多個位置坐標建立AGV小車軌跡模型；其次，針對倉庫AGV小車三維折線路徑，利用改進的蟻群算法來實現路徑優化問題；最后通過對比實驗來驗證基于改進后的蟻群算法的性能。

1 三維空間路徑優化問題建模

1.1 立體倉庫模型構建

在智能倉儲系統中，AGV小車的作業模式主要有入庫和出庫作業[13]。在智能倉儲系統中，單一的AGV小車作業往往需要在多個目標之間進行遍歷工作且貨物所存貨架高度不一，因此需要對AGV小車的作業路徑進行三維空間規劃。在路徑規劃過程中不僅需要考慮二維平面內的最優路徑，還需要注意小車在取貨物時的垂直運動及變換不同貨道時AGV小車的運動。鑒于此，本文建立立體倉庫模型，確定多目標的三維坐標，并通過模擬現實貨架和AGV小車來進行實驗驗證和操作。圖1所示為立體倉庫貨架實物圖，圖2為立體倉庫模型。模型將每排貨架進行網格化劃分，其坐標表示為(y,z)，貨架的排數表示為坐標x。通過這種方式可以將整個貨架式倉儲系統表示為三維網格地圖，這樣貨架的每一格均以三維坐標的形式表示出來，從而為AGV小車的路徑規劃提供保障。

圖1 立體倉庫貨架實物圖

圖2 立體倉庫模型

本文研究所使用的AGV小車并非單一兩點式作業小車，而是可以在多個目標點之間遍歷作業。智能倉儲系統為貨架式倉庫，每個貨架之間為貨道，AGV小車在同一個貨道上可以進行上下、前后運動，如果要到另一個貨架上取貨物，則需要先退出該貨道，再進入到另一個貨道。圖3所示為實驗AGV小車。

圖3 實驗AGV小車

當建立立體倉庫模型，并確定不同目標的三維空間坐標后，AGV小車入庫、出庫作業就可以按照以下三個步驟進行：(1) AGV小車計算所有目標點與自身之間的距離，并選取其中最近的目標點作為本次作業的起始點，并運動至起始點。(2) AGV小車根據所有目標點的位置計算出本次作業的順序，并按順序依次到達下一目標點進行存取貨。(3) AGV小車完成所有目標點的任務后回到起始點，即完成了本次作業，并等待下一次的作業指令。

通過上述分析可知，多目標點之間的順序決定了AGV小車路徑規劃的效率，同時也直接影響了AGV小車的單次作業時間。

1.2 運行軌跡模型構建

在立體倉庫模型中，AGV小車的運動主要包括水平和垂直兩個方向，其中水平方向主要由小車驅動系統自主運行，垂直方向運動主要借助升降機來實現。假設小車為勻速運行，考慮其在啟動及停止時的速度影響，取速度和時間均值，因此不會對路徑優化產生影響。

為了便于對AGV小車路徑進行規劃，本文對AGV小車的運動軌跡進行分類，主要包括：

(1) 兩個目標點位于同一個平面內，且X、Y、Z坐標中僅有一個坐標值不同，此時AGV小車在兩目標點間的運動軌跡為直線；

(2) 兩個目標點位于同一個平面，且X、Y、Z中有兩個坐標值不同；

(3) 兩個目標點位于不同平面，且X、Y、Z中坐標值均不相同。

根據上文分析，假設小車當前所在位置坐標為i=(x1,y1,z1)，目標位置坐標為j=(x2,y2,z2)，則如果AGV小車的運動符合第一種情況，那么其兩點之間的位移如式(1)所示。

S=|y1-y2|或|z1-z2|

(1)

此時，若AVG小車需要在X軸方向上進行操作，那么其需要退出當前所在的貨道，即運行到貨道口，此時位移如式(2)所示。

S=2|y|+|x1-x2|

(2)

若AGV小車的運動符合第二種情況，此時雖然在同一個平面內但并非在同一條直線上，因此需要借助輔助點來實現AGV小車的運動。若AGV小車需要在X軸方向上進行操作，則AGV小車需要退出當前所在的貨道，故兩目標點之間的位移如式(3)所示。

S=|x1-x2|+|y1|+|y2|或 |x1-x2|+|z1-z2|+2|y|或 |y1|+|y2|+|z1-z2|

(3)

若AGV小車的運動符合第三種情況，此時兩目標點不在同一個平面內，可以認為AGV小車需要進行跨平面運動。為實現兩點之間的運動還需要借助三個輔點，如果需要在X軸方向上進行操作，則需要退出當前所在的貨道，故兩目標點之間的位移如式(4)所示。

S=|x1-x2|+|y1|+|y2|+|z1-z2|

(4)

2 改進蟻群算法三維路徑優化

2.1 蟻群算法理論

蟻群算法是由Dorigo根據蟻群外出覓食的行為模擬總結出的一種尋找優化路徑的概率性算法。螞蟻在外出覓食時，將信息素釋放在所經過的路徑上，其他螞蟻對信息素的濃度進行感知，如果信息素濃度較高，說明此路徑目標點距離自己較近，其他螞蟻沿著此路徑行進的同時也會釋放信息素，進而使得此路徑上信息素濃度進一步增加，在正反饋機制的作用下，該路徑上的信息素越來越多。通過不停迭代計算，最終可以得到兩點之間的最短路徑。式(5)所示為蟻群算法中螞蟻選擇下一目標點的概率。

(5)

式中：i、j分別表示兩個目標點；α表示信息素因子，即信息素濃度的高低會對螞蟻對此路徑是否選擇產生一定的影響；β表示啟發式因子，即螞蟻在路徑選擇時信息素所占的重要程度；τij表示i、j兩點之間的信息素濃度；ηij(t)為啟發函數，ηij(t)=1/dij，dij表示i、j兩點之間的距離；tabuk為禁忌表。

當螞蟻遍歷完所有路徑之后返回到初始位置時，實現了一次路徑循環，之后再一次對信息素進行更新。此時每條路徑上的信息素包括隨著時間推移遺留下來的信息素及當前螞蟻釋放的信息素。因此信息素的迭代如式(6)所示。

(6)

根據上述對蟻群算法的原理分析，可知蟻群算法的優勢包括：(1) 通過正反饋不斷增加路徑上的信息素，使得算法在計算的過程中形成收斂的搜索過程，最終得到最優路徑。(2) 蟻群算法通過螞蟻個體釋放信息素來記錄路徑，每個螞蟻個體都可以對周圍環境進行改變，并可以對環境中的信息素進行感知。(3) 算法為分布式并發計算的過程，即每個螞蟻的路徑選擇概率計算是并行的，可大大提高算法效率。(4) 通過信息素濃度進行啟發式搜索，有利于找到全局最優路徑，而不會陷入局部最優。

2.2 改進蟻群算法三維路徑優化方法

在基本蟻群算法中，螞蟻通常會被分配到各個點位，并且需要對所有的目標點進行遍歷，不同目標點之間的順序選擇在很大程度上取決于轉移概率，而轉移概率又與每條路徑的啟發式因子和信息素濃度有關。

對于貨架式立體倉庫而言，要想實現AGV小車的路徑規劃，必須同時考慮到水平路徑選擇和垂直路線規劃。目前，基本蟻群算法主要用于解決二維平面路徑規劃即平面兩點之間的路徑，而對于貨架式立體倉庫這種平行于各坐標軸的折線路徑無法適用，因此需要對基本蟻群算法進行優化。

針對兩目標點的三種位置關系，通過cenpt變量來辨別兩目標點為何種位置關系，進而確定需要增加的輔助點的數量。圖4所示為增加輔助點數量的部分MATLAB代碼。

圖4 增加輔助點數量的部分MATLAB代碼

當cenpt=3,表示AGV小車在兩點之間運動屬于第三種情況，即兩目標點的x、y、z坐標均不一樣，需要增加三個輔助點a、b、c，此時三個點坐標分別為a=(x1,0,z1)，b=(x2,0,z1)，c=(x2,y2,z1)，兩點之間由i到j所經過的點的順序為i→a→b→c→j。當cenpt=2，表示小車在兩點之間運動屬于第二種情況，即兩目標點有兩個坐標值不同。此時可以分成兩種情況，當x坐標相同則只需要增加一個輔助點a=(x,y2,z1)，由i到j所經過的點的順序為i→a→j。當y坐標相同或者z坐標相同，那么小車需要退出貨道，此時需要增加三個坐標點a=(x1,0,z)、b=(x2,0,z)、c=(x2,y2,z)，兩點之間由i到j所經過的點的順序為i→a→b→c→j。當cenpt=1，表示兩個目標點只有一個坐標值不同，此時不需要增加輔助點，兩點之間直接由i運動到j，即i→j。本文提出的改進蟻群算法三維空間路徑優化方法，主要分為以下五個步驟：

步驟1假設算法中共有m個螞蟻，同時把這些螞蟻隨機放置在三維空間的不同點上，設置Nc_max為本次計算的最大迭代次數，并初始化蟻群算法中的各個變量，β為啟發因子，α為信息素因子，ρ為隨著時間推移信息素的揮發系數，Q為信息素的增強系數。

步驟2對算法中的每個個體的初始信息素進行確定，并將螞蟻隨機分配到不同的起始點上，讓其逐個選擇路徑，并將其經過的目標點放到禁忌表中。路徑選擇中，每個螞蟻根據概率函數來判斷應該選擇哪個目標點作為下一點，如式(7)所示。

(7)

在所有螞蟻都遍歷完一次路徑之后，會對各個螞蟻的路徑距離進行比較，并記錄其中最短的路徑，同時會記錄所有螞蟻行走路徑的平均數。圖5所示為實現最短路徑選擇的部分代碼。

圖5 選取最短路徑的部分代碼

步驟3將k值與m值進行比較，若k≥m，則說明k螞蟻已經走完了所有目標點，此時進入步驟4，否則轉入步驟2。

步驟4對全局中的信息素、信息素揮發系數、信息素增強系數進行更新，信息素的更新如式(8)所示。

(8)

圖6 更新信息素部分代碼

步驟5禁忌表清零。在達到最大迭代次數之后，將禁忌表清零，對每次迭代中所獲得的最短路徑進行比較，并最終得到最短路徑和所有目標點的行進順序，并輸出最優路徑結果。

圖7所示為改進蟻群算法實現流程。

圖7 改進蟻群算法實現流程

3 實驗結果與討論

為了驗證改進蟻群算法的有效性，在Window 10操作系統下采用MATLAB 2013a對算法進行仿真實驗，實驗硬件環境：Intel(R)Core(TM) i5-3337U Duo CPU1.8 GHz/8 GB內存。首先，實驗選取具有12列，每列4層，每層30個，共計1 440個倉位的倉庫；其次，選取可以實現多目標點遍歷作業的AGV小車，該小車需要滿足在水平貨道和垂直貨架上運動。為了驗證所提出算法的性能，將其與遺傳算法、基本蟻群算法進行對比實驗，實驗中所設置的目標點數均相同。在本次實驗中，若參數α值過大，則搜索路徑的隨機性會減弱，過小的話會陷入局部最優；β值過大容易選擇局部最短路徑，過小算法收斂速度太低。通過計算分析文中信息啟發因子α和期望啟發因子β的取值，分別取值為1.5和2。初期為了盡快找到最優解，信息素揮發系數ρ取0.1，算法后期根據實際情況對ρ值進行調整。另外，螞蟻個數m取30，最大迭代次數NC_max為100。圖8、圖9分別為50個目標點和25個目標點情況下三種算法的收斂曲線。

圖8 50個目標點收斂曲線

圖9 25個目標點收斂曲線

由圖8、圖9比較可知，優化蟻群算法的迭代計算次數最少，反應時間較短。為了驗證改進后的蟻群算法能夠保證AGV小車在每列貨架位置都能夠正常運行且檢測AGV小車最大化運行時間，故在每一列貨架隨機選取一個目標點。表1所示為隨機生成的12個目標點坐標，其中X軸的取值區間為(1，12)，Y軸的取值區間為(1，30)，Z軸的取值區間為(1，4)。

表1 仿真實驗的隨機生成的目標點

圖10所示為改進后蟻群算法計算出的平均距離和最短距離。可以看出隨著迭代次數的增加，平均距離越來越小，由此表明增加迭代次數對于路徑規劃有一定作用。

圖10 平均路徑和最短路徑

圖11所示為本次實驗中所得到的AGV小車最優路徑軌跡，表2為實驗中目標點的運行順序。圖11中實心圓為最優路徑起始點，空心圓為目標點，菱形為輔助點。由此可知，本文設計的優化蟻群算法在貨架式立體倉庫的AGV小車多目標路徑規劃中有較好的應用效果，算法實現所需要的迭代次數較少，計算速度快，收斂性強，且能獲得最短路徑。

圖11 優化路徑軌跡

表2 仿真實驗目標點運行順序

4 結 語

本文研究了智能倉儲系統中AGV小車多目標路徑規劃，利用蟻群算法將二維平面路徑規劃擴展到三維空間中，并引入禁忌表對基本蟻群算法進行改進，優化AGV小車行駛路徑。通過實驗得出以下結論：(1) 與其他算法相比，本文改進的蟻群算法所需迭代次數少、收斂性強，能夠有效避免算法進入局部最優；(2) 改進后的蟻群算法在智能倉儲系統AGV小車多目標路徑規劃中有較好的應用效果，能獲得最短路徑。