王 震， 陳 熙， 張 浩， 蔚 濤， 鄧 科，季袁冬

(1.四川大學(xué)空天科學(xué)與工程學(xué)院, 成都 610064；2.四川大學(xué)數(shù)學(xué)學(xué)院, 成都 610064)

1 引 言

近年來(lái)，模仿自然界生物群體行為的群體智能理論逐漸成為研究熱點(diǎn).避障是一種最基本的群體行為.相應(yīng)地，現(xiàn)有的避障算法主要基于虛擬勢(shì)場(chǎng)，主要有兩類(lèi)：一類(lèi)是人工勢(shì)場(chǎng)，包括傳統(tǒng)人工勢(shì)場(chǎng)以及對(duì)其勢(shì)場(chǎng)函數(shù)[1-3]、增量系數(shù)[4]、避障機(jī)制[1,5]等的改進(jìn)，該類(lèi)算法根據(jù)形成的虛擬勢(shì)場(chǎng)，沿著勢(shì)能降低的方向?qū)崟r(shí)規(guī)劃避障路徑；另一類(lèi)則以圓形[6-8]、橢圓形[9-10]等極限環(huán)作為勢(shì)場(chǎng)，該類(lèi)算法利用二階非線性函數(shù)的極限環(huán)特性和障礙的位置信息實(shí)時(shí)得出障礙繞行路線.

但是，隨著研究的深入，人們發(fā)現(xiàn)傳統(tǒng)的人工勢(shì)場(chǎng)法與極限環(huán)法在處理復(fù)雜環(huán)境下的群體避障問(wèn)題時(shí)存在不足，障礙的不規(guī)則性、非預(yù)知性與環(huán)境的有界性特別是不能很好地應(yīng)對(duì)的挑戰(zhàn).近年來(lái)，大量學(xué)者對(duì)此開(kāi)展了研究.如文獻(xiàn)[10-12]針對(duì)凹型不規(guī)則障礙，通過(guò)設(shè)置虛擬目標(biāo)點(diǎn)或虛擬牽引力來(lái)引導(dǎo)智能體對(duì)其進(jìn)行繞行，解決了傳統(tǒng)方法在此類(lèi)環(huán)境下的目標(biāo)不可達(dá)問(wèn)題.針對(duì)既不規(guī)則又非預(yù)知的障礙，文獻(xiàn)[1]以虛擬目標(biāo)點(diǎn)解決不規(guī)則障礙繞行問(wèn)題，僅利用局部信息計(jì)算所得的虛擬勢(shì)場(chǎng)便實(shí)現(xiàn)了對(duì)非預(yù)知障礙的成功繞行.值得注意的是，上述研究?jī)H針對(duì)預(yù)知/非預(yù)知復(fù)雜環(huán)境下的單智能體避障，無(wú)法從原理上避免局部極小值與路徑抖動(dòng).此外，針對(duì)帶邊界環(huán)境下群體避障問(wèn)題，文獻(xiàn)[13]提出了基于速度場(chǎng)這一虛擬勢(shì)場(chǎng)的群體避障算法，但其通過(guò)邊界完成群體聚集這一特性使其無(wú)法適應(yīng)大規(guī)模邊界場(chǎng)景或開(kāi)放場(chǎng)景.

鑒于現(xiàn)有對(duì)于不規(guī)則、非預(yù)知障礙與有界環(huán)境下的避障算法研究中針對(duì)群體避障的研究較少，對(duì)三種問(wèn)題同時(shí)存在的復(fù)雜環(huán)境下的群體避障算法研究更少，我們提出以下方案：僅利用單個(gè)智能體的有限探測(cè)信息，在局部可視不規(guī)則障礙的邊緣設(shè)置平衡點(diǎn)，以該點(diǎn)為中心建立局部極限環(huán)，群體沿所有局部極限環(huán)的包絡(luò)對(duì)該障礙進(jìn)行繞行.另一方面，我們將群體在局部可視邊界上的投影點(diǎn)設(shè)置為虛擬障礙，以改進(jìn)的人工勢(shì)場(chǎng)斥力函數(shù)作為該虛擬障礙的勢(shì)場(chǎng)函數(shù)，以避免與邊界發(fā)生碰撞.

2 避障算法

2.1 極限環(huán)

極限環(huán)[10]是非線性方程(組)的相平面中的一個(gè)孤立閉曲線，最早由Van de Pol發(fā)現(xiàn)并用圖解法證明了曲線的存在性.

考慮如下二階非線性系統(tǒng)方程：

(1)

其中x1和x2是系統(tǒng)的狀態(tài)變量，γ∈{-1,1}表示旋轉(zhuǎn)方向(γ=1表示沿順時(shí)針旋轉(zhuǎn)，γ=-1表示沿逆時(shí)針旋轉(zhuǎn))，α1和α2是兩個(gè)正常數(shù)，ρ=1-(x1/R)2-(x2/R)2，用于確定極限環(huán)的形狀.文獻(xiàn)[6]利用李雅普諾夫函數(shù)證明了該方程是全局漸近穩(wěn)定的.為了展示系統(tǒng)方程的極限環(huán)，我們將其改寫(xiě)為

(2)

其中

xff=[x2,-x1]T，

α=diag([α1,α2])，

xfb=ρ[x1,x2]T.

圖1 圓形極限環(huán)軌跡示意圖：順時(shí)針(a)，逆時(shí)針(b)

2.2 局部極限環(huán)避障

傳統(tǒng)極限環(huán)避障算法以障礙為中心設(shè)計(jì)環(huán)形虛擬勢(shì)場(chǎng)，智能體在該勢(shì)場(chǎng)引導(dǎo)下進(jìn)行障礙繞行.當(dāng)障礙不規(guī)則時(shí)，上述方法得到的繞行路徑通常存在冗余，如圖2所示.此外，當(dāng)障礙非預(yù)知時(shí)，我們無(wú)法觀測(cè)到障礙的完整信息，上述方法無(wú)法使用，如圖3所示.為此，我們將局部極限環(huán)與包絡(luò)的思想引入極限環(huán)避障算法中，得到了局部極限環(huán)避障算法.

Fig.2 Obstacle-avoiding path of an agent

圖3 智能體的感知范圍

鑒于障礙不規(guī)則與智能體探測(cè)能力有限，我們利用局部極限環(huán)法來(lái)實(shí)時(shí)規(guī)劃避障路徑，即智能體根據(jù)傳感器探測(cè)到的障礙局部邊緣信息，以距離智能體最近的邊緣點(diǎn)為平衡點(diǎn)，以該點(diǎn)為中心建立局部極限環(huán)，通過(guò)繞行一系列局部極限環(huán)來(lái)實(shí)現(xiàn)避開(kāi)障礙的效果，相應(yīng)的繞行路徑為上述局部極限環(huán)的包絡(luò)，如圖4所示.

圖4 智能體的局部極限環(huán)避障

局部極限環(huán)避障算法的具體實(shí)施步驟如下.

(i) 初始化智能體i的位置、速度、繞行方向及目標(biāo)點(diǎn)的位置，其中繞行方向γi=0.

(ii) 根據(jù)第i個(gè)智能體和設(shè)定目標(biāo)點(diǎn)的位置信息，寫(xiě)出過(guò)兩點(diǎn)的直線方程Li:ax+by+c=0,其中a≥0.

(iii) 若障礙在智能體的探測(cè)范圍內(nèi)，且直線方程Li穿過(guò)所探測(cè)到的局部障礙，則繼續(xù)后面步驟.

(iv) 設(shè)(oxi,oyi)為群體中第i個(gè)智能體在障礙邊緣的可變平衡點(diǎn).若此智能體繞行方向γi取值為0，則執(zhí)行步驟(v)，否則執(zhí)行步驟(vi).

(vi) 設(shè)(xi,yi)為群體中第i個(gè)智能體的位置，rv為預(yù)設(shè)極限環(huán)半徑.我們用下式來(lái)計(jì)算智能體i的速度：

(3)

這樣，隨著群體的運(yùn)動(dòng)，直線方程Li和平衡點(diǎn)(oxi,oyi)不斷變化，但繞行方向一旦確定則維持不變.重復(fù)步驟(ii)～(vi)，直至繞開(kāi)障礙.

借助人工勢(shì)場(chǎng)的思想，我們?cè)谶吔缣幰胍粋€(gè)虛擬斥力場(chǎng)，使智能體在力場(chǎng)中受力運(yùn)動(dòng)，從而避免與邊界碰撞.

在傳統(tǒng)人工勢(shì)場(chǎng)法中，智能體、障礙物是運(yùn)動(dòng)空間中的質(zhì)點(diǎn).假設(shè)q=(x,y)、qo=(xo,yo)分別代表它們的位置.傳統(tǒng)人工勢(shì)場(chǎng)法中的斥力勢(shì)場(chǎng)函數(shù)定義為

(4)

其中krep為斥力增益系數(shù)，ρ(q)為智能體到障礙的空間距離，ρ0為障礙對(duì)智能體的影響半徑.對(duì)上式求負(fù)梯度可得如下斥力函數(shù)：

Frep(q)=-?Urep(q)=

(5)

當(dāng)智能體采用傳統(tǒng)斥力勢(shì)場(chǎng)函數(shù)進(jìn)行避障時(shí)，一旦智能體進(jìn)入邊界的影響半徑，就會(huì)受到其斥力勢(shì)場(chǎng)影響.然而，并不是所有情況都需要?jiǎng)輬?chǎng)的影響.如圖5所示，智能體的位置雖然處于邊界勢(shì)場(chǎng)的影響范圍之內(nèi)，但其運(yùn)動(dòng)速度并未指向邊界，不存在與邊界發(fā)生碰撞的風(fēng)險(xiǎn)，因而并不需要采取避障措施.因此，在設(shè)計(jì)邊界勢(shì)場(chǎng)時(shí)，我們有必要將智能體的位置與速度同時(shí)納入考慮.

圖5 一個(gè)非必要的勢(shì)場(chǎng)影響

(6)

進(jìn)一步，我們定義智能體i在二維空間中qi點(diǎn)的改進(jìn)斥力勢(shì)場(chǎng)函數(shù)如下：

(7)

其中λ為斥力勢(shì)場(chǎng)判定系數(shù)，krep為斥力增益系數(shù)，ρ(qi)=|qi-qoi|為智能體到可變投影點(diǎn)的距離，ρ0為斥力的作用距離.此時(shí)，智能體i在qi點(diǎn)受邊界的斥力為斥力勢(shì)場(chǎng)函數(shù)的負(fù)梯度

Frep(qi)=-?Urep(qi)=

(8)

在上述改進(jìn)的斥力勢(shì)場(chǎng)函數(shù)的引導(dǎo)下，智能體可望成功避免與邊界發(fā)生碰撞.

3 仿 真

為了驗(yàn)證本算法的適應(yīng)性和有效性，我們?cè)O(shè)計(jì)了不規(guī)則障礙和帶邊界障礙兩種典型場(chǎng)景，然后在相同的群體模型[15]下對(duì)本文方法與基于人工勢(shì)場(chǎng)的避障方法進(jìn)行了對(duì)比性仿真.

3.1 不規(guī)則障礙場(chǎng)景下的群體避障

在不規(guī)則障礙的情況下，算法繞行路徑往往存在冗余，本算法可以較好地解決這一問(wèn)題.如圖6所示，在避障過(guò)程中，智能體以實(shí)時(shí)探測(cè)得到的邊界平衡點(diǎn)為中心建立局部極限環(huán)，按照該局部極限環(huán)進(jìn)行動(dòng)態(tài)避障，得到了近似所有局部極限環(huán)包絡(luò)的一條繞行路徑.較傳統(tǒng)極限環(huán)的繞行路徑而言，該繞行路徑消除了路徑冗余.

圖6 不規(guī)則障礙場(chǎng)景下的局部極限環(huán)群體避障

在不規(guī)則障礙場(chǎng)景下，基于局部極限環(huán)法與人工勢(shì)場(chǎng)法的100個(gè)智能體的避障仿真結(jié)果對(duì)比如圖7，8所示，圖中箭頭代表智能體的速度矢量，下同.

在圖7(a)和圖8(a)中，當(dāng)t=26.4s時(shí)，局部極限環(huán)算法的避障進(jìn)程快于人工勢(shì)場(chǎng)法，速度匹配程度地更高，說(shuō)明本算法在避障初期的表現(xiàn)較人工勢(shì)場(chǎng)法為優(yōu).

在圖7(b)和圖8(b)中，在不規(guī)則障礙場(chǎng)景下，人工勢(shì)場(chǎng)法中少部分智能體會(huì)陷入虛擬勢(shì)場(chǎng)的局部極小點(diǎn)，進(jìn)而隨著大部分智能體朝目標(biāo)點(diǎn)運(yùn)動(dòng)，這部分智能體受智能體間吸引力的影響最終會(huì)脫離局部極小點(diǎn)，但仍造成了如圖8(b)所示的“拖尾”和“落后”現(xiàn)象.而本算法較好地解決上述問(wèn)題，在不規(guī)則障礙場(chǎng)景下具有更好的適應(yīng)性.

為進(jìn)一步對(duì)比本文算法與人工勢(shì)場(chǎng)法的適應(yīng)性和有效性，在不規(guī)則障礙場(chǎng)景下，我們對(duì)不同的群體規(guī)模分別進(jìn)行200次仿真，然后對(duì)其統(tǒng)計(jì)結(jié)果進(jìn)行了對(duì)比參見(jiàn)圖9.

從圖9(a)可見(jiàn)，該場(chǎng)景下兩種方法均能有效的避免碰撞.在圖9(b)中，基準(zhǔn)線表示算法規(guī)定的總仿真時(shí)長(zhǎng)，基準(zhǔn)線以下的點(diǎn)表示群體在總仿真時(shí)長(zhǎng)內(nèi)完成了整個(gè)避障過(guò)程，基準(zhǔn)線上的點(diǎn)則表示群體在總仿真時(shí)長(zhǎng)內(nèi)未完成避障過(guò)程，避障過(guò)程自動(dòng)終止.仿真結(jié)果表明，本算法在不同群體規(guī)模下均能夠完成避障，且避障時(shí)間受群體規(guī)模的影響較小.相對(duì)而言，人工勢(shì)場(chǎng)法僅在群體規(guī)模較小(本文仿真中群體規(guī)模小于50)時(shí)能完成整個(gè)避障過(guò)程，但避障時(shí)間受群體規(guī)模影響較大.可見(jiàn)本文算法的適應(yīng)性和有效性均優(yōu)于人工勢(shì)場(chǎng)法.

將改進(jìn)的人工勢(shì)場(chǎng)斥力與局部極限環(huán)結(jié)合，我們可以解決帶邊界障礙場(chǎng)景下的群體避障問(wèn)題.為驗(yàn)證其適應(yīng)性與有效性，我們?cè)O(shè)計(jì)了由邊界和不規(guī)則障礙組成的帶邊界障礙場(chǎng)景，然后進(jìn)行仿真，并與人工勢(shì)場(chǎng)法進(jìn)行對(duì)比.兩種算法(取100個(gè)智能體)的仿真結(jié)果如圖10所示.

由圖10可以看出，人工勢(shì)場(chǎng)法在邊界的約束下有不少智能體陷入局部極小點(diǎn)，路徑抖動(dòng)現(xiàn)象劇烈.另一方面，基于改進(jìn)斥力函數(shù)的局部極限環(huán)法避免了路徑抖動(dòng)現(xiàn)象，能產(chǎn)生較為平滑的軌跡.可見(jiàn)本算法在帶邊界障礙場(chǎng)景下的適應(yīng)性和有效性較好.

進(jìn)一步，在帶邊界場(chǎng)景下，我們進(jìn)行同3.1小節(jié)類(lèi)似的統(tǒng)計(jì)仿真，結(jié)果如圖11所示，圖中的基準(zhǔn)線含義參見(jiàn)3.1小節(jié).由圖11(a)可見(jiàn)，隨著群體規(guī)模的擴(kuò)大，兩種算法都可以有效地避免碰撞，但隨著碰撞個(gè)數(shù)的上升，本算法適應(yīng)性較好.可見(jiàn)在帶邊界障礙場(chǎng)景中，本算法能夠完成不同群體規(guī)模下的避障任務(wù)，避障時(shí)間隨著群體規(guī)模的增加而小幅上升，而人工勢(shì)場(chǎng)法僅能完成小規(guī)模群體(群體規(guī)模小于30)的避障任務(wù)，且避障時(shí)間隨著群體規(guī)模的增加而大幅上升.

面向障礙形態(tài)多樣及帶邊界的非預(yù)知環(huán)境，我們提出了一種局部極限環(huán)群體避障算法.該算法在傳統(tǒng)極限環(huán)法的基礎(chǔ)上加入了改進(jìn)的邊界斥力函數(shù).仿真結(jié)果顯示，相比人工勢(shì)場(chǎng)法，本算法可有效克服局部極小點(diǎn)與路徑抖動(dòng)問(wèn)題，使避障路徑更合理，運(yùn)動(dòng)軌跡更平滑.此外，本算法可有效避免碰撞且避障時(shí)間短，具有較好的有效性與適應(yīng)性.