一個復雜有界環(huán)境下的改進極限環(huán)避障算法

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

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

1 引 言

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

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

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

2 避障算法

2.1 極限環(huán)

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

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

(1)

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

(2)

其中

xff=[x2,-x1]T，

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

xfb=ρ[x1,x2]T.

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

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

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

Fig.2 Obstacle-avoiding path of an agent

圖3 智能體的感知范圍

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

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

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

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

(ii) 根據(jù)第i個智能體和設定目標點的位置信息，寫出過兩點的直線方程Li:ax+by+c=0,其中a≥0.

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

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

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

(3)

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

借助人工勢場的思想，我們在邊界處引入一個虛擬斥力場，使智能體在力場中受力運動，從而避免與邊界碰撞.

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

(4)

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

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

(5)

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

圖5 一個非必要的勢場影響

(6)

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

(7)

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

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

(8)

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

3 仿 真

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

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

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

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

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

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

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

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

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

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

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

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

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