基于改進(jìn)人工勢場的AGV路徑規(guī)劃算法①

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

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

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

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

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

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

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

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

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

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

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

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

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

1 傳統(tǒng)的人工勢場算法

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

1.1 引力勢場

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

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

引力則定義為勢場的負(fù)梯度其表達(dá)式為:

1.2 斥力勢場

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

類似的,斥力的定義為斥力勢場的負(fù)梯度.

斥力勢場及斥力的表達(dá)式如下:

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

1.3 老舊倉庫環(huán)境下傳統(tǒng)AGV 存在的缺陷

1.3.1 與遠(yuǎn)目標(biāo)端障礙物相撞

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

1.3.2 目標(biāo)點不可達(dá)

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

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

1.3.3 局部極小值

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

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

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

2 改進(jìn)人工勢場算法

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

2.1 引力的改進(jìn)

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

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

2.2 斥力的改進(jìn)

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

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

2.3 臨時障礙物的引入

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

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

2.4 改進(jìn)人工勢場算法的步驟

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

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

3 算法的仿真與分析

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

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

圖2 與遠(yuǎn)目標(biāo)端障礙物相撞缺陷環(huán)境中的路徑規(guī)劃

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

圖3 目標(biāo)點不可達(dá)缺陷環(huán)境中的路徑規(guī)劃

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

圖4 局部極小值中半封閉式缺陷環(huán)境的路徑規(guī)劃

圖5 局部極小值中開放式缺陷環(huán)境的路徑規(guī)劃

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

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

圖6 無陷阱環(huán)境中的路徑規(guī)劃

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

4 結(jié)語

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