AGV路徑規劃及避障算法研究綜述

趙學健,葉 昊,賈 偉,孫知信

1(南京郵電大學 現代郵政學院,南京 210003)

2(南京郵電大學 江蘇省郵政大數據技術與應用工程研究中心,南京 210003)

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

0 引 言

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

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

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

根據圖1分類方法,本文首先對各類AGV路徑規劃及避障算法的技術原理、工作流程、優勢、局限性進行了深入分析闡述;在此基礎上,進一步對比分析了不同方法的優劣;最后,本文對AGV路徑規劃及避障算法的未來發展趨勢進行了總結展望,以期進一步推動AGV路徑規劃及避障算法的研究進展.

1 局部避障路徑規劃算法

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

1.1 人工勢場法

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

圖2 人工勢場法原理示意圖Fig.2 Schematic diagram of the principle of artificial potential field methods

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

U=

(1)

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

對合勢場函數進行求導即可得到作用于車輛的人工合力F,其表達式如公式(2)所示:

(2)

2)算法優缺點:人工勢場法算法具有定義直觀、結構簡單且計算量較小等優點,深受廣大研究者偏愛.但也具有局限性,人工勢場法易出現路徑振蕩、路徑過長以及局部最優等問題.

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

1.2 動態窗口法

1)算法原理簡介:動態窗口法(Dynamic Window Approach,DWA)最早于1997年由Dieter Fox等人提出[8],該算法將車輛所在的位置看作是窗口的中心,而窗口的寬度和長度則是車輛的大小和下一跳可到達的最大范圍.該算法從車輛的當前位置開始,基于車輛當前位置(x(t),y(t),θ(t))及車輛的線速度v(t)和角速度w(t),預判t+1時刻車輛位置(x(t+1),y(t+1),θ(t+1))的可能范圍,形成窗口,并計算窗口內是否存在障礙物.如果存在障礙物,則需要調整車輛運動方向,并重新計算窗口的位置和大小,實現避障.車輛狀態更新過程如式(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)算法優缺點分析:在局部避障中,動態窗口法的優點在于它的實時性和精度,該算法只需要計算當前窗口內的元素,而不需要重新計算整個地圖,因此可以實時檢測障礙物,并進行快速的路徑規劃和調整.但該算法高度依賴全局參數,容易在未知環境中失敗[9].

3)算法改進措施:Seder等[9]針對未知且動態的障礙物環境,將動態障礙物的移動視為所占據網格單元的移動,與AGV的運動單元軌跡進行碰撞預測,擴展了AGV在缺少全局參數更新時的無碰撞運動能力.Wang等人[10]重新設計了無人設備運動學模型和基于動態窗口法的局部路徑規劃方法評價函數,提高了環境負荷強度的權重,從而提高窗口靈敏度,縮減了路徑長度和航行時間.

1.3 Bug算法

(4)

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

2)算法優缺點分析:Bug算法結構相對簡單,可以逐步探測避開障礙物,不需要全局環境信息,但從始至終只以最新獲得的環境數據為操作依據,高度依賴傳感器提供數據,易因信息不足而規劃失敗,且無法處理動態障礙物.

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

2 基于幾何模型算法

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

2.1 柵格法

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

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

2.1.1 Dijkstra算法

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

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

(5)

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

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

2)算法優缺點分析:Dijkstra算法具有較強的魯棒性與健壯性,適用范圍廣,可用于非聯通圖,且可以得到完整路徑.但它的時間復雜度非常高,用于大規模地圖時計算成本極高,效率偏低.Dijkstra算法的時間復雜度為O(n2),其中n表示圖中節點的數量.為了提高算法效率,通常使用優先隊列來實現選擇當前最短距離的節點,這時Dijkstra算法的時間復雜度可以降低到O(mlogn),其中m表示邊的數量[17-20].

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

2.1.2 A*算法

1)算法原理簡介:A*算法由Nils John Nilsson等人于1968年提出,和Dijkstra算法一樣都是使用貪心策略來解決路徑規劃問題的成熟算法,而A*算法實際上是對Dijkstra算法的一種擴展和優化[26-28].相比于傳統的搜索算法,它引入了一個啟發式函數h(n),用來評估當前節點到目標節點的距離,進而預測可以找到最優路徑的下一跳節點.因此,A*算法能夠更快地找到最優路徑.

A*算法的啟發代價函數如式(6)所示[28]:

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

(6)

其中,g(n)代表節點n至起點的代價,是當前的實際代價;h(n)代表節點n至目標點的代價,是估計代價,代價通常用歐氏距離、曼哈頓距離表示.

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

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

2.1.3 D*算法

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

D*算法的啟發函數可傳遞.當中心柵格向周圍柵格擴展時,可將其啟發值傳遞給周圍鄰點.D*算法的代價公式由A*函數發展而來,如式(7)所示:

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

(7)

其中,G(s)為起始點至s的代價值,H(s)為啟發值,其計算方式如式(8)所示:

(8)

上式中,s′為s的拓展節點,H(s′)為s′的啟發值,C(s,s′)為相鄰節點的代價值,sgoal為目標點.進行柵格擴展的過程中,被擴展節點的啟發值由其拓展點s′的代價值以及拓展點s′的啟發值計算得來.

2)算法優缺點分析:相對于A*算法,D*算法在搜索效率方法有極大的提升,在100*100方陣圖中可以節省約33%的尋址時間和74.5%的節點個數[34].但是,D*算法規劃的路徑大多貼近障礙物邊緣,路徑平滑度較差.

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

2.1.4 向量場直方圖法

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

圖5 向量場直方圖法示意圖Fig.5 Schematic diagram of vector field histogram method

利用此極坐標圖可以計算出機器人的行走方向.首先確定出移動機器人可以安全避開障礙物所有路徑范圍,再在這些范圍內選擇損耗最低的路徑,即最優路徑.損耗函數L如式(9)所示:

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

(9)

式中,θtar表示目的角度;θwheel表示輪子角度;θbef表示原來角度;k、u、w為比例系數,損耗最小的就是最優路徑,調整這些系數可以改變移動機器人的避障效果.

2)算法優缺點分析:VFH算法的優點包括實現簡單、計算速度快以及處理噪聲干擾的能力強.同時,由于該算法可以使用機器人激光掃描數據構建向量場,因此該算法還可以應用于機器人導航的許多不同領域.雖然VFH算法確實是一種有效的避障算法,但是其處理速度及精度的限制,在某些環境下,例如高速控制或需要快速反應的避障應用中,VFH算法可能無法滿足要求.

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

2.2 Voronoi圖法

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

(10)

其中,D[(i,j),(x,y)]為柵格(i,j)到目標點(x,y)的歐氏距離;i,j與x,y為相應行列號.

2)算法優缺點分析:Voronoi圖法能夠實現平滑導航,同時避開障礙物,但是其算法時間復雜度高達O(n3),為時間復雜度最高的路徑規劃算法之一.

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

3 智能規劃算法

智能規劃算法是一種使用啟發式方法搜索空間來尋找最優路徑的方法,對環境的適應能力強,能夠根據規劃過程中獲得的新環境信息實時優化路徑并進行避障,主要包括基于群體智能的規劃算法和基于采樣的智能規劃算法兩類.

3.1 基于群體智能規劃算法

基于群體智能的規劃算法,是運用群體智能優化算法,通過群體中個體間的協作和競爭來尋找最優路徑,包括基于蟻群算法、粒子群算法、遺傳算法及神經網絡的路徑規劃算法等.

3.1.1 基于蟻群算法的路徑規劃

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

該算法首先要計算“螞蟻”(移動物體)在任意兩節點間轉移的可能性,如式(11)所示:

(11)

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

(12)

由公式(12)得,計算每段路徑的信息素濃度增加量需要累加每只“螞蟻”其對所經節點間路徑的信息素貢獻取決于其信息素常數及路徑長度,如公式(13)所示:

(13)

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

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

3.1.2 基于粒子群算法的路徑規劃

1)算法原理簡介:粒子群算法由Eberhart于1995年提出,通常以粒子的位置和速度來代表問題的解,通過不斷更新粒子的速度和位置來搜索最優解[53].很多AGV領域研究者將AGV所在的位置視為粒子位置,將粒子速度看作是代表每個節點之間的距離,通過更新粒子速度和位置,逐步搜索最優路徑,以實現路徑規劃及避障的目標.原始粒子群算法的速度和位置迭代方法分別如(14)和公式(15)所示:

(14)

(15)

其中,c1,c2為加速常數,用于調節學習最大步長;γ1,γ2兩個隨機函數,取值范圍[0,1],以增加搜索隨機性;w慣性權重,非負數,調節對解空間的搜索范圍;pbestid,gbestd分別為個體最優速度解和群體最優速度解;v,x分別為車輛速度和位置.

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

需要注意的是,在實際應用中,還需要考慮其他約束條件,如車輛數量、載重量約束、可運載品種約束、運行路線約束、工作時間約束等.這些約束條件可以通過對粒子的速度和位置進行限制來實現.綜上所述,粒子群算法可以應用于AGV路徑規劃中,通過將每個解表示為一個粒子,逐步優化每輛AGV執行任務的時間和順序,從而找到最優解或達到迭代次數.

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

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

3.1.3 基于遺傳算法的路徑規劃

1)算法原理簡介:遺傳算法最早是由John Holland于20世紀70年代提出,是一種基于自然進化和遺傳學原理設計的優化搜索算法,通過模擬自然的進化和遺傳過程,通過選擇、交叉和變異等操作,產生下一代潛在解或優化解,逐步優化最終的結果[57].在AGV路徑規劃及避障中,可以將AGV移動路徑看作染色體,將每條路徑的每個節點看作基因,通過實現遺傳算法的基本操作來逐步優化并生成最優路徑.

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

(16)

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

2)算法優缺點分析:與其他優化算法相比較,遺傳算法具有無需求解梯度信息、并行性、全局優化能力和搜索范圍大等優勢.但是,遺傳算法中存在一些關鍵參數,如種群大小、交叉概率、變異概率等,這些參數的選擇對算法的性能影響很大,需要經驗或進行大量試驗來確定最佳參數配置,耗費更多的計算資源和時間.

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

3.1.4 神經網絡法

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

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

(17)

其中,z[i]表示第i層的加權輸入(加權和加上偏差項),g(_)表示激活函數.

反向傳播算法用于根據損失函數來更新神經網絡的權重和偏差,以實現網絡的訓練.在每一層中,通過利用鏈式法則來計算梯度.令L表示損失函數,該函數可以是均方誤差(Mean Square Error)或交叉熵(Cross-entropy)等.對于第l層的權重矩陣w[i]和偏差項b[i],則反向傳播公式可以表示為:

(18)

這些是神經網絡中的基礎公式,用于計算前向傳播以獲取預測結果,并通過反向傳播來更新網絡參數以最小化損失函數.實際上,神經網絡的更復雜的變體和層級結構可能會引入其他公式和技巧,但這些基礎公式構成了神經網絡的核心.

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

2)算法優缺點分析:總的來說,在AGV路徑規劃及避障中使用神經網絡有可能顯著提高自動化材料處理和運輸系統的效率、可靠性和安全性,前提是需要花費大量時間成本提前構建并調校數據集訓練模型.此外,神經網絡在處理新環境的時候,需要額外的遷移學習方法來適應新的場景與任務,甚至需要對神經網絡的架構和參數進行重新配置和調整.

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

3.2 基于采樣的智能規劃算法

使用基于采樣的規劃算法進行路徑規劃及避障包括通過隨機采樣點并將它們連接起來形成圖來構建環境的路線圖,隨后搜索該圖,以找到從起點到目標點的最佳路徑,同時避開障礙物[68].該類算法在采樣點和連接點以形成圖的方式上有所不同,并且根據特定的環境和任務要求,它們各有優缺點[69].使用基于采樣的規劃算法實現路徑規劃及避障可能很復雜,尤其是對于障礙物較多的大型環境.然而,它可以為AGV在動態和不確定環境中規劃路徑提供一種高效有效的方法.當前常見的基于采樣的規劃算法有快速探索隨機樹和概率路線圖算法.

3.2.1 快速搜索隨機樹算法

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

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

RRT算法的關鍵思想是通過不斷生長的樹結構來探索搜索空間,即通過隨機采樣新的點,并將其連接到最近的節點來擴展樹,借此可以快速探索大型搜索空間,并找到有效的路徑.在該算法使用過程中,最重要的是為算法選擇適當的參數,如步長和迭代次數,以平衡環境的探索和開發,并確保算法根據特定的環境和任務要求進行適當的調整[71].

2)算法優缺點分析: RRT算法適用于在動態和雜亂環境中幫助AGV實現路徑規劃及避障,因為其樹狀隨機采樣的機制利于處理高維狀態空間,并且可以快速實時探索大型和復雜的環境.但也正因為其隨機性,該算法在不同時間處理同一環境、同一設備乃至同一任務都會得到不同結果.

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

3.2.2 概率路圖法

1)算法原理簡介:概率路圖(Probabilistic Road Map,簡稱PRM)最早于1996年由Smith R等人提出,主要通過對環境中的隨機點進行采樣進而構建概率路圖,隨后使用啟發式函數搜索連接采樣點以形成路線圖,從而實現移動機器人的路徑規劃及避障[76],其較為通用的啟發式函數由式(19)所示:

(19)

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

2)算法優缺點分析:與之前的RRT算法類似,PRM算法可以在復雜的動態環境中幫助AGV實行路徑規劃及避障.然而,它需要進行大量的采樣和連接,生成大量冗余采樣點,占用大量計算資源.

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

4 混合算法

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

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

綜上所述,混合算法可以融合各類規劃算法的優勢實現特定的改進需求,如規劃路徑的準確性、路徑距離以及規劃路徑時長等.此外,混合算法還具有良好的收斂性和效率高的特點,有利于避免陷入局部最優,提高規劃路徑的質量.更重要的是,混合算法不會因為AGV群體規模過大而變得難以使用.但是在選擇AGV路徑規劃與避障算法時,仍然要以環境模型與運行條件為主要參考指標,選擇滿足應用需求的算法,不必盲目追求使用混合算法,以免資源浪費.

5 AGV路徑規劃及避障算法分析與發展趨勢

5.1 對比分析

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

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

局部避障算法大多較為傳統、成熟,計算方式簡單,收斂速度快,且需要輸入環境中障礙物的詳細信息.例如,人工勢場法所添加的人工勢場是針對環境中潛在障礙物的;動態窗口法本質上是對AGV下一跳可能涉及的區域進行障礙物預警探測;Bug算法更是需要對路徑周邊的障礙物進行邊界追蹤操作,從而安全避障.由此可見,局部避障算法勢必賦予環境參數較高的權重,適合局部問題較多的環境.但是,受限于算法結構,該類算法并不適用于參數更加復雜的高維空間,且規避局部最優的能力有限.

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

相對于上述兩類較為傳統的路徑規劃算法,智能規劃算法更為復雜的結構、更為豐富的參數賦予了其更為強大的學習能力.群智能算法應用于路徑規劃,具有較好的適應性,可適用于不同的應用場景,具有較好的收斂速度,但是容易出現局部優化問題;遺傳算法克服了這一缺陷,但是其交叉和變異操作需要大量的計算,在降低算法收斂速度的同時實現最佳性能;結構更加復雜的神經網絡需要逐步優化模型參數,因此通常需要集成其他智能算法來提高性能.

5.2 發展趨勢

隨著人工智能、機器學習和深度學習等技術的不斷發展,AGV路徑規劃及避障算法也將不斷演化和升級.未來的AGV系統將更加智能、敏捷和自適應,能夠更好地適應復雜多變的環境和場景.未來AGV路徑規劃及避障算法的研究將更加關注以下幾個方面:

1)強化學習方法的廣泛應用.強化學習方法能夠使AGV系統實現更高水平的自主決策和行為,從而更加適應不確定性和變化性的環境;

2)感知與控制的融合.將傳感器感知和控制策略融合起來,實現更加全面、準確和實時的環境感知和控制決策,以達到AGV更高的路徑規劃及避障效果;

3)多智能體的協同合作.多智能體系統能夠實現多AGV之間的協同與合作,從而進一步提高系統的效率和魯棒性;

4)特定應用場景的需求.AGV的應用場景將逐漸擴展,從工業領域擴展到物流、醫療、倉儲、航天、智能家居等領域,不同的應用領域和場景將為AGV路徑規劃及避障提出新的挑戰.

值得一提的是,人工智能、機器學習等技術的不斷發展也會帶來新的挑戰,如機器安全性、隱私保護、倫理道德等問題需要相關領域的專家、學者和決策者一起協作解決.

6 結束語

AGV路徑規劃及避障算法一直是機器人領域的研究熱點和難點問題,本文所涉及的各種研究方法和技術手段也是學術界和工業界關注的焦點.在未來,隨著自動化技術的推進和人工智能的普及,AGV的應用場景將會更加廣泛,因此對于路徑規劃及避障算法的研究和優化也將變得更為重要.相信在廣大研究人員的共同努力下,AGV路徑規劃及避障算法的研究將會取得更加豐碩的成果,為智能制造、自動化倉儲等領域的發展注入新的動力.