基于改進A*算法的倉儲移動機器人路徑規劃研究

王 影,王 晨**,孫萬龍,劉 麒*

(1.吉林化工學院 信息與控制工程學院,吉林 吉林 132022;2.博世汽車部件(長春)有限公司,吉林 長春 130000)

移動機器人在物流行業的應用趨勢日益增強,需要其具備自主性,以適應復雜多變的倉儲環境[1]。路徑規劃是移動機器人實現自主導航和運動的核心技術之一,其中最常見的算法包括A*算法、Dijkstra算法[2]、RRT算法、PRM算法、深度強化學習等。

A*算法是一種基于啟發式搜索的最短路徑規劃算法,因其具有良好的靈活性和應用性被廣泛使用。但該算法仍存在搜索效率較低、路徑轉彎較多等問題,學者們已經提出了許多改進方案。例如:龔鵬等人[3]在原算法的基礎上融合JPS搜索策略,有效地減小內存的占用,提高搜索效率;方文凱等人[4]借助人工勢場算法思想,設立衰減函數,得到最優路徑;孫小倩等人[5]針對消耗時間較長的問題,采用梯度下降法進行路徑長度優化;宋宇等人[6]在評價函數中加入轉彎懲罰項,有效延長機器人的使用壽命,使算法更加適用于物流場景;趙久強等人[7]根據障礙物信息調整啟發函數權重,有效地減少了路徑中的轉彎次數和轉彎角度。

雖然以上改進在某些方面做出了一些提升,但仍存在倉儲移動機器人搜索效率低、運行不穩定等問題。為了進一步提升算法性能,本研究對傳統A*算法的搜索方式、啟發式函數進行改進,并對路徑進行了優化處理,旨在提高搜索效率,保證移動機器人工作安全,可以更好地滿足實際需求,具有廣泛的應用價值和現實意義。

1 理論基礎

1.1 構建倉儲仿真地圖

考慮到倉儲環境具有倉庫空間大、貨架擺放方式多樣、人員進出頻繁以及安全性要求高等特點,本文選用柵格地圖來進行環境構建。柵格地圖由像素組成的網格圖構成,像素的不同顏色(樣式)代表不同的物體或場景,具有簡單易用、場景描述精細、運算速度快等優點[8]。如圖1所示,以30×30的倉儲柵格地圖為例。

圖1 倉儲柵格地圖

其中:白色代表可活動區域,黑色代表障礙物。為了后續仿真實驗的易操作性,本文將可行區域內散落的貨物、停放的搬運車等元素,統一視為障礙物進行處理。

1.2 傳統A*算法

傳統A*算法是一種啟發式搜索算法,屬于單源最短路徑問題的一種求解方法,它可以在有向圖、網格和其他形式的圖形結構中尋找最短路徑[9]。該算法利用估價函數結合節點信息對路徑搜索過程進行引導。具體來說:從起始點開始,通過估價函數的引導,找到代價值最小的點作為當前節點,然后遍歷當前節點鄰近的8個子節點。不斷循環這一過程,直到找到目標節點為止,結束搜索,獲得最短路徑。傳統A*算法的核心公式如式(1)所示。

f(n)=g(n)+h(n) ,

(1)

其中,n表示搜索過程中的一個節點;估價函數f(n)由兩部分構成:起點到當前節點的實際代價g(n)和當前節點到目標節點的預估代價h(n)。

考慮到傳統A*算法是8鄰域搜索算法,需要計算簡單且直觀。因此,本文選用歐幾里得距離來計算代價值,如式(2)、(3)所示。

(2)

(3)

其中,(nx,ny)表示當前節點的坐標;(startx,starty)表示起始節點的坐標;(goalx,goaly)表示目標節點的坐標。

2 路徑規劃

2.1 障礙物膨脹處理

為了使移動機器人能夠在倉儲環境中安全地運行,除了考慮環境中的障礙物外,機器人自身的體積也是需要考慮的重要因素[10]。因此,本文對障礙物進行膨脹處理:當障礙物覆蓋率大于等于0.5時,表示地圖中的障礙物很密集,此時不做任何處理;當障礙物覆蓋率小于0.5時,障礙物分布適中,將障礙物膨脹一個柵格長度。障礙物覆蓋率的計算如式(4)所示。

(4)

式中,r為障礙物覆蓋率;O為障礙物柵格的數量;N為總的柵格數量。障礙物膨脹前后對比如圖2所示。

(a) 原始地圖

2.2 A*算法改進

2.2.1 雙向搜索

由于傳統A*算法是單向搜索,搜索速度較慢,無法滿足倉儲環境的工作需要。因此,本文將單向搜索改進為雙向搜索。雙向A*搜索算法的核心思想是從起點和終點分別、同時向對方進行搜索,同時進行迭代,直到兩個搜索路徑相遇。在每次迭代過程中,算法會選擇當前總代價最小的節點進行擴展,同時更新兩個方向上的實際代價g(n)和預估代價h(n)[11]。雙向搜索可以有效地減少搜索范圍,提高搜索效率,在搜索節點和搜索時間上都會有明顯的優勢。雙向A*搜索算法的工作流程如圖3所示。

圖3 雙向A*搜索算法流程圖

2.2.2 改進估價函數

雖然雙向搜索相較于單向搜索而言,搜索效率顯著提升。但當出現一些特殊的環境場景,如起點和終點分別置于障礙物兩側且必須繞行時,雙向A*搜索算法會拓展一些無用節點,大大降低了搜索效率,如圖4所示。

圖4 特殊的環境場景

分析估價函數f(n)可知:正向搜索節點和反向搜索節點之間的預估代價h(n)為兩點間的歐幾里得距離,在通常情況下都是小于實際路徑代價的。如果在雙向搜索的過程中,能使雙向搜索節點之間的預估代價h(n)十分接近于實際代價,那樣就不會搜索到一些無用的節點。在該算法搜索初期,雙向搜索節點距離較遠,預估代價h(n)是遠遠小于實際代價的,希望h(n)逐漸增大;在該算法搜索后期,雙向搜索節點距離較近,預估代價h(n)逐漸接近于實際代價,希望h(n)隨之減小。這樣做可以在保證路徑較優的情況下,盡量地減少搜索節點,進而提高雙向A*算法的搜索效率。

因此,本文對雙向A*搜索算法的核心部分,即估價函數f(n)進行改進,對其中的預估代價h(n)進行指數加權處理。其中取a>0,在后期的實驗過程中,分別取a=2、5、10進行對比。改進后的公式如式(5)所示。

f(n)=g(n)+h(n)·ah(n)。

(5)

2.3 路徑優化

通過上述兩方面的改進,已解決倉儲環境中移動機器人的搜索效率問題。為了使規劃出的路徑更加精確、實用,本文通過五個步驟優化CloseList列表中的節點,從而降低路徑復雜度,具體步驟如表1所示。這樣做既可以保證不丟失路徑的重要信息,同時可以有效地減少路徑節點,使移動機器人在倉儲環境內可以安全、平穩地運行[12]。

表1 優化CloseList列表中的節點

去除冗余點前后效果對比如圖5所示。

(a) 去除前

3 實驗及結果分析

3.1 單、雙向搜索對比實驗

為驗證雙向搜索的有效性,以搜索時間和搜索節點為主要評價指標,分別在5種不同規模的柵格地圖上進行仿真實驗,實驗結果如圖6所示。

地圖規模(a) 搜索時間對比

實驗結果表明:雙向搜索相較于單向搜索,在搜索時間和搜索節點上分別減少14.6%和42.8%,有效地提高了搜索效率。隨著地圖規模的增大,效果逐漸明顯,尤其在搜索節點上。

3.2 算法對比實驗

為驗證本文算法改進的有效性,以搜索時間為主要評價指標,將本文算法與其余三種算法(Dijkstra算法、RRT算法、傳統A*算法)在同一倉儲柵格地圖上進行仿真實驗,實驗結果如表2、圖7所示。

表2 不同算法的搜索時間(單位:s)

地圖規模圖7 不同算法搜索時間對比

實驗結果表明:本文算法顯著地提高了搜索效率,在較大的地圖規模中,效果明顯。在30×30、40×40、50×50、60×60的地圖規模中,搜索時間相較于傳統A*算法分別降低了2.22%、11.98%、18.59%、15.76%。

4 結 論

本文提出的基于改進A*算法的倉儲移動機器人路徑規劃方法具有高效、可靠和穩定的特點。通過膨脹處理、雙向搜索、預估代價的指數加權等措施,有效解決了傳統A*算法存在的安全性較低、搜索速度較慢等問題。本文算法縮短了搜索時間,減少了搜索節點,提高了倉儲移動機器人的工作效率。此外,可以在路徑優化方面做進一步的提升,以更好地適應倉儲環境的復雜性和動態性,提升倉儲工作的智能化水平。