基于無人叉車行駛時間優化的改進A*算法

童亞男, 肖本賢

(合肥工業大學 電氣與自動化工程學院,安徽 合肥 230009)

當下世界范圍內蓬勃發展的電子商務帶來的日益增長的倉儲物流需求與手動操縱工業車輛的熟練技術人員的不足之間的矛盾日益凸顯,人工手動操作顯然不足以應付物流高峰期的生產和交付需求。為保持高質量的生產和供應水平[1-3],越來越多的倉庫系統選擇采用各種機器人和無人駕駛工業運輸和搬運車輛來替代傳統勞動力完成一系列不需要專業知識的工作[4-6]。因此,移動機器人和無人駕駛車輛的路徑規劃算法成為研究熱點,如神經網絡[7-8]、Dijkstra算法、蟻群算法[9]、人工勢場法、RRT*算法[10-12]、A*算法[13-16]等智能路徑規劃算法。

神經網絡算法學習時間長,規劃效率低。Dijkstra算法搜索為盲搜索,可以得到全局最優路徑,但運行效率低下。人工勢場法計算量小,但存在局部極小陷阱。RRT*算法搜索速度快,但具有很強的隨機性,導致收斂速度慢、生成路徑不平滑。

A*算法是一種啟發式搜索算法,近年來被廣泛應用于路徑規劃領域。由于該算法具有最優性、完備性和高效性,其系列改進算法一直是路徑規劃領域的研究熱點。啟發函數能引導搜索向最優方向進行,在靜態網絡中搜索路徑有效而直接,能搜索到最優路徑;但也存在不足,得到的路徑轉折點多,存在大量冗余節點,不利于無人駕駛車輛進行實際跟蹤[17-19];文獻[20]提出一種可搜索無線鄰域的改進A*算法為無人駕駛車輛尋找可行路徑,對柵格進行線性插值,提高搜索效率,但在復雜地圖上優勢不明顯;文獻[21]提出以矩陣單元進行拓展,提高了算法效率,優化了路徑質量,但在低復雜度且不開闊環境中,性能優化不明顯;文獻[22]通過拓展可搜索鄰域來增加路徑搜索方向,規劃所得路徑比傳統A*算法的更短,轉彎次數更少,但搜索時間大大增加,在復雜精細地圖上實用性不高。

本文提出一種基于行駛時間優化的改進A*算法。以無人叉車為研究對象,從以下3個方面進行改進:

1) 對實際代價函數進行優化。引入轉彎代價補償參數用以表示轉彎額外行駛時間,將轉彎操作導致的額外操作時間納入評估函數,使搜索過程趨向于航向不變的節點。

2) 對啟發函數優化。引入父節點啟發函數值,同時對啟發函數權重進行自適應調整,確保搜索過程快速靠近目標節點且路徑最優。

3) 對路徑規劃的初步結果進行路徑剪枝,平滑路徑降低路徑轉彎總角度,使路徑適于無人叉車的實際跟蹤。

針對以上改進,本文設計了不同環境地圖進行仿真實驗,證明所提出改進算法的有效性和實用性。

1 環境建模

無人叉車的出現提高了工作效率,降低了人力和設備成本。無人叉車的工作效率提升不僅意味著提升叉車行駛速度,還意味著縮短工作循環內的工作時間。叉車在彎道行駛時,需要進行額外減速、制動和重新加速,這不僅增加了工作循環內的工作時間,還會影響無人叉車的整體性能,帶來側翻風險,導致更高的車輛維護成本[4]。

柵格法是目前最常用的環境建模方法之一。將地圖切割成大小相同相互連接的柵格,用黑色柵格代表障礙物所在區域,即不可通行,空白柵格表示該區域可供穿越行駛。在常見的8向柵格圖中,叉車可在相鄰可通行柵格間橫向、縱向或斜向45°行駛;16向24鄰域柵格圖進一步增加了搜索方向,拓展鄰域的增加使得拓展節點時搜索量成倍增加。文獻[22]證明機械地增加搜索鄰域來擴大A*算法的搜索方向在一定程度上改善了路徑的平滑度,但算法搜索時間和存儲空間顯著增加。出于搜索效率考量,本文改進算法基于8向柵格地圖進行環境建模。

在結構化地圖中,叉車在通道中行駛,通道可分為單行道、雙行道和多行道,在通道兩側有貨架、堆疊貨物等多種類型的障礙物。因為在非結構化環境,如小型非結構化倉庫中障礙物分布不規則、通道寬度不確定的情況下,叉車行駛可能產生更多轉彎,轉彎角度更大,所以有更大的路徑優化需求。因此,本文的改進A*算法在進行有效性驗證時建立了多種柵格地圖對叉車工作環境進行模擬。

2 傳統A*算法

A*算法通過設計帶約束性的啟發式函數,在狀態空間內對當前節點的每一個待擴展節點的成本進行評估,并且設計與問題特征相關的啟發函數對性能進行調整,通過比較每個擴展節點的成本,選擇最理想的節點去擴展,直到發現目標節點。在執行路徑規劃時,OPEN list用于保存搜索過程中遇到的擴展節點,將這些節點按評估函數成本f(n)值的大小排序;CLOSE list用于保存OPEN list中評估函數f(n)值最小的可擴展節點。

A*算法的評估函數f(n)計算公式為:

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

(1)

該函數計算由兩部分組成,即從初始節點S到候選節點n的路徑的實際距離成本g(n)和從候選節點n到目標節點G的最優路徑的評估成本h(n)。

實際距離成本g(n)使用歐幾里德距離累加表示,兩點間歐幾里德計算公式如下:

(2)

則相鄰節點n的實際代價函數g(n)值和啟發函數h(n)值可用下列公式進行計算:

(3)

(4)

其中:xG、yG為目標節點G的橫坐標和縱坐標;xn、yn為候選節點n的橫坐標和縱坐標。

傳統A*算法路徑規劃過程如圖1所示。

圖1 傳統A*算法流程

為提高搜索效率、縮短運算時間,本文將柵格圖中每個柵格大小設置為1×10,當叉車在柵格間橫向或豎向移動時,其運動距離記為1,斜向移動時,運動距離記為14,h(n)的計算公式如下:

h(n)=1.4min(Δx,Δy)+|Δx-Δy|

(5)

其中:Δx=|xn-xn+1|;Δy=|yn-yn+1|;xn+1、yn+1分別為節點n+1的橫、縱坐標。

傳統A*算法的評價函數綜合了Dijkstra算法和最佳優先搜索(best-first-search,BFS)算法。將A*算法評價函數f(n)一般化,用下列公式表示:

f(n)=αg(n)+βh(n)

(6)

當系數α=1、β=0時,算法退化為Dijkstra算法,傾向于廣度優先搜索,即搜索偏向接近起點的節點,搜索范圍大、時間長,但可求得兩點之間的最短路徑;當系數α=0、β=1時,算法搜索啟發性更強,更傾向于搜索離目標節點更近的節點,此時A*算法可視為廣度優先搜索(breadth first search,BFS)算法,但規劃所得路徑不一定是最優路徑,因此評估函數f(n)中各項權重需要結合實際需要合理分配以得到更優、更平滑的路徑。

3 改進A*算法

本節對傳統A*算法進行改進,目標是取得靜態環境下無人叉車行駛時間最短的路徑。一方面向實際代價估計函數g(n)中引入轉彎代價補償參數構造轉彎行駛時間函數,以此減少生成路徑中的轉彎次數;另一方面同時向原有的啟發函數中引入父節點啟發函數h(p),并對自身權重進行自適應調整;最后對規劃所得初始路徑進行剪枝,得到最優路徑。

3.1 轉彎代價補償

叉車行駛過程中存在5種不同的直行與轉彎情形,如圖2所示。父節點p、當前節點m和拓展節點n的坐標位置可以用于判斷前進方向是否發生改變:

圖2 節點與行駛方向

λ1=(xm-xp)-(xn-xm)

(7)

λ2=(ym-yp)-(yn-ym)

(8)

其中:(xm,ym)為當前節點m的坐標;(xp,yp)為父節點p的坐標;(xn,yn)為拓展節點n的坐標;λ1為橫向轉向因子;λ2為縱向轉向因子;當λ1=λ2時,叉車行駛方向不變,當λ1≠λ2時,航向改變,需轉彎。

實際行駛過程中,同樣距離行駛在轉彎路段所需時間遠超過直行路段,而傳統A*算法評估函數中g(n)和h(n)僅表示實際已規劃的路徑長度和候選節點到目標節點的最短距離,未考慮轉彎操作過程中由減速制動、重新加速等操作帶來的額外時間成本,規劃所得路徑轉彎次數多,轉彎角度大,在無人叉車的實際工作中并不適用。

為解決上述問題,本文將行駛時間細分為直行行駛時間成本和由當前節點m拓展到候選節點n因轉彎增加的行駛時間成本gt(n)。直行行駛時間由實際代價函數g(n)表示;轉彎行駛時間gt(n)需要引入轉彎代價補償參數ω進行計算,由轉彎代價補償參數ω與拓展柵格的實際距離d加權表示,即

gt(n)=ω(λ1-λ2)dm,n

(9)

改進后實際代價函數g′(n)由兩部分組成,即固有的直線行駛成本g(n)和額外的轉彎時間成本gt(n),其計算公式為:

g′(n)=g(n)+gt(n)=

(10)

3.2 啟發函數優化

A*算法的啟發函數能使算法的搜索方向趨向于更有目的地接近端點。為約束算法搜索方向,減少往返搜索次數,使其快速靠近目標節點,本文在啟發函數中引入了父節點的啟發估計代價h(p),改進后的啟發函數計算公式為:

h′(n)=h(n)+h(p)

(11)

考慮到本文啟發函數h(p)使用歐幾里德距離對兩點間距離進行估計,此距離為兩點之間最短距離,而無人叉車的實際工作環境中存在貨架、貨物、建筑等障礙物,使得兩點間實際路徑距離要遠大于啟發函數所估計的最短距離。在傳統A*算法中,啟發函數權重為1,在小范圍內有多個評價函數值相等的候選節點,需要進行多次比較,搜索效率低。針對上述問題,本文通過比較拓展節點到目標節點及起始節點的距離遠近,對啟發函數的權重β進行自適應調整,以提高搜索效率,同時避免路徑規劃結果陷入局部最優,啟發函數權重β的計算公式如下:

β=1+h(n)/D

(12)

其中,D為起始節點到目標節點的歐幾里德距離,是一個常量。D的計算公式如下:

(13)

其中:(xG,yG)為起始節點坐標;(xS,yS)為目標節點坐標。當候選節點離目標節點較遠時,h(n)較大,啟發函數權重β取值較大,路徑搜索方向快速接近目標節點;當候選節點逐漸靠近目標節點時,h(n)減小,啟發函數權重β也隨之減小,此時算法搜索范圍擴大以確保目標點可達,避免陷入局部最優解。

經改進后評價函數f(n)的計算公式為:

f(n)=g′(n)+βh′(n)=

(14)

3.3 路徑剪枝

對改進后的A*算法所得路徑采取全局路徑剪枝,以剔除冗余拐點,進一步平滑路徑,減小路徑拐彎總角度。

得到初始路徑后,從目標節點G開始,直接將點G與倒數第2個拐點N2相連接,若兩點連線不與障礙物相交,則與倒數第3個拐點N3連接,依此類推,直到連線遇到障礙物。假設目標節點G與倒數第i個拐點Ni的連線與障礙物相交,即L(G,Ni)=+∞,則依次連接目標節點G與倒數第i個拐點Ni和倒數第i-1個拐點Ni-1之間(包括拐點Ni-1)的所有節點,直到節點X與目標節點G的連線是一條不與障礙物相交的直線,保留節點X與節點G,舍棄節點X到節點G間其余節點,以節點X為起點,繼續向前回溯,直到回溯到起始節點S;最后依次連接所有剩余關鍵節點,得到剪枝后的優化路徑。

路徑剪枝過程演示如圖3所示。

圖3 路徑剪枝過程

其中:紅、綠色節點分別表示路徑目標節點和起始節點;黑色實線為初始路徑;紅色虛線為剪枝過程路徑。

首先將目標節點G與倒數第2個拐點N2相連,路徑與障礙物不交叉;繼續依次連接倒數第3個拐點N3、倒數第4個拐點N4連接,其路徑與障礙物均不交叉;直到G與倒數第5個拐點N5相連,路徑與障礙物交叉,即L(G,N5)=+∞;N4、N5存在中間節點B,連接G、B,其路徑與障礙物相交L(G,B)=+∞,則該段路徑剪枝結果為:

Path(G,N4)=G→N4

(15)

以N4為下一次剪枝的起點,將其與其后倒數第2個拐點即N6連接,路徑與障礙物不交叉;繼續向前回溯,到達起始節點S,連接S、N4,L(S,N4)=+∞;連接兩拐點的中間節點D,有L(D,N4)=+∞,則該段路徑剪枝結果為:

Path(N4,S)=N4→N6→S

(16)

剪枝完成后最優路徑完整表示如下:

Path(G,S)=G→N4→N6→S

(17)

剪枝前、后路徑對比如圖4所示。其中,紅色路線為路徑剪枝得到的最優路徑。

傳統A*算法和本文改進A*算法的最優路徑對比數據見表1所列。

表1 最優路徑對比

由表1可知,相較于傳統A*算法,本文改進A*算法所得到的最優路徑長度減少20.80%,拐點總數減少83.33%,轉彎總角度減少215.5°,優化效果顯著。

文獻[23]提出的改進A*算法只保留起始點和拐點進行剪枝操作,共線節點在路徑優化的第1步就被忽略,剪枝過程粗放,導致所得最終路徑并非最優,在復雜地圖上優化效果欠佳。本文所提出的改進A*算法優先判斷拐點間的連線是否與障礙物相交,無需逐個節點搜索,縮短了計算時間;同時保留了與障礙物相交和不相交的相鄰連線間的共線節點用于精確搜索,得到最優路徑。

4 實驗分析

4.1 參數ω的選取對結果的影響

為研究不同的轉彎代價補償參數ω對A*算法所得路徑長度和拐彎節點總數的影響,在30×30的柵格地圖中,隨機生成50組起始節點和目標節點,在轉彎代價補償參數ω取不同值時,使用本文改進A*算法進行路徑規劃實驗。實驗過程中,參數ω的變化范圍控制在[0,1.2]之間,取值間隔設置為0.1,記錄改進A*算法關鍵性能參數,性能表現變化趨勢如圖5所示。

圖5 ω不同取值時算法性能

由圖5可知:ω=0時為傳統A*算法,與本文改進A*算法相比,其規劃結果拐點數量最多,路徑長度最長;在進行實際代價估計函數和啟發函數的優化以及對路徑剪枝后,本文改進A*算法規劃所得路徑整體的拐點個數和路徑總長度大大減小;在轉彎代價補償參數ω=0.2時,轉彎次數顯著減少,且路徑長度最短,本文改進的A*算法比傳統A*算法轉彎節點個數減少了29.23%,路徑總長度減少了20.63%,效果最為理想。

因此本文改進A*算法轉彎代價補償參數ω的最佳取值為0.2,下文所有仿真對比實驗皆基于此條件進行。

4.2 仿真結果

為了評估本文提出的基于無人叉車行駛時間優化的改進A*算法的性能,在2.3 GHz處理器、16 GiB運行內存的Windows 11平臺上進行仿真實驗。

本文分別模擬結構化和非結構化環境構造柵格地圖,使用傳統A*算法、蟻群(ant colony optimization,ACO)算法、Dijkstra算法和本文改進A*算法進行路徑規劃,分析并對比4種算法的性能。

4.2.1 結構化環境地圖

本文建立了叉車結構化工作環境柵格地圖,在該地圖上設立相同的起始節點,使用4種算法進行路徑規劃,仿真實驗結果如圖6所示。其中:綠色柵格為起始節點;紅色柵格為目標節點;黑色柵格為障礙物;白色柵格為可通行區域;紅色軌跡為算法規劃所得路徑。

圖6 工作實景柵格地圖仿真結果

工廠地圖上各算法的仿真性能指標結果對比見表2所列。由表2可知:在搜索時間上,本文改進A*算法比傳統A*算法減少了28.10%,比Dijkstra算法減少了34.80%,實時性得到明顯提升;本文改進A*算法所得路徑長度為463.49,比傳統A*算法縮短了4.20%。

表2 4種算法性能指標對比

決定路徑平滑程度的關鍵數據為拐點個數及拐彎總角度。拐點個數越少,拐彎總角度越小,路徑就越平滑,單個工作循環內需要進行的降速制動等操作頻率就越低,行駛時間就越短。從表2還可以看出:本文改進A*算法比傳統A*算法拐點個數減少了46.20%,比Dijkstra算法減少了41.70%,比ACO算法減少了36.40%;拐點個數的減少,使得路徑拐彎總角度明顯減少,這一指標本文改進A*算法比傳統A*算法減少53.60%,比Dijkstra算法減少50.10%,比ACO算法減少45.30%。

綜上分析可知,本文改進A*算法的效率更高,路徑長度更短,且轉彎角度更小,路徑更平滑。

4.2.1 非結構化環境地圖

為了驗證本文改進A*算法的普適性及在復雜環境下的有效性,分別構建30×30和50×50的非結構性地圖用于模擬更為復雜的工作環境。各算法仿真結果如圖7、圖8所示。

圖7 30×30非結構化環境地圖仿真結果

圖8 50×50非結構化環境地圖仿真結果

2種非結構化地圖中各算法性能參數及本文改進A*算法、傳統A*算法、ACO算法和Dijkstra算法的性能對比見表3、表4所列。

表3 30×30地圖各算法性能參數

表4 50×50地圖各算法性能參數

本文改進A*算法旨在降低無人叉車單個工作循環內的行駛時間。從圖7、圖8可以看出,3種改進算法相較于傳統A*算法路徑規劃結果都更平滑,路徑長度更短。但對比2種尺寸地圖下3種改進算法的仿真結果可知:隨著地圖復雜程度增加,ACO算法、Dijkstra算法減少拐點數量、平滑路徑轉彎角度的效果變差,在50×50環境地圖中仍有較多冗余拐點保留;而本文改進A*算法在50×50地圖中路徑剪枝效果仍然穩定,使得拐點個數和轉彎角度大大減小,大幅減少因轉彎而增加的操作時間。

由表4可知:本文改進A*算法在50×50的地圖中比傳統A*算法拐點數量減少47.10%,拐彎總角度減少65.90%,路徑總長度減少2.24%,路徑平滑程度有很大提升;比ACO算法、Dijkstra改進算法表現更穩定,實時性更強,優化效果更好。

5 結 論

針對傳統A*算法路徑規劃結果實際應用于工業無人叉車上的不足,本文提出了一種改進的A*算法對無人叉車行駛時間進行優化。該算法通過引入轉彎代價補償參數設計轉彎行駛時間函數和啟發函數的優化,在保證路徑最優的情況下減少路徑規劃中拐點個數和轉彎總角度,引入自適應權重縮短無人叉車從起始位置到目標位置所需的時間,確保目標可達。仿真實驗結果驗證了該算法的有效性和可靠性。

本文提出的改進A*算法適用于已知環境的路徑規劃,規劃所得路徑拐點少,轉彎角度小,更適用于無人叉車的實際作業,能大大減少無人叉車工作中轉向、剎車次數,提高車身穩定性及工作效率。未來的工作需要考慮單個無人叉車載重不同、重心位置改變時所能跟蹤的最大轉角并進行路徑規劃,進一步考慮在多個無人叉車協同工作的動態環境中得到路徑短、拐點少的平滑路徑,以適應更加多變的工作場景。