一個復雜有界環境下的改進極限環避障算法

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

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

1 引 言

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

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

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

2 避障算法

2.1 極限環

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

考慮如下二階非線性系統方程：

(1)

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

(2)

其中

xff=[x2,-x1]T，

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

xfb=ρ[x1,x2]T.

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

2.2 局部極限環避障

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

Fig.2 Obstacle-avoiding path of an agent

圖3 智能體的感知范圍

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

圖4 智能體的局部極限環避障

局部極限環避障算法的具體實施步驟如下.

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

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

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

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

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

(3)

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

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

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

(4)

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

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

(5)

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

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

(6)

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

(7)

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

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

(8)

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

3 仿 真

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

3.1 不規則障礙場景下的群體避障

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

圖6 不規則障礙場景下的局部極限環群體避障

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

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

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

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

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

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

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

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

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