一種基于改進(jìn)蟻群算法的AGV小車三維路徑規(guī)劃研究

金 鑫 鑫

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

0 引 言

智能倉儲系統(tǒng)是指以信息化手段實現(xiàn)對倉庫的實時監(jiān)視和全面管理的信息系統(tǒng)，該系統(tǒng)能夠?qū)崟r掌握倉庫容量、了解貨物所存放位置、實現(xiàn)自主貨物轉(zhuǎn)移等[1-2]。在智能倉儲系統(tǒng)中，貨物轉(zhuǎn)移快慢直接關(guān)系到其管理效率，通常執(zhí)行貨物轉(zhuǎn)移作業(yè)的設(shè)備主要為AGV小車，如果要提高貨物轉(zhuǎn)移的速度，就需要對AGV小車的行駛路徑進(jìn)行規(guī)劃[3]。

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

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

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

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

1 三維空間路徑優(yōu)化問題建模

1.1 立體倉庫模型構(gòu)建

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

圖1 立體倉庫貨架實物圖

圖2 立體倉庫模型

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

圖3 實驗AGV小車

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

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

1.2 運(yùn)行軌跡模型構(gòu)建

在立體倉庫模型中，AGV小車的運(yùn)動主要包括水平和垂直兩個方向，其中水平方向主要由小車驅(qū)動系統(tǒng)自主運(yùn)行，垂直方向運(yùn)動主要借助升降機(jī)來實現(xiàn)。假設(shè)小車為勻速運(yùn)行，考慮其在啟動及停止時的速度影響，取速度和時間均值，因此不會對路徑優(yōu)化產(chǎn)生影響。

為了便于對AGV小車路徑進(jìn)行規(guī)劃，本文對AGV小車的運(yùn)動軌跡進(jìn)行分類，主要包括：

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

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

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

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

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

(1)

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

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

(2)

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

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

(3)

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

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

(4)

2 改進(jìn)蟻群算法三維路徑優(yōu)化

2.1 蟻群算法理論

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

(5)

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

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

(6)

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

2.2 改進(jìn)蟻群算法三維路徑優(yōu)化方法

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

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

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

圖4 增加輔助點數(shù)量的部分MATLAB代碼

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

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

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

(7)

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

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

步驟3將k值與m值進(jìn)行比較，若k≥m，則說明k螞蟻已經(jīng)走完了所有目標(biāo)點，此時進(jìn)入步驟4，否則轉(zhuǎn)入步驟2。

步驟4對全局中的信息素、信息素?fù)]發(fā)系數(shù)、信息素增強(qiáng)系數(shù)進(jìn)行更新，信息素的更新如式(8)所示。

(8)

圖6 更新信息素部分代碼

步驟5禁忌表清零。在達(dá)到最大迭代次數(shù)之后，將禁忌表清零，對每次迭代中所獲得的最短路徑進(jìn)行比較，并最終得到最短路徑和所有目標(biāo)點的行進(jìn)順序，并輸出最優(yōu)路徑結(jié)果。

圖7所示為改進(jìn)蟻群算法實現(xiàn)流程。

圖7 改進(jìn)蟻群算法實現(xiàn)流程

3 實驗結(jié)果與討論

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

圖8 50個目標(biāo)點收斂曲線

圖9 25個目標(biāo)點收斂曲線

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

表1 仿真實驗的隨機(jī)生成的目標(biāo)點

圖10所示為改進(jìn)后蟻群算法計算出的平均距離和最短距離?？梢钥闯鲭S著迭代次數(shù)的增加，平均距離越來越小，由此表明增加迭代次數(shù)對于路徑規(guī)劃有一定作用。

圖10 平均路徑和最短路徑

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

圖11 優(yōu)化路徑軌跡

表2 仿真實驗?zāi)繕?biāo)點運(yùn)行順序

4 結(jié) 語

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