面向復雜障礙場的多智能體系統集群避障模型

張超省， 王健， 張林， 王婭

(1.陸軍工程大學 訓練基地， 江蘇 徐州 221004； 2.空軍勤務學院 基礎部， 江蘇 徐州 221200)

0 引言

隨著導航技術、通信技術、控制技術和人工智能技術的發展，未來會有越來越多的無人機、無人車、無人艇等無人裝備走向戰場，擔負偵察、警戒、核生化檢測、彈藥補給、人員搶救、裝備搶修等任務，甚至是成為主戰裝備中的一員。由多個無人裝備組成的多智能體系統，可以替代戰士執行作戰任務，最大限度地減少人員傷亡[1]。對于投入戰場的多智能體系統而言，既要能夠充分發揮集群的規模效應，避免過多個體游離群體之外，還要能夠在盡量保持集群的前提下快速地穿越復雜障礙場。尤其是在地面戰場上，多智能體系統不僅僅要面臨阻絕墻、鐵絲網、三角錐、塹壕等傳統的障礙體，還需要繞過路徑上的掩體工事、武器裝備等形成的阻擋。因此集群避障技術是提高多智能體群體地面戰場適應能力的關鍵。

對集群行為的研究起源于Reynolds等[2]對鳥群行為的計算模擬，提出群中個體應遵循的3條基本規則，即避免碰撞、速度匹配和保持聚集。在Reynolds等的基礎上，Toner等[3]、Couzin等[4]和Vicsek等[5]先后開展了一系列卓有成效的研究工作，形成了3個經典的群集動力學模型，但這些工作均是在自由空間內對集群行為的模擬。

在智能體避障規則方面，有以下具有代表性的研究成果。2004年，Tanner等[6]基于車輛周圍的球面鄰域中獲得的局部信息，提出了一系列非光滑控制律，使車輛能夠在靜態障礙物中集群達到目的地。2010年，Wang等[7]從逆最優控制的角度出發，構造了一個非二次罰函數來實現集群的避障能力，并證明了一致算法的漸近穩定性和最優性。2010年，Yan等[8]針對多智能體系統中的目標跟蹤和避障問題，提出了一種基于人工勢函數和行為規則的控制算法，解決了動態環境下集群避障時無法有效跟蹤目標的問題。2012年，Bai等[9]提出了一種將流量函數與人工勢場相結合的新框架，定義了一種具有可見性約束和層次關聯的動態結構以提高系統的性能。2015年，Burohman等[10]采用輸入輸出線性化方法控制集群避障，提出了一種非完整移動機器人的群集算法，實現了狹窄通道的無碰撞通行。

在障礙體幾何模型方面，有以下具有代表性的研究成果。2006年，Olfati-Saber[11]通過引入兩種虛擬智能體(β-智能體和γ-智能體)來表示障礙體和目標對智能體集群的作用，實現了多個障礙條件下的集群避障問題，成為集群避障領域的經典模型；然而，該模型只用直線和外接圓模擬障礙體，不能模擬復雜的障礙體形狀。2011年，Ghorbanian等[12]把環境中的障礙物用橢圓形狀逼近和封閉，設計了分布式控制規則來實現多智能體群體避障運動。2012年，Hu等[13]采用圓錐形結構模擬運動場中的三維障礙物，并引導智能體沿著錐面上最短的路徑通過障礙物。2017年，Qiu等[14]采用臨時目標法，實現了多智能體在規則直角障礙體中的集群避障。

為便于研究，將地面戰場近似為二維平面，那么地面戰場上無人裝備集群躲避多個障礙體的問題便可以抽象為二維空間內多智能體系統集群穿越復雜障礙場的問題。假設一組智能體集群從某地出發到目的地執行任務，必經之路上存在一個由若干障礙體組成的復雜障礙場，如圖1所示，障礙區域中黑色多邊形表示障礙體原本的形狀，灰色圓形表示障礙體的最小外接圓。由圖1可以看出：障礙體之間原本存在比較大的間隙，能夠作為智能體集群的通道。然而，傳統人工勢場法多采用障礙體的最小外接圓(球)作為多邊形障礙體的邊界，那么原本存在的通道將變窄甚至消失。為了解決上述問題，本文設計了一套面向復雜障礙場的智能體集群避障模型及求解方法。

圖1 面向復雜障礙場的多智能體系統集群Fig.1 Flocking of multi-agent system in complex obstacle field

1 集群避障運動的建模

為了更清楚地闡述集群避障運動的建模過程，引入σ-范數、隆起函數、集群避障運動控制方程等概念。

為了確保向量z的范數‖z‖處處可微分，定義向量z的σ-范數為

(1)

式中：ε∈(0,1]。

為了構建平滑勢函數，采用如(2)式所示的隆起函數：

(2)

式中：h為控制隆起位置的參數，h∈(0,1)。

基于Olfati-Saber的算法3[11]，改進多邊形障礙體環境下的集群避障控制方程，采用(3)式計算第i個智能體的運動：

(3)

1.1 其他智能體對智能體Ai的作用

將多智能體系統視作一個由M個智能體組成的集合V，為便于表示，第i個智能體Ai的外接圓記為B(CAi,RAi)，其中，CAi、RAi分別表示智能體Ai的外接圓圓心(外心)和外接圓半徑(外徑)。

多智能體系統進行集群運動，智能體Ai的運動狀態為

(4)

式中：qi、pi、ui分別為智能體Ai的位置、速度和加速度，qi,pi,ui∈RD，D表示維度。為簡化分析，可以用智能體Ai外心位置CAi作為智能體Ai的位置。

由于智能體必然為實體，存在一定的體積。定義智能體Ai邊界與智能體Aj邊界的距離為

d(Ai,Aj)=‖CAi-CAj‖-RAi-RAj，

(5)

式中：‖·‖表示多維空間的歐幾里得范數。

當智能體之間距離過大時，智能體之間相互影響忽略不計，定義智能體Ai鄰居的集合為

(6)

圖2給出了某個時刻智能體Ai周圍智能體的分布，淺色陰影圓形(虛線)表示智能體Ai的交互距離，深色陰影圓形(實線)表示智能體Ai的外接圓。根據(6)式，可以看出：智能體A1、A2、A5都是智能體Ai的鄰居，而智能體A3、A4都不是智能體Ai的鄰居。

圖2 智能體Ai的鄰域空間Fig.2 Neighborhood space of agent Ai

基于沖擊函數(2)式，定義智能體之間的空間鄰接矩陣A(q)=[aij(q)]，其中元素為

(7)

定義智能體之間的功能函數為

(8)

智能體Ai的鄰居對其作用的方程為

(9)

(10)

1.2 障礙體對智能體Ai的作用

圖3 障礙體Ok對智能體Ai的作用Fig.3 Interaction between agent Ai and obstacle Ok

步驟1智能體Ai外接圓邊界與多邊形障礙體Ok外接圓邊界之間的距離，通過(11)式求解：

(11)

步驟2多邊形障礙體Ok相對于智能體Ai是否激活，定義智能體Ai附近所有激活障礙體的集合為

(12)

(13)

(14)

P1PC·PCP2≥0，

(15)

步驟5假設激活邊為P1P2，進一步求解智能體Ai外心CAi與障礙體Ok的激活邊P1P2的垂線，垂足為K，連線CAiK通過(16)式求出：

(16)

式中：CAiP1為智能體Ai外心到障礙體頂點P1之間的連線(矢量)；Δ為連線CAiP1與連線P1P2之間的夾角θ的余弦值，可由(17)式求出：

(17)

步驟6多邊形障礙體Ok相對于智能體Ai是否排斥，通過(18)式判定：

(18)

步驟7當智能體Ai處于障礙體Ok的排斥距離內，引入一種虛擬智能體來模擬障礙體對智能體的作用，并將這種虛擬智能體記為β-智能體。β-智能體的位置即為智能體Ai在障礙體Ok邊界上的直角投影(正投影)，β-智能體的位置和速度由(19)式可得：

ik=K，ik=Ppi，

(19)

(20)

步驟8基于沖擊函數(2)式，定義智能體Ai與障礙體Ok之間的空間鄰接矩陣B(q)=[bik(q)]，其中元素為

(21)

步驟9智能體Ai與障礙體Ok之間的作用函數為

(22)

步驟10智能體Ai臨近障礙體對智能體Ai的作用方程為

(23)

(24)

1.3 目標對智能體的作用

智能體的目標可以是靜態的，也可以是動態的，因此目標Gγ可定義為

Gγ=(qγ，pγ)，

(25)

式中：qγ、pγ分別表示目標的位置和速度，當pγ=0時，目標靜止不動。

基于人工勢能函數，目標對于智能體Ai的引領作用可由(26)式直接給出：

(26)

2 集群避障運動的求解

通過采用多邊形表示障礙體，能夠解決傳統人工勢場方法采用最小外接圓(球)表示障礙體造成的通道變窄和堵塞問題。然而，多邊形的直邊可能會引起捕獲現象[11]，如何逃離直邊捕獲是智能體集群避障模型必須要解決的另一個重要問題。

2.1 直邊捕獲問題

圖4 障礙體Ok直線邊P1P2對智能體Ai的捕獲現象Fig.4 Capturing phenomenon of edge P1P2 of obstacle Ok to agent Ai

1)求解智能體Ai外心CAi與目標Gγ的連線CAiGγ與障礙體Ok排斥邊P1P2的交點，參考(13)式，如果該交點同時位于線段CAiGγ和障礙體Ok排斥邊P1P2上，則該排斥邊為捕獲邊；

2)求解智能體Ai外心CAi與障礙體Ok排斥邊端點的距離，以排斥邊為P1P2為例，通過(27)式判定：

(27)

如果(27)式成立，則該排斥邊為捕獲邊。

如果排斥邊為捕獲邊，則將目標設置為臨時目標。臨時目標根據智能體Ai、捕獲邊端點P1P2、目標Gγ三者的位置確定，由智能體位置向排斥邊作垂線，當垂足K位于排斥邊之內時，臨時目標點通過(28)式求解：

(28)

式中：Ln為連線P1P2的法向量；Pn=P1P2/‖P1P2‖；Π=(‖CAiP1‖+‖P1Gγ‖)-(‖CAiP2‖+‖P2Gγ‖)。

當垂足K位于排斥邊之外時，臨時目標點通過(29)式求解：

(29)

如果只考慮障礙物靜止的情況，此時：

(30)

2.2 離散化求解方法

(4)式為位置、速度和加速度的數學關系，以連續導數的形式給出。仿真過程中，往往需要離散形式。因此，需要修改(4)式的形式，具體作法為：

1)通過(3)式可以獲得智能體Ai某時刻的加速度ui，實際上智能體加速能力不可能無限大，設智能體驅動加速度最大值為umax，則應作出以下判定：

‖ui‖>umax.

(31)

當(31)式成立時，說明計算獲得的加速度大于智能體最大加速度，則令

ui=umaxui/‖ui‖，

(32)

否則，不作改變。

2)通過(33)式計算智能體Ai某時刻的速度：

pi=p′i+u′iδt，

(33)

式中：δt為離散時間步長；p′i、u′i分別為智能體Ai在前一個時刻的速度和加速度。

同樣，智能體速度不可能無限大，設智能體速度最大值為pmax，則首先作出如(34)式判定：

‖pi‖>pmax.

(34)

當(34)式成立時，說明計算獲得的速度大于智能體最大速度，則令

pi=pmaxpi/‖pi‖,

(35)

否則，不作處理。

3)通過(36)式計算智能體Ai某時刻位置：

(36)

式中：q′i為智能體Ai在前一個時刻的位置。

2.3 關鍵參數選取規則

關鍵參數選取規則為：

(37)

(38)

3)智能體之間、障礙體與智能體之間、目標點與智能體之間的速度影響因子與距離影響因子大致滿足：

(39)

在該規則指導下，本文所提出的集群避障模型能夠完成集群避障要求，但由于離散化求解方法和多智能體系統固有的不確定性，構形必然會暫時遭到破壞，因此上述規則僅能保證盡可能大的構形保持率。

(40)

(41)

3 仿真驗證

以某時刻智能體Ai為對象，上述集群避障運動建模和求解過程可以通過圖5所示的流程圖進行。首先，根據智能體和障礙體的幾何屬性完成參數初始化，頂層虛線框所示；其次，分別計算其他智能體、障礙體和目標點對智能體Ai的作用，中間層從左至右虛線框所示；最后，綜合所有作用力，離散化計算智能體的加速度、速度和位移，底層虛線框所示。

圖5 集群避障建模及求解流程圖Fig.5 Flow chart of flocking model and its solution

下面給出20個智能體穿越障礙場、抵達目標的仿真結果。初始時刻，該組智能體外接圓半徑均為1.0 m，以[25 m,0 m]為起始位置、以4×5的陣型和2 m的間隔、沿x軸正向并關于x軸對稱分布，所有智能體的初始速度均為[0 m/s，0 m/s]。

復雜障礙場由2個三角形、2個四邊形和1個五邊形障礙體組成，其頂點坐標位置可以表示為

F={[130 m,30 m;150 m,50 m；160 m,0 m]，
[80 m，-60 m;110 m，-50 m;90 m，-30 m]，
[130 m，-50 m;120 m，10 m;150 m，0 m;160 m，-25 m]，
[90 m，-20 m;92 m，-21 m;94 m，21 m;89 m，20 m]，
[90 m，40 m;110 m，20 m;130 m，40 m;
120 m，55 m;100 m，55 m]}，

其中，每一行表示一個障礙體的頂點坐標(x，y)，各頂點以分號隔開，各障礙體均靜止不動。模型中的參數如表1所示。

表1 模型參數

圖6 靜態目標下多智能體系統集群避障Fig.6 Obstacle avoidance of multi-agent system when moving in the direction of static target

第1個任務是集群穿越障礙場，達到靜態目標周邊。目標狀態由Gγ=(qγ,pγ)確定，其中qγ=[220 m， 0 m]，pγ=[0 m/s， 0 m/s]。第1個任務對應的集群運動過程如圖6所示，其中黑色多邊形表示障礙體，紅色圓形表示智能體，紅色五角星表示目標。為了更好地展示智能體集群在遇到障礙物時的分離與集合行為，坐標范圍經過人為設定。由圖6可以看出：初始時，智能體相對密集地集中于出發點，如圖6(a)所示；隨后，智能體之間保持期望距離并抵達條形障礙體附近，如圖6(b)所示；當智能體進入條形障礙體的排斥距離時，由于(28)式和(29)式的作用，智能體分別選擇了兩個不同的臨時目標，開始分裂為兩組集群，如圖6(c)所示；下面一組智能體集群繼續分裂成兩組智能體集群通過四邊形障礙體，如圖6(d)所示；當多數智能體通過后側三角形和四邊形障礙體之間時，由于通道較窄，出現非常明顯的擠壓行為，智能體只能魚貫而出，如圖6(e)所示。通過圖6還可以看到：在避障時，有少數智能體沒有與大多數智能體組成的集群連結，然而，當通過障礙體后，智能體都以相同速度朝目標方向運動迅速形成集群，如圖6(f)、圖6(g)和圖6(h)所示。

第2個任務是集群穿越障礙場，智能體集群分成兩組實現兩個動態目標追蹤或攻擊。兩個目標的狀態為

其中：A表示幅值，A=20 m；ω為角速度，ω=0.01π rad/s.

圖7 動態目標下智能體集群避障Fig.7 Obstacle avoidance of multi-agent system when moving in the direction of dynamic target

在其他參數保持不變的條件下，第2個任務對應的集群運動過程，如圖7所示，其中紅色圓形和紅色星標分別表示第1組智能體及其對應目標，藍色圓形和藍色星標分別表示第2組智能體及對應目標。由圖7可以看出：剛開始時，所有智能體以一個集群以特定構形到達障礙場附近，如圖7(a)所示；隨后，由于障礙體的排斥作用，集群開始分離，構形遭到破壞，如圖7(b)所示；由于目標牽引作用，當大部分智能體越過障礙場后又開始逐步形成新的集群，并分別朝著各自對應的目標集群運動，如圖7(c)和圖7(d)所示；當兩個目標交匯時，兩組智能體集合在一起，如圖7(e)所示；當兩個目標重新分離時，兩組智能體朝向各自的目標離散，如圖7(f)所示；當兩個目標再次靠近又分離時，兩組智能體再次集合之后又朝著各自的目標離散。此處存在個別(紅色)智能體被脅迫到另一組(藍色)智能體集群中，如圖7(d)、圖7(f)和圖7(h)所示。不難得出結論：在兩個動態目標存在下，模型依然能夠對發揮較好的支配作用。但是，兩組智能體離散時存在的脅迫現象還需要設計其他規則加以消除，比如不同目標對應智能體之間只存在排斥力不存在吸引力。更多細節，將在后續研究中進一步闡述。

4 結論

本文首先針對地面戰場上存在的復雜障礙場，分析了傳統人工勢場法中最小外接圓(球)描述障礙體的不足，引入了多邊形的概念來描述復雜障礙體，以降低障礙場通道變窄和堵死的概率；其次，著重研究了多智能體系統集群避障過程中智能體與障礙體之間的相互作用，基于智能體外心與障礙體外心的距離確定障礙體是否處于激活狀態，基于智能體外心與障礙體內心的連線確定激活障礙體的激活邊，給出了作用力的表達式；再次，分析了直線型邊界的捕獲現象及其產生原因，提出采用臨時目標的方式繞過捕獲邊從而克服了捕獲現象，介紹了離散化求解方法和模型中關鍵參數選取的規則；最后，給出了仿真分析結果，驗證了不論目標處于靜態或動態，本文避障模型都可以實現復雜障礙場下的集群避障控制。

實際上，多邊形(多面體)直邊(面)捕獲問題就是一種局部極小值點問題。由于直邊捕獲問題屬于多邊形障礙體建模的衍生問題，本文給出了逃離方法；其他類型的局部極小值問題，各種處理方法很多，比如分層控制、調參、改進勢場函數等等，本文不再贅述。

同樣，通過仿真結果，可以了解到智能體集群的分離、結合和擠壓行為。障礙物的出現可能使智能體集群分離為更多的集群，從而失去相互聯系改變原有的網絡拓撲。因此，在解決智能體集群避障時，必須解決在切換拓撲網絡中有限通信的集群決策問題，這是目前相當有挑戰性的課題。