倪建云,杜合磊,谷海青,李 浩,吳 杰,薛晨陽
(1.天津市復(fù)雜系統(tǒng)控制理論與應(yīng)用重點實驗室, 天津 300384;2.天津理工大學(xué) 電氣工程與自動化學(xué)院, 天津 300384)
路徑規(guī)劃是移動機(jī)器人領(lǐng)域的重要分支之一,也是移動機(jī)器人導(dǎo)航技術(shù)的重點[1]。路徑規(guī)劃問題就是在一定約束條件下,按照一定的評價標(biāo)準(zhǔn)尋找一條最優(yōu)或次優(yōu)的無碰撞路徑[2]。移動機(jī)器人的路徑規(guī)劃按照對環(huán)境的已知程度,可以劃分為基于環(huán)境已知的全局路徑規(guī)劃和基于環(huán)境未知或局部已知的局部路徑規(guī)劃[3]。常用的方法有蟻群算法、柵格法、遺傳算法、快速擴(kuò)展隨機(jī)樹法、人工勢場法等。人工勢場法因具有反應(yīng)速度快、實時性強(qiáng)等優(yōu)點,被廣泛應(yīng)用于路徑規(guī)劃中。但是人工勢場存在目標(biāo)不可達(dá)和局部極小值的問題[4],如何更好地解決人工勢場存在的問題,國內(nèi)外學(xué)者做了廣泛的研究,最終產(chǎn)生了2個主要的方向。一種是通過改進(jìn)人工勢場的勢函數(shù),降低人工勢場陷入局部極小值的概率;另一種是與其他算法進(jìn)行融合來克服人工勢場的缺點。Lazarwaka等[5]提出了一種離散人工勢場法,將移動機(jī)器人的運動環(huán)境離散化,找尋最低離散點,解決局部極小值問題。王迪等[6]提出了一種左轉(zhuǎn)勢場法,使移動機(jī)器人陷入局部極小值時強(qiáng)制轉(zhuǎn)向,從而跳出局部極小值,但是這種方法在遇到類似封閉的陷阱區(qū)域時存在局限性,無法到達(dá)目標(biāo)點。楊凱等[7]通過移動機(jī)器人當(dāng)前位置、目標(biāo)點位置和障礙物位置建立數(shù)學(xué)關(guān)系,設(shè)置虛擬目標(biāo)點位置,以解決局部極小值問題。于振中等[8]提出了一種填平勢場來引導(dǎo)移動機(jī)器人走出局部極小值,但這種方法需要不斷將各種勢場強(qiáng)度進(jìn)行代數(shù)和疊加,計算量大且復(fù)雜。Sang等[9]將A*算法生成的全局路徑點分為最優(yōu)子目標(biāo)點序列,引導(dǎo)移動機(jī)器人不斷到達(dá)子目標(biāo)點,從而解決局部極小值問題。劉翰培等[10]針對局部極小值問題將模糊控制思想引入到了人工勢場法中,對移動機(jī)器人偏轉(zhuǎn)角進(jìn)行精確控制。趙炳巍等[11]結(jié)合模擬退火算法,在出現(xiàn)局部極小值位置附近增設(shè)隨機(jī)目標(biāo)點,用臨時引力牽引移動機(jī)器人走出局部極小值。
本文對傳統(tǒng)人工勢場的基本原理進(jìn)行了簡要概述,分析了目標(biāo)不可達(dá)和局部極小值形成的原因。在改進(jìn)斥力場函數(shù)的基礎(chǔ)上,通過橢圓形目標(biāo)策略設(shè)置虛擬目標(biāo)點,使移動機(jī)器人在陷入局部極小值時所受合力不為零,從而逃離局部極小值。另外,在橢圓形目標(biāo)策略設(shè)置虛擬目標(biāo)點的基礎(chǔ)上提出橢圓形跟蹤策略,采用模型預(yù)測控制算法跟蹤既定的部分橢圓形到達(dá)所設(shè)置的虛擬目標(biāo)點解決局部極小值。為了滿足移動機(jī)器人速度與加速度連續(xù)的要求,采用了3次均勻B樣條曲線對所規(guī)劃出的路徑進(jìn)行擬合處理。最后,在仿真平臺上對改進(jìn)算法與傳統(tǒng)算法進(jìn)行仿真對比實驗,實驗結(jié)果表明,本文的方法能夠有效解決傳統(tǒng)人工勢場的缺點。
人工勢場法是一種虛擬力法[12-13],于1986年首次被Khatib提出來的。該方法是將移動機(jī)器人抽象為一個點,該點在人工勢場2種虛擬場源的作用下運動。虛擬場源分為2類,一類是引力勢場源:將目標(biāo)點視為引力極產(chǎn)生引力,引力極產(chǎn)生的引力是移動機(jī)器人位置與目標(biāo)點位置之間的距離相關(guān)函數(shù);另一類是斥力勢場源:將障礙物視為斥力極產(chǎn)生斥力,斥力極產(chǎn)生的斥力是移動機(jī)器人位置與障礙物位置之間的距離相關(guān)函數(shù)。引力與斥力疊加的矢量大小和方向就是移動機(jī)器人運動的大小和方向,傳統(tǒng)人工勢場法如圖1所示。

圖1 傳統(tǒng)人工勢場法示意圖
假設(shè)移動機(jī)器人在運動環(huán)境中的位置向量為X=(x,y)T,目標(biāo)點位置向量為Xg=(xg,yg)T,定義引力勢場函數(shù)[14]:
(1)
式中:Uatt(X)為引力勢場;ka為引力勢場常量。相應(yīng)的引力為Uatt(X)的負(fù)梯度:
Fatt(X)=-grad(Uatt(X))=
-ΔUatt(X)=-ka(X-Xg)
(2)
假設(shè)障礙物在運動環(huán)境中的位置向量為Xo=(xo,yo)T,定義斥力勢場函數(shù)為:
式中:Urep(X)為斥力勢場;kr為斥力勢場常量;ρ為障礙物的最大影響范圍。相應(yīng)的斥力為Urep(X) 的負(fù)梯度:
Frep(X)=-grad(Urep(X))=-ΔUrep(X)=

(4)
總勢場為引力勢場與斥力勢場的和:
Utotal(X)=Uatt(X)+Urep(X)
(5)
合力為引力與斥力的矢量和:
Ftotal(X)=Fatt(X)+Frep(X)=

(6)
傳統(tǒng)人工勢場法(T-APF)的目標(biāo)不可達(dá)問題就是當(dāng)目標(biāo)點附近存在障礙物,即目標(biāo)點此時處在障礙物最大影響范圍之內(nèi)時,移動機(jī)器人在運動時受到的斥力大于引力,導(dǎo)致移動機(jī)器人停止運動或在某一區(qū)域內(nèi)徘徊,從而無法到達(dá)目標(biāo)點的過程,如圖2所示,此時斥力大于引力,合力方向偏于目標(biāo)點位置方向,導(dǎo)致移動機(jī)器人無法到達(dá)目標(biāo)點。

圖2 目標(biāo)不可達(dá)問題示意圖
局部極小值就是移動機(jī)器人所受到的引力與斥力合力大小相同方向相反,即移動機(jī)器人受到的合力為零,移動機(jī)器人停止了運動或在某一區(qū)域徘徊的過程。針對運動環(huán)境中障礙物數(shù)量的不同,具體分析移動機(jī)器人陷入局部極小值的情況。
對于小于2個障礙物的簡單運動環(huán)境,移動機(jī)器人陷入局部極小值最常見的情況有3種:一是障礙物在移動機(jī)器人與目標(biāo)點中間;二是目標(biāo)點在移動機(jī)器人與障礙物中間;三是2個障礙物分布在移動機(jī)器人與目標(biāo)點連線的兩邊。3種情況分別如圖3—圖5所示。

圖3 局部極小值1受力分析示意圖

圖4 局部極小值2受力分析示意圖

圖5 局部極小值3受力分析示意圖
對于大于2個障礙物的復(fù)雜運動環(huán)境,移動機(jī)器人陷入局部極小值最常見的情況有兩字形陷阱問題。如圖6 U型陷阱區(qū)域受力分析和圖7 L型陷阱區(qū)域受力分析所示,圖中的Frep代表著斥力和。

圖6 U型陷阱區(qū)域受力分析示意圖

圖7 L型陷阱區(qū)域受力分析示意圖
為了能夠更好地處理目標(biāo)不可達(dá)問題,本文采用改進(jìn)人工勢場法(I-APF)進(jìn)行解決,即在斥力勢場函數(shù)中加入距離因子,距離因子是移動機(jī)器人當(dāng)前位置與目標(biāo)點位置之間的歐氏距離。則此時斥力場函數(shù)為:

(7)
相應(yīng)的斥力為:

(8)
式(7)和式(8)中的(X-Xg)n是距離因子,Frep 1和Frep2是斥力Frep(X)的2個分力,Frep1所在方向與障礙物位置向量指向移動機(jī)器人位置向量的方向一致,Frep2所在方向與移動機(jī)器人位置向量指向目標(biāo)點位置向量的方向一致。選取0 圖8 改進(jìn)斥力場函數(shù)受力分析示意圖 對于圖4中局部極小值2的情況,本文采用當(dāng)移動機(jī)器人陷入局部極小值時忽略障礙物斥力的方法進(jìn)行解決,此時移動機(jī)器人只受到目標(biāo)點引力,解決局部極小值2問題如圖9所示。 圖9 解決局部極小值2問題示意圖 本文提出了一種橢圓形目標(biāo)策略(IEVAPF)解決人工勢場法存在的局部極小值問題。該方法以移動機(jī)器人與障礙物之間的歐氏距離為長半軸,以障礙物膨脹距離為短半軸建立橢圓形,短軸所在的直線與橢圓形相交的頂點為虛擬目標(biāo)點構(gòu)建位置,此時移動機(jī)器人受到虛擬目標(biāo)點的引力逃離局部極小值位置。由于運動環(huán)境不同,所以選取的障礙物有所不同,對于單一障礙物運動環(huán)境,障礙物只有一個選擇,此時產(chǎn)生2個虛擬目標(biāo)點可以隨機(jī)選取其中一個;對于2個障礙物運動環(huán)境,2個障礙物可以隨機(jī)選取,但是需要選取遠(yuǎn)離另一個障礙物位置的虛擬目標(biāo)點;對于多個障礙物運動環(huán)境,尤其是2個陷阱區(qū)域,選取離移動機(jī)器人最遠(yuǎn)距離的障礙物實行橢圓形目標(biāo)策略。各運動環(huán)境解決方法如圖10橢圓形目標(biāo)策略所示。 圖10 橢圓形目標(biāo)策略 針對圖10(c)和圖10(d)中橢圓形目標(biāo)策略,為了提高規(guī)劃效率,防止移動機(jī)器人在逃離局部極小值時再次陷入新的局部極小值點,對長半軸加入一個權(quán)重因子α,即長半軸: L=α(X-Xo),α≥1 (9) 權(quán)重因子α的選擇影響虛擬目標(biāo)點的位置,應(yīng)使得橢圓形可以包圍邊緣障礙物,在考慮移動機(jī)器人大小的前提下,可以有效避免在運動過程中碰撞到障礙物,致使規(guī)劃失敗。 本文提出了一種橢圓形跟蹤策略(IEMAPF),在橢圓形目標(biāo)策略確定橢圓形和虛擬目標(biāo)點的基礎(chǔ)上,采用結(jié)合移動機(jī)器人運動學(xué)模型的模型預(yù)測控制算法[15-16]設(shè)計控制器,進(jìn)行跟蹤既定的部分橢圓形到達(dá)虛擬目標(biāo)點,從而解決陷入局部極小值的問題。移動機(jī)器人的運動學(xué)狀態(tài)方程為: (10) 式(10)中:(x,y)為移動機(jī)器人后軸中心坐標(biāo);φ為移動機(jī)器人的橫擺角;v為后輪速度;δ為前輪轉(zhuǎn)角;l為移動機(jī)器人前后輪之間軸距長度。針對于單個障礙物、2個障礙物和多個障礙物的運動環(huán)境,橢圓形跟蹤策略的解決方法如圖11所示。以圖11(a)所示的單個障礙物環(huán)境為例,當(dāng)機(jī)器人處于局部極小的狀態(tài)時,在橢圓形目標(biāo)策略確定了橢圓形和虛擬目標(biāo)點的基礎(chǔ)上,采用了橢圓形跟蹤策略跟蹤既定的部分橢圓形,即圖中橢圓形的實線部分。針對圖11(d)中“L”字形陷阱區(qū)域的情況,由于加入了權(quán)重因子α,在實行橢圓形跟蹤策略時,根據(jù)橢圓形目標(biāo)策略所構(gòu)建的橢圓形,提前預(yù)測機(jī)器人陷入局部極小的位置坐標(biāo)點,即圖中虛線受力分析部分,繼而進(jìn)行橢圓形跟蹤策略,即圖中橢圓形的實線部分。 圖11 橢圓形跟蹤策略示意圖 B樣條曲線因其局部可修改性的優(yōu)點,尤其是具有表達(dá)式簡單的特點,使得B樣條曲線在路徑擬合處理中得到了廣泛的應(yīng)用。其中三次均勻B樣條曲線在節(jié)點處具有二階連續(xù)性的特點,可以滿足移動機(jī)器人速度與加速度連續(xù)性要求[17],因此,本文針對所規(guī)劃出的路徑在拐點處不平滑且降低了移動機(jī)器人轉(zhuǎn)彎效率的問題,引入了三次均勻B樣條曲線對所規(guī)劃路徑進(jìn)行擬合處理。B樣條曲線的數(shù)學(xué)表達(dá)式為[18-19]: (11) 式中:Pi為路徑中給定的控制點坐標(biāo);Ni,k(t)為B樣條曲線的基函數(shù),基函數(shù)的具體表達(dá)式為: (12) (13) 將式(13)代入到B樣條表達(dá)式式(11)中可得到三次均勻B樣條曲線方程的矩陣表達(dá)形式為: (14) 針對以上提到的所有運動環(huán)境,為了驗證I-APF、IEVAPF和IEMAPF有效性,使用Matlab搭載運動環(huán)境進(jìn)行仿真實驗。對目標(biāo)不可達(dá)和單個障礙物、2個障礙物和多個障礙物環(huán)境問題分別進(jìn)行對比仿真。本文設(shè)置的人工勢場參數(shù)如表1所示。下面所有的運動環(huán)境實驗仿真的人工勢場參數(shù)都與表1的參數(shù)相同。 表1 人工勢場參數(shù) 對于圖2中目標(biāo)不可達(dá)問題,采用圖8所示的改進(jìn)斥力場函數(shù)受力分析方法進(jìn)行解決。圖12所示為目標(biāo)不可達(dá)問題的運動環(huán)境,藍(lán)色星號(0,0) 為起點位置坐標(biāo),綠色實心圓(10,10)為目標(biāo)點位置坐標(biāo),黑色實心圓(9,9.5)為障礙物位置坐標(biāo)。圖12(a)中,在傳統(tǒng)人工勢場作用下,移動機(jī)器人未能到達(dá)目標(biāo)點位置,圖12(b)中,在改進(jìn)斥力場函數(shù)情況下,移動機(jī)器人最終到達(dá)目標(biāo)點。圖12(c)是三次均勻B樣條曲線擬合處理(B-APF)后的路徑結(jié)果,可以看出,在路徑拐點處擬合后的路徑相比之前更平滑。 圖12 目標(biāo)不可達(dá)問題的運動環(huán)境仿真示意圖 對于圖4中局部極小值2情況,根據(jù)圖9給出的解決方法進(jìn)行實驗驗證。設(shè)置起點位置坐標(biāo)(0,0),目標(biāo)點位置坐標(biāo)(10,10),障礙物位置坐標(biāo)(11,11)。圖13(a)表示傳統(tǒng)人工勢場,移動機(jī)器人在距離目標(biāo)點一段距離處徘徊,導(dǎo)致路徑規(guī)劃失敗,此時忽略障礙物斥力,如圖13(b)所示,移動機(jī)器人順利到達(dá)目標(biāo)點。由圖13(c)所示,經(jīng)過三次均勻B樣條曲線擬合處理后,去掉了路徑上的冗余點,使路徑更平滑。 圖13 局部極小值2仿真示意圖 5.2.1單一障礙物環(huán)境仿真 對于圖3中局部極小值1情況,圖10(a)和圖11(a)分別給出了橢圓形目標(biāo)策略和橢圓形跟蹤策略解決方法。設(shè)置圖3中運動環(huán)境起點位置坐標(biāo)(0,0),目標(biāo)點位置坐標(biāo)(10,10),障礙物位置坐標(biāo)(7,7)。圖14(a)和圖14(b)給出了2種策略的實驗仿真,圖14(c)是三次均勻B樣條曲線擬合橢圓形目標(biāo)策略(B-IEVAPF)的仿真結(jié)果,圖14(d)是三次均勻B樣條曲線擬合橢圓形跟蹤策略(B-IEMAPF)的仿真結(jié)果。 5.2.2兩個障礙物環(huán)境仿真 對于圖5中2個障礙物造成局部極小值的情況,根據(jù)圖10(b)和圖11(b)2種策略進(jìn)行解決。設(shè)置圖5中運動環(huán)境起點位置坐標(biāo)(0,0),目標(biāo)點位置坐標(biāo)(10,10),障礙物位置坐標(biāo)(5.5,3.5)和(3.5,5.5)。圖15(a)和圖15(b)分別是2種策略實驗仿真,圖15(c)和圖15(d)給出了2種策略經(jīng)過三次均勻B樣條曲線處理過的仿真結(jié)果。 圖15 局部極小值3仿真 5.2.3復(fù)雜障礙物環(huán)境仿真 對于圖6和圖7中多障礙物復(fù)雜環(huán)境,分別按照圖10(c)、圖11(c)和圖10(d)、圖11(d)進(jìn)行實驗仿真。運動環(huán)境中起點位置坐標(biāo)(0,0),目標(biāo)點位置坐標(biāo)(10,10),障礙物位置坐標(biāo)排列成“U”字形和“L”字形。圖16是圖6中U形陷阱區(qū)域問題的仿真,且給出了三次均勻B樣條曲線處理后的結(jié)果。圖16中沒有加入權(quán)重因子α,為了驗證加入權(quán)重因子的效果,圖17中L形陷阱區(qū)域仿真給出了仿真驗證。由圖10(d)和圖11(d)中可以看出,在采用2種策略進(jìn)行解決局部極小值問題時,橢圓形與障礙物相交導(dǎo)致設(shè)置的虛擬目標(biāo)點位置可能使移動機(jī)器人再次陷入局部極小值,因此,根據(jù)式(9)選取權(quán)重因子α=1.2,改變橢圓形長半軸大小,讓橢圓形可以包圍邊緣障礙物,提高移動機(jī)器人的規(guī)劃效率,如圖18所示。圖17(a)和圖17(b)中,在加入權(quán)重因子的情況下,可以順利完成規(guī)劃任務(wù)。圖18(a)中,未加入權(quán)重因子,導(dǎo)致再次陷入局部極小值點,圖18(b)中,在加入權(quán)重因子后,可以順利逃離局部極小值點且避免了二次陷入局部極小值的問題。同時為了驗證不同權(quán)重因子對路徑規(guī)劃的影響,分別設(shè)置了權(quán)重因子數(shù)值為1.2如圖18(b),權(quán)重因子數(shù)值為2如圖18(c)。圖中可以看出兩者對IEVAPF方法影響不大,但對于圖18(d)中IEMAPF方法影響較大,相比圖17(b),由于橢圓形變大使跟蹤既定的部分橢圓形路徑變長,通過B樣條擬合處理后的圖18(e)中路徑也要相對變長,具體路徑評價參數(shù)可見表4不同權(quán)重因子路徑評價表所示。圖16(c)、(d)和圖17(c)、(d)分別給出了2種陷阱區(qū)域的2種策略經(jīng)過三次均勻B樣條曲線處理過的仿真結(jié)果。 圖16 U形陷阱區(qū)域仿真 圖17 L形陷阱區(qū)域仿真 圖18 加入權(quán)重因子對比仿真示意圖 針對IEMAPF方法,在局部極小值點位置時,通過當(dāng)前位置姿態(tài)與下一運動時刻位置姿態(tài)計算獲取移動機(jī)器人前輪轉(zhuǎn)角,為了驗證移動機(jī)器人不同速度下IEMAPF方法的有效性,圖19給出了不同速度下IEMAPF方法對比圖。圖19(a)給出了不同速度下跟蹤既定路徑的仿真,為了能夠清楚地分析,圖19(c)對不同位置的跟蹤效果進(jìn)行了局部放大處理。從局部放大圖和圖19(b)跟蹤誤差圖可以分析出,當(dāng)速度v=10 m/s(圖中藍(lán)色表示)時,相比v=2 m/s(圖中紅色表示)時跟蹤效果較差一點,但是在速度相差較大時,都能夠保持良好的跟蹤精度且誤差小于0.031 m。為了更好地貼合既定路徑,采用相對較小的跟蹤速度。 為了驗證IEVAPF和IEMAPF 2種策略的有效性,圖20給出了復(fù)雜區(qū)域?qū)嶒灧抡?。?fù)雜區(qū)域運動環(huán)境中包括了目標(biāo)不可達(dá)和所有局部極小值的環(huán)境。運動環(huán)境起點位置坐標(biāo)設(shè)置成(0,0),目標(biāo)點位置坐標(biāo)為(14,14),51個障礙物組成各種陷阱環(huán)境。 由圖20(a)和圖20(b)所示,2種策略在陷入2次局部極小值后成功到達(dá)目標(biāo)點,有效證明本文所提方法能夠解決傳統(tǒng)人工勢場法的缺點。圖20(c)、(d)是經(jīng)過三次均勻B樣條處理后的路徑。 圖19 不同速度IEMAPF仿真圖 圖20 復(fù)雜區(qū)域仿真圖 為了使圖12目標(biāo)不可達(dá)仿真圖和圖13局部極小值2仿真圖的仿真結(jié)果更加直觀,對傳統(tǒng)人工勢場法、改進(jìn)人工勢場法和經(jīng)三次均勻B樣條擬合后人工勢場法的路徑長度進(jìn)行對比。由表2可知,傳統(tǒng)人工勢場法失效,導(dǎo)致機(jī)器人不能到達(dá)目標(biāo)點,三次均勻B樣條擬合后,人工勢場法在路徑長度上要短于改進(jìn)人工勢場法。 表2 路徑評價表1 為了直觀地驗證2種策略能夠有效解決傳統(tǒng)人工勢場法的缺點,表3以移動機(jī)器人路徑長度和擬合后的路徑長度為評價標(biāo)準(zhǔn)進(jìn)行對比。 表3 路徑評價表2 由表3可以看出:橢圓形跟蹤策略要比橢圓形目標(biāo)策略的路徑上短,可以提高移動機(jī)器人的運動效率。經(jīng)過三次均勻B樣條曲線擬合后,路徑長度都明顯縮短,橢圓形跟蹤策略仍然優(yōu)于橢圓形目標(biāo)策略。 由表4中不同權(quán)重因子可以分析出:當(dāng)沒有加入權(quán)重因子,即權(quán)重因子為1時,路徑規(guī)劃失敗;當(dāng)選取的權(quán)重因子不斷變大時,對IEMAPF方法和B-IEMAPF方法影響較大,因此,設(shè)置權(quán)重因子時,應(yīng)在保證成功規(guī)劃的基礎(chǔ)上,盡量選取較小的權(quán)重因子。 表4 不同權(quán)重因子路徑評價 針對傳統(tǒng)人工勢場法存在目標(biāo)不可達(dá)和局部極小值問題,提出一種改進(jìn)的人工勢場法。在改進(jìn)斥力場函數(shù)的基礎(chǔ)上,提出橢圓形目標(biāo)策略和橢圓形跟蹤策略,當(dāng)機(jī)器人陷入局部極小值后仍能夠及時向目標(biāo)點移動,完成路徑規(guī)劃任務(wù)。為了使規(guī)劃路徑更加平滑,采用三次均勻B樣條曲線對規(guī)劃路徑進(jìn)行擬合處理。最后在仿真平臺中對傳統(tǒng)人工勢場法與IAPF、IEVAPF、IEMAPF、B-IEVAPF和B-IEMAPF進(jìn)行不同運動環(huán)境的仿真實驗,證實了所提改進(jìn)人工勢場法的可行性與有效性。

3.1 橢圓形目標(biāo)策略

3.2 橢圓形跟蹤策略

4 三次均勻B樣條擬合處理

5 實驗仿真

5.1 目標(biāo)不可達(dá)環(huán)境仿真

5.2 局部極小值環(huán)境仿真







5.3 路徑評價對比



6 結(jié)論