基于改進A＊算法的車間AGV 路徑規(guī)劃

王邁新，閆 莉，李雨菲

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

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

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

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

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

圖1 車間柵格地圖Fig.1 Workshop grid map

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

（1）半成品上料

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

（2）成品下料

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

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

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

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

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

（1）目標設(shè)定

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

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

2）AGV 總體運輸距離盡量短。

（2）基本假設(shè)

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

1）AGV 小車行駛時速度保持勻速；

2）AGV 運行環(huán)境為靜態(tài)環(huán)境，小車行駛過程中不會遇到動態(tài)障礙；

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

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

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

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

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

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

w：物料運輸任務(wù)編號；

i：AGV 空車行駛路徑上拐點的編號；

m：AGV 背貨行駛路徑上拐點的編號；

Ve：AGV 空車時的速度；

Vf：AGV 背貨時的速度；

θi：AGV 在空車狀態(tài)下第i 個拐點時轉(zhuǎn)過的角度；

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

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

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

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

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

（2）決策變量

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

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

約束條件：

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

3 改進A*算法

3.1 改進代價函數(shù)

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

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

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

針對A* 算法規(guī)劃出的AGV 路徑在柵格圖中會經(jīng)過障礙物頂點的問題，本文提出當前在搜索節(jié)點時去除使路徑經(jīng)過障礙物頂點的子節(jié)點的方式來解決。

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

3.3 圓弧轉(zhuǎn)彎

傳統(tǒng)A* 算法規(guī)劃的AGV 路徑上會有許多拐角尖點，當AGV 行駛至拐彎尖點時，需要先減速停車，然后原地旋轉(zhuǎn)45°或者90°完成轉(zhuǎn)向，整個行駛過程不夠平順，因此本文用90°圓弧線和45°圓弧線來代替原來的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)彎時的圓弧半徑和圓弧上各個點的坐標：

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

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

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

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

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

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

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

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

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

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

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

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

4 仿真驗證

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

表4 A*算法改進前后性能比較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ù)路線圖（改進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ù)路線圖（改進A*算法）Fig.8 Route map of AGV when executing the blanking task（improved A* algorithm）

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

5 結(jié)語

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