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

摘? 要：為解決智能倉儲(chǔ)系統(tǒng)中多機(jī)器人協(xié)同控制問題，提出一種基于預(yù)約表障礙地圖的改進(jìn)A*路徑規(guī)劃算法。首先利用預(yù)約表生成障礙地圖并對(duì)機(jī)器人進(jìn)行避障處理;然后給出一種改進(jìn)A*算法基于障礙地圖預(yù)約表更新倉儲(chǔ)系統(tǒng)中機(jī)器人實(shí)時(shí)位置并實(shí)現(xiàn)動(dòng)態(tài)路徑規(guī)劃;最后，基于NImyRIO機(jī)器人平臺(tái)對(duì)所提算法進(jìn)行了實(shí)驗(yàn)仿真分析，結(jié)果表明所提算法具備一定的可靠性并可提高倉儲(chǔ)系統(tǒng)的運(yùn)行效率。

關(guān)鍵詞：智能倉儲(chǔ)系統(tǒng);多機(jī)器人系統(tǒng);路徑規(guī)劃

中圖分類號(hào)：TP242.6? ? ?文獻(xiàn)標(biāo)識(shí)碼：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）

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

2? 基于改進(jìn)A*算法的機(jī)器人路徑規(guī)劃算法設(shè)計(jì)（Design of robot path planning algorithm based on improved A* algorithm）

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

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

3? 系統(tǒng)仿真驗(yàn)證分析（System simulation verification analysis）

本文主要基于NI myRIO實(shí)現(xiàn)智能倉儲(chǔ)機(jī)器人實(shí)驗(yàn)平臺(tái)，并在LabVIEW開發(fā)環(huán)境予以實(shí)現(xiàn)。

3.1? ?環(huán)境地圖柵格化處理

A*算法主要通過計(jì)算機(jī)器人通過某一位置時(shí)的代價(jià)函數(shù)來實(shí)現(xiàn)路徑規(guī)劃，本文在對(duì)倉儲(chǔ)環(huán)境地圖柵格化處理建模時(shí)，規(guī)定不可通行節(jié)點(diǎn)代價(jià)值為100，可通行節(jié)點(diǎn)代價(jià)值為1，以此構(gòu)建一個(gè)地圖矩陣，并采用LabVIEW強(qiáng)度圖表進(jìn)行顯示，如圖1所示。圖中，黑色代表100，為不可通行的坐標(biāo)，白色代表1，為可通行的坐標(biāo)。

3.2? ?改進(jìn)A*算法實(shí)驗(yàn)仿真

智能倉儲(chǔ)機(jī)器人在運(yùn)行過程中需完成障礙地圖的更新、沖突坐標(biāo)的調(diào)節(jié)，并基于各機(jī)器人當(dāng)前坐標(biāo)根據(jù)新的障礙地圖重新規(guī)劃路徑。為減小仿真程序設(shè)計(jì)復(fù)雜性，每臺(tái)機(jī)器人僅預(yù)測(cè)下一步節(jié)點(diǎn)坐標(biāo)，主機(jī)根據(jù)所有機(jī)器人下一步節(jié)點(diǎn)坐標(biāo)去協(xié)調(diào)可能有沖突機(jī)器人，以及更新障礙地圖。傳統(tǒng)A*算法是用來計(jì)算到達(dá)目標(biāo)坐標(biāo)的最佳路徑，所以會(huì)規(guī)劃出某些不可通行路徑，如圖2所示。

其中紅色為不可通行節(jié)點(diǎn)。在實(shí)際應(yīng)用中通常是不可能實(shí)現(xiàn)的，因此本文加入一個(gè)路徑有效性驗(yàn)證程序，將障礙地圖中不可通行的坐標(biāo)數(shù)據(jù)進(jìn)行處理，以驗(yàn)證路徑中是不可通行坐標(biāo)真實(shí)性。同時(shí)可判斷出機(jī)器人的下一坐標(biāo)是否為障礙坐標(biāo)，進(jìn)而判斷出下一步的動(dòng)作。在A*算法中，從某一個(gè)節(jié)點(diǎn)出發(fā)可有八種方向選擇，如圖3所示，但在倉儲(chǔ)環(huán)境不允許機(jī)器人進(jìn)行對(duì)角運(yùn)動(dòng)，可在A*算法中通過改變對(duì)角運(yùn)動(dòng)代價(jià)的方式來將該情況排除，對(duì)角運(yùn)動(dòng)和不可通行的節(jié)點(diǎn)一樣，其代價(jià)設(shè)置為100。本文所提倉儲(chǔ)機(jī)器人動(dòng)態(tài)路徑規(guī)劃流程圖如圖4所示。

3.3? ?倉儲(chǔ)機(jī)器人避障仿真模擬

圖5為兩臺(tái)機(jī)器人發(fā)生交叉碰撞時(shí)仿真模擬，機(jī)器人1（藍(lán)色）的優(yōu)先級(jí)高于機(jī)器人2（紅色）。機(jī)器人1由A向B運(yùn)動(dòng)，機(jī)器人2由C向D運(yùn)動(dòng)，圖5（a）中兩機(jī)器人的下一步均為節(jié)點(diǎn)E，發(fā)生交叉碰撞;主機(jī)根據(jù)優(yōu)先級(jí)協(xié)調(diào)后機(jī)器人2原地等待，機(jī)器人1繼續(xù)運(yùn)動(dòng)，如圖5（b）所示;待機(jī)器人1通過節(jié)點(diǎn)E后，機(jī)器人2繼續(xù)前進(jìn)，如圖5（c）所示;最終兩機(jī)器人順利通過節(jié)點(diǎn)E，如圖5（d）所示。

3.4? ?倉儲(chǔ)機(jī)器人路徑規(guī)劃代價(jià)分析

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

在實(shí)際應(yīng)用中，當(dāng)某一區(qū)域的機(jī)器人數(shù)量到達(dá)該區(qū)域的承受極限時(shí)，搬運(yùn)機(jī)器人通過該區(qū)域的效率將會(huì)變得很低，影響倉儲(chǔ)系統(tǒng)的整體效率。當(dāng)某區(qū)域的機(jī)器人數(shù)量較多時(shí)，A*算法進(jìn)行路徑規(guī)劃所求得通過該區(qū)域的路徑代價(jià)將會(huì)更高，如果該代價(jià)大于兩目標(biāo)點(diǎn)間最大代價(jià)（兩目標(biāo)點(diǎn)曼哈頓距離與障礙物代價(jià)的乘積），則可能會(huì)規(guī)劃出穿過墻壁的錯(cuò)誤路線，如圖7所示。

機(jī)器人從A點(diǎn)運(yùn)動(dòng)至B的最優(yōu)路徑如圖7（a）所示，當(dāng)這條路徑中有一臺(tái)機(jī)器人停留時(shí)，假設(shè)所占據(jù)節(jié)點(diǎn)的代價(jià)為100，規(guī)劃的路徑如圖7（b）所示，但當(dāng)有兩臺(tái)機(jī)器人停留時(shí)，通過兩臺(tái)機(jī)器人路徑的總代價(jià)大于從墻壁穿行的總代價(jià)，錯(cuò)誤規(guī)劃了一條不可通行路徑，如圖7（c）所示。可根據(jù)實(shí)際倉儲(chǔ)環(huán)境和機(jī)器人數(shù)量合理設(shè)置該代價(jià)值予以解決。在上述環(huán)境中，兩臺(tái)機(jī)器人作為障礙物占據(jù)通行路徑，設(shè)置代價(jià)為50，路徑規(guī)劃算法可正常工作，如圖7（d）所示。

4? ?結(jié)論（Conclusion）

本文所提改進(jìn)A*算法采用障礙地圖和預(yù)約表相結(jié)合方法實(shí)現(xiàn)了智能倉儲(chǔ)多機(jī)器人的動(dòng)態(tài)路徑規(guī)劃和協(xié)同，通過實(shí)驗(yàn)仿真分析，可以看出所提方法可更好的利用倉庫空間提高倉儲(chǔ)效率。但僅對(duì)每個(gè)機(jī)器人下一步動(dòng)作進(jìn)行預(yù)約仍有很大局限性，無法滿足大規(guī)模倉儲(chǔ)環(huán)境應(yīng)用，在實(shí)際應(yīng)用中，可通過合理平衡場(chǎng)地大小與機(jī)器人實(shí)際運(yùn)行數(shù)量兩者之間的關(guān)系予以解決，保證系統(tǒng)可靠運(yùn)行。

參考文獻(xiàn)（References）

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

[2]張國亮.動(dòng)態(tài)環(huán)境中移動(dòng)機(jī)器人路徑規(guī)劃研究綜述[J].機(jī)床與液壓，2013，41（01）：157-162.

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

[4] 董朝瑞，郭欣，李寧，等.基于改進(jìn)A*算法的多機(jī)器人動(dòng)態(tài)路徑規(guī)劃[J].高技術(shù)通訊，2020，30（01）：71-81.

[5] 王洪斌，尹鵬衡，鄭維，等.基于改進(jìn)的A*算法與動(dòng)態(tài)窗口法的移動(dòng)機(jī)器人路徑規(guī)劃[J].機(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] 王勇.智能倉庫系統(tǒng)多移動(dòng)機(jī)器人路徑規(guī)劃研究[D].哈爾濱工業(yè)大學(xué)，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] 王志中.復(fù)雜動(dòng)態(tài)環(huán)境下自主機(jī)器人路徑規(guī)劃研究[J].組合機(jī)床與自動(dòng)化加工技術(shù)，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ī)器人協(xié)同路徑規(guī)劃方法[J].計(jì)算機(jī)集成制造系統(tǒng)，2018，24（02）：410-418.

[13] 張智，翁宗南，蘇麗，等.室內(nèi)機(jī)器人避碰路徑規(guī)劃[J].小型微型計(jì)算機(jī)系統(tǒng)，2019，40（10）：2077-2081.