王邁新，閆 莉，李雨菲

（西安工業(yè)大學(xué) 機(jī)電工程學(xué)院，西安 710021）

AGV 是一種服務(wù)型機(jī)器人，其主要功能是幫助實(shí)現(xiàn)物料運(yùn)輸[1]，其中路徑規(guī)劃是AGV 的一項(xiàng)關(guān)鍵技術(shù)，即尋找一條從起點(diǎn)到終點(diǎn)能夠避開(kāi)障礙物的安全路徑。解決路徑規(guī)劃問(wèn)題的算法有智能搜索算法（如遺傳算法、蟻群算法、粒子群算法等）、基于人工智能算法（如Q-Learning 算法、深度學(xué)習(xí)）、基于幾何模型算法（如A* 算法、Voronoi 圖）和基于局部避障算法（如人工勢(shì)場(chǎng)法、動(dòng)態(tài)窗口法）[2]。其中，A*算法具有計(jì)算量小、尋路時(shí)間短的優(yōu)點(diǎn)[3]，但是在柵格環(huán)境下傳統(tǒng)的A* 算法規(guī)劃的路徑也存在著轉(zhuǎn)彎次數(shù)多、路徑不平滑、路徑經(jīng)過(guò)障礙物頂點(diǎn)的問(wèn)題。文獻(xiàn)[4]運(yùn)用切線交點(diǎn)畫(huà)圓法使轉(zhuǎn)折點(diǎn)進(jìn)行圓弧過(guò)渡，并提出了設(shè)置虛擬障礙物的避障方式，但是最終的路徑距離反而增加；文獻(xiàn)[5]通過(guò)剔除路徑上的冗余節(jié)點(diǎn)和不必要節(jié)點(diǎn)使A* 算法規(guī)劃后的AGV路徑拐點(diǎn)更少；文獻(xiàn)[6]則往A* 算法啟發(fā)函數(shù)中引入父節(jié)點(diǎn)啟發(fā)函數(shù)和切比雪夫距離，并選取關(guān)鍵節(jié)點(diǎn)使最終的路徑節(jié)點(diǎn)大大減少，路徑更平滑，但是路徑經(jīng)過(guò)障礙物的頂點(diǎn)。

為解決A* 算法規(guī)劃的AGV 路徑存在轉(zhuǎn)彎點(diǎn)多、經(jīng)過(guò)障礙物頂點(diǎn)以及不平滑的問(wèn)題，本文對(duì)A*算法進(jìn)行改進(jìn)。首先，在代價(jià)函數(shù)中引入AGV 從起點(diǎn)行駛至當(dāng)前點(diǎn)的路徑長(zhǎng)度和起點(diǎn)行駛至當(dāng)前點(diǎn)的父節(jié)點(diǎn)的時(shí)間成本；再去除當(dāng)前搜索下使路徑經(jīng)過(guò)障礙物頂點(diǎn)的子節(jié)點(diǎn)，使AGV 在行駛的過(guò)程中能夠與障礙物保持安全距離；最后用45°圓弧和90°圓弧代替折線轉(zhuǎn)彎使行駛過(guò)程更加平滑。此外，建立以搬運(yùn)任務(wù)時(shí)間最短為目標(biāo)的單AGV 路徑規(guī)劃模型，通過(guò)仿真驗(yàn)證得出，改進(jìn)后的A* 算法在轉(zhuǎn)彎次數(shù)、路徑長(zhǎng)度以及AGV 行駛的時(shí)間上都有改善。

1 構(gòu)建電子地圖

以某汽車(chē)差速器外殼零件加工車(chē)間為背景，采用柵格法構(gòu)建電子地圖，將車(chē)間建模為40×40 的柵格圖，每個(gè)柵格對(duì)應(yīng)的現(xiàn)實(shí)尺寸為2 m×2 m。柵格地圖中主要由可通行柵格和障礙柵格組成。MATLAB繪制的車(chē)間柵格地圖如圖1 所示。其中成品庫(kù)面積約為240 m2，半成品庫(kù)面積約為520 m2，產(chǎn)線的占地面積依次約為336 m2。產(chǎn)線有且僅有一個(gè)上料點(diǎn)和一個(gè)下料點(diǎn)。

圖1 車(chē)間柵格地圖Fig.1 Workshop grid map

AGV 在車(chē)間內(nèi)主要完成產(chǎn)線半成品上料以及成品下料，以下是AGV 在執(zhí)行上下料任務(wù)的具體流程：

（1）半成品上料

AGV 接到上料任務(wù)后會(huì)從空貨架暫存區(qū)搬運(yùn)一個(gè)空貨架前往半成品庫(kù)，由叉車(chē)將整托貨物放置貨架上；隨后AGV 將整托貨物搬運(yùn)至產(chǎn)線上料區(qū)進(jìn)行空滿交換；完成空滿交換后AGV 會(huì)將攜帶有空容器的貨架搬運(yùn)至叉車(chē)交接區(qū)，叉車(chē)將貨架上的空容器回收；最后AGV 將空貨架搬運(yùn)至空貨架暫存區(qū)，完成上料任務(wù)。

（2）成品下料

AGV 接到下料任務(wù)后會(huì)從空貨架暫存區(qū)搬運(yùn)一個(gè)空貨架前往叉車(chē)交接區(qū)，叉車(chē)將容器放置在貨架上；隨后AGV 將帶有容器的貨架搬運(yùn)至產(chǎn)線下料區(qū)進(jìn)行空滿交換；完成空滿交換后AGV 會(huì)將載有成品的貨架搬運(yùn)至成品庫(kù)；最后AGV 將空貨架從成品庫(kù)交接區(qū)搬運(yùn)至空貨架暫存區(qū)，完成下料任務(wù)。

2 單AGV 路徑規(guī)劃模型

2.1 目標(biāo)設(shè)定與基本假設(shè)

AGV 在車(chē)間內(nèi)的運(yùn)行參數(shù)，如表1 所示。

表1 AGV 運(yùn)行參數(shù)Tab.1 Operating parameters of AGV

（1）目標(biāo)設(shè)定

本文在構(gòu)建數(shù)學(xué)模型時(shí)以最短配送時(shí)間為原則進(jìn)行路徑規(guī)劃，從以下2 個(gè)方面來(lái)實(shí)現(xiàn)以最短時(shí)間完成將半成品送至產(chǎn)線或者將成品送至成品庫(kù)的任務(wù)：

1）路徑規(guī)劃過(guò)程中應(yīng)盡量減少AGV 轉(zhuǎn)彎的次數(shù)；

2）AGV 總體運(yùn)輸距離盡量短。

（2）基本假設(shè)

為了更好地達(dá)到目標(biāo)，需要作以下假設(shè)：

1）AGV 小車(chē)行駛時(shí)速度保持勻速；

2）AGV 運(yùn)行環(huán)境為靜態(tài)環(huán)境，小車(chē)行駛過(guò)程中不會(huì)遇到動(dòng)態(tài)障礙；

3）AGV 有充足的電量，無(wú)需充電，能夠滿足執(zhí)行任務(wù)過(guò)程中電量的需要；

4）不考慮AGV 舉升或下放貨架的時(shí)間；

5）不考慮叉車(chē)往周轉(zhuǎn)貨架上裝貨時(shí)間以及從周轉(zhuǎn)貨架上卸貨時(shí)間；

6）不考慮AGV 在上料區(qū)及下料區(qū)進(jìn)行物料空滿交換的時(shí)間。

2.2 參數(shù)與變量定義

（1）基于以上假設(shè)，在建立模型前需要對(duì)模型中所需要的參數(shù)進(jìn)行定義：

w：物料運(yùn)輸任務(wù)編號(hào)；

i：AGV 空車(chē)行駛路徑上拐點(diǎn)的編號(hào)；

m：AGV 背貨行駛路徑上拐點(diǎn)的編號(hào)；

Ve：AGV 空車(chē)時(shí)的速度；

Vf：AGV 背貨時(shí)的速度；

θi：AGV 在空車(chē)狀態(tài)下第i 個(gè)拐點(diǎn)時(shí)轉(zhuǎn)過(guò)的角度；

θm：AGV 在載貨狀態(tài)下第m 個(gè)拐點(diǎn)時(shí)轉(zhuǎn)過(guò)的角度；

ωe：AGV 空車(chē)時(shí)旋轉(zhuǎn)的角速度；

ωf：AGV 背貨時(shí)旋轉(zhuǎn)的角速度；

L（i，i+1）：AGV 空車(chē)狀態(tài)下從第i 個(gè)拐點(diǎn)到第（i+1）個(gè)拐點(diǎn)之間行駛的距離；

L（m，m+1）：AGV 在載貨狀態(tài)下從第m 個(gè)拐點(diǎn)到第（m+1）個(gè)拐點(diǎn)之間行駛的距離；

（2）決策變量

2.3 目標(biāo)函數(shù)與約束條件

在基于基本假設(shè)的前提下，AGV 執(zhí)行任務(wù)所花費(fèi)的時(shí)間主要由在拐點(diǎn)之間路徑上的時(shí)間成本以及轉(zhuǎn)彎增加的時(shí)間成本組成。以小車(chē)執(zhí)行任務(wù)所花費(fèi)的時(shí)間最短為目標(biāo)可以構(gòu)建目標(biāo)函數(shù)，其表達(dá)式如式（1）所示：

約束條件：

式（2）表示車(chē)間內(nèi)每個(gè)搬運(yùn)任務(wù)在任意時(shí)間只能由1 臺(tái)AGV 完成，A 表示AGV；式（3）表示任意時(shí)間1 臺(tái)AGV 只能完成1 個(gè)搬運(yùn)任務(wù)。

3 改進(jìn)A*算法

3.1 改進(jìn)代價(jià)函數(shù)

針對(duì)A* 算法規(guī)劃的路徑轉(zhuǎn)彎次數(shù)多，對(duì)其代價(jià)函數(shù)進(jìn)行改進(jìn)，改進(jìn)后的代價(jià)函數(shù)為

式（4）中：w（n-1）表示過(guò)去已規(guī)劃完成的路徑長(zhǎng)度；d（n）表示父節(jié)點(diǎn)n-1 到子節(jié)點(diǎn)n 的距離；t（n-1）表示AGV 在已規(guī)劃完成的路徑上行駛的時(shí)間成本。

3.2 去除使路徑經(jīng)過(guò)障礙物的子節(jié)點(diǎn)

針對(duì)A* 算法規(guī)劃出的AGV 路徑在柵格圖中會(huì)經(jīng)過(guò)障礙物頂點(diǎn)的問(wèn)題，本文提出當(dāng)前在搜索節(jié)點(diǎn)時(shí)去除使路徑經(jīng)過(guò)障礙物頂點(diǎn)的子節(jié)點(diǎn)的方式來(lái)解決。

如圖2 所示，A* 算法改進(jìn)前后避障路線，假設(shè)起點(diǎn)的坐標(biāo)為（x，y），柵格邊長(zhǎng)為1，則目標(biāo)點(diǎn)的坐標(biāo)為（x，y+2），起點(diǎn)周?chē)赏ㄐ械淖庸?jié)點(diǎn)有（x+1，y+1），（x+1，y），（x-1，y），（x-1，y+1）。根據(jù)A* 算法中f（n）最小的子節(jié)點(diǎn)為下一節(jié)點(diǎn)的原理可知，AGV 之后將會(huì)行駛至子節(jié)點(diǎn)（x+1，y+1）或子節(jié)點(diǎn)（x-1，y+1），但是會(huì)出現(xiàn)AGV 的路徑會(huì)經(jīng)過(guò)障礙物的頂點(diǎn)的情況。改進(jìn)后A* 算法將子節(jié)點(diǎn)（x-1，y+1）和子節(jié)點(diǎn)（x+1，y+1）從當(dāng)前可通行的節(jié)點(diǎn)中去除，則當(dāng)前總代價(jià)f（n）最小的子節(jié)點(diǎn)為（x-1，y）和（x+1，y）。如圖2 所示，改進(jìn)后的A* 算法避障，AGV 從起點(diǎn)（x，y）行駛至節(jié)點(diǎn)（x-1，y），在節(jié)點(diǎn)（x-1，y）處再次計(jì)算得出下一步節(jié)點(diǎn)到（x-1，y+1）處，最終實(shí)現(xiàn)以直角轉(zhuǎn)折的方式規(guī)避障礙物。

3.3 圓弧轉(zhuǎn)彎

傳統(tǒng)A* 算法規(guī)劃的AGV 路徑上會(huì)有許多拐角尖點(diǎn)，當(dāng)AGV 行駛至拐彎尖點(diǎn)時(shí)，需要先減速停車(chē)，然后原地旋轉(zhuǎn)45°或者90°完成轉(zhuǎn)向，整個(gè)行駛過(guò)程不夠平順，因此本文用90°圓弧線和45°圓弧線來(lái)代替原來(lái)的90°折線轉(zhuǎn)彎和45°折線轉(zhuǎn)彎。

由A* 算法規(guī)劃出的路徑可知，AGV 的轉(zhuǎn)彎分為45°轉(zhuǎn)彎和90°轉(zhuǎn)彎。AGV 轉(zhuǎn)彎情況如表2 所示，45°轉(zhuǎn)彎共有16 種情況，90°轉(zhuǎn)彎共有8 種情況。

表2 AGV 轉(zhuǎn)彎情況Tab.2 Various turning conditions of AGV

假定柵格的尺寸為1×1，可以求得90°轉(zhuǎn)彎和45°轉(zhuǎn)彎時(shí)的圓弧半徑和圓弧上各個(gè)點(diǎn)的坐標(biāo)：

（1）90°轉(zhuǎn)彎

90°圓弧轉(zhuǎn)彎如圖3 所示，AGV 從起點(diǎn)（x1，y1）行駛到目標(biāo)點(diǎn)（x2，y2）經(jīng)歷了90°圓弧轉(zhuǎn)彎（轉(zhuǎn)彎情況屬于表2 中第20 號(hào)），圓弧半徑R=1/2，x0=（x1+x2）/2，y0=（y1+y2）/2，α 為圓弧半徑與水平方向的夾角，則有：

圖3 90°圓弧轉(zhuǎn)彎Fig.3 90°arc turn

通過(guò)公式（8）可求得圓弧上各個(gè)點(diǎn)的坐標(biāo)，同理，運(yùn)用相同的方法可以得出表2 中其余7 種90°轉(zhuǎn)彎情況下的圓弧上各點(diǎn)的坐標(biāo)。

（2）45°轉(zhuǎn)彎

如圖4 所示，AGV 從起點(diǎn)（x1，y1）行駛至目標(biāo)點(diǎn)（x2，y2）經(jīng)歷了45°圓弧轉(zhuǎn)彎（轉(zhuǎn)彎情況屬于表2 中第4 號(hào)），經(jīng)過(guò)計(jì)算，圓弧半徑R=圓弧對(duì)應(yīng)的圓心坐標(biāo)x0=x1+0.5，y0=y1-R，β 為圓弧半徑與水平方向的夾角，則有：

圖4 45°圓弧轉(zhuǎn)彎Fig.4 45°arc turn

通過(guò)式（9）可求得圓弧上各個(gè)點(diǎn)的坐標(biāo)，同理，運(yùn)用相同的方法可以得出表2 中其余15 種45°轉(zhuǎn)彎情況下的圓弧上各點(diǎn)的坐標(biāo)。

3.4 基于改進(jìn)后A*算法的AGV 路徑規(guī)劃模型

改進(jìn)A* 算法下AGV 在行駛的過(guò)程中不再需要通過(guò)停車(chē)轉(zhuǎn)向來(lái)實(shí)現(xiàn)轉(zhuǎn)彎，可以直接進(jìn)行彎道行駛。因此AGV 整個(gè)行駛的時(shí)間是由AGV 直線行駛的時(shí)間、彎道行駛的時(shí)間以及在工作站點(diǎn)處轉(zhuǎn)向的時(shí)間組成。在基于原有的基本假設(shè)下，改進(jìn)后的目標(biāo)函數(shù)如式（10）所示：

其中參數(shù)如表3 所示。

表3 參數(shù)Tab.3 Parameter

4 仿真驗(yàn)證

利用MATLAB 2017a 對(duì)改進(jìn)后的A* 算法進(jìn)行驗(yàn)證，利用傳統(tǒng)A* 算法和改進(jìn)A* 算法對(duì)AGV 執(zhí)行上料任務(wù)規(guī)劃的路徑，如圖5 和圖6 所示；利用傳統(tǒng)A*算法和改進(jìn)A* 算法對(duì)AGV 執(zhí)行下料任務(wù)規(guī)劃的路徑，如圖7 和圖8 所示。從圖中可以看出改進(jìn)后A* 算法規(guī)劃的路徑轉(zhuǎn)彎點(diǎn)更少，路徑更平滑，且AGV 在行駛的過(guò)程中能夠與障礙物保持安全距離。將仿真得到的轉(zhuǎn)彎次數(shù)與路徑長(zhǎng)度做記錄，如表4 所示。

表4 A*算法改進(jìn)前后性能比較Tab.4 Performance comparison of A* algorithm before and after improvement

圖5 AGV 執(zhí)行上料任務(wù)路線圖（傳統(tǒng)A*算法）Fig.5 Route map of AGV when performing the loading task（traditional A* algorithm）

圖6 AGV 執(zhí)行上料任務(wù)路線圖（改進(jìn)A*算法）Fig.6 Route map of AGV when performing the loading task（improved A* algorithm）

圖7 AGV 執(zhí)行下料任務(wù)路線圖（傳統(tǒng)A*算法）Fig.7 Route map of AGV when executing the blanking task（traditional A* algorithm）

圖8 AGV 執(zhí)行下料任務(wù)路線圖（改進(jìn)A*算法）Fig.8 Route map of AGV when executing the blanking task（improved A* algorithm）

通過(guò)對(duì)A* 算法改進(jìn)前后的性能比較可以得出，改進(jìn)后的A* 算法使AGV 執(zhí)行任務(wù)時(shí)間縮短，距離縮短了2.54%，路徑上轉(zhuǎn)彎次數(shù)減少了60%。

5 結(jié)語(yǔ)

本文在傳統(tǒng)A* 算法的基礎(chǔ)上改進(jìn)其代價(jià)函數(shù)，并且在算法搜索節(jié)點(diǎn)時(shí)刪除當(dāng)前使路徑經(jīng)過(guò)障礙物頂點(diǎn)的子節(jié)點(diǎn)，最后利用45°圓弧線和90°圓弧線來(lái)代替折線轉(zhuǎn)彎對(duì)路徑進(jìn)行處理。結(jié)果表明，改進(jìn)后的A* 算法規(guī)劃的路徑距離更短，轉(zhuǎn)彎次數(shù)更少，相應(yīng)地減少了AGV 搬運(yùn)的時(shí)間，并且AGV 在整個(gè)行駛的過(guò)程中能夠與障礙物保持安全距離，更加滿足實(shí)際需求。