基于改進A*算法的倉儲環境AGV路徑規劃

牟德君，初鵬祥

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

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

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

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

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

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

1 地圖建模

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

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

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

2 改進A*算法

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

2.1 采用時間代價

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

式（1）為A*算法的評價函數，v 為AGV 運行速度，在正常行駛時速度恒定；式（2）是構建的和時間代價相關的評價函數。

2.2 引入轉向代價

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

式中：α 為轉向時間系數；T 為單次轉向所需時間；ct為轉向時間代價。

2.3 引入擁堵代價

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

式中：load（t）表示該時間段內所有未完成路徑中該節點的出現次數；β 為將負載轉換為負載代價的轉換系數。

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

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

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

2.4 加權歸一化

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

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

圖2 權重函數Fig.2 Weighting function

3 仿真驗證

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

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

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

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

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

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

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

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

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

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

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

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

4 結語

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