電商倉庫揀貨機器人路徑規劃與實現

（浙江萬里學院，浙江 寧波 315100）

1 引言

隨著電子商務行業的迅速發展，網絡購物成為一種潮流，很大一部分人熱衷于通過網絡購買需要的東西。在這樣的發展趨勢下，人們對物流服務也越來越重視，而運轉效率就是物流服務的一個重要指標。對于普通客戶來講，速度是評價服務的重要標準之一。

倉庫作為貨物運轉的節點，對貨物運轉有著至關重要的影響。現如今大多數的倉庫自動化水平還比較低，訂單的揀選基本依靠勞動力完成，這樣一來效率低，二來錯誤率高，用戶體驗較差。并且現今人力成本上升，傳統的工作方式早已不能滿足社會需求[1]。

為解決這樣的窘境，各大運營商紛紛在機器人方面加大投入研發，比較典型的如亞馬遜的Kiva機器人、阿里巴巴的“曹操”機器人、京東的六軸機械臂等，目前已有部分倉庫將機器人運用到現實的作業中。在電商倉庫配送中心的搬運成本中，揀貨的搬運成本約占90%，與揀貨直接相關的人力占50%。揀貨時間約占整個配送中心操作時間的30%-40%。在配送過程中，揀貨是整個配送中心操作系統的核心，合理規劃與管理揀貨過程，對配送中心工作效率的提高具有決定性的影響。

本文就提高電商倉庫配送中心工作效率提出揀貨機器人路徑優化方法，就路徑優化中的最短路徑及多機器人之間的避障進行研究并建模得出結果。

2 方案設計

2.1 地圖設計

合理的倉庫地圖設計有利于倉庫存儲物資的合理安排，能夠降低倉庫工作人員的工作量，減少不必要的重復勞動。倉庫路徑、貨架的合理布局有利于通道的暢通，確保倉庫工作人員和機器人的通行安全。地圖的設計應根據貨物種類、障礙物位置、倉庫規模等因素做一些合理的規劃。

圖文件使用Tiled Map輔助繪制，實驗根據貨架位置及障礙物位置做一個簡單的路徑設計，具體倉庫地圖結構如圖1所示，其中包括貨架位置、障礙物、路徑以及路徑的交叉點。為方便機器人與服務器的信息溝通，每個交叉點處會設置二維碼以表示該交叉點在地圖上的坐標位置，由于交叉點為一個正方形，這里以正方形左上角位置為交叉點坐標并設置相應序號。圖文件完成同時生成tmx文件，JAVA語言讀取文件生成有效信息。這里的有效信息主要是路徑和路徑交叉點的相關描述，包括序號、長度、坐標等[2]。如：

以上是交叉點描述信息以及交叉點信息的二維碼描述方式，其中id表示的信息包含該點的所在圖層、序號及其坐標。二維碼信息表示該點坐標。

圖1 倉庫圖

以上是路徑描述信息，id表示該路徑起點與終點坐標，point表示起點與終點信息。

下面根據路徑與交叉點的關系生成矩陣，矩陣的行和列分別為兩個點的序號。當圖中兩點可通過某條路徑相連接，則在矩陣相對應的位置輸出1，不能連接的輸出0。這樣最后輸出一個m×m的矩陣，矩陣可直觀的表示出圖信息。第二個矩陣與第一個矩陣類似，兩點不能連接的輸出0，可通過某條路徑連接的輸出該路徑的長度。至此地圖信息對應的矩陣初步形成。

機器人每到一個節點掃描到二維碼信息，同時向服務器發送實時位置，服務器根據此信息確定機器人接下來的路徑同時向機器人發送行動指令。為避免多機器人路徑沖突，當機器人向服務器發送定點位置時，將下一步運行的路徑置∞，即斷開該路徑，這樣避免同時工作的機器人路過此路徑，實現多機器人之間的避障。

2.2 數據庫設計

常見的數據庫類型有Oracle、SQL Server、MySQL等。綜合數據容量、價格以及操作難易程度等因素，本次實驗選擇了MySQL數據庫。

JSP通過Connection接口訪問數據庫，java.sql.Satatement接口用來執行靜態的SQL語句，java.sql.PreparedSatatement接口執行動態的SQL語句。

實驗中數據庫新建兩個表。表1存儲各類商品的揀貨點等信息。當訂單產生時得到一個訂單中所有商品的名稱，服務器根據商品名稱從數據庫獲得對應取貨點，將這些取貨點加入到一個工作進程中，并發布給機器人開始工作。表2存儲機器人序號、機器人所在位置的坐標以及該坐標對應交叉點的序號。當機器人運行到某交叉點掃描到二維碼，將自身序號以及二維碼包含的信息輸入到數據庫，當二維碼顯示的點序號與取貨點的序號一致，則機器人執行取貨行為。

2.3 算法設計

求最短路徑的算法有很多，常用的方法有人工勢場法[3]、A*算法[4]等，都是針對簡單的點到點的路徑規劃任務。本次設計選用Dijkstra算法與最鄰近算法相結合，以整體時間最優為目標。

Dijkstra算法首先是得到起點V0到其他各頂點距離，V0-＞V0的權值為0，當 V0與Vi可連接，其權值為V0-＞Vi的長度，當 V0與 Vi不可連接，V0-＞Vi權值為∞，這樣可得到一個描繪路徑權值的矩陣。Dijkstra算法適合運用于求解單源最短路徑的問題，可得到到其他各頂點的最短路徑，而訂單需求的節點可能是多個，所以單純使用Dijkstra算法不能滿足需求[5]。最鄰近算法，即優先選擇前往與當前所在點最接近的點，然后以該點為起點前往下一個點，最后得到一個最接近于最短路徑的答案。

針對電商倉庫的特點，單個機器人無法滿足工作的需求，所以還有一個重點問題，多機器人同時工作時要如何分配才能不發生沖突。本文采取的避障方式有兩種：一種是當某條路徑正在被占用時，更改其對應權值為∞，下一個訂單對應的路徑規劃就會避開這兩條路徑，直至被占用路徑任務完成，釋放被占用路徑，更改權值為原來的長度數值。第二種是等待，當路徑被占用，下一個需要經過該路徑的機器人可選擇等待，等前一個機器人離開本路徑后再進入該路徑。如有多個機器人同時等待同一個路徑，以訂單產生時間設置優先級，先產生的訂單優先級較高。當沖突發生時，通過預估前一個任務完成釋放路徑的時間及下一個任務的等待時間，計算繞行耗費時間即繞行比原路徑多花的時間，并對等待時間與繞行時間進行比較，選擇時間較短的方式。

整個運行過程為：首先服務器獲得需要揀取的商品名稱，然后從數據庫獲取各商品對應揀貨點，即需要到達的各頂點，將各頂點帶入算法中得到經過多點的最短路徑，到此一個訂單的初步路徑規劃工作完成。運行過程中，如規劃的某條路徑正在被占用，則重新規劃接下來的路徑，不斷更新，確保不會產生碰撞或者堵塞。

3 功能實現

首先讀取地圖信息，生成矩陣。然后將矩陣帶入算法，同時輸入任務點，獲得多點之間的最短路徑。最后向機器人發送任務要求，機器人執行任務過程中經過交叉點時讀取對應二維碼信息，與服務器的信息交互，實現避障，即多個任務同時進行，路徑之間無交叉點。

本文的地圖文件是針對電商倉庫設計的。目的在于確定機器人位置與離揀貨貨架最近的路徑上的點，得到機器人到揀貨點最短線路的計算。確定了倉庫中的多個點后，根據倉庫地圖描述文件計算多點之間的最短線路，并能夠實現避障，機器人之間不會碰撞且不會導致道路堵塞。任務起點為機器人休息區或者存放點，終點為訂單打包區，這個根據需求進行設計，存入地圖信息。其它節點根據訂單所需貨物，通過數據庫信息獲取貨物所在貨架信息。根據多點信息及描述文件計算最短線路的步驟如下：

（1）確定起點、取貨點及倉庫地圖描述文件。

（2）定義圖的鄰接矩陣、圖的點集合以及路徑集合。

（3）解析倉庫描述文件，初始化圖的點集和邊集。

（4）根據訂單確定訪問點，帶入算法得到最短路徑。

（5）服務器向機器人發送指令，機器人路過頂點掃描到二維碼，向服務器發送實時位置。

（6）服務器根據機器人實時位置信息實時更新道路實現避障，在某條路徑被訪問時，下一個任務避開該路徑，以及規劃下一條路徑，找到另一條最短路徑。

4 實驗結果

實驗初步設置兩個任務實現避障。即實現圖1中點到點之間的最短路徑的獲取，當兩個任務同時進行時，后一個任務不會同時與前一個任務在同一路徑重合，避免碰撞的情況發生。

實驗過程首先根據Tiled Map獲得的描述文件，使用MyEclipse軟件讀取描述文件信息獲得路徑及交叉點關系的矩陣。然后使用軟件進行仿真，將矩陣帶入得到帶權圖（Graph）[6]。最后輸入任務，通過Dijkstra算法獲得最短路徑，經過對算法的改進實現避障。

任務一，2-＞50,任務二，2-＞49。獨自運行時，實驗得出結果，任務一生成路徑如圖2所示，經過節點2、9、50，由于有1個轉彎，這里設置速度，一個單位長度需1s，轉彎需多增加2s，總任務時間為90s。任務二生成路徑如圖3所示，經過節點2、9、49，也有1個轉彎，總任務時間為90s。同時運行時，由于任務一優先級高，路徑不發生改變，任務二為了避免與任務一產生沖突，可選擇繞行或者等待。這里可以預估任務一到達節點9的時間，2-＞9距離56，則需要56s，所以預估56s到達節點9，即任務二需等待56s。如果繞行經過的路徑節點修改為2、45、1、8、49，有2個轉彎，總任務時間變為156s，比之前規劃多了66s。相較于繞行，等待反而快了10s，所以這里選擇了等待，生成路徑如圖4所示，這樣的規劃避免了兩個機器人工作途中碰撞的可能性。

從實驗結果可直觀的看到最短路徑，多個任務時會避免碰撞或者擁堵。

圖2 任務一路徑

圖3 任務二路徑

圖4 任務一、二同時執行時路徑

5 結語

本文實現了對訂單路徑規劃的方案制定，規劃了整個流程，并模擬完成了過程中最短路徑的獲取及機器人之間的避障。但是對路徑規劃算法的優化還不夠完善，還有其他約束條件以及可能產生碰撞的情況沒有考慮完全，后期還需考慮，以達到更加高效、實時、準確的實現路徑規劃及避障。并且本文實現的僅僅是路徑方面的優化避障，并未涉及機器人設計，后期會涉及到機器人主芯片的設計，初步考慮使用Android系統的嵌入式電路板實現機器人與服務器信息交流。至于機器人取貨等行為有待進一步開發設計。

相信隨著電商行業的不斷發展，電商倉庫工作量會越來越大，如何簡化工作流程，節約工作時間愈加變成一個重點問題，未來機器人的使用也會越來越普及。