AGV復合自主路徑規(guī)劃方法研究

肖獻強，王鼎用，王家恩，耿奕旻

（合肥工業(yè)大學機械工程學院，安徽 合肥 230009）

1 引言

如今，工廠逐漸轉(zhuǎn)向智能化的發(fā)展趨勢愈加明顯，AGV（Au‐tomated Guided Vehicle）成為眾多學者研究的熱點課題。路徑規(guī)劃作為AGV智能化的核心部分，目前主要有兩種規(guī)劃方式：基于環(huán)境已知的全局路徑規(guī)劃和基于環(huán)境未知的局部路徑規(guī)劃方法。在這兩種類型的規(guī)劃方法中，主要有Dijkstra算法[1]、蟻群算法[2]、人工勢場法[3]、遺傳算法[4]、A*算法[5-7]、D*算法[8]等。在工廠的實際應用中，AGV的工況具有大范圍、動態(tài)性、人機混雜的3種特征?；诖耍芯拷鉀QAGV在動態(tài)環(huán)境下的自動避讓和動態(tài)路徑規(guī)劃顯得尤為重要。國內(nèi)外相關(guān)領(lǐng)域的學者提出了全局路徑規(guī)劃與局部路徑規(guī)劃相互結(jié)合的方式，文獻［9］提出了將A*算法與人工勢場法相結(jié)合的方式，其優(yōu)化了力源，將AGV后面的斥力去除及最大角度的優(yōu)化，但是仍然沒有解決局部最優(yōu)的根本問題。文獻［10］將文化基因算法與Morphin算法相結(jié)合，雖然作者對機器人混合路徑規(guī)劃進行了改進，但是此路徑規(guī)劃算法較為復雜。

針對提高AGV實時路徑規(guī)劃的效率，提出了將A*算法與D*算法相結(jié)合的自主路徑規(guī)劃方法，主要思想是：AGV在已經(jīng)創(chuàng)建的柵格地圖上設置全局路徑的起始點與目標點，根據(jù)路徑的起始點與目標點調(diào)用A*算法生成全局路徑；當AGV在全局路徑上行駛檢測到障礙物時，將路徑上障礙物的下一點設置為局部路徑的目標點，根據(jù)當前點與局部路徑目標點確定局部路徑搜索的柵格地圖，較小的路徑搜索范圍，提高了路徑規(guī)劃的實時性。

2 復合路徑規(guī)劃方法

2.1 A＊算法

A*算法作為經(jīng)典的路徑搜索算法，是最有效的直接搜索算法，其搜索的方式是在Dijkstra算法的基礎上采用啟發(fā)式搜索算法，其啟發(fā)式估價函數(shù)如下：

式中：f(n)—節(jié)點n的估價函數(shù)；g(n)—從起始點到節(jié)點n的實際的代價；h(n)—從節(jié)點n到目標點的預估代價值。其中h(n)有3種方式預估代價值，分別有曼哈頓距離、歐幾里得距離、對角線距離。

2.2 D＊算法

D*算法，即為動態(tài)的A*算法，其通過一個維護一個優(yōu)先隊列來對場景中的路徑節(jié)點進行搜索，用Dijstra算法從目標節(jié)點向起始節(jié)點搜索，儲存路網(wǎng)中目標點到各個節(jié)點的最短路徑和該位置到目標點的實際值，如式（2）所示：

式中：h(n)—當前點到目標點的實際代價值；c(next，n)—當前點到下一節(jié)點的新權(quán)值，next—下一節(jié)點的原實際值。

2.3 這里的復合路徑規(guī)劃模型

在柵格地圖上，AGV自主地根據(jù)起始點與目標點以及障礙物的位置關(guān)系，基于曼哈頓啟發(fā)搜索方式的A*算法搜索得到從起始點到目標點且繞開障礙物的一條路徑。假設當前點的位置為(x i,y i)，目標點的位置為(x j,y j)，移動單位距離的代價為P，則曼哈頓的距離求解公式如示（3）：

當AGV在行駛過程中檢測到障礙物時，在全局路徑上搜索和設置局部路徑目標點，如圖1所示。

圖1 復合自主路徑規(guī)劃示意圖Fig.1 Schematic Diagram of Composite Autonomous Path Planning Method

根據(jù)當前點與局部路徑目標點確定的虛線柵格地圖區(qū)域，將其設置為局部路徑搜索范圍。調(diào)用D*算法生成局部路徑，將局部路徑與全局路徑進行拼接，實現(xiàn)AGV當前位置到目標位置的全局規(guī)劃路徑更新，完成實時自主避障的功能。

2.4 復合路徑規(guī)劃數(shù)學方法

在AGV行駛中，根據(jù)環(huán)境的動態(tài)變化初始化的柵格地圖,創(chuàng)建一個M×N的數(shù)學矩陣A M×N：

矩陣式（4）中，任意元素ai j代表的含義具體如下：0—表示空閑點，1—障礙點；2—起始點；3—目標點；8—路徑點。假設此時矩陣A M×N中為沒有障礙物，則A M×N中的內(nèi)部元素全為0，在柵格矩陣中設置起始點為A［f］［k］，設置目標點為A［g］［h］，起始點與目標點的相對距離大于2個元素距離。定義矩陣A M×N中行向量坐標增大的方向為路徑搜索的Y軸正方向，列向量坐標增大的方向為路徑搜索的X軸正方向，設置起始點路徑搜索的方向為Y軸正方向。根據(jù)A*算法的啟發(fā)式函數(shù)搜索生成全局路徑，在生成的全局路徑中，將路徑上任意相互正交相鄰3點的正交點去除，得到如式（5）所示包含路徑的矩陣：

假設修剪的拐點數(shù)為x，根據(jù)起始點A［f］［k］與目標點A［g］［h］，得到從起始到目標點的總耗費為：

若在柵格地圖坐標為上存在障礙點，則在矩陣中路徑上設置障礙點為A M×N[i][j]=1，則表示為如下的矩陣：

根據(jù)具體生成的路徑數(shù)據(jù)，設置局部路徑的起始點和目標點。在生成的路徑上，將AGV當前點A M×N[m][n]設置為起始點，將障礙點的下一點A M×N[s][t]設置為局部路徑的目標點，并根據(jù)局部路徑起始站點與目標站點在矩陣中位置確定包含起始點與目標站點的局部柵格地圖，具體確定方式如下：

截取橫向的矩陣，設矩陣E|m-s|×M的表示為：

截取縱向的矩陣，設矩陣E N×|n-t|的表示為：

則截取后的矩陣為：

此時調(diào)用D*算法在生成的局部地圖中規(guī)劃局部路徑，設局部路徑的拐點數(shù)為y，則局部路徑從起始點到目標點的耗費為：

假設全局路徑上路徑局部路徑的數(shù)量為z，每個局部路徑避開路徑上的障礙點數(shù)量為ei，則路徑的總耗費值F：

3 應用分析與仿真

3.1 應用分析

本次測試方法為使用含有站點坐標信息的二維碼標簽，根據(jù)空間大小布置二維碼。利用二維碼標簽構(gòu)建AGV理想行駛路徑L，路徑中Ln表示為路徑中第n個二維碼站點坐標，表示方法為。調(diào)用A*算法生成一條起始點到目標點的路徑L=[L0，...，L n]。遇到障礙物時調(diào)用D*算法生成局部路徑，假設為S=[S0，...，S n]，拼接完成后得到全局路徑L'=[L0，...，S0，...，S n，...，L n]。

3.2 路徑仿真

首先設置路徑的起始站點為<0，0>與目標站點<2，4>，并設置AGV的路徑搜索方式為曼哈頓搜索。AGV根據(jù)起始點與目標點相互位置關(guān)系調(diào)用A*算法搜索全局的路徑，并將拐點去除得到全局路徑L=[L0，L1，L3，L3，L4，L5]，當行駛到每個站點時，實時解析路徑的下兩個站點，此處稱之為“預備站點”和“目標站點”，并檢測柵格地圖中的目標站點是否有障礙物。假設在路徑上將障礙點設置為<0，3>。當AGV行駛到<0，1>坐標點時，其通過報站的站點檢測到目標站點有障礙物，調(diào)用D*算法，以<0，2>為起始點，以<1，4>為目標點確定局部路徑搜索范圍進行局部路徑規(guī)劃，得到局部路徑S=[S0，S1，S2]，其中S0=<0，2>，S1=<1，3>，S2=<1，4>。進行拼接得到路徑L'=[L0，L1，S0，S1，S2，L5]，如矩陣（13）所示為進行路徑拼接得到的矩陣表示：

根據(jù)在矩陣中規(guī)劃出的路徑站點坐標及相互位置關(guān)系得到各個站點的信息，將規(guī)劃出的路徑信息寫入路徑數(shù)據(jù)文件中，如表1所示。

表1 路徑數(shù)據(jù)文件Tab.1 Path Data File

表中：坐標值為站點在矩陣中的所處的位置，目標速度為根據(jù)AGV的電機特性在配置文件中的標定值，目標方向的設定原則為：當目標點的坐標為（x，y），目標點的下一點坐標為（x，y+1）,則目標點的方向為1，對應的方向角度為90°；當目標點的下一點為（x-1，y）,則目標點的方向為2，對應的方向角度為180°；當目標點的下一點為（x，y-1）,則目標點的方向為3，對應的方向角度為270°；當目標點的下一點坐標為（x+1，y）,則目標點方向為4，對應的方向角度為0°。

4 試驗

4.1 地圖構(gòu)建

AGV根據(jù)試驗場地大小在系統(tǒng)界面中創(chuàng)建柵格地圖，同時在實際場景地面上按照比例張貼二維碼柵格，試驗現(xiàn)場的地圖構(gòu)建，如圖2所示。

圖2 測試現(xiàn)場Fig.2 Test Site

試驗的AGV類型為雙輪差速驅(qū)動，有2個驅(qū)動輪和4個萬向隨動輪，導航方式為二維碼和慣性導航復合的形式，車載傳感器有前后6個光電開關(guān)和6個碰撞開關(guān)，AGV中間底部安裝有工業(yè)攝像機用于識別車體相對二維碼地標位置。

4.2 復合路徑規(guī)劃測試

地圖中AGV的起始站點和目標站點分別設置為<0，0>和<2，4>，測試生成路徑試驗AGV軌跡，如圖3所示。

圖3 AGV測試路徑Fig.3 AGV Test Path

根據(jù)地圖的起始點與目標點坐標，調(diào)用A*算法曼哈頓啟發(fā)方式生成的全局路徑，如圖3（a）所示，并在拐點<0，4>處修剪為光滑的曲線路徑。當在<0，3>存在障礙時，AGV在行駛到<0，1>時檢測到目標站點存在障礙，將<0，2>設置為局部路徑的起始點，將<1，4>設置為局部路徑目標點，進行路徑拼接得到路徑，如圖3（b）所示。

通過AGV行駛軌跡可以看出，當AGV在目標站點檢測到障礙物時，確定局部路徑起始點為障礙物的前一站點，確定局部路徑目標站點為障礙物的下一站點，并在存在拐點處的局部路徑修剪為光滑的曲線路徑。試驗結(jié)果表明，所提出的方法實現(xiàn)AGV在動態(tài)障礙場景中自主規(guī)避障礙的能力。

5 結(jié)論

（1）根據(jù)障礙物位置和全局規(guī)劃的路徑確定局部地圖搜索范圍，使得局部路徑規(guī)劃效率更高和避障的實時性。（2）所提的復合路徑規(guī)劃方法，可應用于多種導航方式，例如：SLAM導航、激光導航、二維碼導航等。（3）所研究的方法目前只能在柵格地圖中實現(xiàn)，若地圖沒有采用柵格建模，則只能將地圖轉(zhuǎn)換為柵格地圖才能采用，針對此問題，我們將繼續(xù)研究解決這種問題。