趙學(xué)健,葉 昊,賈 偉,孫知信

1(南京郵電大學(xué) 現(xiàn)代郵政學(xué)院,南京 210003)

2(南京郵電大學(xué) 江蘇省郵政大數(shù)據(jù)技術(shù)與應(yīng)用工程研究中心,南京 210003)

3(南京先維信息技術(shù)有限公司,南京 210001)

0 引 言

在工業(yè)4.0、“中國(guó)制造2025”、智慧物流和智慧工廠等概念的推動(dòng)下,工業(yè)移動(dòng)機(jī)器人市場(chǎng)呈現(xiàn)高速增長(zhǎng)的態(tài)勢(shì).自動(dòng)導(dǎo)向車(Automated Guided Vehicle,AGV)是指裝備有電磁或光學(xué)等自動(dòng)導(dǎo)引裝置,能夠沿規(guī)定的導(dǎo)引路徑行駛,具有安全保護(hù)以及各種移載功能的運(yùn)輸車[1].AGV能夠代替人工轉(zhuǎn)移、裝卸和搬運(yùn)貨品,有效地降低了人工勞動(dòng)強(qiáng)度,提高了工作效率,提升在部分危險(xiǎn)且復(fù)雜的環(huán)境中工作的安全性,目前廣泛應(yīng)用于物流、機(jī)械、電子、化工等行業(yè).AGV的路徑規(guī)劃和避障算法是實(shí)現(xiàn)AGV自主導(dǎo)航的關(guān)鍵技術(shù),決定了AGV在復(fù)雜環(huán)境中能否高效、安全地完成任務(wù),近年來(lái)成為AGV領(lǐng)域的重要研究熱點(diǎn)之一.

AGV路徑規(guī)劃是指為AGV在特定應(yīng)用場(chǎng)景下,按照特定的性能指標(biāo)搜索一條從起始狀態(tài)到目標(biāo)狀態(tài)的最優(yōu)或近似最優(yōu)的運(yùn)行路徑.路徑規(guī)劃的目標(biāo)可以是最大化AGV的效率,減少行駛時(shí)間,降低能耗,優(yōu)化資源利用率等.路徑規(guī)劃算法需要考慮各種約束條件,如靜態(tài)障礙物、動(dòng)態(tài)障礙物、區(qū)域限制等,因此避障算法是路徑規(guī)劃算法的核心組成部分,用于判斷、預(yù)測(cè)和避免AGV與障礙物之間的碰撞,從而確保AGV運(yùn)行過(guò)程中的安全性和可靠性.

根據(jù)AGV路徑規(guī)劃及避障算法的原理與技術(shù)特點(diǎn)[2],AGV路徑規(guī)劃及避障算法大致劃分為局部避障路徑規(guī)劃算法、基于幾何模型的路徑規(guī)劃算法、智能路徑規(guī)劃算法及混合路徑規(guī)劃算法等,如圖1所示.

根據(jù)圖1分類方法,本文首先對(duì)各類AGV路徑規(guī)劃及避障算法的技術(shù)原理、工作流程、優(yōu)勢(shì)、局限性進(jìn)行了深入分析闡述;在此基礎(chǔ)上,進(jìn)一步對(duì)比分析了不同方法的優(yōu)劣;最后,本文對(duì)AGV路徑規(guī)劃及避障算法的未來(lái)發(fā)展趨勢(shì)進(jìn)行了總結(jié)展望,以期進(jìn)一步推動(dòng)AGV路徑規(guī)劃及避障算法的研究進(jìn)展.

1 局部避障路徑規(guī)劃算法

局部避障路徑規(guī)劃算法是一種用于避免 AGV與局部環(huán)境中的障礙物發(fā)生碰撞或沖突的算法.它的目標(biāo)是確定 AGV 在當(dāng)前環(huán)境中的最佳移動(dòng)路徑,以避開靜態(tài)或動(dòng)態(tài)的障礙物,并以安全和高效的方式達(dá)到目標(biāo)位置.此類算法通常先確立起點(diǎn)到終點(diǎn)間的直線為初始最優(yōu)路徑,再基于AGV周圍的環(huán)境感知信息,采用一系列步驟盡可能以較小的調(diào)整實(shí)現(xiàn)對(duì)初始最優(yōu)路徑上一切障礙物的有效規(guī)避,形成最終最優(yōu)路徑.該類算法主要包含人工勢(shì)場(chǎng)法、動(dòng)態(tài)窗口法以及Bug算法等.

1.1 人工勢(shì)場(chǎng)法

1)算法原理簡(jiǎn)介:人工勢(shì)場(chǎng)法(Artificial Potential Field approach,APF)最早于1985年由Khatib提出[3],基于對(duì)AGV周圍環(huán)境中潛在障礙物施加人工生成的勢(shì)場(chǎng),使AGV從高勢(shì)場(chǎng)區(qū)域移動(dòng)到低勢(shì)場(chǎng)區(qū)域,其工作原理如圖2所示.

圖2 人工勢(shì)場(chǎng)法原理示意圖Fig.2 Schematic diagram of the principle of artificial potential field methods

該算法從車輛到目標(biāo)點(diǎn)為方向設(shè)置目標(biāo)點(diǎn)引力勢(shì)場(chǎng),以各障礙物到車輛為方向設(shè)置障礙物斥力勢(shì)場(chǎng),二者疊加形成合勢(shì)場(chǎng),車輛在該合勢(shì)場(chǎng)的作用下運(yùn)動(dòng),從而使車輛以盡可能短的路徑,避開障礙物,到達(dá)目標(biāo)點(diǎn).具體的合勢(shì)場(chǎng)函數(shù)U如式(1)所示:

U=

(1)

式中,n為引力勢(shì)場(chǎng)正比例系數(shù);k為斥力勢(shì)場(chǎng)正比例系數(shù);d0為障礙物影響范圍;x為車輛的位置坐標(biāo);xgoal為目標(biāo)點(diǎn)的位置坐標(biāo);xobs為障礙物的位置坐標(biāo);d(x,xgoal)為車輛當(dāng)前位置與目標(biāo)點(diǎn)之間的距離一個(gè)矢量,方向從車輛指向目標(biāo)點(diǎn);d(x,xobs)為車輛與障礙物之間的距離.

對(duì)合勢(shì)場(chǎng)函數(shù)進(jìn)行求導(dǎo)即可得到作用于車輛的人工合力F,其表達(dá)式如公式(2)所示:

(2)

2)算法優(yōu)缺點(diǎn):人工勢(shì)場(chǎng)法算法具有定義直觀、結(jié)構(gòu)簡(jiǎn)單且計(jì)算量較小等優(yōu)點(diǎn),深受廣大研究者偏愛.但也具有局限性,人工勢(shì)場(chǎng)法易出現(xiàn)路徑振蕩、路徑過(guò)長(zhǎng)以及局部最優(yōu)等問(wèn)題.

3)算法改進(jìn)措施:近幾年,研究人員針對(duì)傳統(tǒng)人工勢(shì)場(chǎng)法存在的缺陷提出了各種改進(jìn)措施,主要包括增設(shè)速度勢(shì)場(chǎng)、優(yōu)化斥力勢(shì)場(chǎng)與斥力調(diào)節(jié)因子、增設(shè)虛擬目標(biāo)點(diǎn)等措施.Joe Sfeir等人[3]優(yōu)化了排斥力勢(shì)場(chǎng),將離心力等旋轉(zhuǎn)力以及小車慣性整合入勢(shì)場(chǎng)之中,減少了路徑振蕩問(wèn)題,得到更加平滑的行車軌跡.陳冠星等[4]通過(guò)增添虛擬目標(biāo)點(diǎn)輔助機(jī)器人規(guī)避局域最優(yōu)問(wèn)題.張涌等[5]通過(guò)改進(jìn)斥力調(diào)節(jié)因子和斥力作用域的方式優(yōu)化傳統(tǒng)人工勢(shì)場(chǎng),賦予了AGV同向超車能力.張鐘元等[6]根據(jù)無(wú)人設(shè)備控制律設(shè)計(jì)保持速度、位置一致的控制協(xié)議,采用歸一化和高階指數(shù)對(duì)人工勢(shì)場(chǎng)力進(jìn)行縮放變換,解決勢(shì)場(chǎng)力變化幅度過(guò)大導(dǎo)致的路徑損失以及震蕩失效問(wèn)題.桂雪琪等人[7]提出將極限環(huán)與人工勢(shì)場(chǎng)法相結(jié)合構(gòu)造避障速度引導(dǎo)項(xiàng),解決了局部極小值帶來(lái)的集群遇障分群困難、避障徘徊停滯等問(wèn)題.

1.2 動(dòng)態(tài)窗口法

1)算法原理簡(jiǎn)介:動(dòng)態(tài)窗口法(Dynamic Window Approach,DWA)最早于1997年由Dieter Fox等人提出[8],該算法將車輛所在的位置看作是窗口的中心,而窗口的寬度和長(zhǎng)度則是車輛的大小和下一跳可到達(dá)的最大范圍.該算法從車輛的當(dāng)前位置開始,基于車輛當(dāng)前位置(x(t),y(t),θ(t))及車輛的線速度v(t)和角速度w(t),預(yù)判t+1時(shí)刻車輛位置(x(t+1),y(t+1),θ(t+1))的可能范圍,形成窗口,并計(jì)算窗口內(nèi)是否存在障礙物.如果存在障礙物,則需要調(diào)整車輛運(yùn)動(dòng)方向,并重新計(jì)算窗口的位置和大小,實(shí)現(xiàn)避障.車輛狀態(tài)更新過(guò)程如式(3)所示:

x(t+1)=x(t)+v(t)dtcos(θ(t))
y(t+1)=y(t)+v(t)dtsin(θ(t))
θ(t+1)=θ(t)+w(t)dt

(3)

2)算法優(yōu)缺點(diǎn)分析:在局部避障中,動(dòng)態(tài)窗口法的優(yōu)點(diǎn)在于它的實(shí)時(shí)性和精度,該算法只需要計(jì)算當(dāng)前窗口內(nèi)的元素,而不需要重新計(jì)算整個(gè)地圖,因此可以實(shí)時(shí)檢測(cè)障礙物,并進(jìn)行快速的路徑規(guī)劃和調(diào)整.但該算法高度依賴全局參數(shù),容易在未知環(huán)境中失敗[9].

3)算法改進(jìn)措施:Seder等[9]針對(duì)未知且動(dòng)態(tài)的障礙物環(huán)境,將動(dòng)態(tài)障礙物的移動(dòng)視為所占據(jù)網(wǎng)格單元的移動(dòng),與AGV的運(yùn)動(dòng)單元軌跡進(jìn)行碰撞預(yù)測(cè),擴(kuò)展了AGV在缺少全局參數(shù)更新時(shí)的無(wú)碰撞運(yùn)動(dòng)能力.Wang等人[10]重新設(shè)計(jì)了無(wú)人設(shè)備運(yùn)動(dòng)學(xué)模型和基于動(dòng)態(tài)窗口法的局部路徑規(guī)劃方法評(píng)價(jià)函數(shù),提高了環(huán)境負(fù)荷強(qiáng)度的權(quán)重,從而提高窗口靈敏度,縮減了路徑長(zhǎng)度和航行時(shí)間.

1.3 Bug算法

(4)

其中,d(x,qgoal)為機(jī)器人當(dāng)前位置到終點(diǎn)距離;F為爬蟲指向終點(diǎn)方向與第一個(gè)可見障礙物的距離;dmin(qgoal)為走過(guò)的路徑點(diǎn)與終點(diǎn)最近的距離;P為障礙物最小壁厚.

2)算法優(yōu)缺點(diǎn)分析:Bug算法結(jié)構(gòu)相對(duì)簡(jiǎn)單,可以逐步探測(cè)避開障礙物,不需要全局環(huán)境信息,但從始至終只以最新獲得的環(huán)境數(shù)據(jù)為操作依據(jù),高度依賴傳感器提供數(shù)據(jù),易因信息不足而規(guī)劃失敗,且無(wú)法處理動(dòng)態(tài)障礙物.

3)算法改進(jìn)措施:當(dāng)前研究者對(duì)Bug算法的改進(jìn)研究主要針對(duì)其數(shù)據(jù)獲取及處理能力的缺陷.查榮瑞等人[14]提出的一種基于深層卷積神經(jīng)網(wǎng)絡(luò)和改進(jìn)Bug算法的機(jī)器人避障方法,該方法采用多任務(wù)深度卷積神經(jīng)網(wǎng)絡(luò)提取道路圖像特征,實(shí)現(xiàn)圖像分類和語(yǔ)義分割任務(wù),實(shí)驗(yàn)結(jié)果表明,所提方法有效的平衡了多視覺(jué)任務(wù)的精度與效率,并能準(zhǔn)確規(guī)劃出安全的避障路徑,輔助機(jī)器人完成導(dǎo)航避障.Melo等人[15]提出一種由矩陣紅外傳感器與常規(guī)相機(jī)疊加組成的熱測(cè)量系統(tǒng),提高了AGV實(shí)時(shí)獲取環(huán)境信息的能力,降低了Bug算法的傳感器成本.

2 基于幾何模型算法

基于幾何模型的路徑規(guī)劃算法主要包含柵格法和Voronoi圖法.其中,柵格法又包含Dijkstra最短路徑算法、A*算法、D*算法及向量場(chǎng)直方圖法等多個(gè)分支.

2.1 柵格法

柵格法(Grid method),最早于1968年由W.E.Howden提出,又稱格點(diǎn)法或點(diǎn)陣法,是一種數(shù)值計(jì)算方法,用于將連續(xù)域(如平面或空間)中的各種物理量離散化,并在離散空間中求解微分方程或其它數(shù)學(xué)問(wèn)題[16],其基本思想是把處理區(qū)域(如二維平面)分割成一系列小方格(稱為柵格或像元).每個(gè)小方格內(nèi)的物理量用單個(gè)節(jié)點(diǎn)(或稱為格點(diǎn)或像素)來(lái)表示,而節(jié)點(diǎn)之間的值則通過(guò)對(duì)小方格之間的相對(duì)位置關(guān)系進(jìn)行差分逼近來(lái)計(jì)算.

利用該類方法處理AGV路徑規(guī)劃及避障問(wèn)題時(shí),需要將環(huán)境中所有柵格分為自由柵格與占用柵格,并將環(huán)境內(nèi)所有障礙物信息保存于占用柵格信息中,以便搜索算法在只有自由柵格的連通圖中找到一條由起點(diǎn)柵格至目標(biāo)柵格的無(wú)碰撞路徑.柵格法常用的搜索算法有Dijkstra最短路徑算法、A*算法、D*算法等.

2.1.1 Dijkstra算法

1)算法原理簡(jiǎn)介:Dijkstra算法由荷蘭計(jì)算機(jī)科學(xué)家Edsger W.Dijkstra于1959年提出[17],可用于解決有權(quán)圖的單源最短路徑問(wèn)題,1973年Johnson將該算法用于交通路徑規(guī)劃[18].Dijkstra算法適用于有向或無(wú)向帶權(quán)圖,其算法思想基于貪心策略,每次選擇當(dāng)前最短距離的節(jié)點(diǎn)作為下一步的處理對(duì)象,在求解過(guò)程中使用了一個(gè)距離數(shù)組記錄已經(jīng)確定最短路徑的節(jié)點(diǎn)到起點(diǎn)的距離,以及一個(gè)集合S記錄已經(jīng)確定了最短路徑的節(jié)點(diǎn),最終求解出起點(diǎn)到所有節(jié)點(diǎn)的最短路徑[19].

Dijkstra算法的基本步驟如圖4所示[20].該算法最主要的兩個(gè)步驟是求出從源點(diǎn)出發(fā)到各頂點(diǎn)的最短路徑和遍歷下一跳最短路徑,如式(5)所示:

(5)

圖4 Dijkstra算法步驟圖Fig.4 Step diagram of Dijkstra algorithm

其中,lkj是從任意已知最短源點(diǎn)路徑的頂點(diǎn)k到各頂點(diǎn)j的直接連接距離;dj為源點(diǎn)到各個(gè)頂點(diǎn)的最短路徑;dk為已經(jīng)最短源點(diǎn)路徑的頂點(diǎn)k的最短源點(diǎn)路徑;di為指定最短路徑下一跳選擇頂點(diǎn)的最短源點(diǎn)路徑.

2)算法優(yōu)缺點(diǎn)分析:Dijkstra算法具有較強(qiáng)的魯棒性與健壯性,適用范圍廣,可用于非聯(lián)通圖,且可以得到完整路徑.但它的時(shí)間復(fù)雜度非常高,用于大規(guī)模地圖時(shí)計(jì)算成本極高,效率偏低.Dijkstra算法的時(shí)間復(fù)雜度為O(n2),其中n表示圖中節(jié)點(diǎn)的數(shù)量.為了提高算法效率,通常使用優(yōu)先隊(duì)列來(lái)實(shí)現(xiàn)選擇當(dāng)前最短距離的節(jié)點(diǎn),這時(shí)Dijkstra算法的時(shí)間復(fù)雜度可以降低到O(mlogn),其中m表示邊的數(shù)量[17-20].

3)算法改進(jìn)措施:得益于其較強(qiáng)的魯棒性與健壯性[21],這款古老且效率較低的算法仍然吸引了眾多學(xué)者的研究與改進(jìn).一部分學(xué)者們選擇通過(guò)優(yōu)化有權(quán)圖權(quán)重標(biāo)準(zhǔn)改善該算法性能.例如,蔣丹陽(yáng)[22]結(jié)合實(shí)際問(wèn)題,將氣溫、擁擠度等特定環(huán)境參數(shù)納入權(quán)重計(jì)算中,得到一種更加貼合其室外小車尋址需求的Dijkstra算法;劉維民等[23]同樣也再傳統(tǒng)Dijkstra算法的基礎(chǔ)上加入了熱度值對(duì)路徑繁忙程度進(jìn)行評(píng)估,是規(guī)劃的路徑更合理,預(yù)防了AGV之間的沖突.另一部分學(xué)者則通過(guò)限定搜索區(qū)域改善該算法性能.例如,黃翼虎等[24]結(jié)合時(shí)間窗算法,通過(guò)改變規(guī)劃中的路徑節(jié)點(diǎn)向量,將每一個(gè)節(jié)點(diǎn)的所有前節(jié)點(diǎn)記錄在路徑節(jié)點(diǎn)向量中,在所有的路徑中,搜索出一條最短路徑,保證此最短路徑與其他路徑無(wú)沖突;李茂森等人[25]研究了一種顧及約束條件的Dijkstra算法快速自動(dòng)生成接縫線多邊形的方法,通過(guò)影像外方位元素對(duì)Dijkstra算法的搜索區(qū)域進(jìn)行約束,快速搜索出最短路徑并生成接縫線多邊形,生成的接縫線多邊形中對(duì)極大與極小多邊形進(jìn)行基于定位影像與單張正射影像外輪廓的多邊形優(yōu)化,達(dá)到快速自動(dòng)生產(chǎn)數(shù)字正射影像的目的.實(shí)驗(yàn)結(jié)果表明此方法在生成效率上大大優(yōu)于voronoi圖生成接縫線多邊形方法.綜上,該算法的優(yōu)化潛力巨大,值得進(jìn)一步研究.

2.1.2 A*算法

1)算法原理簡(jiǎn)介:A*算法由Nils John Nilsson等人于1968年提出,和Dijkstra算法一樣都是使用貪心策略來(lái)解決路徑規(guī)劃問(wèn)題的成熟算法,而A*算法實(shí)際上是對(duì)Dijkstra算法的一種擴(kuò)展和優(yōu)化[26-28].相比于傳統(tǒng)的搜索算法,它引入了一個(gè)啟發(fā)式函數(shù)h(n),用來(lái)評(píng)估當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的距離,進(jìn)而預(yù)測(cè)可以找到最優(yōu)路徑的下一跳節(jié)點(diǎn).因此,A*算法能夠更快地找到最優(yōu)路徑.

A*算法的啟發(fā)代價(jià)函數(shù)如式(6)所示[28]:

f(n)=g(n)+h(n)

(6)

其中,g(n)代表節(jié)點(diǎn)n至起點(diǎn)的代價(jià),是當(dāng)前的實(shí)際代價(jià);h(n)代表節(jié)點(diǎn)n至目標(biāo)點(diǎn)的代價(jià),是估計(jì)代價(jià),代價(jià)通常用歐氏距離、曼哈頓距離表示.

2)算法優(yōu)缺點(diǎn)分析:相對(duì)于需要將所有節(jié)點(diǎn)展開進(jìn)行搜尋的算法,A*算法最大的優(yōu)點(diǎn)就是引入了啟發(fā)信息作為向目標(biāo)點(diǎn)移動(dòng)的決策輔助,所以不再需要遍歷整個(gè)地圖,降低了計(jì)算復(fù)雜度,減少了時(shí)間損耗少.但是,如果代價(jià)函數(shù)選擇不合理,該算法可能會(huì)輸出不符合最優(yōu)解的過(guò)長(zhǎng)路徑.此外,柵格法精度越高,柵格分的就越小,會(huì)導(dǎo)致計(jì)算工作量幾何式增長(zhǎng)及節(jié)點(diǎn)冗余問(wèn)題.

3)算法改進(jìn)措施:為了解決路徑過(guò)長(zhǎng)問(wèn)題,并進(jìn)一步縮短搜索時(shí)間,Chen Jiqing等人[29]結(jié)合自適應(yīng)擴(kuò)展方法和方向約束最優(yōu)節(jié)點(diǎn)擴(kuò)展方法,提出了一種方向約束自適應(yīng)擴(kuò)展雙向A*算法.在與傳統(tǒng)A*算法對(duì)比實(shí)驗(yàn)的結(jié)果表明,在3種障礙比例下均獲得了顯著更優(yōu)的搜索時(shí)間,在10%和25%障礙比例下獲得了更短的路徑長(zhǎng)度.為了解決節(jié)點(diǎn)冗余問(wèn)題,秦浩然等人[30]采用了動(dòng)態(tài)加權(quán)系數(shù)和引入轉(zhuǎn)彎懲罰的方法,對(duì)A*算法中代價(jià)函數(shù)的實(shí)際累積代價(jià)和估計(jì)代價(jià)分別加權(quán),平衡累積代價(jià)和估計(jì)代價(jià)對(duì)算法搜索速度的影響,構(gòu)造與AGV能耗相關(guān)聯(lián)的懲罰項(xiàng),減少路徑轉(zhuǎn)折點(diǎn)數(shù)量,提高系統(tǒng)工作效率.實(shí)驗(yàn)結(jié)果表明,相比傳統(tǒng)A*算法,改進(jìn)算法經(jīng)動(dòng)態(tài)加權(quán),搜索時(shí)間平均縮短了11.8%,引入轉(zhuǎn)彎懲罰后,轉(zhuǎn)彎角度平均縮短了66.1%,生成的路徑質(zhì)量更高.王毅恒等人[31]則在沖突A*算法基礎(chǔ)上,增添了一個(gè)擴(kuò)展節(jié)點(diǎn)消減模塊,通過(guò)該模塊可以生成一個(gè)候選節(jié)點(diǎn)序列,當(dāng)模型部件生成的輸出與實(shí)際觀測(cè)值不一致時(shí),改進(jìn)的沖突A*算法會(huì)縮減可擴(kuò)展的沖突節(jié)點(diǎn),然后生成下一個(gè)候選診斷并進(jìn)行循環(huán),直到搜索結(jié)束;實(shí)驗(yàn)結(jié)果表明,改進(jìn)的沖突A*算法在搜索速度上相比沖突A*算法提升50%.

2.1.3 D*算法

1)算法原理簡(jiǎn)介:D*算法(Dynamic A*)是由Sven Koenig與Maxim Likhachev于2002年提出的一種基于A*算法的增量式路徑規(guī)劃算法[32].D*算法通過(guò)一個(gè)啟發(fā)式評(píng)估函數(shù)評(píng)估已知和未知部分的路徑,動(dòng)態(tài)生成從起點(diǎn)到終點(diǎn)的最佳路徑,并動(dòng)態(tài)更新路徑,使其適應(yīng)環(huán)境的變化[33].在搜索過(guò)程中,D*算法會(huì)不斷更新路徑上的各個(gè)節(jié)點(diǎn)的代價(jià)值,這樣即使其中某些節(jié)點(diǎn)發(fā)生了變化,也可以立即確定新的最短路徑.

D*算法的啟發(fā)函數(shù)可傳遞.當(dāng)中心柵格向周圍柵格擴(kuò)展時(shí),可將其啟發(fā)值傳遞給周圍鄰點(diǎn).D*算法的代價(jià)公式由A*函數(shù)發(fā)展而來(lái),如式(7)所示:

F(s)=G(s)+H(s)

(7)

其中,G(s)為起始點(diǎn)至s的代價(jià)值,H(s)為啟發(fā)值,其計(jì)算方式如式(8)所示:

(8)

上式中,s′為s的拓展節(jié)點(diǎn),H(s′)為s′的啟發(fā)值,C(s,s′)為相鄰節(jié)點(diǎn)的代價(jià)值,sgoal為目標(biāo)點(diǎn).進(jìn)行柵格擴(kuò)展的過(guò)程中,被擴(kuò)展節(jié)點(diǎn)的啟發(fā)值由其拓展點(diǎn)s′的代價(jià)值以及拓展點(diǎn)s′的啟發(fā)值計(jì)算得來(lái).

2)算法優(yōu)缺點(diǎn)分析:相對(duì)于A*算法,D*算法在搜索效率方法有極大的提升,在100*100方陣圖中可以節(jié)省約33%的尋址時(shí)間和74.5%的節(jié)點(diǎn)個(gè)數(shù)[34].但是,D*算法規(guī)劃的路徑大多貼近障礙物邊緣,路徑平滑度較差.

3)算法改進(jìn)措施:研究者大多針對(duì)D*算法路徑平滑度較差的缺陷進(jìn)行改進(jìn).溫廣輝等人[35]利用貝塞爾曲線進(jìn)行優(yōu)化以提高路徑的平滑度;劉春霞[36]采用元胞自動(dòng)機(jī)擴(kuò)展Moore型鄰居結(jié)構(gòu),向當(dāng)前點(diǎn)周圍的16個(gè)方向進(jìn)行搜索,將轉(zhuǎn)動(dòng)角度的最小增量降低到π/8,可有效減少機(jī)器人不必要的旋轉(zhuǎn),使得路徑更加平滑.

2.1.4 向量場(chǎng)直方圖法

1)算法原理簡(jiǎn)介:向量場(chǎng)直方圖法(Vector Field Histogram,VFH)是由Koren于1991年提出的[37],向量場(chǎng)直方圖法的關(guān)鍵是在傳感器的周圍建立柵格,且每個(gè)柵格對(duì)應(yīng)當(dāng)前AGV向該方向運(yùn)動(dòng)的概率指數(shù).這樣可以避免由于傳感器所獲得數(shù)據(jù)暫時(shí)延遲而或丟失可能導(dǎo)致的錯(cuò)誤.任意時(shí)刻創(chuàng)建的圖形都是一個(gè)劃分的柵格,只有在傳感器掃描范圍內(nèi)的數(shù)據(jù)才會(huì)在柵格內(nèi)從而取代已有的舊數(shù)據(jù).為了能夠有效避開障礙物,它形成了一個(gè)極坐標(biāo)圖,其中x軸代表行走的方向與障礙物所構(gòu)成的角度,y軸是根據(jù)占有柵格的多少來(lái)計(jì)算障礙物就在運(yùn)動(dòng)方向的概率,如圖5所示.

圖5 向量場(chǎng)直方圖法示意圖Fig.5 Schematic diagram of vector field histogram method

利用此極坐標(biāo)圖可以計(jì)算出機(jī)器人的行走方向.首先確定出移動(dòng)機(jī)器人可以安全避開障礙物所有路徑范圍,再在這些范圍內(nèi)選擇損耗最低的路徑,即最優(yōu)路徑.損耗函數(shù)L如式(9)所示:

L=k×θtar+u×θwheel+w×θbef

(9)

式中,θtar表示目的角度;θwheel表示輪子角度;θbef表示原來(lái)角度;k、u、w為比例系數(shù),損耗最小的就是最優(yōu)路徑,調(diào)整這些系數(shù)可以改變移動(dòng)機(jī)器人的避障效果.

2)算法優(yōu)缺點(diǎn)分析:VFH算法的優(yōu)點(diǎn)包括實(shí)現(xiàn)簡(jiǎn)單、計(jì)算速度快以及處理噪聲干擾的能力強(qiáng).同時(shí),由于該算法可以使用機(jī)器人激光掃描數(shù)據(jù)構(gòu)建向量場(chǎng),因此該算法還可以應(yīng)用于機(jī)器人導(dǎo)航的許多不同領(lǐng)域.雖然VFH算法確實(shí)是一種有效的避障算法,但是其處理速度及精度的限制,在某些環(huán)境下,例如高速控制或需要快速反應(yīng)的避障應(yīng)用中,VFH算法可能無(wú)法滿足要求.

3)算法改進(jìn)措施:研究者們對(duì)VFH算法的改進(jìn)主要針對(duì)其精度和速度方面,朱茂飛等人[38]在VFH+算法中引入車輛的最大轉(zhuǎn)角約束與引導(dǎo)路徑的離散點(diǎn)方向,來(lái)限制VFH+的候選方向范圍,并修改代價(jià)函數(shù)獲取合適的前進(jìn)方向,提高了傳統(tǒng)VFH算法的精度.D Díaz等人[39]提出了一種稱為VFH+D的增強(qiáng)算法,該算法考慮了不同的障礙物矢量大小和動(dòng)態(tài)避障的衰減,在不影響安全的情況下使AGV的平均速度提升了30%.Jake Ormond等人[40]將引入“海馬體”思想,優(yōu)化傳感器數(shù)據(jù)的處理模式,提出了一個(gè)基于矢量的模型來(lái)支持靈活的導(dǎo)航,表現(xiàn)出強(qiáng)烈的方向極化,獲得的路徑更優(yōu).

2.2 Voronoi圖法

1)算法原理簡(jiǎn)介:Voronoi圖法由俄羅斯數(shù)學(xué)家Georgy Voronoi于1908年提出,是一種用于測(cè)定給定點(diǎn)集分割幾何形狀的方法,是計(jì)算機(jī)視覺(jué)和圖像處理算法的重要基礎(chǔ)[41,42],常用于自主導(dǎo)航機(jī)器人,如AGV或無(wú)人機(jī)的路徑規(guī)劃.該算法主要利用障礙物位置、工作單元邊界等信息生成機(jī)器人可移動(dòng)區(qū)域的多邊形結(jié)構(gòu),縮小最優(yōu)路徑搜索范圍.多邊形結(jié)構(gòu)的拓展需要車輛立足當(dāng)前柵格坐標(biāo),計(jì)算其到周邊未搜索柵格的歐式距離,選擇距離較近的無(wú)障礙的柵格納入多邊形結(jié)構(gòu),如式(10)所示:

(10)

其中,D[(i,j),(x,y)]為柵格(i,j)到目標(biāo)點(diǎn)(x,y)的歐氏距離;i,j與x,y為相應(yīng)行列號(hào).

2)算法優(yōu)缺點(diǎn)分析:Voronoi圖法能夠?qū)崿F(xiàn)平滑導(dǎo)航,同時(shí)避開障礙物,但是其算法時(shí)間復(fù)雜度高達(dá)O(n3),為時(shí)間復(fù)雜度最高的路徑規(guī)劃算法之一.

3)算法改進(jìn)措施:Voronoi圖算法導(dǎo)航路徑雖然具有較好的平滑度和避障精度,但是算法的導(dǎo)航性能和效率較低.Abboud等人[43]在Voronoi圖算法基礎(chǔ)上,提出了一種時(shí)間復(fù)雜度為O(n7/3)的算法,降低了原始Voronoi圖算法的時(shí)間復(fù)雜度.Marreiros E.C.等人[44]通過(guò)分析和計(jì)算確定了一種特定非線性情況下Voronoi圖邊界的框架,洞悉了AGV路徑規(guī)劃及避障的數(shù)學(xué)本質(zhì),精簡(jiǎn)了目標(biāo)函數(shù)處理的問(wèn)題.張曉賀等人[45]提出了一種異質(zhì)空間下加權(quán)Voronoi圖的柵格生成算法,根據(jù)空間傳導(dǎo)能力確定每個(gè)柵格的傳導(dǎo)權(quán)重,然后進(jìn)行十字交叉光柵掃描,在距離變換中按柵格對(duì)距離進(jìn)行分解,將目標(biāo)影響權(quán)重和柵格傳導(dǎo)權(quán)重納入變換公式,最后連通每個(gè)柵格到最近目標(biāo)點(diǎn)的最短路徑,全過(guò)程不受目標(biāo)數(shù)量的影響.黃蓮花等人[46]采用NURBS樣條規(guī)劃曲線對(duì)機(jī)器人的全局路徑進(jìn)行細(xì)化插補(bǔ),進(jìn)一步提升了Voronoi圖算法的路徑平滑度.

3 智能規(guī)劃算法

智能規(guī)劃算法是一種使用啟發(fā)式方法搜索空間來(lái)尋找最優(yōu)路徑的方法,對(duì)環(huán)境的適應(yīng)能力強(qiáng),能夠根據(jù)規(guī)劃過(guò)程中獲得的新環(huán)境信息實(shí)時(shí)優(yōu)化路徑并進(jìn)行避障,主要包括基于群體智能的規(guī)劃算法和基于采樣的智能規(guī)劃算法兩類.

3.1 基于群體智能規(guī)劃算法

基于群體智能的規(guī)劃算法,是運(yùn)用群體智能優(yōu)化算法,通過(guò)群體中個(gè)體間的協(xié)作和競(jìng)爭(zhēng)來(lái)尋找最優(yōu)路徑,包括基于蟻群算法、粒子群算法、遺傳算法及神經(jīng)網(wǎng)絡(luò)的路徑規(guī)劃算法等.

3.1.1 基于蟻群算法的路徑規(guī)劃

1)算法原理簡(jiǎn)介:蟻群算法(Ant Colony Optimization,ACO)[47]由意大利學(xué)者Dorigol在1992年提出,在AGV路徑規(guī)劃及避障中,該算法通過(guò)設(shè)置最短路程作為目標(biāo)函數(shù),運(yùn)用螞蟻尋找食物時(shí)的信息素沉淀和信息素蒸發(fā)規(guī)則,逐步搜索出最優(yōu)路徑.

該算法首先要計(jì)算“螞蟻”(移動(dòng)物體)在任意兩節(jié)點(diǎn)間轉(zhuǎn)移的可能性,如式(11)所示:

(11)

“螞蟻”選擇轉(zhuǎn)移期望較高的節(jié)點(diǎn)后,進(jìn)行信息素濃度的迭代,如式(12)所示:

(12)

由公式(12)得,計(jì)算每段路徑的信息素濃度增加量需要累加每只“螞蟻”其對(duì)所經(jīng)節(jié)點(diǎn)間路徑的信息素貢獻(xiàn)取決于其信息素常數(shù)及路徑長(zhǎng)度,如公式(13)所示:

(13)

2)算法優(yōu)缺點(diǎn)分析:本質(zhì)上,蟻群算法實(shí)際上是對(duì)路徑規(guī)劃及避障過(guò)程中涉及參數(shù)的權(quán)重進(jìn)行了優(yōu)化,由于邏輯嚴(yán)謹(jǐn)、計(jì)算便捷而沿用至今[48].作為一種基于信息素的啟式算法,蟻群算法可以輕松應(yīng)對(duì)各種參數(shù)眾多且復(fù)雜的路徑評(píng)估模型.這一點(diǎn)在E.Alhenawi等人2023年的最新研究中得到完美體現(xiàn)[49],他們通過(guò)應(yīng)用一些考慮到路徑安全傾斜角的約束來(lái)保證所選登山路徑的安全性,生成的大小可變的數(shù)據(jù)集用于在運(yùn)行時(shí)間、加速、效率和成本方面評(píng)估所提出的算法,而實(shí)驗(yàn)結(jié)果表明并行ACO算法顯著(P<0.05)優(yōu)于多種傳統(tǒng)順序計(jì)算的規(guī)劃算法.隨著物流服務(wù)規(guī)模不斷擴(kuò)大,在本地部署算法已經(jīng)不足以滿足大型物流中轉(zhuǎn)中心的AGV調(diào)度需求.這就需要云計(jì)算部署以集中化、資源池化的方式來(lái)應(yīng)對(duì)海量的路徑數(shù)據(jù).此外,蟻群算法仍不能避免受困于局部最優(yōu)解和搜索停滯問(wèn)題.

3)算法改進(jìn)措施:為了優(yōu)化蟻群算法云端部署,研究者們進(jìn)行了大量研究.Sumathi M等人[50]使用HLB混合復(fù)雜均衡算法來(lái)控制蟻群算法上云后,其平均等待時(shí)間 (AWT)、平均執(zhí)行時(shí)間 (AET)、平均響應(yīng)時(shí)間 (ART)、跨度、吞吐量分析、周轉(zhuǎn)時(shí)間和 LB 時(shí)間都得到不同程度的優(yōu)化.聶秀珍等人[51]在蟻群算法的基礎(chǔ)上引入了探索性步長(zhǎng)算法,可以根據(jù)當(dāng)前搜索狀態(tài)動(dòng)態(tài)調(diào)整搜索步長(zhǎng),進(jìn)一步提高其搜索效率和接索精度.程娟[52]在蟻群算法中加入了方向性引導(dǎo)以及動(dòng)態(tài)優(yōu)化后,進(jìn)行對(duì)比實(shí)驗(yàn)發(fā)現(xiàn)改進(jìn)蟻群算法較基本蟻群算法及空間最短距離算法,得到最優(yōu)路徑的結(jié)果更加準(zhǔn)確,同時(shí)改進(jìn)蟻群算法的迭代次數(shù)有所減少.

3.1.2 基于粒子群算法的路徑規(guī)劃

1)算法原理簡(jiǎn)介:粒子群算法由Eberhart于1995年提出,通常以粒子的位置和速度來(lái)代表問(wèn)題的解,通過(guò)不斷更新粒子的速度和位置來(lái)搜索最優(yōu)解[53].很多AGV領(lǐng)域研究者將AGV所在的位置視為粒子位置,將粒子速度看作是代表每個(gè)節(jié)點(diǎn)之間的距離,通過(guò)更新粒子速度和位置,逐步搜索最優(yōu)路徑,以實(shí)現(xiàn)路徑規(guī)劃及避障的目標(biāo).原始粒子群算法的速度和位置迭代方法分別如(14)和公式(15)所示:

(14)

(15)

其中,c1,c2為加速常數(shù),用于調(diào)節(jié)學(xué)習(xí)最大步長(zhǎng);γ1,γ2兩個(gè)隨機(jī)函數(shù),取值范圍[0,1],以增加搜索隨機(jī)性;w慣性權(quán)重,非負(fù)數(shù),調(diào)節(jié)對(duì)解空間的搜索范圍;pbestid,gbestd分別為個(gè)體最優(yōu)速度解和群體最優(yōu)速度解;v,x分別為車輛速度和位置.

粒子群算法在AGV路徑規(guī)劃中的具體工作流程如下.首先,在粒子群算法中,每個(gè)解被表示為一個(gè)粒子,粒子的位置代表解空間中的一個(gè)候選解.在多AGV路徑規(guī)劃問(wèn)題中,可以將每個(gè)粒子看作一個(gè)候選解,即一組任務(wù)的完成順序.每個(gè)粒子的位置是一個(gè)長(zhǎng)度為N的序列,表示每輛AGV要執(zhí)行的任務(wù)順序.然后,通過(guò)適應(yīng)度函數(shù)評(píng)估每個(gè)粒子的路徑長(zhǎng)度和時(shí)間窗約束是否滿足.在多AGV路徑規(guī)劃問(wèn)題中,適應(yīng)度函數(shù)可以用來(lái)評(píng)估每個(gè)粒子的路徑長(zhǎng)度和時(shí)間窗約束是否滿足.最后,通過(guò)更新粒子的速度和位置,逐步優(yōu)化解的質(zhì)量.在多AGV路徑規(guī)劃問(wèn)題中,通過(guò)更新粒子的速度和位置,可以逐步優(yōu)化每輛AGV執(zhí)行任務(wù)的時(shí)間和順序,從而找到最優(yōu)解或達(dá)到迭代次數(shù).

需要注意的是,在實(shí)際應(yīng)用中,還需要考慮其他約束條件,如車輛數(shù)量、載重量約束、可運(yùn)載品種約束、運(yùn)行路線約束、工作時(shí)間約束等.這些約束條件可以通過(guò)對(duì)粒子的速度和位置進(jìn)行限制來(lái)實(shí)現(xiàn).綜上所述,粒子群算法可以應(yīng)用于AGV路徑規(guī)劃中,通過(guò)將每個(gè)解表示為一個(gè)粒子,逐步優(yōu)化每輛AGV執(zhí)行任務(wù)的時(shí)間和順序,從而找到最優(yōu)解或達(dá)到迭代次數(shù).

2)算法優(yōu)缺點(diǎn)分析:相比于其他啟發(fā)式算法,粒子群算法的優(yōu)點(diǎn)在于簡(jiǎn)單易懂、易于實(shí)現(xiàn)以及不易陷入局部極小值,因此在AGV路徑規(guī)劃及避障中具有一定的應(yīng)用前景.但是,該算法收斂速度比較慢,且處理離散問(wèn)題仍不能完全規(guī)避局部最優(yōu)解.

3)算法改進(jìn)措施:秦昌禮等人[54]對(duì)粒子群優(yōu)化算法進(jìn)行改進(jìn),結(jié)合鴿子啟發(fā)優(yōu)化算法的快速收斂能力,提出一種基于改進(jìn)粒子群優(yōu)化和鴿子啟發(fā)優(yōu)化算法的兩階段混合優(yōu)化算法進(jìn)行全局路徑規(guī)劃.與傳統(tǒng)的粒子群優(yōu)化算法相比,新方法可以有效避免陷入局部最優(yōu).全局最優(yōu)路徑長(zhǎng)度縮短約3.8%,減少路徑規(guī)劃時(shí)間.彭慕蓉等人[55]采用線性遞減慣性權(quán)重改進(jìn)的粒子群算法設(shè)計(jì)控制方案,最后提出時(shí)間乘誤差絕對(duì)值積分準(zhǔn)則與誤差占比相結(jié)合的變化適應(yīng)度函數(shù),有效地提高了粒子群算法的收斂速度.Q.Zhao等人[56]提出了一種受人類決策和尖點(diǎn)突變理論啟發(fā)的兩階段多群粒子群優(yōu)化算法(TMPSO),該算法采用多群方法,在整個(gè)迭代過(guò)程中先后采用無(wú)約束全局優(yōu)化TMPSO和約束全局優(yōu)化cTMPSO的兩階段搜索策略,在第2階段所有子群合并為一個(gè)大的群,從而進(jìn)一步細(xì)化全局最佳粒子,以增強(qiáng)局部搜索能力.

3.1.3 基于遺傳算法的路徑規(guī)劃

1)算法原理簡(jiǎn)介:遺傳算法最早是由John Holland于20世紀(jì)70年代提出,是一種基于自然進(jìn)化和遺傳學(xué)原理設(shè)計(jì)的優(yōu)化搜索算法,通過(guò)模擬自然的進(jìn)化和遺傳過(guò)程,通過(guò)選擇、交叉和變異等操作,產(chǎn)生下一代潛在解或優(yōu)化解,逐步優(yōu)化最終的結(jié)果[57].在AGV路徑規(guī)劃及避障中,可以將AGV移動(dòng)路徑看作染色體,將每條路徑的每個(gè)節(jié)點(diǎn)看作基因,通過(guò)實(shí)現(xiàn)遺傳算法的基本操作來(lái)逐步優(yōu)化并生成最優(yōu)路徑.

遺傳算法的理論基礎(chǔ)是圖式定理.該定理可以決定下一代潛在解及優(yōu)化解的規(guī)模,可以表達(dá)為公式(16):

(16)

其中,m(H,t)為在t代群體中存在圖式H的串的個(gè)數(shù);f(H)為在t代群體中包含圖式H的串的平均適應(yīng)值;f為t代群體中所有串的平均適應(yīng)值;l為串的長(zhǎng)度;Pc為交換概率;Pm為變異概率.

2)算法優(yōu)缺點(diǎn)分析:與其他優(yōu)化算法相比較,遺傳算法具有無(wú)需求解梯度信息、并行性、全局優(yōu)化能力和搜索范圍大等優(yōu)勢(shì).但是,遺傳算法中存在一些關(guān)鍵參數(shù),如種群大小、交叉概率、變異概率等,這些參數(shù)的選擇對(duì)算法的性能影響很大,需要經(jīng)驗(yàn)或進(jìn)行大量試驗(yàn)來(lái)確定最佳參數(shù)配置,耗費(fèi)更多的計(jì)算資源和時(shí)間.

3)算法改進(jìn)措施:遺傳算法性能強(qiáng)大,但計(jì)算成本高,因此研究者對(duì)其的改進(jìn)措施大多聚焦于計(jì)算速度提升和計(jì)算資源節(jié)約方面.Liu Y等人[58]提出一種多自適應(yīng)遺傳算法(MAGA),通過(guò)引入充電任務(wù)和可變速度來(lái)優(yōu)化 AGV 的任務(wù)調(diào)度,同時(shí)也考慮到了 AGV 以最大限度地減少完工時(shí)間、使用的 AGV 數(shù)量和耗電量.經(jīng)過(guò)對(duì)比實(shí)驗(yàn)表明,MAGA 是目前應(yīng)用在AGV調(diào)度領(lǐng)域的遺傳算法中效果最好的.W Zhou等人[59]針對(duì)物流倉(cāng)儲(chǔ)過(guò)道空間狹小導(dǎo)致的AGV沖突問(wèn)題,在適應(yīng)度函數(shù)中加入了擁塞系數(shù),使AGV小車間的沖突現(xiàn)象減少了4.2%.為了進(jìn)一步縮減遺傳算法制定最優(yōu)路徑的速度.Fontes等人[60]制定了一個(gè)混合整數(shù)線性規(guī)劃 (MILP) 模型,并提出了一種雙目標(biāo)多群體偏置隨機(jī)密鑰遺傳算法 (mp-BRKGA).實(shí)驗(yàn)表明,通過(guò)求解所提出的 MILP 模型可以找到近似真實(shí)的Pareto前沿,并且mp-BRKGA可以找到均勻分布的Pareto 前沿,能夠匹配出降低完工時(shí)間和能源消耗的最優(yōu)路徑.

3.1.4 神經(jīng)網(wǎng)絡(luò)法

1)算法原理簡(jiǎn)介:神經(jīng)網(wǎng)絡(luò)(Genetic Algorithm,簡(jiǎn)稱GA)最早于1943年由心理學(xué)家W.S.McCulloch提出,是一類受人腦結(jié)構(gòu)和功能啟發(fā)的機(jī)器學(xué)習(xí)算法[61].神經(jīng)網(wǎng)絡(luò)通暢由多層互連節(jié)點(diǎn)(也稱為神經(jīng)元)組成,每個(gè)節(jié)點(diǎn)對(duì)其輸入執(zhí)行數(shù)學(xué)運(yùn)算,并將結(jié)果傳遞給下一層,最后一層產(chǎn)生網(wǎng)絡(luò)的輸出,通常是基于輸入數(shù)據(jù)的預(yù)測(cè)或分類.最基本的神經(jīng)網(wǎng)絡(luò)是前饋神經(jīng)網(wǎng)絡(luò)(Feedforward Neural Network),主要使用前向傳播公式和反向傳播公式實(shí)現(xiàn)模型訓(xùn)練.以下是這兩個(gè)公式的基本形式:

對(duì)于具有L層的神經(jīng)網(wǎng)絡(luò),其中第i層(l=1,2,…,L)表示網(wǎng)絡(luò)中的每一層,輸入層為第0層.在每一層中,每個(gè)神經(jīng)元都有一個(gè)激活函數(shù).令a[i]表示第i層的激活值,w[i]表示第i層的權(quán)重矩陣,b[i]表示第i層的偏差向量,a[i-1]表示第i-1層的激活值.則前向傳播公式可以表示為:

(17)

其中,z[i]表示第i層的加權(quán)輸入(加權(quán)和加上偏差項(xiàng)),g(_)表示激活函數(shù).

反向傳播算法用于根據(jù)損失函數(shù)來(lái)更新神經(jīng)網(wǎng)絡(luò)的權(quán)重和偏差,以實(shí)現(xiàn)網(wǎng)絡(luò)的訓(xùn)練.在每一層中,通過(guò)利用鏈?zhǔn)椒▌t來(lái)計(jì)算梯度.令L表示損失函數(shù),該函數(shù)可以是均方誤差(Mean Square Error)或交叉熵(Cross-entropy)等.對(duì)于第l層的權(quán)重矩陣w[i]和偏差項(xiàng)b[i],則反向傳播公式可以表示為:

(18)

這些是神經(jīng)網(wǎng)絡(luò)中的基礎(chǔ)公式,用于計(jì)算前向傳播以獲取預(yù)測(cè)結(jié)果,并通過(guò)反向傳播來(lái)更新網(wǎng)絡(luò)參數(shù)以最小化損失函數(shù).實(shí)際上,神經(jīng)網(wǎng)絡(luò)的更復(fù)雜的變體和層級(jí)結(jié)構(gòu)可能會(huì)引入其他公式和技巧,但這些基礎(chǔ)公式構(gòu)成了神經(jīng)網(wǎng)絡(luò)的核心.

神經(jīng)網(wǎng)絡(luò)通常用于廣泛的應(yīng)用,如圖像識(shí)別、自然語(yǔ)言處理和預(yù)測(cè)分析.它們特別適合于涉及大量復(fù)雜數(shù)據(jù)的任務(wù),例如高維輸入或噪聲數(shù)據(jù)[62].綜上,神經(jīng)網(wǎng)絡(luò)可以基于工作場(chǎng)景一切參數(shù)對(duì)AGV的運(yùn)輸過(guò)程進(jìn)行建模,以更加智能高效的方式實(shí)現(xiàn)路徑規(guī)劃及避障[63].具體來(lái)說(shuō),他們可以根據(jù)來(lái)自LiDAR或相機(jī)等傳感器的數(shù)據(jù)進(jìn)行訓(xùn)練,以學(xué)習(xí)當(dāng)前環(huán)境狀態(tài)和AGV最佳路徑之間的映射;然后,使用神經(jīng)網(wǎng)絡(luò)實(shí)時(shí)生成一個(gè)路徑計(jì)劃,該計(jì)劃考慮了環(huán)境的當(dāng)前狀態(tài)和任何潛在的障礙或危險(xiǎn).通過(guò)學(xué)習(xí)過(guò)去的經(jīng)驗(yàn)并不斷提高路徑規(guī)劃及避障結(jié)果的最優(yōu)性,神經(jīng)網(wǎng)絡(luò)也可以用于優(yōu)化AGV的路徑規(guī)劃及避障過(guò)程,提高計(jì)算效率[64],同時(shí)可以提高AGV和在其環(huán)境中工作的人類的安全性.

2)算法優(yōu)缺點(diǎn)分析:總的來(lái)說(shuō),在AGV路徑規(guī)劃及避障中使用神經(jīng)網(wǎng)絡(luò)有可能顯著提高自動(dòng)化材料處理和運(yùn)輸系統(tǒng)的效率、可靠性和安全性,前提是需要花費(fèi)大量時(shí)間成本提前構(gòu)建并調(diào)校數(shù)據(jù)集訓(xùn)練模型.此外,神經(jīng)網(wǎng)絡(luò)在處理新環(huán)境的時(shí)候,需要額外的遷移學(xué)習(xí)方法來(lái)適應(yīng)新的場(chǎng)景與任務(wù),甚至需要對(duì)神經(jīng)網(wǎng)絡(luò)的架構(gòu)和參數(shù)進(jìn)行重新配置和調(diào)整.

3)算法改進(jìn)措施:由于神經(jīng)網(wǎng)絡(luò)模型訓(xùn)練的必要性,所以改進(jìn)措施通常著手于神經(jīng)網(wǎng)絡(luò)參數(shù)和訓(xùn)練數(shù)據(jù)集來(lái)源兩方面.Wang等人[65]開發(fā)了一種新的AGV多狀態(tài)調(diào)度算法 (MSSA),該算法在 FMS 中的 AGV 利用率和總處理制造跨度之間進(jìn)行了良好的權(quán)衡.與經(jīng)典的空閑調(diào)度策略相比,MSSA在每次計(jì)算中調(diào)度了更多的AGV和任務(wù),使其優(yōu)化目標(biāo)更接近全局優(yōu)化目標(biāo).Mozo等人[66]提出應(yīng)用先進(jìn)的深度神經(jīng)網(wǎng)絡(luò)來(lái)預(yù)測(cè)AGV軌跡誤差,即使在5G網(wǎng)絡(luò)中出現(xiàn)干擾,通過(guò)捕獲 PLC-AGV 連接的數(shù)據(jù)包而不使用用戶設(shè)備(AGV或PLC)中的任何傳感器,這有助于解決方案的實(shí)時(shí)部署.此外,部分研究者利用神經(jīng)網(wǎng)絡(luò)的強(qiáng)大功能進(jìn)一步推進(jìn)了AGV的智能化升級(jí),比如Budzan等人[67]對(duì)ResNet50和MobileNetV2等常用于手勢(shì)識(shí)別的算法進(jìn)行優(yōu)化修改,使用遷移學(xué)習(xí)方法進(jìn)行二次訓(xùn)練,得到一種簡(jiǎn)單有效的卷積神經(jīng)網(wǎng)絡(luò)(CNN)來(lái)賦予AGV小車快速識(shí)別人類手勢(shì)并執(zhí)行手勢(shì)命令的功能,測(cè)試成功率在96%以上.

3.2 基于采樣的智能規(guī)劃算法

使用基于采樣的規(guī)劃算法進(jìn)行路徑規(guī)劃及避障包括通過(guò)隨機(jī)采樣點(diǎn)并將它們連接起來(lái)形成圖來(lái)構(gòu)建環(huán)境的路線圖,隨后搜索該圖,以找到從起點(diǎn)到目標(biāo)點(diǎn)的最佳路徑,同時(shí)避開障礙物[68].該類算法在采樣點(diǎn)和連接點(diǎn)以形成圖的方式上有所不同,并且根據(jù)特定的環(huán)境和任務(wù)要求,它們各有優(yōu)缺點(diǎn)[69].使用基于采樣的規(guī)劃算法實(shí)現(xiàn)路徑規(guī)劃及避障可能很復(fù)雜,尤其是對(duì)于障礙物較多的大型環(huán)境.然而,它可以為AGV在動(dòng)態(tài)和不確定環(huán)境中規(guī)劃路徑提供一種高效有效的方法.當(dāng)前常見的基于采樣的規(guī)劃算法有快速探索隨機(jī)樹和概率路線圖算法.

3.2.1 快速搜索隨機(jī)樹算法

1)算法原理簡(jiǎn)介:快速探索隨機(jī)樹(Rapidly-exploring Random Tree,簡(jiǎn)稱RRT)于2017由Steven M.LaValle等人提出,該算法通過(guò)隨機(jī)采樣環(huán)境中的點(diǎn)并朝著目標(biāo)點(diǎn)構(gòu)建樹狀圖實(shí)現(xiàn)路徑規(guī)劃及避障[70],其具體流程如圖6所示.

圖6 快速探索隨機(jī)樹算法流程圖Fig.6 Flow chart of Rapidly-exploring Random Tree

RRT算法的關(guān)鍵思想是通過(guò)不斷生長(zhǎng)的樹結(jié)構(gòu)來(lái)探索搜索空間,即通過(guò)隨機(jī)采樣新的點(diǎn),并將其連接到最近的節(jié)點(diǎn)來(lái)擴(kuò)展樹,借此可以快速探索大型搜索空間,并找到有效的路徑.在該算法使用過(guò)程中,最重要的是為算法選擇適當(dāng)?shù)膮?shù),如步長(zhǎng)和迭代次數(shù),以平衡環(huán)境的探索和開發(fā),并確保算法根據(jù)特定的環(huán)境和任務(wù)要求進(jìn)行適當(dāng)?shù)恼{(diào)整[71].

2)算法優(yōu)缺點(diǎn)分析: RRT算法適用于在動(dòng)態(tài)和雜亂環(huán)境中幫助AGV實(shí)現(xiàn)路徑規(guī)劃及避障,因?yàn)槠錁錉铍S機(jī)采樣的機(jī)制利于處理高維狀態(tài)空間,并且可以快速實(shí)時(shí)探索大型和復(fù)雜的環(huán)境.但也正因?yàn)槠潆S機(jī)性,該算法在不同時(shí)間處理同一環(huán)境、同一設(shè)備乃至同一任務(wù)都會(huì)得到不同結(jié)果.

3)算法改進(jìn)措施:盡管已經(jīng)具備較強(qiáng)的實(shí)用性,RRT仍可以通過(guò)各種修改進(jìn)行擴(kuò)展,以提高其性能,例如RRT*,它優(yōu)化路徑以獲得最低成本;或者RRT Connect,它分別從起點(diǎn)和目標(biāo)點(diǎn)出發(fā)生成兩棵樹,在地圖中互相尋找直至連接成最終路徑[72].為了控制其隨機(jī)性,J Guo等人[73]提出了一種名為UPPHE的數(shù)據(jù)驅(qū)動(dòng)方法,即反饋快速探索隨機(jī)樹星算法 (FRRT*),具有數(shù)據(jù)驅(qū)動(dòng)的風(fēng)險(xiǎn)網(wǎng)絡(luò)和反饋模塊, 可以利用從態(tài)勢(shì)數(shù)據(jù)中提取的信息來(lái)約束隨機(jī)樹的生長(zhǎng),并進(jìn)行有偏調(diào)整,從而提高規(guī)劃效率.仿真實(shí)驗(yàn)驗(yàn)證了風(fēng)險(xiǎn)網(wǎng)絡(luò)指導(dǎo)規(guī)劃的有效性,以及反饋模塊帶來(lái)的效率提升.H Wang等人[74]提出一種基于矢量化地圖和動(dòng)態(tài)約束實(shí)現(xiàn)的改進(jìn)RRT*(Rapidly-Exploring Random Tree Star)算法,用于解決基于鉸接結(jié)構(gòu)和漂移環(huán)境條件的地下智能車輛路徑規(guī)劃及避障問(wèn)題.C Zammit等人[75]建議未來(lái)的研究者嘗試將啟發(fā)式函數(shù)融入當(dāng)前RRT算法中,以約束其隨機(jī)探索的范圍.他們將現(xiàn)有主要AGV算法代入相同的場(chǎng)景中進(jìn)行測(cè)試,并使用相同的性能指標(biāo)進(jìn)行分析后發(fā)現(xiàn)A*算法生成相對(duì)于 RRT 算法更短的路徑,是因?yàn)锳*算法只探索路徑生成所需的部分空間,而 RRT 算法均勻地探索整個(gè)空間.

3.2.2 概率路圖法

1)算法原理簡(jiǎn)介:概率路圖(Probabilistic Road Map,簡(jiǎn)稱PRM)最早于1996年由Smith R等人提出,主要通過(guò)對(duì)環(huán)境中的隨機(jī)點(diǎn)進(jìn)行采樣進(jìn)而構(gòu)建概率路圖,隨后使用啟發(fā)式函數(shù)搜索連接采樣點(diǎn)以形成路線圖,從而實(shí)現(xiàn)移動(dòng)機(jī)器人的路徑規(guī)劃及避障[76],其較為通用的啟發(fā)式函數(shù)由式(19)所示:

(19)

其中,rf(c)為局部區(qū)域規(guī)劃器連接點(diǎn)c時(shí)失敗的概率;n(c)是試圖連接c的總次數(shù);f(c)是失敗的次數(shù),如果c與n連接失敗,那么c和n的連接失敗次數(shù)都要加一;w(c)為采樣點(diǎn)權(quán)重系數(shù).

2)算法優(yōu)缺點(diǎn)分析:與之前的RRT算法類似,PRM算法可以在復(fù)雜的動(dòng)態(tài)環(huán)境中幫助AGV實(shí)行路徑規(guī)劃及避障.然而,它需要進(jìn)行大量的采樣和連接,生成大量冗余采樣點(diǎn),占用大量計(jì)算資源.

3)算法改進(jìn)措施:改進(jìn)PRM算法最重要的是為算法選擇適當(dāng)?shù)膮?shù),例如樣本數(shù)量和連接算法,以確保算法針對(duì)特定環(huán)境和任務(wù)要求進(jìn)行適當(dāng)調(diào)整,避免采樣點(diǎn)冗余.林俊志等人[77]對(duì)全局路徑規(guī)劃PRM進(jìn)行改進(jìn),引入橢圓約束,減少了82.7%的冗余節(jié)點(diǎn),提高了規(guī)劃效率.韓超等人[78]主要對(duì)一種模擬光照節(jié)點(diǎn)模型的PRM路徑規(guī)劃及避障優(yōu)化算法進(jìn)行研究,采用模擬光照方法,將每個(gè)節(jié)點(diǎn)視為光源,在未照亮的區(qū)域生成隨機(jī)節(jié)點(diǎn),直至光照區(qū)域能將起始點(diǎn)和目標(biāo)點(diǎn)連通,生成無(wú)向有權(quán)圖的邊,讓采樣節(jié)點(diǎn)數(shù)為1000個(gè)的PRM算法的平均規(guī)劃時(shí)間降低了88.38%.Li Qiongqiong等人[79]采用了雙向增量的碰撞檢測(cè)方法,并優(yōu)化了碰撞檢測(cè)調(diào)用次數(shù),提高了路線圖的構(gòu)建效率.PRM還可以通過(guò)各種細(xì)節(jié)優(yōu)化以提高其性能,例如延遲沖突檢查直到實(shí)際需要最終路徑的Lazy PRM,或者借助新型啟發(fā)式函數(shù)優(yōu)化路徑以獲得最小成本的PRM*[80].由上述研究可得,PRM算法在采樣點(diǎn)數(shù)量控制方面仍然有較大的改進(jìn)潛力.

4 混合算法

由于物流倉(cāng)儲(chǔ)環(huán)境與業(yè)務(wù)流程的復(fù)雜性,單一的路徑規(guī)劃算法往往難以滿足實(shí)際應(yīng)用場(chǎng)景的需求.因此,將優(yōu)勢(shì)各異的規(guī)劃算法巧妙融合成為AGV路徑規(guī)劃及避障研究的趨勢(shì).Vikas等人[81]融合改進(jìn)的雙曲引力搜索算法MGSA和動(dòng)態(tài)窗口法DWA,提出一種新型混合路徑規(guī)劃及避障算法MGSA-DWA.MGSA引入混沌因子,在近鄰環(huán)境中進(jìn)行混沌搜索對(duì)人工勢(shì)場(chǎng)法進(jìn)行改進(jìn),有助于幫助AGV躲避運(yùn)行過(guò)程中出現(xiàn)的動(dòng)態(tài)障礙.MGSA與傳統(tǒng)的DWA方法結(jié)合后,在路徑長(zhǎng)度與導(dǎo)航速度方面都有顯著提升.馮莉等人[82]則通過(guò)改進(jìn)雙向迪杰斯特拉算法,實(shí)現(xiàn)節(jié)點(diǎn)排序,配合A*算法的避障功能,使得路徑移動(dòng)距離平均下降14.74%,轉(zhuǎn)向次數(shù)平均減少8%,移動(dòng)時(shí)間平均減少13.41%.魏宏源[83]提出的綜合粒子群算法則是兼具蟻群算法的正反饋與粒子群的多樣性,快速地將多種參數(shù)引入路徑評(píng)估之中,大大提高了AGV的尋址效率.馬新國(guó)等人[84]則提出了一種名為RRT-Dijkstra融合算法,即在得到RRT算法規(guī)劃出的一條可行路徑后,向周圍擴(kuò)展可行區(qū)域,將可行區(qū)域柵格化,通過(guò)Dijkstra算法找出可行區(qū)域中的最短路線,優(yōu)化RRT算法得出的路線.該融合算法較傳統(tǒng)RRT算法路徑縮短了19.25%,拐點(diǎn)減少了84.21%,迭代次數(shù)減少了71.91%.Liang等[85]針對(duì)規(guī)劃效率低和成本高問(wèn)題,提出一種遺傳算法GA和蟻群優(yōu)化算法ACOA相結(jié)合的混合算法,實(shí)驗(yàn)結(jié)果表明,該混合算法能夠獲得機(jī)器人最優(yōu)路徑,節(jié)省時(shí)間和成本,具有較高的魯棒性.馮浩然等人[86]則將改進(jìn)A*算法與動(dòng)態(tài)窗口算法進(jìn)行融合,規(guī)劃出一條具有實(shí)時(shí)性的最優(yōu)路徑.李超[87]以提高智能倉(cāng)儲(chǔ)多AGV時(shí)間和能量利用率為總體優(yōu)化目標(biāo),提出了一種結(jié)合多染色體組改進(jìn)遺傳算法的動(dòng)態(tài)任務(wù)鏈調(diào)度模型,實(shí)現(xiàn)了對(duì)充電資源的均勻分配與區(qū)域擁擠度預(yù)測(cè)等功能庫(kù),在不改變硬件配置的情況下,改進(jìn)調(diào)度相對(duì)于傳統(tǒng)調(diào)度能夠提升10%以上飽和貨物處理效率,幫助企業(yè)實(shí)現(xiàn)降本增效.

由于AGV在物流倉(cāng)儲(chǔ)需要頻繁運(yùn)貨,出取貨次序也成為了AGV路徑規(guī)劃及避障的重要參數(shù).對(duì)此,李偉民等人[88]提出一種 PRM 算法與蟻群算法相結(jié)合的融合算法,即先利用 PRM 算法進(jìn)行 AGV 路徑規(guī)劃及避障,再利用蟻群算法決策出取貨順序,生成總的路徑.他們將 10 次的PRM 蟻群融合算法的平均值與原始PRM算法進(jìn)行比較,在路徑長(zhǎng)度方面縮短了5.4%,運(yùn)算時(shí)間也縮短了62%.

綜上所述,混合算法可以融合各類規(guī)劃算法的優(yōu)勢(shì)實(shí)現(xiàn)特定的改進(jìn)需求,如規(guī)劃路徑的準(zhǔn)確性、路徑距離以及規(guī)劃路徑時(shí)長(zhǎng)等.此外,混合算法還具有良好的收斂性和效率高的特點(diǎn),有利于避免陷入局部最優(yōu),提高規(guī)劃路徑的質(zhì)量.更重要的是,混合算法不會(huì)因?yàn)锳GV群體規(guī)模過(guò)大而變得難以使用.但是在選擇AGV路徑規(guī)劃與避障算法時(shí),仍然要以環(huán)境模型與運(yùn)行條件為主要參考指標(biāo),選擇滿足應(yīng)用需求的算法,不必盲目追求使用混合算法,以免資源浪費(fèi).

5 AGV路徑規(guī)劃及避障算法分析與發(fā)展趨勢(shì)

5.1 對(duì)比分析

本文根據(jù)AGV路徑規(guī)劃及避障算法的原理,將常見的主流AGV路徑規(guī)劃及避障算法分為局部避障算法、基于幾何模型的規(guī)劃算法及智能規(guī)劃算法三大類,并對(duì)主流AGV路徑規(guī)劃及避障算法的原理、優(yōu)缺點(diǎn)及研究進(jìn)展進(jìn)行了詳細(xì)介紹,如表1所示.

表1 主流AGV路徑規(guī)劃及避障算法匯總表Table 1 Summary of mainstream AGV path planning and obstacle avoidance algorithms

局部避障算法大多較為傳統(tǒng)、成熟,計(jì)算方式簡(jiǎn)單,收斂速度快,且需要輸入環(huán)境中障礙物的詳細(xì)信息.例如,人工勢(shì)場(chǎng)法所添加的人工勢(shì)場(chǎng)是針對(duì)環(huán)境中潛在障礙物的;動(dòng)態(tài)窗口法本質(zhì)上是對(duì)AGV下一跳可能涉及的區(qū)域進(jìn)行障礙物預(yù)警探測(cè);Bug算法更是需要對(duì)路徑周邊的障礙物進(jìn)行邊界追蹤操作,從而安全避障.由此可見,局部避障算法勢(shì)必賦予環(huán)境參數(shù)較高的權(quán)重,適合局部問(wèn)題較多的環(huán)境.但是,受限于算法結(jié)構(gòu),該類算法并不適用于參數(shù)更加復(fù)雜的高維空間,且規(guī)避局部最優(yōu)的能力有限.

基于幾何模型的規(guī)劃算法,顧名思義,即將路徑環(huán)境進(jìn)行幾何重構(gòu),形成環(huán)境簡(jiǎn)化模型,一定程度上具有更強(qiáng)的魯棒性與應(yīng)對(duì)特殊環(huán)境的能力,主要包括柵格法和Voronoi圖法等.柵格法主要是基于離散的思想將二維環(huán)境地圖等額分割一系列小方格,從而簡(jiǎn)化每一節(jié)點(diǎn)下一跳路徑選擇的方式.值得一提的是,向量直方圖法是根據(jù)障礙物密度構(gòu)建用于劃分柵格的極坐標(biāo)系的.Voronoi圖法的收斂速度算不上優(yōu)越,但是由于簡(jiǎn)化了工作環(huán)境,對(duì)環(huán)境適應(yīng)性更強(qiáng),且可以有效解決局部最優(yōu)問(wèn)題,可以對(duì)路徑進(jìn)行針對(duì)性優(yōu)化,以更小的代價(jià)獲得更優(yōu)的路徑.

相對(duì)于上述兩類較為傳統(tǒng)的路徑規(guī)劃算法,智能規(guī)劃算法更為復(fù)雜的結(jié)構(gòu)、更為豐富的參數(shù)賦予了其更為強(qiáng)大的學(xué)習(xí)能力.群智能算法應(yīng)用于路徑規(guī)劃,具有較好的適應(yīng)性,可適用于不同的應(yīng)用場(chǎng)景,具有較好的收斂速度,但是容易出現(xiàn)局部?jī)?yōu)化問(wèn)題;遺傳算法克服了這一缺陷,但是其交叉和變異操作需要大量的計(jì)算,在降低算法收斂速度的同時(shí)實(shí)現(xiàn)最佳性能;結(jié)構(gòu)更加復(fù)雜的神經(jīng)網(wǎng)絡(luò)需要逐步優(yōu)化模型參數(shù),因此通常需要集成其他智能算法來(lái)提高性能.

5.2 發(fā)展趨勢(shì)

隨著人工智能、機(jī)器學(xué)習(xí)和深度學(xué)習(xí)等技術(shù)的不斷發(fā)展,AGV路徑規(guī)劃及避障算法也將不斷演化和升級(jí).未來(lái)的AGV系統(tǒng)將更加智能、敏捷和自適應(yīng),能夠更好地適應(yīng)復(fù)雜多變的環(huán)境和場(chǎng)景.未來(lái)AGV路徑規(guī)劃及避障算法的研究將更加關(guān)注以下幾個(gè)方面:

1)強(qiáng)化學(xué)習(xí)方法的廣泛應(yīng)用.強(qiáng)化學(xué)習(xí)方法能夠使AGV系統(tǒng)實(shí)現(xiàn)更高水平的自主決策和行為,從而更加適應(yīng)不確定性和變化性的環(huán)境;

2)感知與控制的融合.將傳感器感知和控制策略融合起來(lái),實(shí)現(xiàn)更加全面、準(zhǔn)確和實(shí)時(shí)的環(huán)境感知和控制決策,以達(dá)到AGV更高的路徑規(guī)劃及避障效果;

3)多智能體的協(xié)同合作.多智能體系統(tǒng)能夠?qū)崿F(xiàn)多AGV之間的協(xié)同與合作,從而進(jìn)一步提高系統(tǒng)的效率和魯棒性;

4)特定應(yīng)用場(chǎng)景的需求.AGV的應(yīng)用場(chǎng)景將逐漸擴(kuò)展,從工業(yè)領(lǐng)域擴(kuò)展到物流、醫(yī)療、倉(cāng)儲(chǔ)、航天、智能家居等領(lǐng)域,不同的應(yīng)用領(lǐng)域和場(chǎng)景將為AGV路徑規(guī)劃及避障提出新的挑戰(zhàn).

值得一提的是,人工智能、機(jī)器學(xué)習(xí)等技術(shù)的不斷發(fā)展也會(huì)帶來(lái)新的挑戰(zhàn),如機(jī)器安全性、隱私保護(hù)、倫理道德等問(wèn)題需要相關(guān)領(lǐng)域的專家、學(xué)者和決策者一起協(xié)作解決.

6 結(jié)束語(yǔ)

AGV路徑規(guī)劃及避障算法一直是機(jī)器人領(lǐng)域的研究熱點(diǎn)和難點(diǎn)問(wèn)題,本文所涉及的各種研究方法和技術(shù)手段也是學(xué)術(shù)界和工業(yè)界關(guān)注的焦點(diǎn).在未來(lái),隨著自動(dòng)化技術(shù)的推進(jìn)和人工智能的普及,AGV的應(yīng)用場(chǎng)景將會(huì)更加廣泛,因此對(duì)于路徑規(guī)劃及避障算法的研究和優(yōu)化也將變得更為重要.相信在廣大研究人員的共同努力下,AGV路徑規(guī)劃及避障算法的研究將會(huì)取得更加豐碩的成果,為智能制造、自動(dòng)化倉(cāng)儲(chǔ)等領(lǐng)域的發(fā)展注入新的動(dòng)力.