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

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

0 引言

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

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

A＊算法是一種狀態(tài)空間中的啟發(fā)式搜索算法。首先，對(duì)每個(gè)搜索位置進(jìn)行評(píng)估，得到最佳位置，再?gòu)脑撟罴盐恢贸霭l(fā)進(jìn)行搜索直到達(dá)到目標(biāo)。其核心為估價(jià)函數(shù)如式（1）所示。

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

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

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

圖1 A＊算法的搜索過(guò)程

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

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)重，θ 為起始點(diǎn)到目標(biāo)點(diǎn)的矢量和父節(jié)點(diǎn)與當(dāng)前子節(jié)點(diǎn)矢量的夾角。 cos(θ)表示兩個(gè)矢量的余弦相似度，用來(lái)衡量?jī)蓚€(gè)矢量方向的一致性。其值越接近1，表明夾角越接近0度，即兩個(gè)矢量方向越一致。

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

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

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

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

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

考慮到改進(jìn)后的新啟發(fā)函數(shù)中歐幾里得距離和余弦相似度的不同量綱會(huì)對(duì)結(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)路徑，存在較多拐點(diǎn)。而在實(shí)際復(fù)雜的車間環(huán)境中，考慮到空間障礙物的分布及低速轉(zhuǎn)彎、加減速等實(shí)際情況，往往需要盡量減少轉(zhuǎn)彎次數(shù)以有效提高AGV叉車運(yùn)行效率。

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

圖3 “田”字型路線

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

圖4 拐點(diǎn)優(yōu)化圖

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

3 仿真驗(yàn)證及分析

■3.1 地圖構(gòu)建

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

圖5 20×20柵格地圖

■3.2 結(jié)果分析

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

圖6 算法流程圖

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

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

表1 算法實(shí)驗(yàn)數(shù)據(jù)對(duì)比

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

4 結(jié)論

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