陸金柳，王玉槐（通訊作者），金培梁，周詩捷，周清璐，呂平

（1.杭州師范大學(xué)錢江學(xué)院，浙江杭州，310036；2.亞信科技（中國）有限公司，北京，100193）

0 引言

自動導(dǎo)引AGV（Automated Guided Vehicle）叉車，因其高柔性化、高可靠性、高適應(yīng)、高效靈活性的無人化全自動運輸，在物料配送、倉儲碼垛等物流搬運方面得到了廣泛的應(yīng)用。路徑的選擇及優(yōu)化極大地影響著AGV叉車的運輸效率。路徑規(guī)劃是移動機(jī)器人自主導(dǎo)航的關(guān)鍵技術(shù)之一，是指搜索一條從起始點至目標(biāo)點的最優(yōu)無碰路徑［1］。目前，常用的路徑規(guī)劃算法有Dijkstra算法、A＊算法、蟻群算法、遺傳算法、粒子群算法等[2-6]。其中，A＊算法因為能更加高效、快速地求解出已知靜態(tài)環(huán)境的起始點和目標(biāo)點間的最短路徑［7］，從而迅速地完成全局路徑規(guī)劃，因此被廣泛應(yīng)用于移動機(jī)器人的路徑規(guī)劃中。為此，本文結(jié)合AGV叉車的實際工作環(huán)境，研究了A＊算法在啟發(fā)函數(shù)和路徑平滑策略兩方面的改進(jìn)，實現(xiàn)了更優(yōu)的平滑路徑規(guī)劃，為提高AGV叉車的工作效率和工作準(zhǔn)確度提供了良好的基礎(chǔ)。

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

A＊算法是一種狀態(tài)空間中的啟發(fā)式搜索算法。首先，對每個搜索位置進(jìn)行評估，得到最佳位置，再從該最佳位置出發(fā)進(jìn)行搜索直到達(dá)到目標(biāo)。其核心為估價函數(shù)如式（1）所示。

其中， f(n)是從初始狀態(tài)經(jīng)由狀態(tài)n到目標(biāo)狀態(tài)的代價估計， g(n)是在狀態(tài)空間中從初始狀態(tài)到狀態(tài)n的實際代價， h(n)是從狀態(tài)n到目標(biāo)狀態(tài)的最佳路徑的估計代價。啟發(fā)函數(shù)選取節(jié)點到目標(biāo)點的直線距離d，即歐幾里得距離[8]，如式（2）所示。

其中，( Xm, Ym)為目標(biāo)點m的坐標(biāo)，( Xk,Yk)為節(jié)點k的坐標(biāo)。

A＊算法的搜索情況如圖1所示。在以節(jié)點構(gòu)成“田”字型柵格地圖下的搜索過程中，需建立已行點集和可行點集兩個集合。已行點集存放所有搜索過的點和障礙點?？尚悬c集是通過以當(dāng)前節(jié)點為子節(jié)點，搜索其連通4-鄰域節(jié)點而建立，存放當(dāng)前子節(jié)點鄰域范圍內(nèi)允許行走的節(jié)點。然后，搜索可行點集中最小總代價節(jié)點作為其下一節(jié)點，通過回溯可得其父節(jié)點和祖父節(jié)點。。最終，規(guī)劃形成欲行駛的路徑。圖中紅色圓環(huán)代表起始點，藍(lán)色方塊代表目標(biāo)點，黑色方格點代表障礙物，彩色方格點代表搜索過程中需判斷的點。

圖1 A＊算法的搜索過程

由圖可見，傳統(tǒng)算法所搜索的點占了大部分地圖，運算時間久，效率低，且所規(guī)劃的路徑存在10處拐點，直接導(dǎo)致AGV叉車在實際運行中不斷加減速和轉(zhuǎn)彎。傳統(tǒng)A＊算法要遍歷可行點集的所有點，查找估價函數(shù) f(n)值最小的節(jié)點，每檢查一個節(jié)點都需執(zhí)行一次。添加新節(jié)點或更新下一節(jié)點時，也都需判斷節(jié)點是否在可行點集或已行點集中，因此，其存在占用內(nèi)存大、搜索范圍廣、運算時間久、效率低、路徑不平滑等問題。為此，本文結(jié)合AGV叉車實際工作需求，提出一種改進(jìn)的A＊算法，優(yōu)化上述問題。

2 改進(jìn)型A＊算法

■2.1 啟發(fā)函數(shù)的改進(jìn)

傳統(tǒng)A＊算法的啟發(fā)函數(shù)只具備距離信息，而缺少搜索方向與目標(biāo)方向的一致性匹配。為此，本文提出目標(biāo)方向趨向啟發(fā)，引入余弦相似度到歐幾里得距離模型，形成新的啟發(fā)函數(shù)，如式（3）所示，從而使搜索方向更趨近于目標(biāo)方向，提高搜索效率。

其中， W0和 W1為靜態(tài)權(quán)重，θ 為起始點到目標(biāo)點的矢量和父節(jié)點與當(dāng)前子節(jié)點矢量的夾角。 cos(θ)表示兩個矢量的余弦相似度，用來衡量兩個矢量方向的一致性。其值越接近1，表明夾角越接近0度，即兩個矢量方向越一致。

設(shè)任意路徑矢量上有三個點 A、B和C，其坐標(biāo)分別為(x1, y1)、(x2, y2)和( x3, y3)。點A到B的矢量為AB,點B到C的矢量為BC，將AB平移，使點A與點B重合,得到矢量BD ,則BD與BC的夾角為θ，形成矢量三角形，如圖2所示。

圖2 路徑節(jié)點形成的矢量三角形

由圖中幾何關(guān)系可得，

其中，i和j分別代表x和y方向的單位向量。則有：

基于上述方法求得的余弦相似度，最大值為1，最小值為-1。若其值趨于1，則兩矢量趨于同向；若其值趨于0，則兩矢量趨于垂直；若其值趨于-1，則兩矢量趨于反向。

考慮到改進(jìn)后的新啟發(fā)函數(shù)中歐幾里得距離和余弦相似度的不同量綱會對結(jié)果產(chǎn)生影響，可采用Min-Max標(biāo)準(zhǔn)化[9]、Z-Score標(biāo)準(zhǔn)化[10]等方法進(jìn)行數(shù)據(jù)標(biāo)準(zhǔn)化處理。

■2.2 路徑平滑策略

傳統(tǒng)A＊算法所規(guī)劃的路徑僅僅是數(shù)學(xué)上的最優(yōu)路徑，存在較多拐點。而在實際復(fù)雜的車間環(huán)境中，考慮到空間障礙物的分布及低速轉(zhuǎn)彎、加減速等實際情況，往往需要盡量減少轉(zhuǎn)彎次數(shù)以有效提高AGV叉車運行效率。

設(shè)起始點A和目標(biāo)點B構(gòu)成“田”字型路線，如圖3所示。由圖可見，在單向行駛的前提下，由起始點A可經(jīng)過6條路徑到達(dá)目標(biāo)點B，且該6條路徑具有相同的長度。其中，路徑(1→4→7→8→9)和(1→2→3→6→9),用黑色實線表示，均存在1個拐點，其余經(jīng)過中間節(jié)點5所構(gòu)成的路徑，均存在2個或3個拐點。顯然，在路徑長度相同條件下，拐點數(shù)量少的路徑應(yīng)作為優(yōu)選路徑被規(guī)劃，而其余路徑則宜作為備選路徑?？紤]到直線行駛速度比轉(zhuǎn)彎速度更快，在一定程度上，甚至可以以少量增加直線距離換取減少拐點數(shù)量，達(dá)到整體路徑更優(yōu)?？梢姡诓豢紤]會車的前提下，拐點是路徑平滑優(yōu)化的重要考慮策略。

圖3 “田”字型路線

平滑策略是基于路徑代價和拐點數(shù)量的綜合考量。在路徑代價相同的前提下，優(yōu)選拐點數(shù)最少的路徑。具體通過計算祖父節(jié)點至父節(jié)點的矢量方向，進(jìn)而沿該方向搜尋位于該父節(jié)點下的子節(jié)點，然后，判斷該子節(jié)點是否位于可行點集，對于可行子節(jié)點計算路徑總代價，若與優(yōu)化前的點代價相同，則用該子節(jié)點更替優(yōu)化前的節(jié)子點進(jìn)行平滑優(yōu)化。以圖4所示拐點優(yōu)化為例，設(shè)優(yōu)化前的子節(jié)點位于其父節(jié)點正下方，顯然優(yōu)化前和優(yōu)化后具有相同路徑代價，則沿祖父節(jié)點Pi-2至父節(jié)點Pi-1的方向，優(yōu)選當(dāng)前可行節(jié)點Pi作為子節(jié)點，用父節(jié)點右側(cè)的子節(jié)點更替下方的子節(jié)點，最終到達(dá)下一節(jié)點Pi+1，最終獲得拐點更少的平滑路徑。

圖4 拐點優(yōu)化圖

另外，考慮到環(huán)境地圖中障礙物因素造成的空間較為狹窄，拐點較多時，則在未平滑優(yōu)化的路徑中回溯拐點較為集中處，通過引入路徑松弛閾值少量增加路徑長度，減少直角轉(zhuǎn)向，優(yōu)選拐點數(shù)少的路徑，以避免AGV叉車在實際運行中不斷減速轉(zhuǎn)向，提高整體效率。

3 仿真驗證及分析

■3.1 地圖構(gòu)建

為驗證本文所提改進(jìn)算法的有效性，采用仿真軟件平臺MATLAB R2017a進(jìn)行仿真。構(gòu)建20×20的柵格地圖，如圖5所示。圖中紅色圓環(huán)代表起始點，藍(lán)色方塊代表目標(biāo)點，黑色方格點代表障礙物，彩色方格點代表搜索過程中需判斷的點。

圖5 20×20柵格地圖

■3.2 結(jié)果分析

本文算法的流程圖如圖6所示。為了對傳統(tǒng)A＊算法和改進(jìn)后A＊算法進(jìn)行對比分析，分別進(jìn)行了兩組測試。測試1中，起始點和目標(biāo)點的坐標(biāo)分別為（7,13）和（18,2）,相應(yīng)的搜索情況和路徑結(jié)果如圖7所示。測試2中，起始點和目標(biāo)點的坐標(biāo)分別為（2,19）和（14,7），相應(yīng)的搜索情況和路徑結(jié)果如圖8所示。兩組測試的相關(guān)結(jié)果數(shù)據(jù)如表1所示。

圖6 算法流程圖

圖7 測試1的搜索情況和路徑結(jié)果

圖8 測試2的搜索情況和路徑結(jié)果

表1 算法實驗數(shù)據(jù)對比

由表1可見，在測試1的規(guī)劃中，本文算法減少了4個拐點，減少率達(dá)到了33.33%；減少了53個搜索點，減少率達(dá)46.90%；節(jié)約了0.18s時間，效率提高了18.18%。在測試2的規(guī)劃中本文算法減少了6個拐點，減少率達(dá)到了46.15%；減少了77個搜索點，減少率達(dá)51.68%；節(jié)約了0.27s時間，效率提高了23.90%。在測試1的規(guī)劃中，本文算法與傳統(tǒng)算法保持相同的路徑長度；而在測試2的規(guī)劃中，本文算法比傳統(tǒng)算法增加了2格的路徑長度。但在實際AGV運行中，相比于多6次直角轉(zhuǎn)向而言，直線距離增加2個節(jié)點間距的整體效率將更高。綜上可見，本文改進(jìn)后的A＊算法運算速度明顯提高，搜索效率加快，拐點數(shù)量減少，使路徑更加平滑。

4 結(jié)論

在柵格地圖條件下，針對傳統(tǒng)A＊算法規(guī)劃路徑不快且路徑拐點多而不平滑的問題，提出一種改進(jìn)的A＊算法。一方面，引入余弦相似度，并融合到歐幾里得距離模型中，形成新的啟發(fā)函數(shù)，使搜索方向更趨近于目標(biāo)方向，提高了路徑規(guī)劃效率。另一方面，利用幾何法形成路徑平滑策略，消除了多余拐點，使路徑更加平滑，更為符合AGV叉車的實際運動情況。仿真結(jié)果表明，本文改進(jìn)后的算法能夠有效提高路徑規(guī)劃效率，并規(guī)劃出更為平滑的路徑。