室內(nèi)倉儲物流機器人路徑規(guī)劃研究

摘 要：在室內(nèi)倉儲運營過程中，物流機器人取代人力配送成為物流行業(yè)的主流發(fā)展趨勢。在倉儲物流機器人系統(tǒng)中，一方面，要求通信、傳感器等硬件模塊具備良好性能；另一方面，路徑規(guī)劃也十分關(guān)鍵，決定了物流機器人的配送效率。因此，研究室內(nèi)倉儲物流機器人的路徑規(guī)劃具有重要意義。文章分析了傳統(tǒng)A*算法的原理及存在的局限性，針對其局限性，采用了單行道方式和轉(zhuǎn)彎懲罰項，基于改進A*算法提出一種室內(nèi)倉儲物流機器人路徑規(guī)劃方法，并提出在固定環(huán)境中投入合適機器人數(shù)量的策略，以期通過科學(xué)、合理的機器人路徑規(guī)劃提高物流倉庫的工作效率和機器人系統(tǒng)的運行效率。

關(guān)鍵詞：室內(nèi)倉儲；物流機器人；路徑規(guī)劃；A*算法

中圖分類號：F272.3 文獻標志碼：A DOI：10.13714/j.cnki.1002-3100.2024.20.038

Abstract： In the indoor warehousing operation， logistics robots replaces the human distribution and becomes the mainstream development trend of logistics industry. In warehousing logistics robot system， on the one hand， it is required that communication， sensors and other hardware modules have good performance. On the other hand， the path planning is also crucial， which determines the distribution efficiency of logistics robots. Therefore， the study of the path planning of indoor warehousing logistics robots is of great significance. This article analyzes the principle and limitations of traditional A* algorithm. In response to these limitations， a one-way approach and a penalty for turning are adopted. Based on the improved A* algorithm， this article puts forward a path planning method of indoor warehousing logistics robots and a strategy for investing an appropriate number of robots in a fixed environment. It aims to improve the working efficiency of logistics warehouse and the operation efficiency of the robot system through the scientific and reasonable robot path planning .

Key words： indoor warehousing; logistics robot; path planning; A* algorithm

1 傳統(tǒng)A*算法

常見的全局路徑規(guī)劃經(jīng)典算法包括Dijkstra算法、A*算法、RRT算法等。其中，A*算法采用啟發(fā)函數(shù)在二維柵格地圖上搜索出一種更優(yōu)路徑。在搜索過程中，A*算法會不斷計算搜索節(jié)點的總代價，按照總代價優(yōu)先級選擇代價最小的節(jié)點，直至搜索到目標節(jié)點結(jié)束。A*算法通過代價函數(shù)f（n）對搜索方向進行啟發(fā)性控制，在確定待拓展結(jié)點和范圍后，再以其中最小代價函數(shù)值的結(jié)點為當(dāng)前結(jié)點，且與當(dāng)前結(jié)點互相連接的其他結(jié)點的代價函數(shù)也會隨之更新，直至搜索至目標結(jié)點[1]。A*算法的具體執(zhí)行流程如下：第一步，進行二維柵格建模，設(shè)定起始點與終點標號，創(chuàng)建開放列表及關(guān)閉列表；第二步，將起點作為父節(jié)點加入關(guān)閉列表，關(guān)閉列表中還包括起點周圍八個方向的非障礙物節(jié)點，再計算列表中每個節(jié)點的實際距離、啟發(fā)函數(shù)、總代價等；第三步，計算出開放列表中總代價最小的節(jié)點，并將其作為父節(jié)點，將原父節(jié)點移入關(guān)閉列表；第四步，將新的父節(jié)點周圍八個方向的非障礙物節(jié)點加入開放列表，并重新計算實際距離；第五步，判斷當(dāng)前父節(jié)點是否為終點，如判斷結(jié)果為“是”，則算法結(jié)束，對目標節(jié)點的父節(jié)點進行逆序輸出，得出A*算法規(guī)劃的路徑；如判斷結(jié)果為“否”，則重復(fù)執(zhí)行第三步[2]。A*算法可以通過計算節(jié)點的總代價得到一條最短路徑，但是二維柵格地圖尺寸越大，需要重復(fù)搜索的無用節(jié)點就越多，會降低算法的搜索效率。因此，基于A*算法的全局路徑規(guī)劃僅是物流機器人在環(huán)境地圖中規(guī)劃出的參考路徑，與機器人在實際環(huán)境中行進的最終路徑存在較大差異，尤其是生成環(huán)境需要大范圍地圖，柵格基數(shù)過于龐大，不僅會影響全局路徑規(guī)劃的效率，而且室內(nèi)倉儲物流環(huán)境始終處于動態(tài)狀態(tài)，系統(tǒng)需要頻繁搜索障礙物以規(guī)劃局部路徑。因此，需要對傳統(tǒng)A*算法進行改進，以簡化搜索流程、提高路徑規(guī)劃效率、提高物流機器人的運行效率。

2 基于改進A*的尋路算法設(shè)計

雖然A*算法簡單、方便，但是上文中也提到，其僅適用于結(jié)點個數(shù)多、求解最短路徑的場景中，在室內(nèi)倉儲物流這類特殊應(yīng)用場景中需要引入轉(zhuǎn)角及單行道約束，并減少系統(tǒng)擁塞及機器人碰撞的機率。具體設(shè)計思路如下。

2.1 減少機器人碰撞策略

倉儲機器人的工作環(huán)境為室內(nèi)物流倉庫，通常需要多個機器人同時運行，以提高倉儲物流工作效率，但傳統(tǒng)A*算法僅考慮單純的路徑長度，無法滿足實際工作需要。機器人的能耗與其工作狀態(tài)有直接相關(guān)性，運行過程中強調(diào)時間最短、能耗最低、最實用。因此，需要進行合理的任務(wù)分配以減少機器人能耗。如果用Tr表示機器人運行時間長度，則可通過下式計算得出[3]。

Tr=Tl+Tt+Tw

式中，Tl為機器人直線行駛時間，速度恒定條件下該值與路徑長度呈正相關(guān)；Tt為機器人轉(zhuǎn)向時消耗時間，角度恒定條件下該值與轉(zhuǎn)向角度呈正相關(guān)；Tw為機器人等待時間，任務(wù)分配、卸貨取貨時間、環(huán)境擁塞程度等指標會影響該值。

如果物流倉庫采用單個機器人，無需考慮任務(wù)分配時間，外部工作人員的工作效率決定了機器人的取貨卸貨時間。因此，只需考慮環(huán)境擁塞的等待時間。但在實際的倉儲環(huán)境中往往需要多個機器人，以提高倉儲物流工作效率，就會產(chǎn)生相向碰撞、側(cè)向碰撞、同向碰撞等問題。其中，相向碰撞是兩個機器人占用同一條路徑相向而行導(dǎo)致的；側(cè)向碰撞則是多個機器人同時占用轉(zhuǎn)角位置，或者機器人分別行駛于各自當(dāng)前路徑，但有一定機率發(fā)生側(cè)向碰撞；同向碰撞通常是由于機器人行進速度相同，但外因?qū)е缕渲幸粋€機器人短暫停留而發(fā)生碰撞。碰撞是導(dǎo)致室內(nèi)機器人系統(tǒng)擁塞的主要因素。為解決這一問題，建議采用單行道方式，如圖1所示。

該單行道約束的方式用有向圖取代無向圖。A*算法在搜索過程中會按照特定的方向拓展，能夠提高機器人運行的有序性，雖然在某種程度上增加了路徑長度，但是卻可以減少碰撞[4]。

2.2 減少機器人轉(zhuǎn)向策略

上文中提到，機器人轉(zhuǎn)向時間會影響機器人轉(zhuǎn)向時的消耗時間。因此，路徑規(guī)劃還需要減少機器人的轉(zhuǎn)向次數(shù)，以減少轉(zhuǎn)向角度，避免機器人頻繁轉(zhuǎn)向而降低運行效率。針對該問題，可以在A*算法中引入轉(zhuǎn)彎懲罰項。在計算當(dāng)前搜索節(jié)點的轉(zhuǎn)彎懲罰項時，要獲得兩點之間的最短路徑，并達到路徑能夠保證相對平滑且減少轉(zhuǎn)彎的目的。通過得到起點s與終點e形成的向量se→→→，以及前節(jié)點n、終點e形成的向量ne→→→，兩個向量圍成的平行四邊形的面積便表示轉(zhuǎn)彎懲罰項，即計算上述兩個向量的叉積即可得到路徑最短，同時避免路徑有較多轉(zhuǎn)角的問題[5]。引入轉(zhuǎn)彎懲罰項后，綜合考慮了路徑的長度和角度，以減少轉(zhuǎn)向角度，提高機器人的工作效率。

3 基于改進A*算法的室內(nèi)倉儲物流機器人路徑規(guī)劃策略

實際物流倉庫中投入的機器人數(shù)量越多、環(huán)境越狹窄，機器人發(fā)生碰撞的機率就越大。機器人自身帶有傳感器，可以使其在遇到障礙時停止行進，以避免碰撞，但在實際的路徑規(guī)劃設(shè)計時，需要考慮如何在固定的環(huán)境中投放合適的機器人數(shù)量，既要保證物流倉庫的工作效率，又要提高機器人系統(tǒng)的運行效率。

3.1 機器人擁塞概率計算

在實際運行過程中，機器人在某個位置的停留時間、在對應(yīng)區(qū)域范圍內(nèi)的機器人數(shù)量決定了機器人發(fā)生碰撞的機率，即機器人停留的時間越長，區(qū)域范圍內(nèi)的機器人數(shù)量越多，機器人碰撞的概率越高，發(fā)生擁塞的機率也越大?？筛鶕?jù)下式對倉儲環(huán)境發(fā)生擁塞的概率進行計算[6]。

Pt=1-e-kt*tstay

Pr=1-e-kr*Nr

Ppre=Pt*Pr

GPi，j=GPi，j，last+Ppir，je

式中，tstay為機器人在某位置停留時間；

Nr為該區(qū)域一定范圍內(nèi)的機器人數(shù)量；

Pt為由時間導(dǎo)致的預(yù)測擁塞概率；

Pr為機器人數(shù)量導(dǎo)致的預(yù)測擁塞概率，通過乘積表征最終概率；

d為機器人位于某柵格的距離；

θ為機器人轉(zhuǎn)向角度；

v為機器人速度；

w為機器人角速度；

kt、kr為參數(shù)。

將每次柵格點（i，j）處預(yù)測的擁塞概率累加到原始擁塞概率地圖GPlast中的（i，j）點處，即可獲得擁塞概率地圖GP。

3.2 多機器人任務(wù)調(diào)度策略

在實際工作場景中，多個機器人在物流倉庫自主移動，攜帶貨架至固定終點，在該工作場景中有N個機器人，并對機器人進行編號，即Ri（i=1，2，3，……，N）。這些機器人需要完成M個任務(wù)，每個任務(wù)也有特定編號，即Ti（i=1，2，3，……，M），在特定時間tj（j=0，1，2，……）處，如何為任務(wù)Ti找到合適的機器人Ri執(zhí)行對應(yīng)任務(wù)是獲得更高的工作效率、解決任務(wù)調(diào)度問題的關(guān)鍵[7]。良好的任務(wù)調(diào)度可實現(xiàn)資源的高效分配，室內(nèi)倉儲工作環(huán)境中，多機器人調(diào)度包括集中式調(diào)度與分布式調(diào)度兩種。其中，分布式調(diào)度更符合人類思維，但是要求機器人能夠自主決策，每個機器人都熟知工作環(huán)境、擁有環(huán)境地圖，準確判斷每個機器人的位置。以目前的技術(shù)而言，其在物理實現(xiàn)上還存在難度。集中式調(diào)度通過核心調(diào)度機構(gòu)進行調(diào)度，即在核心調(diào)度機構(gòu)中輸入環(huán)境地圖，由核心機構(gòu)進行統(tǒng)一調(diào)度，機器人僅執(zhí)行即可，大大降低了對機器人的要求。物流倉庫機器人通過任務(wù)編號執(zhí)行任務(wù)。在此情況下，機器人的調(diào)度需要考慮兩個問題：一是任務(wù)生成后調(diào)度合適的機器人，減少機器人無效移動;二是考慮機器人到達卸貨點后如何選擇空位置放置貨架。針對該類問題，可以引進貪心策略，即在調(diào)度合適的機器人方面，調(diào)度對象為到達任務(wù)點時間最短且可用于調(diào)度的機器人。路徑長度、環(huán)境擁塞程度決定了機器人的運行時間，具體選擇策略符合下式[8]。

式中，T xpath為從當(dāng)前任務(wù)點機器人x按路徑path運動可能花費的時間；Rx為對于當(dāng)前任務(wù)代價最小的機器人。

針對機器人到達卸貨點后如何選擇空位置放置貨架的問題，在對應(yīng)任務(wù)編號生成后卸貨點的位置就已經(jīng)固定，即機器人在完成任務(wù)過程中搬離貨架與搬入貨架總路徑長度相同，任務(wù)量M不變，所有機器人行走的路徑和不變，在路徑規(guī)劃時只需避開擁塞程度高的區(qū)域即可，優(yōu)先選擇擁塞程度低的區(qū)域放置貨架。具體選擇策略符合下式[9]：

式中，為機器人按路徑path行進到處貨架的開銷；Pi，j為貨架最終停放位置。

4 結(jié) 語

綜上所述，在室內(nèi)倉儲物流機器人運行系統(tǒng)中，任務(wù)調(diào)度、路徑規(guī)劃均是重要內(nèi)容，會對機器人的工作效率產(chǎn)生決定性影響。高效的任務(wù)調(diào)度及科學(xué)的路徑規(guī)劃是保證機器人系統(tǒng)穩(wěn)定性、智能性的核心要素。本文提出一種基于改進A*算法的機器人路徑規(guī)劃方案，以減少機器人的碰撞和轉(zhuǎn)向，并結(jié)合室內(nèi)倉儲物流工作場景計算機器人擁塞概率，提出多機器人任務(wù)調(diào)度策略TECel3IeRed7fBxmR90dlpgnsqfyyvsaoFUd/uWIW7Q=，以解決傳統(tǒng)A*算法存在的問題，優(yōu)化機器人路徑規(guī)劃方案，提高機器人的工作效率。

參考文獻：

[1] 鄧星，張競丹，邵海見，等．基于改進人工蜂群進化算法的移動機器人路徑規(guī)劃與仿真分析[J]．江蘇科技大學(xué)學(xué)報（自然科學(xué)版），2020，34（2）：66-71.

[2] 石志剛，梅松，邵毅帆，等．基于人工勢場法的移動機器人路徑規(guī)劃研究現(xiàn)狀與展望[J]．中國農(nóng)機化學(xué)報，2021，42（12）：182-188.

[3] 王成，任佳，張育．基于改進蟻群算法的無人船路徑規(guī)劃研究[J]．海南大學(xué)學(xué)報（自然科學(xué)版），2021，39（3）：242-250.

[4] 張松燦，普杰信，司彥娜，等．蟻群算法在移動機器人路徑規(guī)劃中的應(yīng)用綜述[J]．計算機工程與應(yīng)用，2020，56（8）：10-19.

[5] 周超，谷玉海，任斌．基于一種改進A～*算法的移動機器人路徑規(guī)劃研究[J]．重慶理工大學(xué)學(xué)報（自然科學(xué)），2021，35（5）：127-134.

[6] 槐創(chuàng)鋒，郭龍，賈雪艷，等．改進A*算法與動態(tài)窗口法的機器人動態(tài)路徑規(guī)劃[J]．計算機工程與應(yīng)用，2021，57（8）：244-248.

[7] 張松燦，普杰信，司彥娜，等．蟻群算法在移動機器人路徑規(guī)劃中的應(yīng)用綜述[J]．計算機工程與應(yīng)用，2020，56（8）：10-19.

[8] 謝春麗，高勝寒，孫學(xué)志．融合改進A～*算法和貝塞爾曲線優(yōu)化的路徑規(guī)劃算法[J]．重慶理工大學(xué)學(xué)報（自然科學(xué)），2022，36（7）：177-187.

[9] 龔鵬，李文博，馬慶升，等．基于改進A～*算法的無人車路徑規(guī)劃研究[J]．組合機床與自動化加工技術(shù)，2023（3）：17-20，24.