基于改進人工勢場的AGV路徑規劃算法①

李鈞澤,孫 詠,焦艷菲,劉淳文,隋 東

1(中國科學院大學,北京 100049)

2(中國科學院 沈陽計算技術研究所,沈陽 110168)

3(沈陽中科數控技術股份有限公司,沈陽 110168)

隨著新興物流產業的發展,新建倉儲物流系統已逐漸實現了倉儲智能自動化.作為智能倉儲的重要組成部分,AGV (automated guided vehicle) 即自動導引車,在物流行業的應用正變得越來越廣泛.但對已建成多年的老舊倉庫,由于其廠房倉庫存在障礙物多雜且形狀不規則等特點,使 AGV的尋徑效率極大降低,嚴重阻礙了其智能化改造的進程.

路徑規劃即根據 AGV 所處的環境信息、運輸任務的位置信息,依照相應評價標準,規劃的一條從起始位置到目的位置的無碰撞最佳路徑[1].常用的路徑規劃算法有 Dijkstra 算法、A*算法、人工勢場算法、蟻群算法、遺傳算法等.其中人工勢場法(artificial potential field,APF)具有結構簡單、動態適應強、計算量小等優點,因此在實時避障與倉儲物流領域得到了廣泛的使用.

但傳統的人工勢場算法存在一定的局限性,例如目標不可達問題、局部極小值問題等[2,3].對此,國內外的專家學者各自提出了不同的改進人工勢場法來解決通用環境下的缺陷問題.趙明等[4]創新性地提出了自適應域—人工勢場改進算法,并通過域引導勢場對啟發點進行了域勢場傳遞,此種改進算法較好地解決了局部極小值問題.唐嘉寧等[5]在改進算法中引入了電場中的模擬等勢線概念,并對原算法中的斥力函數進行了改進,此改進算法有效解決了局部極小值問題.Weerakoon 等[6]提出了一種無死鎖的改進人工勢場算法,該算法通過引入與速度方向相關聯的障礙物信息,解決了傳統算法中目標點不可達與局部極小值問題.Fedele 等[7]為解決多障礙物勢場疊加引起的局部極小值問題,提出了一種基于勢場切換策略的改進人工勢場算法.

本文擬在老舊倉庫這一特定環境下進行研究,文中提及的老舊倉庫特指具有以下特點的倉庫.

(1)建成時間距今已超5年.

(2)倉庫內貨架堆積無序且緊密.

(3)倉庫內雜物分布隨機且與貨架擺放位置無明顯邊界.

本文將在此處預先對下文所提及算法進行明確指代.其中后文提及的傳統人工勢場法是指 Khatib 于1986年首次提出的人工勢場算法[8],后文中將以T-APF(traditional artificial potential field)代指.而針對本文所提出的新型改進人工勢場算法,后文將以I-APF(improved artificial potential field)代指.

針對傳統人工勢場算法(T-APF)中存在的缺陷,本文提出了一種新型的改進人工勢場算法(I-APF),該算法通過對引力與斥力的修正,解決了目標點不可達問題及易與遠目標端障礙物相撞問題;通過添加臨時障礙物的手段,解決了局部極小值問題.借由上述手段,提升了老舊倉庫中人工勢場算法尋徑成功率.最后使用 Matlab 軟件,對 I-APF的有效性進行了驗證.

1 傳統的人工勢場算法

人工勢場算法是由 Khatib 提出的,并首先應用于機械臂的運動規劃領域[8],后經發展現廣泛應用于路徑規劃領域.在路徑規劃問題中,人工勢場分別由目標點產生的引力勢場與障礙物產生的斥力勢場疊加而成.AGV 小車在人工勢場中受到勢場合力的作用,避開沿途障礙物,向目標點運動.

1.1 引力勢場

為使 AGV 小車能夠順利到達目標點,引力勢場的強度隨與目標點的距離增大而增大.因此,在T-APF 中引力勢場Uatt的定義為:

其中,Uatt代表引力勢場,katt為引力勢場常數,X表示AGV 所在當前點的位置坐標,Xg表示目標點的位置坐標,d(X,Xg)表示當前位置與目標點間的歐氏距離.

引力則定義為勢場的負梯度其表達式為:

1.2 斥力勢場

為使 AGV 可以避開障礙物,斥力勢場需要滿足勢能隨 AGV與障礙物的接近而增大,遠離而減小,當二者距離增大至斥力勢場所影響的最大距離d0時,障礙物與AGV 無碰撞的可能性,斥力勢場的大小應置為0.

類似的,斥力的定義為斥力勢場的負梯度.

斥力勢場及斥力的表達式如下:

其中,Urep為斥力勢場,krep為斥力勢場常數,X0表示障礙物的位置坐標,d(X,X0)表示當前位置與障礙物之間的歐氏距離,d0為斥力勢場影響的最大范圍.

1.3 老舊倉庫環境下傳統AGV 存在的缺陷

1.3.1 與遠目標端障礙物相撞

由式(2)可知,引力大小與AGV 及目標點間的距離呈線性關系.在路徑規劃初期,由于 AGV 距離目標點較遠,AGV 受到的引力較大.因此在接近障礙物之前,AGV 已具有較大的初速度,即使隨著與障礙物的接近斥力在逐漸增大,但引力的作用及慣性的存在仍使得 AGV 會與遠目標端障礙物相撞.

1.3.2 目標點不可達

由式(2)與式(4)可知,如果目標點附近存在障礙物,隨著 AGV 逐漸向目標點與障礙物靠近,斥力大小在逐漸增大,引力大小在逐漸減小,在到達某一區域時會出現斥力大于引力的情況,使得小車背離目標點運動,當離開此區域時,引力再次占據主導地位,小車重新向此區域運動,如此循環小車只能在目標點附近振蕩徘徊,最終停在勢能最低點處.

通用場景下由于障礙物分布稀疏,在目標點處附近存在障礙物的概率很低,實際使用中一般不考慮該問題.而老舊倉庫這一特定環境中,由于空間狹小,貨架、貨物、障礙物分布密集,目標不可達的發生概率極大增加,因而在該環境下目標點不可達問題成為了AGV 路徑規劃的嚴重阻礙.

1.3.3 局部極小值

局部極小值的實質就是在路徑某處出現了斥力與引力的平衡態,使得AGV 陷入了局部穩定狀態.如圖1所示,本文將局部極小值分為以下兩種情況:其一為開放式障礙物影響下的局部極小值,該類缺陷通常由多個障礙物組成,且障礙物間存在能使 AGV 直接穿越的間距,當 AGV 陷入其中時,由于受到相互平衡的斥力與引力,無法繼續前進.其二為半封閉式障礙物影響下的局部極小值,此類缺陷由孤立障礙物或多個間距極小的障礙物組成(障礙物間距不足以使 AGV 直接穿越).當 AGV 陷入其中時,無法通過直接穿越障礙物進行逃脫.同前者相似,AGV 在陷阱內受到相互平衡的斥力與引力,無法繼續前進.

圖1 開放式及半封閉式局部極小值示意圖

在老舊倉庫中由于障礙物的分布較通用場景下多而密,且分布的復雜程度、無序程度極大增加.因而通用場景下出現頻率極低的引力斥力平衡現象即局部極小值缺陷,在老舊倉庫中出現的頻率極大增加,成為了不容輕視的問題.

2 改進人工勢場算法

現在對傳統人工勢場算法的主流改進方式,多著眼于先對勢場改進,進而間接影響勢場力,最后改變AGV 運動狀態[9-11].以文獻[10]中的改進算法為例,其通過在T-APF 斥力勢場公式,即式(3)后添加AGV與目標點歐氏距離的n次冪作為距離因子,使得 AGV與目標點的距離也成為影響斥力勢場的因素之一.在對其改進的斥力勢場求負梯度后得到一個復合斥力.該復合斥力由兩個分力構成,其中一個斥力方向同原T-APF中的斥力,由障礙物指向AGV,另一斥力的方向由AGV 指向目標點.這種改進方式雖被證明是有效的,但是通過其改進勢場求得的復合斥力表達式冗余且復雜,直接導致了路徑規劃效率的降低.而本文直接對勢場力進行了優化,不再關注勢場本身,所得模型既兼顧了傳統算法的簡潔形式又不受到缺陷影響.

2.1 引力的改進

對引力改進針對的是與遠目標端障礙物相撞及目標點不可達缺陷.針對前者缺陷,根源在于遠離目標點時引力大于斥力.如果直接減小全局引力勢場常數,這樣雖然可避免AGV 在遠離目標點時與障礙物相撞,但當接近目標點時易因引力不足而造成目標點不可達的問題.因此,為兼顧遠距離處避碰,近距離處目標點可達,本文通過設定引力勢場安全距離常量ds將引力函數分段,在距離目標點較近的部分引力勢場常數可以適當增大,有助于解決接近目標點時引力不足造成的目標不可達問題.在距離目標點較遠的部分,應適當減小引力勢場常數,避免與障礙物相碰.改進后的引力勢場可以兼顧遠距離處避碰,近距離處目標點可達.其表達式如式(5)所示:

其中,k*att為較小的引力勢場常數,j*att為較大的引力勢場常數,ds為引力勢場安全距離常量.

2.2 斥力的改進

對斥力的改進針對的同樣是與遠目標端障礙物相撞及目標點不可達缺陷.同時解決這兩個缺陷的關鍵在于,要確保 AGV 在路徑規劃途中,非碰撞的情況下引力始終略大于斥力,從而使AGV 持續向目標點運動.由引力表達式(5)可知,隨著 AGV與目標點的靠近,引力大小在不斷減小,此時若不對斥力大小進行削減,極易造成靠近目標點時,斥力大于引力,出現目標點不可達現象.若直接減小斥力勢場常數,由式(5)可知,在路徑規劃初期引力極大,AGV 易與遠目標端障礙物相撞.因此斥力的變化趨勢需同引力一致.于是在原斥力表達式中,加入 AGV 當前位置與目標點的歐式距離作為因數,使引力與斥力的變化趨勢基本一致.在此基礎上,通過調整斥力勢場常數使斥力略小于引力,即可順利規劃路徑.改進后的斥力表達式如式(6)所示:

其中,d(X,Xg)為AGV 到目標點的歐氏距離.

2.3 臨時障礙物的引入

AGV 陷入局部極小值的原因是路徑規劃途中出現了斥力大于等于引力的區域(也稱陷阱區域),導致 AGV在該區域內出現局部振蕩現象,無法逃離.本文擬采用添加臨時障礙物的方式破壞 AGV 在陷阱區域內力的平衡態,實現 AGV的逃離,隨后再刪去臨時障礙物.具體逃離策略分直接穿越陷阱區域與繞行陷阱區域兩種.

對于半封閉式局部極小值問題,由于障礙物分布極為連續,AGV 無法做到直接穿越,因此只能選用繞行方式逃離陷阱區域.對于開放式局部極小值陷阱,由于障礙物分布較為稀疏,為使規劃路徑盡可能短,采用直接穿越方式逃離陷阱區域.

2.4 改進人工勢場算法的步驟

算法1.改進人工勢場算法X Xg k*att j*att dskrep d0 rtn0 l n 1) 參數初始化.首先初始化位置參數,包括 AGV的起始位置,目標點位置,障礙物位置坐標數組.其次初始化 APF的模型參數,包括引力勢場常數、,引力勢場安全距離常量,斥力勢場常數,斥力勢場最大影響范圍,陷阱半徑,最大逃離迭代數.最后初始化模擬仿真參數,包括步長,最大循環迭代次數.2) 進入循環體,并計算 AGV 所受合力.分別計算目標點對當前位置處AGV的引力及 AGV 受到的所有障礙物產生的斥力,并對引力與所有斥力求和.3) 計算 AGV 經過迭代后的坐標.通過合力與當前位置坐標,依據牛頓運動定律,計算下一路徑點 AGV 坐標,并將其置為AGV 當前位置點.

4)判斷AGV是否達到目標點.本算法規定當AGV與目標點距離小于迭代步長,視為AGV 已到達目標點.計算目標點與AGV 距離,與作比較,若 則表示 AGV 沒有到達目標點,將繼續執行第5) 步.否則判定 AGV 已經到達目標點,將當前路徑點坐標與目標點坐標加入軌跡數組,退出循環迭代,程序結束.l d(X,Xg) ld(X,Xg)＞l 5) 判定 AGV是否與障礙物相撞.本算法規定當AGV與障礙物距離小于步長 時,視為AGV與障礙物相撞.計算當前位置與所有障礙物的距離,取其中最小值與比較,若 則表示 AGV 沒有與障礙物相撞,繼續執行第6) 步.否則判定 AGV與障礙物相撞,程序結束.l dmin ldmin＞l 6) 判定 AGV是否陷入局部極小值.若當前迭代次數大于最大逃離迭代數,計算當前點位置坐標與前n0 個位置坐標 距離,當時,判定 AGV 陷入局部極小值陷阱,此時添加臨時障礙物后返回第2) 步繼續循環迭代.其他情況則視為沒有陷入局部極小值,直接返回第2) 步繼續迭代.n0 XXn0 d(X-Xn0)＜rt

3 算法的仿真與分析

本文使用 Matlab 對所提出的改進人工勢場算法進行仿真實驗,其中測試主機為Acer Aspire VN7-591G,配置為Intel(R) Core(TM) i5-4210H 2.90 GHz,內存為12 GB,并在Windows 10 操作系統下進行仿真,測試算法的有效性.

圖2針對的是與遠目標端障礙物相撞缺陷的路徑規劃仿真.該組仿真的參數如下:起點(0,0),終點(10,10)katt=30,k*att=10,j*att=30,krep=2,d0=3,l=0.2.如圖2所示,在使用 T-APF 進行路徑規劃時,AGV 在(2,2)處與障礙物發生碰撞.而使用 I-APF 時AGV 則成功達到目標點處.如前所述,I-APF 能夠成功避障的原因如下,其一為對引力表達式的改進,引入了k*att,使得 AGV 在距目標點較遠時引力較小.其二,對斥力的改進,在斥力表達式中加入因數d(X,Xg)使得斥力大小的變化趨勢同引力一致.因此,在距離目標點遠時斥力也相應地增大了,避免出現引力遠大于斥力的情況.

圖2 與遠目標端障礙物相撞缺陷環境中的路徑規劃

圖3針對的是老舊倉庫中易出現的目標點不可達缺陷的路徑規劃仿真.該組仿真參數如下:起點(0,0)終點(3,3)katt=30,ka*tt=20,j*att=40,krep=2,d0=1.5,l=0.1.如圖3所示,使用T-APF 進行仿真時,由于目標點附近存在障礙物,引力隨與目標點的接近而減小,斥力隨與障礙物接近而增大,此消彼長之下,最終會在接近目標點的途中出現斥力大于等于引力的情況,因而在震蕩后AGV 將無法到達目標點.而使用 I-APF 進行仿真時,由于在斥力勢場中引入了d(X,Xg),在AGV 接近目標點時,斥力也會和引力一樣同步減小,避免了斥力大于引力的情況發生.在引力方面,通過引入j*att補償了因距離減小而變小的引力,進一步地確保了在路徑規劃的末段引力大于斥力,使 AGV 可以順利到達目標點.

圖3 目標點不可達缺陷環境中的路徑規劃

圖4圖5分別針對的是局部極小值中的半封閉式障礙缺陷與開放式障礙缺陷的路徑規劃仿真,其中對半封閉式障礙采用繞行逃脫策略,對開放式障礙采用直接穿越的逃脫策略.開放式障礙組仿真參數如下:起點(0,0) 終點(3,3)katt=10,k*att=8,j*att=20,krep=2,d0=1.5,l=0.2.半封閉式障礙組仿真參數如下:起點(0,0) 終點(6,6)katt=10,ka*tt=8,j*att=30,krep=2,d0=1.5,l=0.2.如圖4圖5,使用 T-APF 法進行路徑規劃時,由于局部受力平衡,使得 AGV 陷入陷阱區域無法逃脫.對此,我們在AGV 陷入局部極小值時在附近添加了臨時的虛擬障礙物,幫助 AGV 脫離陷阱區域,隨后再將臨時障礙物去掉,使 AGV 順利到達目標點.

圖4 局部極小值中半封閉式缺陷環境的路徑規劃

圖5 局部極小值中開放式缺陷環境的路徑規劃

除對上述 T-APF 算法的典型缺陷環境進行路徑規劃仿真外,本文也對無陷阱環境進行了路徑規劃仿真.該組仿真參數如下:起點(0,0) 終點(10,8)katt=10,ka*tt=8,j*att=30,krep=3,d0=2,l=0.2.由圖6可知,在不存在缺陷障礙的情況下,兩種算法均可使 AGV 成功到達目標點.由表1數據可知,無論從路徑長度還是程序運行時間上來看,I-APF 算法均優于T-APF 算法.

表1 對T-APF與I-APF的算法評估

圖6 無陷阱環境中的路徑規劃

本節共進行了4 組實驗,前3 組實驗對前文中提到的3 種常見缺陷進行了陷阱障礙物仿真,并在其上分別使用 I-APF與T-APF 進行路徑規劃,實驗結果顯示 T-APF 無法成功規劃完整路徑,I-APF 可使 AGV 成功到達目標點.最后一組實驗是在無陷阱障礙物情況下進行的,目的是為了比較在無陷阱情況下,兩種算法的優劣情況,實驗結果顯示,二者均可使 AGV 成功到達目標點.但對路徑長度與程序運行時間兩個評價指標進行對比發現,I-APF 優于T-APF.

4 結語

為解決老舊倉庫中人工勢場算法易陷入陷阱的問題,本文提出了一種新型的改進人工勢場算法(I-APF).并在仿真環境下對傳統人工勢場算法(T-APF)與改進人工勢場算法進行了實驗,結果表明改進人工勢場算法優于傳統人工勢場算法.下一步研究中將計劃使改進人工勢場算法支持對動態障礙物的避障,使改進人工勢場算法可以更好地適用于老舊倉庫中 AGV的路徑規劃.