基于定向極限環的Cucker-Smale群體避障模型

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

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

1 引 言

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

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

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

2 極限環避障算法

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

(1)

其極限環如圖1所示，其中平衡點為x1=x2=0，當01時,軌跡向內旋轉.

圖1 系統(1)的極限環Fig.1 Limit cycle diagram of system(1)

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

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

(2)

基本的極限環避障步驟如下.

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

(3)

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

(4)

則避障加速度為

aoi=koHmPui

(5)

3 群體避障模型

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

3.1 避障模型

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

(6)

h(pui,Ω,info)=HPui=

(7)

3.2 障礙合并方法

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

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

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

圖3 個體的通道示意圖

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

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

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

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

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

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

3.3 定向避障規則

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

圖4 個體繞行場景1

圖5 個體繞行場景2

4 仿 真

在MATLAB仿真環境中進行實驗，計算機配置為AMD銳龍R5 4600六核處理器，16 G內存，3 GHz主頻，Window10操作系統.

實驗一，鄰近多障礙靜態場景避障.

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

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

作為對照，傳統極限環避障模型在該場景中的仿真見圖8.

(a)

(b)

(d)

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

(a)

(b)

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

實驗二,復雜障礙物群場景避障.

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

圖10 實驗二群體避障軌跡

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

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

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

5 結 語

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