基于定向極限環(huán)的Cucker-Smale群體避障模型

張 浩， 陳 熙， 王 震， 蔚 濤， 鐘蘇川

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

1 引 言

生物體普遍存在群體避障行為，如森林中穿梭的鳥群，湖泊里游動的魚群，地上尋找食物的蟻群等生物群體僅依靠簡單的規(guī)則和局部通訊便能順利避開運動過程中的障礙到達(dá)目標(biāo)，且整個過程中呈現(xiàn)出整體協(xié)調(diào)有序的行為表現(xiàn).

在工程領(lǐng)域，考慮到無人機(jī)、機(jī)器人等自主智能體在多障礙物環(huán)境很容易發(fā)生碰撞，也有必要研究群體實時避障問題.為此，國內(nèi)外學(xué)者做了大量研究，提出了多種方法，如模型預(yù)測控制法[1]、人工勢場法[2]、極限環(huán)法[3-6]等.其中，針對多無人機(jī)協(xié)同規(guī)避控制的問題，文獻(xiàn)[1]構(gòu)建多目標(biāo)優(yōu)化控制模型，通過納什最優(yōu)的分布式預(yù)測控制方法實現(xiàn)了多無人機(jī)防撞.針對無人機(jī)集群內(nèi)部防碰撞以及遭遇突發(fā)障礙時的集群防碰撞問題，文獻(xiàn)[2]引入力學(xué)概念及集群內(nèi)部吸引力、排斥力以及編隊構(gòu)型力等概念，通過集群個體間的信息共享以及類腦知識發(fā)育構(gòu)建了基于群信息共享和類腦反射的無人機(jī)防碰撞模型.文獻(xiàn)[4]基于生物群集理論，提出了基于極限環(huán)理論的智能體避障控制算法，實現(xiàn)了靜態(tài)障礙環(huán)境下的多智能體編隊避障.文獻(xiàn)[5]將勢場法和極限環(huán)相結(jié)合，實現(xiàn)了機(jī)器人在人和靜態(tài)障礙物混合場景中避障.文獻(xiàn)[6]根據(jù)極限環(huán)設(shè)計了并行橢圓極限環(huán)(PELC)和多準(zhǔn)則優(yōu)化(PELC *)算法，實現(xiàn)車輛有效、快速、安全避開任何形狀障礙物.

然而，上述文獻(xiàn)大多僅研究單個或少量個體的實時避障，而密集群體內(nèi)部的個體碰撞很容易產(chǎn)生鏈?zhǔn)叫?yīng)，因而采用上述方法很難取得較好的大規(guī)模群體避障效果.此外，文獻(xiàn)[7-8]通過將障礙物定義為特殊智能體來避免碰撞，但未考慮復(fù)雜場景.文獻(xiàn)[9-10]則考慮設(shè)置虛擬領(lǐng)導(dǎo)點減少群體避障過程中的碰撞，但是虛擬領(lǐng)導(dǎo)點的路徑需要提前規(guī)劃，不適合未知復(fù)雜環(huán)境下的實時避障.針對上述多障礙物環(huán)境下的大規(guī)模群體避障問題，本文在傳統(tǒng)極限環(huán)避障和現(xiàn)有群體模型[12]基礎(chǔ)上改進(jìn)了多障礙物合并方法，引入了定向的運動規(guī)則，提出了一種基于改進(jìn)Cucker-Smale模型的定向極限環(huán)群體避障算法.

2 極限環(huán)避障算法

極限環(huán)避障方法是一種局部路徑規(guī)劃方法[3]，其實質(zhì)是個體能夠與障礙物保持一定距離，按照順時針或者逆時針的方向繞過障礙物邊沿，以避免與其發(fā)生碰撞.其非線性動力系統(tǒng)的方程如下：

(1)

其極限環(huán)如圖1所示，其中平衡點為x1=x2=0，當(dāng)01時,軌跡向內(nèi)旋轉(zhuǎn).

圖1 系統(tǒng)(1)的極限環(huán)Fig.1 Limit cycle diagram of system(1)

為了減少個體不必要地繞行，通常引入感知-規(guī)避方法中的碰撞錐思想[12-14]來設(shè)計極限環(huán)避障判斷規(guī)則.碰撞錐思想廣泛應(yīng)用于實時碰撞檢測和威脅評估，其原理是僅基于個體和障礙物相對位置矢量和相對速度矢量的簡單幾何關(guān)系實現(xiàn)個體與障礙物碰撞檢測與評估.考慮到個體感知能力有限，本文在傳統(tǒng)碰撞錐上加入個體探測范圍(藍(lán)色圓)，如圖2所示.

圖2 個體的障礙物探測示意圖

(2)

基本的極限環(huán)避障步驟如下.

(ii) 計算避障判定系數(shù)，如果為1則繼續(xù)后面步驟，否則障礙物om對個體ui作用力設(shè)為0，即

(3)

(iii) 根據(jù)以下二階非線性方程來計算個體ui在任意位置的作用力：

(4)

則避障加速度為

aoi=koHmPui

(5)

3 群體避障模型

對于有多個障礙物存在的場景，一般的處理方式是簡單合并鄰近障礙物[4]，其前提是環(huán)境是已知的.本文考慮在未知環(huán)境下模型根據(jù)所設(shè)計的群體避障模型的障礙物合并方法和定向避障規(guī)則，不斷探測障礙物環(huán)境逐步獲得環(huán)境信息，進(jìn)而采取合適的策略，最終快速通過多障礙物區(qū)域，朝向目標(biāo)點運動.

3.1 避障模型

為了群體能順利通過障礙區(qū)域，模型采用文獻(xiàn)[12]的群體模型，并在此基礎(chǔ)上引入避障繞行項如下：

(6)

h(pui,Ω,info)=HPui=

(7)

3.2 障礙合并方法

當(dāng)探測到多個障礙物時，模型將處理分為兩個階段.

第一階段，群體對探測范圍內(nèi)的障礙物進(jìn)行兩兩通道測量，并將獲得的通道近似值傳遞給鄰域其它個體.如圖3所示，兩個體ui和uj都探測到兩個障礙物o1、o2，并分別獲得其探測通道dci，dcj.推廣到一般情況，對于可探測到障礙物o1、o2的個體u1,…,ui,…,un，其探測通道分別為dc1,…,dci,…,dcn，則該通道的近似值取

dcmin=min{dc1,…,dci,…,dcn}.

圖3 個體的通道示意圖

第二階段，根據(jù)通道近似值判定當(dāng)前兩個障礙物o1、o2是否需要合并.

(i) 當(dāng)d(o1,o2)=dcmin

(ii) 當(dāng)d(o1,o2)=dcmin>C，即通道近似值小于通道最小安全距離時，模型認(rèn)為群體不能從當(dāng)前障礙物間通過，此時合并障礙物并取離個體最近的障礙物的極限環(huán)作用力為該個體避障作用力.如圖3所示，離個體ui最近的障礙物是o1，則該個體所受避障作用力為aoi=koH1Pui.

一般情況下，對于兩個及以上數(shù)量的障礙物，可兩兩合并形成障礙物群Μ，其充分條件如下：

(I) ?oi,oj∈Ω，有d(oi,oj)

(II) ?oi,oj∈Ω，有d(oi,oj)≥C時，若在om,…,on∈Ω,使得d(oi,om)

3.3 定向避障規(guī)則

在障礙物繞行過程中，真實障礙物的形狀大小以及威脅程度往往未知，個體基于當(dāng)前位置和障礙物極限環(huán)確定的繞行方向不一定合適，從而可能會在繞行過程中出現(xiàn)回頭的現(xiàn)象，因而需要對個體繞行方向進(jìn)行定向，以確保在連續(xù)障礙場景的時候不會出現(xiàn)群體紊亂.具體規(guī)則是：當(dāng)個體探測到新的障礙物時，所受作用力大小由當(dāng)前最近障礙物極限環(huán)避障作用決定，作用力方向需要根據(jù)當(dāng)前障礙物與上一個時刻障礙物關(guān)系進(jìn)行規(guī)定.

圖4 個體繞行場景1

圖5 個體繞行場景2

4 仿 真

在MATLAB仿真環(huán)境中進(jìn)行實驗，計算機(jī)配置為AMD銳龍R5 4600六核處理器，16 G內(nèi)存，3 GHz主頻，Window10操作系統(tǒng).

實驗一，鄰近多障礙靜態(tài)場景避障.

為驗證鄰近多障礙靜態(tài)場景群體避障效果，設(shè)置該場景有四個靜態(tài)障礙物o1,o2,o3,o4，其中o1和o2，o1和o3，o2和o4通道分別為dc1,dc2,dc3，且dc1C.群體避障過程圖和軌跡圖如圖6，7所示，圖中箭頭為個體速度矢量，虛線圓半徑表示個體的群體內(nèi)部期望保持間距(即群體內(nèi)部排斥力作用范圍)，實心圓表示障礙物，軌跡圖中不同顏色表示不同時刻(如橙黃色表示初始時刻，紅色表示最終時刻)，下同.

由群體避障過程圖6和軌跡圖7可以看出，個體在探測到障礙物群o1o2和單個障礙物o1、o2時，依據(jù)當(dāng)前狀態(tài)選擇合適的繞行方向，并在離開障礙物區(qū)域后重新聚集在一起，朝向目標(biāo)點運動.

作為對照，傳統(tǒng)極限環(huán)避障模型在該場景中的仿真見圖8.

(a)

(b)

(d)

圖7 實驗1中的群體避障軌跡

(a)

(b)

在圖8(a)中，群體在從障礙物o1，o2間的狹窄通道通過時與障礙物發(fā)生碰撞，可見傳統(tǒng)算法不能很好處理鄰近障礙物場景.圖8(b)中，群體通過探測障礙物o1，o2間的通道確定其不能從該通道通過后便根據(jù)定向規(guī)則，沿著障礙物邊沿繞行.可見，相比較于傳統(tǒng)算法，新算法在保證實時的前提下，能有效處理鄰近多障礙物場景，避免碰撞發(fā)生.

實驗二,復(fù)雜障礙物群場景避障.

為驗證新算法對于連續(xù)墻及對稱矩形等復(fù)雜障礙物群的避障效果，我們設(shè)置實驗二場景為由阻擋群體前進(jìn)的五個障礙物o1o2o3o4o5組成的障礙物群，孤立障礙物o6、o7、o8和對稱矩形障礙物o9、o10、o11、o12.群體避障部分過程圖和軌跡圖如圖9、10所示.

圖10 實驗二群體避障軌跡

如圖9(a)所示，不同于簡單合并障礙物的模型，本模型建立在對未知環(huán)境不斷探測的基礎(chǔ)上，根據(jù)定向思想使群體一直沿著障礙物邊沿運動，最終繞出障礙物群o1o2o3o4o5o6o7，避免個體回頭與其鄰近個體發(fā)生碰撞.如圖9(b)所示，群體可以順利通過對稱障礙物，無需考慮局部極小值問題[15]，減少了算法設(shè)計難度.在整個過程中群體都能順利通過復(fù)雜障礙物場景，表明算法效果較好.

為驗證在不同群體規(guī)模和隨機(jī)初始狀態(tài)下本算法的適應(yīng)性和有效性，我們以實驗1中的場景進(jìn)行仿真，取同一群體規(guī)模下200次仿真結(jié)果平均值為群體避障仿真結(jié)果.傳統(tǒng)算法(第2節(jié)中的極限環(huán)避障法)與本算法對比如圖11所示.

由圖11(a)知，當(dāng)群體規(guī)模擴(kuò)大時，本算法的平均碰撞個數(shù)有所增加.在個體數(shù)為200時碰撞個數(shù)為6.97，最高碰撞概率為3.48%，遠(yuǎn)低于傳統(tǒng)算法的最高碰撞概率25.55%.由圖11(b)可知，群體規(guī)模較小時本算法避障時間遠(yuǎn)小于傳統(tǒng)算法.隨著群體規(guī)模擴(kuò)大，本算法的避障時間與傳統(tǒng)算法趨于相等.綜上，隨著群體規(guī)模擴(kuò)大，采用本算法群體能安全快速通過該實驗場景.相比于基本極限環(huán)避障法，本文算法在保證一定避障效率的條件下，群體避障的安全性有了較大提升.

5 結(jié) 語

本文研究大規(guī)模群體在多障礙物環(huán)境的避障問題.首先，為解決多障礙物場景群體避障問題，我們改進(jìn)了障礙物合并方法，設(shè)計了定向規(guī)則，進(jìn)而提出定向群體避障模型.仿真結(jié)果表明，采用本算法，群體能順利安全通過多障礙區(qū)域，且算法對于不同群體規(guī)模和初始條件適應(yīng)性較好.