牟德君，初鵬祥

（燕山大學 機械工程學院，秦皇島 066004）

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

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

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

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

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

1 地圖建模

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

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

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

2 改進A*算法

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

2.1 采用時間代價

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

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

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

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

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

2.3 引入擁堵代價

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

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

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

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

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

2.4 加權(quán)歸一化

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

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

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

3 仿真驗證

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

圖3 復雜地圖中的路徑Fig.3 Paths in complex maps

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

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

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

圖4 導入負載地圖后的路徑Fig.4 Path after importing the load map

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

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

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

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

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

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

4 結(jié)語

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