物流機器人路徑規劃仿真研究

文 / 龔志鋒 石 超 閆 豐 陳建銀

隨著電子商務高速發展，對倉儲物流的效率要求越來越高，隨之而來的便是以倉儲物流機器人（AGV）為代表的自動化浪潮，智能倉儲的概念也應運而生，以在提高倉儲揀選效率的同時，應對不斷上漲的勞動力成本。目前，揀選作業是庫內最主要的環節，至少占據50%的庫內操作成本，決定著客戶的服務體驗水平，因此如何利用物流機器人進一步提升揀選作業效率，對倉儲物流具有重要意義；而高效的路徑規劃算法，正是決定物流機器人作業效率的關鍵因素，是物流機器人能夠流暢運行的核心之一。

一、研究背景

A＊算法是一種常用的啟發式路徑查找和圖形遍歷算法，其改進自Dijkstra算法，擁有較好的性能與準確度。但是對于AGV而言，最短路徑往往并不是最合理的路線，其路線具有更多的影響因素：

1. AGV與機動車一樣，一般只能夠向前行走，轉向需要花費額外的時間，因此路線應盡可能減少轉向次數。

2. 多輛AGV同時運行時，其互相之間路線會出現相交與沖突，規劃路徑時應盡可能避免路線沖突。

3. 當AGV不可避免的出現擁堵時，能夠根據當前路況重新規劃一條新的路線。

針對以上影響因素，本次研究遵循A＊算法的基本方法，對A＊算法中的的F值計算進行更加深入的探索，使其計算方法更加合理，能夠更好地契合AGV的路線規劃需要。

二、算法思路

本文最終將算法通過仿真程序實現，考慮到影響AGV行走的各項因素，具體會從A＊算法的F值計算與任務管理兩方面著手，二者配合以實現AGV的流暢運行。

1. 代價值計算優化

為了使邏輯思路更加清晰，本文使用結構體來表示每一個節點。

（1）轉向代價

原A＊算法中計算F值時，由移動代價與估算成本相加得到，當有多條最短路徑時，其只會隨機返回一條最短路徑，并沒有考慮路徑的拐彎因素，而現實情況是，AGV需要停止后才能進行原地旋轉，會花費額外的時間。對此，本文在計算中加入反映AGV旋轉的轉向代價，使得到的結果更加偏向于直線行走。

原F值計算公式為：

式中：

F，當前節點的總代價；

G，從起點移動到當前節點的移動代價；

H，當前節點到終點的估算成本，

本文采用曼哈頓距離。

在公式中加入新的變量R，代表AGV的轉向代價。如圖1所示，共有3條路線，分別為ADE、BDE、CDE，當前研究節點為E，其父節點為D，其中2條路線將會發生旋轉，因此對于節點E，關鍵在于判斷從D到E是否會發生旋轉。

圖1 轉向情況

從圖1中可以發現，ADE、CDE這兩種情況下需要進行旋轉，BDE不需要旋轉，而A、C這兩個節點與E節點的橫縱坐標完全不同，B節點與E節點的橫坐標相同，由此可以做出推斷，一旦當前節點與父節點的父節點坐標完全不一致，則由父節點到達當前節點就需要進行轉向，否則不需要且R為0，

因此，新的F值計算公式為：

增加的R，便是轉向代價。

（2）路徑沖突代價

由于實際生產情況下，通常都會是幾十臺AGV同時運行，若仍然給每臺AGV獨立規劃路徑，則必定會出現不同AGV的路徑相互干擾甚至沖突的狀況，因此需要在為每臺AGV進行規劃路徑時，考慮已規劃路徑AGV的影響，引入路徑沖突代價D，從而將所有AGV間的相互干擾降至最小。

為了能夠更好地判斷各條路徑間的關系，需要構建一張公共地圖，在地圖的每個節點上存儲當前節點的信息與每條路徑對該節點的占用情況，以供AGV規劃路徑時進行查詢。

判斷是否會在當前節點產生沖突時，首先查詢當前的地圖節點，讀取當前地圖節點所有AGV的占用信息，然后和當前規劃路徑進行比對，若產生沖突則賦予沖突代價D一個較大的值，否則D為0。進行判斷時，首先計算當前規劃路徑對該地圖節點的占用時間區間是否與已規劃路徑的占用時間區間相交，若時間發生沖突，則進一步判斷兩條路徑的方向是否相向，若相向，則認為路徑沖突。

如圖2所示，中央的格子為當前計算的地圖節點，O為已規劃路徑離開當前地圖節點的方向，A、B、C、D為當前規劃路徑移動至當前地圖節點的可能方向，其中A、C、D方向的情況下，AGV只需等待一小段時間，等前面的車輛離開便可以成功移動，而B方向與已規劃路徑的離開方向是相向的，可以認為B方向與已規劃路徑存在沖突。

圖2 路徑沖突

此外，每當路徑規劃完畢，便會返回一個終點的路徑節點，此時需要根據新路徑的信息對地圖節點進行更新，以用于后續新路徑的規劃。

最終，總代價的計算更新為：

增加的D，便是路徑沖突代價。

2. 任務管理優化

仿真程序主要由AGV模塊與任務管理模塊構成，通過定時器觸發各主要對象的更新，AGV模塊與任務管理模塊通過Qt的信號與槽機制進行交互。

路徑規劃并不能做到萬無一失，當現場道路狹窄而AGV數量比較多的時候，發生擁堵的概率仍然會比較高，因此在合理的時機命令被堵住的AGV重新規劃線路是十分有必要的。

圖3 AGV單次任務循環

表1 AGV任務單次循環

（1）AGV模塊

AGV僅有兩種狀態，空閑與任務，空閑時在原地等待，有任務時行走。

如圖3所示，通過定時器觸發AGV自身的任務循環，同時需要不斷更新AGV對地圖的實際占用情況以更好地規劃路徑。AGV若有任務在身時，便會首先對下一個目標位置進行碰撞檢測，若移動至下一節點會發生碰撞則停在原地并發出碰撞信號，任務管理接收信號后便會進行碰撞計數，若連續碰撞多次，則會觸發重新規劃路線，否則就移動至下一節點并釋放上一節點，若AGV處于空閑狀態則要發出信號占據當前停留節點。在這一循環中共有3種信號，對應到任務管理模塊中便有3個槽進行接收和處理。偽代碼如表1所示，可以看出AGV發出的信號都需要任務管理進行處理。

圖4 任務管理模塊單次循環

圖5 輸入模塊與訂單輸入信息

同時，AGV需要2個槽用于接收任務管理模塊發送的信號，其具體功能為：

槽4，用于處理信號4，此時任務管理模塊發布了新的任務坐標與路徑，AGV需要進行接收并更改自身的目標與路徑，并將AGV狀態更改為任務狀態。

槽5，用于處理信號5，此時AGV經過了連續多次碰撞檢測發現無法繼續前進，需要接收來自任務管理模塊新規劃的路徑，并按照新路徑的指引繼續前進。

（2）任務管理模塊

任務管理模塊同樣擁有自身的任務循環，由定時器觸發，同時帶有4個用于處理AGV信號的槽。其中，任務管理模塊的循環主要邏輯為：遍歷所有AGV，對其中處于空閑狀態的設備發布新的任務，調用A＊算法算出路徑后，將路徑通過信號4發送給對應的AGV，具體流程，如圖4所示。

任務管理模塊用于處理AGV信號的3個槽的具體功能為：

槽1，用于處理信號1，此時AGV處于空閑狀態并停留在了原地，此時任務管理模塊需要將地圖節點中對應節點的agvOccupied屬性更改為true，如此在規劃路徑時便會避開此節點。

圖6 動畫模塊

槽2，用于處理信號2，此時AGV按照路徑前往下一節點，因此需要保證AGV即將離開的節點的agvOccupied屬性為false，同時將對應AGV的碰撞檢測計數清零。

槽3，用于處理信號3，此時AGV經過碰撞檢測認為移動至下一個節點會發生碰撞，任務管理模塊會進行碰撞計數，若計數達到一定次數，則會觸發重新規劃路線，并通過信號5將新的路徑發送給指定AGV。

在AGV與任務管理模塊的循環、信號、槽的相互配合下，便可以實現較為合理的AGV路線重規劃，從而降低堵塞概率。

三、仿真實現

為了驗證路徑規劃算法的可行性，本文在Qt Creator中采用C++編程語言建立一個可視化仿真系統，用于模擬在倉儲物流中物流機器人的批量路徑規劃。

圖7 規劃結果

1. 仿真系統介紹

仿真系統主要由輸入模塊與動畫模塊構成，輸入模塊負責接收用戶的參數，動畫模塊負責將仿真結果實時演示給用戶。

（1）輸入模塊

如圖5所示，在輸入模塊中，用戶可以使用Excel軟件定制倉位信息與訂單信息，仿真程序便可以讀取Excel文件，仿真開始后程序可以根據用戶的倉位與訂單給AGV下達揀貨任務。同時，在輸入模塊中，用戶可以自定義AGV與揀貨人員的數量從而在觀察路徑規劃算法有效性的同時得到不同人機配比下的揀貨效率。

（2）動畫模塊

如圖6所示，動畫模塊負責將仿真結果實時輸出到畫面上，讓用戶能夠更直觀地了解仿真的情況，觀察哪邊容易發生擁堵。同時，仿真的地圖可以根據需要進行修改，對應的，倉位信息同樣需要同步修改。

2. 有效性驗證

最后通過人為制定具體的AGV點對點任務以驗證算法的有效性，如圖7所示，有4個點對點任務，分別指派給4臺AGV，任務具體為：A1-A2、B1-B2、C1-C2、D1-D2。

將任務導入程序后觀察AGV的實際行動路線。如圖7所示，AGV的行動路線基本符合算法的思路，在預計會產生沖突時，采用了繞行的路線。

此外，通過生成較多數量的AGV并派發相對重復的訂單，還原AGV產生擁堵的情況，經過測試可以發現，當AGV在原地擁堵超過一定時間后，其便會掉頭沿著新的路線繼續行走，如圖8所示，中間最下方的AGV的目的地為當前巷道的上方，由于前方發生了擁堵，因此其掉頭尋找新的路線，說明任務管理模塊發揮了作用。

圖8 自動規劃新路線

四、結論

本文在A＊算法的基礎上對物流機器人的揀選路徑進行了系統性研究，針對現場實際出現的問題提出了對應的解決方案，并利用C++編寫仿真系統對解決方案進行了有效性驗證，最終得到如下結論：

1.構建公共的地圖占用信息，有助于更加合理地進行AGV路徑規劃。經過本文的探索可以發現，AGV在預測路況的條件下可以有效避免路徑沖突的發生。

2.在A＊算法中加入轉彎代價，可以有效避免AGV在規劃路徑時因隨機性導致轉彎過多的情況。

3.合理的任務管理機制，可以有效疏通堵塞情況，本文采用了相對較為簡單的次數觸發機制，配合地圖信息的實時更新，使AGV在狹小通道相互妨礙而停滯時能夠自動繞路。