基于改進(jìn)A*算法的倉儲(chǔ)環(huán)境AGV路徑規(guī)劃

牟德君，初鵬祥

（燕山大學(xué) 機(jī)械工程學(xué)院，秦皇島 066004）

國外kiva 倉儲(chǔ)AGV[1]在亞馬遜大規(guī)模成功應(yīng)用之后，國內(nèi)近年也開始建造大型倉庫，并在倉庫中使用AGV 代替人工，實(shí)現(xiàn)“貨到人”揀貨方式[2]。

揀選任務(wù)完成分配后，需要進(jìn)行AGV 的全局路徑規(guī)劃，常見全局路徑規(guī)劃方法有A* 算法[3]、蟻群算法[4]、RRT 算法[5]等，A* 算法具有簡單，計(jì)算量小等優(yōu)點(diǎn)，倉儲(chǔ)環(huán)境中是橫縱方向通道，不受A* 算法規(guī)劃路徑多轉(zhuǎn)折，不夠平滑的缺點(diǎn)影響，所以十分適用[6]。

目前大部分的倉儲(chǔ)AGV 采取的路徑規(guī)劃方法仍是傳統(tǒng)A* 算法或其他簡單算法，而隨著倉儲(chǔ)行業(yè)的集群效應(yīng)，倉庫規(guī)模的擴(kuò)大以及同時(shí)工作的AGV 數(shù)量的增多將會(huì)引起單個(gè)揀選任務(wù)執(zhí)行時(shí)間長，從而導(dǎo)致倉貨滯留[7]，為了提高倉儲(chǔ)環(huán)境的工作吞吐量，需要采用多個(gè)方面的改進(jìn)來提高效率，而其中對路徑規(guī)劃算法的改進(jìn)是很重要的。

針對A* 算法的改進(jìn)方面多種多樣，第1 類是改變評價(jià)函數(shù)：通過改變A* 算法評價(jià)函數(shù)的具體計(jì)算方法，減少尋路時(shí)間[8-9]；改進(jìn)評價(jià)函數(shù)的權(quán)重比例，以此減少生成路徑的冗余點(diǎn)和拐點(diǎn)[10]；在評價(jià)函數(shù)中加入新的系數(shù)，來考慮其他方面的影響[11]。第2 類是算法融合[12]，文獻(xiàn)[13]增加了一個(gè)預(yù)處理的過程，通過跳點(diǎn)搜索算法挑選出一批有代表性的跳點(diǎn)，改進(jìn)算法通過連接跳點(diǎn)，可以實(shí)現(xiàn)較長距離的跳躍；文獻(xiàn)[14]提出一種基于啟發(fā)信息擴(kuò)展節(jié)點(diǎn)的A*算法與混合蟻群算法相結(jié)合的路徑規(guī)劃方法，通過基于啟發(fā)信息的節(jié)點(diǎn)擴(kuò)展函數(shù)，解決A* 算法擴(kuò)展節(jié)點(diǎn)時(shí)，會(huì)造成無用計(jì)算的問題。第3 類是對規(guī)劃的方向進(jìn)行改變[15]，采取更多可選擇角度來提高路徑的平滑度，獲得最優(yōu)解。第4 類是對已規(guī)劃路徑進(jìn)行處理，采用刪除無用節(jié)點(diǎn)的方法[16]或是采用不同處理方式對路徑進(jìn)行優(yōu)化使路徑更平滑[17]。

本文中針對大規(guī)模倉儲(chǔ)環(huán)境中面積大、AGV 數(shù)量眾多而導(dǎo)致長時(shí)間等待甚至死鎖的情況，以總工作時(shí)間最短為目標(biāo)改進(jìn)A* 算法，構(gòu)建時(shí)間評價(jià)函數(shù)；引入轉(zhuǎn)向代價(jià)，減少轉(zhuǎn)向；引入擁堵代價(jià)，避免局部交通量大的路段發(fā)生擁堵甚至死鎖情況；對評價(jià)函數(shù)進(jìn)行自適應(yīng)加權(quán)，使搜索前期可以快速收斂，后期避免陷入局部最優(yōu)，最終提高AGV 揀貨工作效率。

1 地圖建模

本文基于柵格法建立了包含可移動(dòng)式貨架、揀選臺(tái)、移動(dòng)式物流機(jī)器人等硬件設(shè)備的智能倉庫簡化示意模型，如圖1所示，倉庫由4 行6 列的4×8貨架組成，即圖中黑色標(biāo)識(shí)的柵格部分。在貨架之間以及貨架與揀貨臺(tái)之間的通道中同時(shí)穿梭著多個(gè)移動(dòng)機(jī)器人，圖中空白灰色柵格表示可移動(dòng)通道，最左側(cè)方塊代表AGV 的充電處，也是起始位置，最右側(cè)方塊代表揀貨臺(tái)。

圖1 倉庫柵格地圖Fig.1 Warehouse raster map

選擇的貨架布置格式是4×8 格式，內(nèi)外雙層，當(dāng)機(jī)器人需要搬運(yùn)內(nèi)層的貨架時(shí)，需要先將外層的貨架搬開。選擇這種布置方式的優(yōu)勢是可以節(jié)省大量的空間。而在搬運(yùn)外層貨架時(shí)會(huì)阻塞縱向通道，所以選擇雙排的縱向通道，在貨架搬運(yùn)過程中不會(huì)影響對向的機(jī)器人正常運(yùn)動(dòng)。通道是雙向單行道，規(guī)定單向運(yùn)行，運(yùn)行方向和車道相同，采用單向道可以避免正面碰撞。

2 改進(jìn)A*算法

在進(jìn)行全局路徑規(guī)劃時(shí)采用A* 算法，為了實(shí)現(xiàn)總工作時(shí)間最短的目標(biāo)，針對倉儲(chǔ)環(huán)境對傳統(tǒng)算法進(jìn)行一些改進(jìn)，采用曼哈頓距離計(jì)算路徑距離。

2.1 采用時(shí)間代價(jià)

原算法采用距離代價(jià)來表示評價(jià)函數(shù)，不夠直接，為了方便和其他代價(jià)相加時(shí)單位的統(tǒng)一，引入時(shí)間代價(jià)構(gòu)建評價(jià)函數(shù)：

式（1）為A*算法的評價(jià)函數(shù)，v 為AGV 運(yùn)行速度，在正常行駛時(shí)速度恒定；式（2）是構(gòu)建的和時(shí)間代價(jià)相關(guān)的評價(jià)函數(shù)。

2.2 引入轉(zhuǎn)向代價(jià)

在AGV 轉(zhuǎn)向時(shí)需要經(jīng)歷一段減速—停車—加速的過程，引入轉(zhuǎn)向代價(jià)，減少路徑的轉(zhuǎn)向能有效降低工作時(shí)間，節(jié)省能源消耗。

式中：α 為轉(zhuǎn)向時(shí)間系數(shù)；T 為單次轉(zhuǎn)向所需時(shí)間；ct為轉(zhuǎn)向時(shí)間代價(jià)。

2.3 引入擁堵代價(jià)

在某一時(shí)間一片區(qū)域的小車達(dá)到一定數(shù)量后就會(huì)產(chǎn)生擁堵，當(dāng)產(chǎn)生擁堵時(shí)，AGV 需要停車等待或者重新規(guī)劃路徑進(jìn)行繞行，甚至產(chǎn)生死鎖。引入擁堵代價(jià)改善擁堵情況：

式中：load（t）表示該時(shí)間段內(nèi)所有未完成路徑中該節(jié)點(diǎn)的出現(xiàn)次數(shù)；β 為將負(fù)載轉(zhuǎn)換為負(fù)載代價(jià)的轉(zhuǎn)換系數(shù)。

在交通管理方面常用來進(jìn)行交通擁堵判斷的擁堵判斷參數(shù)有交通量、道路交通容量、交通流密度、空間占有率和車輛速度等[18]。其中交通量是在一段時(shí)間內(nèi)經(jīng)過某一截面車輛的數(shù)目。針對建立的倉儲(chǔ)柵格地圖，選擇交通量作為判斷參數(shù)，將交通量定義為在一段時(shí)間內(nèi)經(jīng)過某一可通行柵格AGV 的數(shù)目。如果1 個(gè)AGV 在1 個(gè)柵格上停留，則經(jīng)過1 s則數(shù)目加1，統(tǒng)計(jì)出該柵格60 s 的load（t）。

根據(jù)測試效果將交通擁堵程度分為4 級，如表1所示，在load<10 時(shí)，說明該柵格暢通，不需要附加懲罰，此時(shí)負(fù)載轉(zhuǎn)換系數(shù)β 設(shè)為0；在10≤load<15 時(shí)，該柵格輕度擁堵，此時(shí)在有其它道路具有相同的路徑代價(jià)而擁擠程度更低的情況下，應(yīng)選擇其它的路徑，負(fù)載轉(zhuǎn)換系數(shù)β 設(shè)為0.1；在15≤load<20時(shí)，該柵格擁堵，此時(shí)應(yīng)使AGV 盡量繞開該點(diǎn)，避免進(jìn)一步的擁堵，負(fù)載轉(zhuǎn)換系數(shù)β 設(shè)為0.3；在load≥20 時(shí)，該柵格嚴(yán)重?fù)矶?，此時(shí)如果能找到其它路徑就不要經(jīng)過該柵格，負(fù)載轉(zhuǎn)換系數(shù)β 設(shè)為10。

表1 擁堵程度分級Tab.1 Congestion classification

2.4 加權(quán)歸一化

在搜索前期，希望能快速找到方向，讓h（n）的權(quán)重系數(shù)占比增大。在路徑接近目標(biāo)時(shí)，為避免整個(gè)算法陷入局部最優(yōu)，讓g（n）的權(quán)重系數(shù)占比增大。對評價(jià)函數(shù)進(jìn)行加權(quán)歸一化處理。最終改進(jìn)A*算法的評價(jià)函數(shù)為

式（10）中：（start_x，start_y）為起點(diǎn)坐標(biāo)；（goal_x，goal_y）為終點(diǎn)坐標(biāo)。α 函數(shù)如圖2所示，隨著搜索路徑g（n）增大，x 隨之增大，α 也增大。

圖2 權(quán)重函數(shù)Fig.2 Weighting function

3 仿真驗(yàn)證

采用Matlab2014b 進(jìn)行仿真，驗(yàn)證各個(gè)部分改進(jìn)的有效性和合理性。首先驗(yàn)證引入轉(zhuǎn)向代價(jià)的效果，設(shè)定轉(zhuǎn)向時(shí)間為1 s，轉(zhuǎn)向時(shí)間系數(shù)設(shè)為1.5，為了明顯驗(yàn)證算法改進(jìn)的效果，構(gòu)建30×30 的復(fù)雜柵格地圖，模擬擁堵或存在其他AGV 工作時(shí)的復(fù)雜環(huán)境，在復(fù)雜地圖中規(guī)劃的路徑如圖3所示。

圖3 復(fù)雜地圖中的路徑Fig.3 Paths in complex maps

由圖3（a）可以看出傳統(tǒng)A* 算法在尋找路徑時(shí)共進(jìn)行了12 次轉(zhuǎn)向，由圖3（b）可以看出改進(jìn)的A*算法在尋找路徑時(shí)共進(jìn)行了6 次轉(zhuǎn)向，在路徑代價(jià)相同的情況下，轉(zhuǎn)向的時(shí)間代價(jià)減少了一半。

為驗(yàn)證改進(jìn)算法對不同擁堵的躲避情況，構(gòu)建擁堵負(fù)載地圖，如圖4所示。記錄每個(gè)柵格的load（t）。給圖4中單獨(dú)柵格處設(shè)為1 號柵格，添加load（t）為10，使該處柵格處于輕度擁堵情況。

圖4（a）中為傳統(tǒng)算法規(guī)劃的路徑，采用改進(jìn)算法選擇了另一條同路徑消耗的路徑，避開了負(fù)載更高的1 號柵格。

圖4 導(dǎo)入負(fù)載地圖后的路徑Fig.4 Path after importing the load map

兩個(gè)路段都處于相同擁堵程度時(shí)的路徑如圖5所示，在圖5中對兩個(gè)最短路徑的一部分路段賦予相同的負(fù)載，比較在不同擁堵情況下規(guī)劃的路徑情況。

設(shè)圖5（a）中兩個(gè)單獨(dú)柵格為負(fù)載柵格，都添加負(fù)載load（t）為20，使柵格處于重度擁堵情況，采用改進(jìn)算法規(guī)劃的路徑選擇了繞遠(yuǎn)路徑而避開擁堵區(qū)域；在圖5（b）中兩負(fù)載柵格都添加負(fù)載load（t）為15，使該處兩柵格處于相同擁堵情況，采用改進(jìn)算法規(guī)劃的路徑和傳統(tǒng)算法相同，不會(huì)導(dǎo)致路徑非最優(yōu)。

圖5 兩個(gè)路段都處于相同擁堵程度時(shí)的路徑Fig.5 Path when both sections are at same level of congestion

對比算法改進(jìn)前后規(guī)劃相同路徑所需要的時(shí)間，共選擇8 組路徑，起點(diǎn)和目標(biāo)點(diǎn)用該柵格點(diǎn)編號表示，驗(yàn)證系數(shù)加權(quán)歸一的效果如表2所示。

表2 A*算法和改進(jìn)A*算法路徑規(guī)劃用時(shí)Tab.2 A* algorithm and improved A* algorithm path planning time

由表2可以得出，在路徑較長時(shí)，改進(jìn)算法規(guī)劃時(shí)間要短于傳統(tǒng)算法，由于規(guī)劃用時(shí)較長，改進(jìn)算法節(jié)省的時(shí)間也很多，在路徑較短時(shí)，改進(jìn)算法規(guī)劃時(shí)間略長于傳統(tǒng)算法，但差距不大。因?yàn)閭}儲(chǔ)環(huán)境很大，揀貨任務(wù)中也需要規(guī)劃從貨架到揀選站臺(tái)的往返長距離路徑，所以改進(jìn)后算法更適用于建立的環(huán)境模型。

4 結(jié)語

針對倉儲(chǔ)環(huán)境中的多AGV 進(jìn)行路徑規(guī)劃，對傳統(tǒng)的A* 算法進(jìn)行改進(jìn)，首先為了滿足總體的工作時(shí)間最短的目標(biāo)以及同其他的引入代價(jià)具有相同的單位，采用時(shí)間代價(jià)代替路徑距離代價(jià)構(gòu)建目標(biāo)函數(shù)；為了減少路徑的轉(zhuǎn)向，引入轉(zhuǎn)向代價(jià)，減少路徑代價(jià)相同時(shí)轉(zhuǎn)向消耗；其次考慮局部地區(qū)交通網(wǎng)擁堵帶來的長時(shí)間等待以及死鎖情況，引入擁堵代價(jià)，選擇其他路徑躲避擁堵路段；最后引入加權(quán)系數(shù)，加快前期搜索速度，而在搜索后期減慢搜索速度，避免局部最優(yōu)。