室內(nèi)倉(cāng)儲(chǔ)物流機(jī)器人路徑規(guī)劃研究

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

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

中圖分類號(hào)：F272.3 文獻(xiàn)標(biāo)志碼：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*算法

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

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

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

2.1 減少機(jī)器人碰撞策略

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

Tr=Tl+Tt+Tw

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

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

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

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

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

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

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

3.1 機(jī)器人擁塞概率計(jì)算

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

Pt=1-e-kt*tstay

Pr=1-e-kr*Nr

Ppre=Pt*Pr

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

式中，tstay為機(jī)器人在某位置停留時(shí)間；

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

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

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

d為機(jī)器人位于某柵格的距離；

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

v為機(jī)器人速度；

w為機(jī)器人角速度；

kt、kr為參數(shù)。

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

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

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

式中，T xpath為從當(dāng)前任務(wù)點(diǎn)機(jī)器人x按路徑path運(yùn)動(dòng)可能花費(fèi)的時(shí)間；Rx為對(duì)于當(dāng)前任務(wù)代價(jià)最小的機(jī)器人。

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

式中，為機(jī)器人按路徑path行進(jìn)到處貨架的開(kāi)銷；Pi，j為貨架最終停放位置。

4 結(jié) 語(yǔ)

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

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