智能倉儲中基于A*算法的多AGV路徑規劃研究

(北京物資學院 北京 100000)

一、引言

AGV作為智能倉儲揀選的主要工具已得到廣泛使用，它的使用帶來如節約勞動成本、提高揀選準確率等優點。路徑規劃是AGV領域的熱點問題，是為AGV在包含障礙物的空間中規劃出一條從起點到目標點的最優路徑。

近幾年多AGV路徑規劃問題近開始得到人們關注，如劉國棟[1]提出一種兩階段動態路徑規劃策略，先應用k最短路徑法生成離線路徑集，再綜合阻塞系數，進行分階段路徑規劃。晁永生[2]等提出動態修改路徑的兩階段協調方法，實現多機器人無碰撞運動。張丹露[3]提出基于交通規則、預約表和動態加權地圖的方式完成多機器人路徑規劃。針對多AGV路徑規劃方法和策略雖多，但其在智能倉儲領域的應用中遠沒有形成一套系統的理論和方法，還處于不斷發展和完善中，目前存在的問題是：

(1)實時性問題。由于環境的復雜性加之機器人受傳感器性能影響，無法進行在線實時全局規劃，這是研究難點；

(2)機器人間避碰問題。多機器人系統中，每臺機器人要同時顧及與其它機器人間、障礙物間的碰撞,如何預測機器人行走動向尋找機器人間無碰撞路徑是研究的熱點；

(3)避障協調規則問題。多機器人在確定沖突將要發生后，對于沖突點怎么合理解決是研究重點。

針對以上問題，在對智能倉儲中多機器人路徑規劃過程中，本文主要對路徑的避碰問題和協調規則進行研究。

二、算法設計

本文采用A*算法，主要原因如下：A*算法具有較小的時間復雜度、空間復雜度，能在短時間內獲得最優路徑；A*算法作為啟發式算法具有較強的適應能力。

A*算法的核心思想體現在綜合考慮起始點到當前點的真實代價和當前節點到目標點的估計代價，核心部分為評價函數，表達式為：f(n)=g(n)+h(n)

我們采用曼哈頓距離進行距離的估算，這樣才能更接近移動機器人行走的實際路程。由于倉儲物流機器人進行轉向的時間耗費和能量耗費不同，因此在h(n)中加入轉向代價，因此啟發式函數的表達式為：h’(n)=h(n)+ε

我們先通過A*算法對多個AGV規劃出各自的最優臨時路線，這些路線可能導致多個AGV可能會同時經過一個路口，在這種情況下，可以根據柵格地圖和時間窗來確定將會發生哪種沖突類型，然后采用避障協調策略解決沖突。

在本文中將采取兩種避障協調策略，等待策略和重新規劃路線策略。對于相向相遇沖突可以通過對低優先級任務將沖突柵格對應的代價值設置為∞，再重新規劃來解決；對于垂直相遇沖突通過預估低優先級任務繞行耗費時間和等待時間，并對二者進行比較，選擇時間較短的方式。對于死鎖狀況，可以根據優先級的高低按照前面方式逐一進行規劃。AGV本身有自己的優先級設定，負載的AGV優先級高于空載AGV,負載狀態下前往貨架位置的AGV優先級高于前往揀選臺的優先級。

三、功能實現

本文針對電商倉庫設計柵格地圖，目的在于確定機器人位置與目標貨架最短的路徑上的點，得到AGV最短線路的計算。本文最終構建28*30柵格地圖，每臺AGV在地圖中占據一個柵格大小。目標貨架位置根據訂單貨物所在的貨架確定，通過柵格節點信息獲取貨物所在貨架信息，具體實現最短線路的步驟如下：

(1)確定地圖位置節點，包括起始點、取貨點、卸貨點；

(2)根據貨物訂單確定目標貨架，利用求解算法得到最短路徑；

(3)利用時間窗對路徑進行沖突檢查，如沖突發生采用避障策略解決沖突；

(4)對新路徑進行時間窗檢查，如果發現沖突繼續激活避障策略，如果無沖突則找到最優路徑，尋路結束。

四、實驗結果

為方便直觀的用本文方法研究機器人路徑規劃問題，現對機器人一系列操作做以下假設：

(1)機器人直行路過一個柵格花費1秒；轉彎花費2秒，等待時間為3秒；

(2)AGV負載和未負載狀態下運行速度相同且保持不變。

實驗初步設置兩個任務實現避障。圖1中路線①為揀選臺到目標貨架的初始路線，路線②為目標貨架到揀選臺的初始路徑。經過時間窗檢測后發現兩條路線在路徑重合點處發生沖突，根據本文提出的算法由于貨架到揀選臺的優先級相對較低，所以對路徑②來說，將重疊時間窗內沖突節點設置為在該時間段內不可通過節點，比較等待代價和重新規劃路徑代價，最終路徑結果如圖2所示。經過檢測后路徑①和路徑②沒有時間窗重疊，所以為最終最優路徑。

圖1 初始路徑規劃 圖2 本文算法路徑規劃

五、結束語

本文通過A*算法對訂單任務進行路徑規劃，并模擬訂單揀選過程完成最短路徑的獲取及機器人之間的避障。但是文中對可能產生的碰撞問題沒有完全考慮，并且文中采取的算法的實時性不足，這些都是以后要研究的重點。本文實現的僅僅是路徑方面的優化避障，并未涉及機器人間信息交流方式。相信隨著智能倉庫中AGV的數量越來越多工作量會越來越大，如何優化工作流程，設計出合理路徑，進而節約工作時間愈加變成一個重點問題。