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

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

中圖分類號：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*算法

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

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

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

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

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

Tr=Tl+Tt+Tw

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

如果物流倉庫采用單個(gè)機(jī)器人，無需考慮任務(wù)分配時(shí)間，外部工作人員的工作效率決定了機(jī)器人的取貨卸貨時(shí)間。因此，只需考慮環(huán)境擁塞的等待時(shí)間。但在實(shí)際的倉儲環(huán)境中往往需要多個(gè)機(jī)器人，以提高倉儲物流工作效率，就會產(chǎn)生相向碰撞、側(cè)向碰撞、同向碰撞等問題。其中，相向碰撞是兩個(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)擁塞的主要因素。為解決這一問題，建議采用單行道方式，如圖1所示。

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

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

上文中提到，機(jī)器人轉(zhuǎn)向時(shí)間會影響機(jī)器人轉(zhuǎn)向時(shí)的消耗時(shí)間。因此，路徑規(guī)劃還需要減少機(jī)器人的轉(zhuǎn)向次數(shù)，以減少轉(zhuǎn)向角度，避免機(jī)器人頻繁轉(zhuǎn)向而降低運(yùn)行效率。針對該問題，可以在A*算法中引入轉(zhuǎn)彎懲罰項(xiàng)。在計(jì)算當(dāng)前搜索節(jié)點(diǎn)的轉(zhuǎn)彎懲罰項(xiàng)時(shí)，要獲得兩點(diǎn)之間的最短路徑，并達(dá)到路徑能夠保證相對平滑且減少轉(zhuǎn)彎的目的。通過得到起點(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)角的問題[5]。引入轉(zhuǎn)彎懲罰項(xiàng)后，綜合考慮了路徑的長度和角度，以減少轉(zhuǎn)向角度，提高機(jī)器人的工作效率。

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

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

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

在實(shí)際運(yùn)行過程中，機(jī)器人在某個(gè)位置的停留時(shí)間、在對應(yīng)區(qū)域范圍內(nèi)的機(jī)器人數(shù)量決定了機(jī)器人發(fā)生碰撞的機(jī)率，即機(jī)器人停留的時(shí)間越長，區(qū)域范圍內(nèi)的機(jī)器人數(shù)量越多，機(jī)器人碰撞的概率越高，發(fā)生擁塞的機(jī)率也越大?？筛鶕?jù)下式對倉儲環(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ù)測擁塞概率；

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

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

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

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

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

kt、kr為參數(shù)。

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

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

在實(shí)際工作場景中，多個(gè)機(jī)器人在物流倉庫自主移動(dòng)，攜帶貨架至固定終點(diǎn)，在該工作場景中有N個(gè)機(jī)器人，并對機(jī)器人進(jìn)行編號，即Ri（i=1，2，3，……，N）。這些機(jī)器人需要完成M個(gè)任務(wù)，每個(gè)任務(wù)也有特定編號，即Ti（i=1，2，3，……，M），在特定時(shí)間tj（j=0，1，2，……）處，如何為任務(wù)Ti找到合適的機(jī)器人Ri執(zhí)行對應(yīng)任務(wù)是獲得更高的工作效率、解決任務(wù)調(diào)度問題的關(guān)鍵[7]。良好的任務(wù)調(diào)度可實(shí)現(xiàn)資源的高效分配，室內(nèi)倉儲工作環(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)度通過核心調(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í)行即可，大大降低了對機(jī)器人的要求。物流倉庫機(jī)器人通過任務(wù)編號執(zhí)行任務(wù)。在此情況下，機(jī)器人的調(diào)度需要考慮兩個(gè)問題：一是任務(wù)生成后調(diào)度合適的機(jī)器人，減少機(jī)器人無效移動(dòng);二是考慮機(jī)器人到達(dá)卸貨點(diǎn)后如何選擇空位置放置貨架。針對該類問題，可以引進(jìn)貪心策略，即在調(diào)度合適的機(jī)器人方面，調(diào)度對象為到達(dá)任務(wù)點(diǎn)時(shí)間最短且可用于調(diào)度的機(jī)器人。路徑長度、環(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為對于當(dāng)前任務(wù)代價(jià)最小的機(jī)器人。

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

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

4 結(jié) 語

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

參考文獻(xiàn)：

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

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

[3] 王成，任佳，張育．基于改進(jìn)蟻群算法的無人船路徑規(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～*算法的無人車路徑規(guī)劃研究[J]．組合機(jī)床與自動(dòng)化加工技術(shù)，2023（3）：17-20，24.