智能倉儲機器人動態路徑規劃研究

李金釗 張世宣 周小鈴 鄭瀟玥 胡宗政 張勇

摘? 要：為解決智能倉儲系統中多機器人協同控制問題，提出一種基于預約表障礙地圖的改進A*路徑規劃算法。首先利用預約表生成障礙地圖并對機器人進行避障處理;然后給出一種改進A*算法基于障礙地圖預約表更新倉儲系統中機器人實時位置并實現動態路徑規劃;最后，基于NImyRIO機器人平臺對所提算法進行了實驗仿真分析，結果表明所提算法具備一定的可靠性并可提高倉儲系統的運行效率。

關鍵詞：智能倉儲系統;多機器人系統;路徑規劃

中圖分類號：TP242.6? ? ?文獻標識碼：A

Abstract： In order to solve the problem of coordinately controlling multi robots in intelligent storage system， an improved A * path planning algorithm is proposed based on the obstacle map. First， the reservation table is used to generate the obstacle map， which helps the robots to avoid the obstacles. Then， an improved A * algorithm is proposed to update the real-time position of robot in storage system based on the reservation table of the obstacle map and realize the dynamic path planning. Finally， based on Ni myRIO system， the simulation results show that the algorithm is reliable and can improve the efficiency of the storage system.

Keywords： intelligent storage system; multi robot system; path planning

1? ?引言（Introduction）

隨著物流倉儲業的不斷發展，由智能機器人所構成的智能化的物流倉儲系統成為現代物流產業不可或缺的重要組成部分[1]。目前智能倉儲機器人最新研究主要集中于路徑規劃及多機器人協作等多個方面，在現代倉儲物流系統中，多機器人協同運作可極大提高效率，而多機器人動態路徑規劃是實現多機器人協同前提[2]。關于多機器人的路徑規劃問題研究由來已久，其主要目標是實現[3，4]：（1）從出發點出發到達預定的目標點;（2）獲取無碰撞的安全路徑;（3）選取距離最優或者次優路徑[5]。路徑規劃本質上是依據代價最小、路線最短或行走時間最短等優化準則，在工作空間中找一條從起點到目標狀態的能避開障礙的最優路徑。蟻群算法[6]、D*算法[7]作為智能算法可實現多機器人的動態路徑規劃，但這兩種算法無法得到全局最優路徑，難以滿足倉儲系統運行效率。A*算法[8]是一種常見的全局最優路徑規劃算法，但傳統A*算法作為一種靜態路徑規劃算法，難以直接應用于動態倉儲環境，通常需要對其改進以應用于智能倉儲系統求解動態路徑規劃的最優解。本文提出一種改進的A*路徑規劃算法，并基于NI myRIO所搭建的多機器人平臺進行了仿真實驗研究，實驗結果表明該算法具備運行可靠性，且可提高倉儲系統的運行效率。

2? 基于改進A*算法的機器人路徑規劃算法設計（Design of robot path planning algorithm based on improved A* algorithm）

智能倉儲系統上貨點到卸貨點可看作一個點對點系統，智能倉儲機器人從接貨點到達卸貨點，需要完成動態避障和自主路徑規劃等功能。傳統A*算法作為一種啟發式搜索算法，只適用于靜態地圖中點對點循跡，但現代倉儲環境中不僅有靜止障礙物，還有運行的機器人作為障礙物[9，10]。機器人運行過程中，只有同時避開靜態障礙物及運行中的其他機器人才能安全到達目標點[11]。傳統的A*算法難以直接應用于現代倉儲物流系統，因此，本文提出一種基于預約表和障礙物地圖[12]的改進型的A*算法以解決智能倉儲動態環境中的多機器人路徑規劃問題。其主要將復雜環境下倉儲機器人的路徑規劃問題轉換為一種連續搜索問題，通過對所有機器人位置的實時獲取，生成一張實時的障礙物地圖并采用預約表形式予以記錄，每臺機器人在該預約表地圖的基礎上進行路徑規劃，可以有效地防止上述的意外情況的發生。本文主要利用柵格建模法[13]構建環境障礙地圖，地圖中每個節點為一個可通行單位，而節點之間的黑線忽略不計。在每個節點中植入RFID電子標簽用以小車的定位，每個卸貨點則定義為關鍵節點，如圖3所示。為保證系統運行穩定性，假設如下：（1）機器人在任意一條道路中只能單向行駛;（2）機器人直行通過一個節點的路徑代價為1;（3）每個柵格在同一時刻僅允許通過或容納一輛小車;（4）機器人運動速度相同。

上述假設可杜絕機器人之間相向碰撞和追擊碰撞問題，但無法避免交叉碰撞問題，具體可以分為兩類：一是兩臺機器人將同時達到同一節點;二是一臺機器人在某個節點轉向時，另一臺機器人即將到達該節點。要解決交叉碰撞可采用任一臺機器人停止運動方式進行規避，對機器人設定優先級。本文根據機器人工作流程及模型構建要求，定義正在轉向狀態的機器人優先級最高，其次滿載時的機器人優先級高于空載狀態機器人，對相同負載狀態機器人的優先級采用機器人編號的方式予以解決，即編號越小機器人優先級較高。最后，通過實時更新障礙物地圖并將其結合預約表方法并結合傳統A*算法以實現多機器人的動態路徑規劃。在機器人運行過程中，除了上貨點和卸貨點關鍵節點外，其余機器人所占據的節點作為障礙物添加到地圖中。每臺機器人只考慮下一步的動作和將要達到的節點，并將信息上傳至控制中心，控制中心將這些信息整理后得到一張實時的障礙變化地圖，各機器人再根據這張地圖確定新的路徑并將下一步的動作和將要達到的節點上傳。如此往復可以實現多機協同的路徑規劃。

3? 系統仿真驗證分析（System simulation verification analysis）

本文主要基于NI myRIO實現智能倉儲機器人實驗平臺，并在LabVIEW開發環境予以實現。

3.1? ?環境地圖柵格化處理

A*算法主要通過計算機器人通過某一位置時的代價函數來實現路徑規劃，本文在對倉儲環境地圖柵格化處理建模時，規定不可通行節點代價值為100，可通行節點代價值為1，以此構建一個地圖矩陣，并采用LabVIEW強度圖表進行顯示，如圖1所示。圖中，黑色代表100，為不可通行的坐標，白色代表1，為可通行的坐標。

3.2? ?改進A*算法實驗仿真

智能倉儲機器人在運行過程中需完成障礙地圖的更新、沖突坐標的調節，并基于各機器人當前坐標根據新的障礙地圖重新規劃路徑。為減小仿真程序設計復雜性，每臺機器人僅預測下一步節點坐標，主機根據所有機器人下一步節點坐標去協調可能有沖突機器人，以及更新障礙地圖。傳統A*算法是用來計算到達目標坐標的最佳路徑，所以會規劃出某些不可通行路徑，如圖2所示。

其中紅色為不可通行節點。在實際應用中通常是不可能實現的，因此本文加入一個路徑有效性驗證程序，將障礙地圖中不可通行的坐標數據進行處理，以驗證路徑中是不可通行坐標真實性。同時可判斷出機器人的下一坐標是否為障礙坐標，進而判斷出下一步的動作。在A*算法中，從某一個節點出發可有八種方向選擇，如圖3所示，但在倉儲環境不允許機器人進行對角運動，可在A*算法中通過改變對角運動代價的方式來將該情況排除，對角運動和不可通行的節點一樣，其代價設置為100。本文所提倉儲機器人動態路徑規劃流程圖如圖4所示。

3.3? ?倉儲機器人避障仿真模擬

圖5為兩臺機器人發生交叉碰撞時仿真模擬，機器人1（藍色）的優先級高于機器人2（紅色）。機器人1由A向B運動，機器人2由C向D運動，圖5（a）中兩機器人的下一步均為節點E，發生交叉碰撞;主機根據優先級協調后機器人2原地等待，機器人1繼續運動，如圖5（b）所示;待機器人1通過節點E后，機器人2繼續前進，如圖5（c）所示;最終兩機器人順利通過節點E，如圖5（d）所示。

3.4? ?倉儲機器人路徑規劃代價分析

在路徑規劃中，如實際路線有不可通行節點，A*算法會優先走過可通行節點，而后再通過不可通行節點，故會出現圖6所示往復行為。圖6（a）中機器人1由E向B運動，會依次通過E→A→C→B;當機器人1剛到達節點A時，假設C處被機器人2占據，在下次的障礙地圖更新后，C則為不可通行節點，A將會重新規劃路線如圖6（b），機器人1下一步將會回到節點E，當機器人2離開節點C時，機器人1又將重新回到節點A，出現往復的行為。為保證機器人不發生類似往復運動，可設定機器人節點與靜態障礙物節點采用相同代價值，減少兩條路徑代價相同的情況，當有兩條總代價花費相同的路徑時，A*算法會優先選擇第一個點代價更低的路徑。

在實際應用中，當某一區域的機器人數量到達該區域的承受極限時，搬運機器人通過該區域的效率將會變得很低，影響倉儲系統的整體效率。當某區域的機器人數量較多時，A*算法進行路徑規劃所求得通過該區域的路徑代價將會更高，如果該代價大于兩目標點間最大代價（兩目標點曼哈頓距離與障礙物代價的乘積），則可能會規劃出穿過墻壁的錯誤路線，如圖7所示。

機器人從A點運動至B的最優路徑如圖7（a）所示，當這條路徑中有一臺機器人停留時，假設所占據節點的代價為100，規劃的路徑如圖7（b）所示，但當有兩臺機器人停留時，通過兩臺機器人路徑的總代價大于從墻壁穿行的總代價，錯誤規劃了一條不可通行路徑，如圖7（c）所示。可根據實際倉儲環境和機器人數量合理設置該代價值予以解決。在上述環境中，兩臺機器人作為障礙物占據通行路徑，設置代價為50，路徑規劃算法可正常工作，如圖7（d）所示。

4? ?結論（Conclusion）

本文所提改進A*算法采用障礙地圖和預約表相結合方法實現了智能倉儲多機器人的動態路徑規劃和協同，通過實驗仿真分析，可以看出所提方法可更好的利用倉庫空間提高倉儲效率。但僅對每個機器人下一步動作進行預約仍有很大局限性，無法滿足大規模倉儲環境應用，在實際應用中，可通過合理平衡場地大小與機器人實際運行數量兩者之間的關系予以解決，保證系統可靠運行。

參考文獻（References）

[1] 陳明智，錢同惠，張仕臻，等.倉儲物流機器人集群避障及協同路徑規劃方法[J].現代電子技術，2019，42（22）：174-177;182.

[2]張國亮.動態環境中移動機器人路徑規劃研究綜述[J].機床與液壓，2013，41（01）：157-162.

[3] 李立，孫龍建.基于LabVIEW和NI myRIO的智能避障小車設計[J].電子器件，2018，41（02）：543-548.

[4] 董朝瑞，郭欣，李寧，等.基于改進A*算法的多機器人動態路徑規劃[J].高技術通訊，2020，30（01）：71-81.

[5] 王洪斌，尹鵬衡，鄭維，等.基于改進的A*算法與動態窗口法的移動機器人路徑規劃[J].機器人，2020（03）：346-353.

[6] Karaboga D， Akay B. A comparative study of Artificial Bee Colony algorithm[J]. Applied Mathematics & Computation， 2009， 214（1）： 108-132.

[7] Ferguson D， Stentz A. Using interpolation to improve path planning：The Field D* algorithm[J]. Journal of Field Robotics， 2006， 23（2）： 79-101.

[8] 王勇.智能倉庫系統多移動機器人路徑規劃研究[D].哈爾濱工業大學，2010.

[9] FazlollahtabarH， Saidi-Mehrabad M. Methodologies to Optimize Automated Guided Vehicle Scheduling and Routing Problems： A Review Study[J]. Journal of Intelligent & Robotic Systems， 2015， 77（3-4）： 525-545.

[10] 王志中.復雜動態環境下自主機器人路徑規劃研究[J].組合機床與自動化加工技術，2018（01）：64-68.

[11] Fu B， Chen L， Zhou Y T， et al. An improved A* algorithm for the industrial robot path planning with high success rate and short length[J]. Robotics and Autonomous Systems， 2018（106）： 26-37.

[12] 張丹露，孫小勇，傅順，等.智能倉庫中的多機器人協同路徑規劃方法[J].計算機集成制造系統，2018，24（02）：410-418.

[13] 張智，翁宗南，蘇麗，等.室內機器人避碰路徑規劃[J].小型微型計算機系統，2019，40（10）：2077-2081.