Swarm Flocking 經典蜂擁模型大全

文章目錄

• 1. Reynold Boid 模型
• 2. Vicsek 模型
• • 2.1 參考文獻
  • 2.2 模型定義
• 3. Cucker-Smale 模型
• • 3.1 參考文獻
  • 3.2 模型定義
• 3. Couzin模型
• • 3.1 參考文獻
  • 3.2 模型定義
  • 3.3 控制規律
• 4. Gábor Vásárhelyi模型
• • 4.1 參考文獻
  • 4.2 模型定義
  • • 4.2.1 排斥速度 Repulsion
    • 4.2.2 速度對齊項 Velocity alignment term
    • 4.2.3 牆壁和障礙物的作用 Interaction with walls and obstacles
    • 4.2.4 自推進項 Self-propelling term
    • 4.2.5 最終速度

1. Reynold Boid 模型

  Boid 模型是 Reynold 在1986 年建立的一個用來模拟群體行為的空間模型，是首次針對蜂擁運動提出的著名模型。在該模型中定義了三個基本規則：

i）分離（Separation），即每個個體受到其鄰域内的其他個體的排斥力的矢量和，以避免和附近的智能體碰撞。

ii）聚合（Cohesion），即每個個體受到其鄰域内的其他個體的吸引力的矢量和，以保持整個團隊的緊湊。

iii）速度比對（Alignment），即讓每個個體與其鄰域内的其他個體的平均速度保持一緻，最終使整個團隊的速度趨于一緻。

  在此三條規則的基礎上，諸多學者對蜂擁運動展開了深入研究。

2. Vicsek 模型

2.1 參考文獻

Vicsek, Tamás, et al. “Novel type of phase transition in a system of self-driven particles.” Physical review letters 75.6 (1995): 1226.

2.2 模型定義

  在 Vicsek 模型對中，群體中的個體可以與其周圍半徑為 r r r内的其他個體互相作用，在仿真開始時，個體位置和速度随機分布，并且每個個體運動速度均為 v v v且一直保持不變，每一步的仿真時間為 Δ t \Delta_{t} Δt​，則個體的位置更新可以表示為：

x i ( t + 1 ) = x i ( t ) + v i ( t ) Δ t x_i(t+1)=x_i(t)+v_i(t)\Delta_{t} xi​(t+1)=xi​(t)+vi​(t)Δt​

角度的更新可以表示為：

θ i ( t + 1 ) = ⟨ θ ) ⟩ r + Δ θ \theta_i(t+1)=\left\langle {\theta)} \right\rangle_r +\Delta{\theta} θi​(t+1)=⟨θ)⟩r​+Δθ

其中 ⟨ θ ( t ) ⟩ r \left\langle {\theta(t)} \right\rangle_r ⟨θ(t)⟩r​表示在個體 i i i通信範圍 r r r内群體中個體的平均速度（包含個體 i i i）。平均方向角由 a r c t a n [ ⟨ s i n ( θ ( t ) ) ⟩ r / ⟨ c o s ( θ ( t ) ) ⟩ r ] arctan[\left\langle {sin(\theta(t))} \right\rangle_r/ \left\langle {cos(\theta(t))} \right\rangle_r] arctan[⟨sin(θ(t))⟩r​/⟨cos(θ(t))⟩r​]。其中 Δ θ \Delta{\theta} Δθ表示噪音，是以均勻機率随機從 [ − η / 2 , η / 2 ] [-\eta/2,\eta/2] [−η/2,η/2]中取得的。同時還有三個随機參數： η \eta η、 ρ \rho ρ和 v v v，其中 v v v是粒子在兩次相鄰步長之間個體運動的距離。

3. Cucker-Smale 模型

3.1 參考文獻

Cucker, Felipe, and Steve Smale. “Emergent behavior in flocks.” IEEE Transactions on automatic control 52.5 (2007): 852-862.

3.2 模型定義

  Cucker-Smale 模型與上面的 Vicsek 模型相似，但是該模型提供了詳細的收斂性證明。在該模型中位置更新函數如下：

x i ( t + 1 ) = x i ( t ) + v i ( t ) Δ t x_i(t+1)=x_i(t)+v_i(t)\Delta_{t} xi​(t+1)=xi​(t)+vi​(t)Δt​

使用速度更新函數代替 Vicsek 模型中的角度更新函數

v i ( t + 1 ) − v i ( t ) = ∑ j = 1 k a i j ( v j ( t ) − v i ( t ) ) {{v}_{i}}(t+1)-{{v}_{i}}(t)=\sum\limits_{j=1}^{k}{{{a}_{ij}}({{v}_{j}}(t)-{{v}_{i}}(t))} vi​(t+1)−vi​(t)=j=1∑k​aij​(vj​(t)−vi​(t))

其中 a i j a_{ij} aij​是與個體 i i i和個體 i i i位置相關的函數

a i j = η ∥ x i − x j ∥ 2 {{a}_{ij}}\text{=}\eta {{\left\| {{x}_{i}}-{{x}_{j}} \right\|}^{2}} aij​=η∥xi​−xj​∥2

η ( y ) \eta(y) η(y)是遞減函數

η ( y ) = K ( σ 2 + y ) β \eta (y)=\frac{K}{{{({{\sigma }^{2}}+y)}^{\beta }}} η(y)=(σ2+y)βK​

3. Couzin模型

3.1 參考文獻

Couzin, Iain D. , et al. “Collective Memory and Spatial Sorting in Animal Groups.” Journal of Theoretical Biology 218.1(2002):1-11.

3.2 模型定義

  個體在原點中心處，并将其周圍空間劃分為三個區域： z o r zor zor = 排斥區， z o o zoo zoo = 速度比對區， z o a zoa zoa = 吸引區。同時改模型還考慮個體的“盲區”，其位于個體背後，即個體隻能感覺 α \alpha α範圍内的資訊。

3.3 控制規律

  該模型控制分為三個階段分别對應于 z o r zor zor， z o o zoo zoo和 z o a zoa zoa 三個區域。其中優先級最高的為 z o r zor zor。

1）當個體 i i i視野内的 z o r zor zor區域内有個體時，（忽略背後360- α \alpha α範圍内的個體），其受到 z o r zor zor區域内個體的排斥，則下一時刻的速度可以表示為：

d r ( t + τ ) = − ∑ j ≠ i n r r i j ( t ) ∣ r i j ( t ) ∣ {{d}_{r}}(t+\tau )=-\sum\limits_{j\ne i}^{{{n}_{r}}}{\frac{{{r}_{ij}}(t)}{|{{r}_{ij}}(t)|}} dr​(t+τ)=−j​=i∑nr​​∣rij​(t)∣rij​(t)​

其中 r i j = c j − c i c j − c i ∣ r_{ij}=\frac{c_j-c_i}{c_j-c_i|} rij​=cj​−ci​∣cj​−ci​​， c i c_i ci​和 c j c_j cj​分别表示個體 i i i和 j j j的位置矢量， n r n_r nr​表示位于個體 i i i的 z o r zor zor區域内的其他個體的數量。

2）當個體 i i i視野内的 z o r zor zor區域内沒有其他個體時，即 n r = 0 n_r=0 nr​=0，這時個體對 z o o zoo zoo和 z o a zoa zoa 區域中的個體做出反應。

• 對于 z o o zoo zoo區域内個體：

d o ( t + τ ) = − ∑ j ≠ i n o v j ( t ) ∣ v j ( t ) ∣ {{d}_{o}}(t+\tau )=-\sum\limits_{j\ne i}^{{{n}_{o}}}{\frac{{{v}_{j}}(t)}{|{{v}_{j}}(t)|}} do​(t+τ)=−j​=i∑no​​∣vj​(t)∣vj​(t)​

• 對于 z o a zoa zoa區域内個體：

d a ( t + τ ) = − ∑ j ≠ i n a r i j ( t ) ∣ r i j ( t ) ∣ {{d}_{a}}(t+\tau )=-\sum\limits_{j\ne i}^{{{n}_{a}}}{\frac{{{r}_{ij}}(t)}{|{{r}_{ij}}(t)|}} da​(t+τ)=−j​=i∑na​​∣rij​(t)∣rij​(t)​

其中 n o n_o no​和 n a n_a na​分别為位于個體 i i i的 z o o zoo zoo和 z o a zoa zoa 區域中的個體的數量， v j v_j vj​表示個體 j j j的速度矢量。

  最終下一時刻個體 i i i的期望速度 d i ( t + τ ) d_i(t+\tau) di​(t+τ)定義為：

1）若 z o r zor zor區域内有其他個體，即 n r ≠ 0 n_r \ne 0 nr​​=0，則

d i ( t + τ ) = d r ( t + τ ) d_i(t+\tau)=d_r(t+\tau) di​(t+τ)=dr​(t+τ)

2）若 z o r zor zor區域内沒有其他個體，即 n r = 0 n_r=0 nr​=0，則：

• 若 z o o zoo zoo區域内有其他個體， z o a zoa zoa區域内沒有，即 n o ≠ 0 n_o \ne0 no​​=0且 n a = 0 n_a=0 na​=0，則

  d i ( t + τ ) = d o ( t + τ ) d_i(t+\tau)=d_o(t+\tau) di​(t+τ)=do​(t+τ)

• 若 z o a zoa zoa區域内有其他個體， z o o zoo zoo區域内沒有，即 n a ≠ 0 n_a \ne0 na​​=0且 n o = 0 n_o=0 no​=0，則

  d i ( t + τ ) = d a ( t + τ ) d_i(t+\tau)=d_a(t+\tau) di​(t+τ)=da​(t+τ)

• 若 z o o zoo zoo區域和内 z o a zoa zoa曲雲均有其他個體，即 n o ≠ 0 n_o \ne0 no​​=0且 n a ≠ 0 n_a \ne0 na​​=0，則

  d i ( t + τ ) = 1 2 [ d o ( t + τ ) + d a ( t + τ ) ] d_i(t+\tau)=\frac{1}{2}[d_o(t+\tau)+d_a(t+\tau)] di​(t+τ)=21​[do​(t+τ)+da​(t+τ)]

确定下一時刻的期望速度 d i ( t + τ ) d_i(t+\tau) di​(t+τ)後，個體 i i i在下一時刻從目前速度 v i ( t ) v_i(t) vi​(t)向速度 d i ( t + τ ) d_i(t+\tau) di​(t+τ)轉動角度 θ \theta θ，得到下一時刻速度 v i ( t + τ ) v_i(t+\tau) vi​(t+τ)，這裡的 θ \theta θ應該小于最大轉動角度 θ τ \theta_{\tau} θτ​。至此，該模型建立完畢。

4. Gábor Vásárhelyi模型

4.1 參考文獻

Vásárhelyi Gábor, et al. “Optimized flocking of autonomous drones in confined environments.” Science Robotics 3.20(2018):eaat3536-.

4.2 模型定義

一個可調的自推植絨模型

4.2.1 排斥速度 Repulsion

  當個體 i i i與其周圍的個體 j j j的距離小于距離門檻值 r 0 r e p r^{rep}_0 r0rep​時，個體 j j j對個體 i i i産生排斥速度項。個體 i i i周圍 r 0 r e p r^{rep}_0 r0rep​距離内沒有其他個體時，該項為0。則排斥速度項定義如下：

v i j r e p = { p r e p ⋅ ( r 0 r e p − r i j ) ⋅ r i − r j r i j i f   r i j < r 0 r e p 0 o t h e r w i s e v_{ij}^{rep}=\left\{ \begin{matrix} {{p}^{rep}}\cdot (r_{0}^{rep}-{{r}_{ij}})\cdot \frac{{{r}_{i}}-{{r}_{j}}}{{{r}_{ij}}} & if\text{ }{{r}_{ij}}<r_{0}^{rep} \\ 0 & otherwise \\ \end{matrix} \right. vijrep​={prep⋅(r0rep​−rij​)⋅rij​ri​−rj​​0​if rij​<r0rep​otherwise​

其中 v i j r e p v_{ij}^{rep} vijrep​為個體 i i i收到個體 j j j的影響産生的速度項， p r e p p^{rep} prep為排斥速度項的增益系數（線性增益）。

  如下圖所示，左邊藍色斜線為 v i j r e p v_{ij}^{rep} vijrep​在參數 r = 10 r=10 r=10、 p = 1 p=1 p=1、 v = 10 v=10 v=10時的的排斥速度項。

是以，個體 i i i最終排斥速度項定義如下：

v i r e p = ∑ j ≠ i v i j r e p v_{i}^{rep}=\sum\limits_{j\ne i}{v_{ij}^{rep}} virep​=j​=i∑​vijrep​

4.2.2 速度對齊項 Velocity alignment term

  以往的工作通常使用幂律函數，使個體與群體内其他個體的速度差在空間中漸近衰減為零。這些模型在較低速度範圍内的某些特定條件下可以正常工作。速度對齊項也必須充當阻尼媒體，以減少由于對例如斥力的延遲和噪聲導緻的自激振蕩現象。它必須是局部的，但同時還必須具有可擴充性，以适應較大的速度（因為可能存在較大的速度差異）。最後一個條件意味着如果限制了代理的加速度，則應在速度差較大時應該放寬制動距離，以避免碰撞。

  是以文中使用理想的制動曲線，即空間中平滑的速度衰減函數 D ( . ) D(.) D(.)：在高速時保持恒定加速度，在低速時保持指數速度，其定義如下：

D ( r , a , p ) = { 0 i f   r ≤ 0 r p i f   0 < r p < a / p 2 a r − a 2 / p 2 o t h e r w i s e D(r,a,p)=\left\{ \begin{matrix} 0 & if\text{ }r\le 0 \\ rp & if\text{ }0<rp<a/p \\ \sqrt{2ar-{{a}^{2}}/{{p}^{2}}} & otherwise \\ \end{matrix} \right. D(r,a,p)=⎩⎨⎧​0rp2ar−a2/p2

​​if r≤0if 0<rp<a/potherwise​

其中， r r r是代理與預期停止點之間的距離， a a a是首選加速度， p p p是線性增益， p p p還确定了減速的兩個階段之間的交叉點。

  速度對齊項的基本原理是禁止給定距離上的兩個代理在此距離之外的速度差大于此理想制動曲線所允許的值，是以在其他基于瞬時力的方程式中用作運動規劃項，該項定義如下：

v i j f r i c t max ⁡ = max ⁡ ( v f r i c t , D ( r i j − r 0 f r i c t , a f r i c t , p f r i c t ) ) v_{ij}^{frict\max }=\max ({{v}^{frict}},D({{r}_{ij}}-r_{0}^{frict},{{a}^{frict}},{{p}^{frict}})) vijfrictmax​=max(vfrict,D(rij​−r0frict​,africt,pfrict))

v i j f r i c t = { c f r i c t ( v i j − v i j f r i c t max ⁡ ) ⋅ v i − v j v i j if  v i j > v i j f r i c t max ⁡ 0 otherwise v_{ij}^{frict}=\left\{ \begin{matrix} {{c}^{frict}}({{v}_{ij}}-v_{ij}^{frict\max })\cdot \frac{{{v}_{i}}-{{v}_{j}}}{{{v}_{ij}}} & \text{if }{{v}_{ij}}>v_{ij}^{frict\max } \\ 0 & \text{otherwise} \\ \end{matrix} \right. vijfrict​={cfrict(vij​−vijfrictmax​)⋅vij​vi​−vj​​0​if vij​>vijfrictmax​otherwise​

  在上面的等式中， C f r i c t C^{frict} Cfrict是速度對準誤差減小的線性系數； v f r i c t v^{frict} vfrict是速度松弛，以允許一定量的速度差，而與代理之間的距離無關， r 0 f r i c t r^{frict}_0 r0frict​是代理 i i i與個體 j j j相關且還沒有到達個體 j j j所在位置的停止點的距離。 p f r i c t p^{frict} pfrict和 a f r i c t a^{frict} africt是線性增益和對齊的加速度參數，并且 v i j = ∣ v i − v j ∣ v_{ij} = | v_i − v_j | vij​=∣vi​−vj​∣是代理 i i i和 i i i之間的速度內插補點。 為代理 i i i計算的相對于其他代理的總速度對齊項（與排斥項類類似）似，其定義為：

v i f r i c t = ∑ j ≠ i v i j f r i c t v_{i}^{frict}=\sum\limits_{j\ne i}{v_{ij}^{frict}} vifrict​=j​=i∑​vijfrict​

4.2.3 牆壁和障礙物的作用 Interaction with walls and obstacles

  文章使用競技台對群體進行吸引和限制，并替代了傳統群體對群體的吸引力。群體中的個體朝着競技場飛行，進入競技場後個體受到競技場牆壁的排斥力，以確定個體在競技場内運動。

v i s s h i l l m a x = D ( r i s , r 0 s h i l l , a s h i l l , p s h i l l ) v^{shillmax}_{is}=D(r_{is},r^{shill}_0,a^{shill},p^{shill}) visshillmax​=D(ris​,r0shill​,ashill,pshill)

v i j w a l l = v i j f r i c t ( C − 1 ) = { ( v i s − v i s s h i l l max ⁡ ) ⋅ v i − v s v i s if  v i s > v i s s h a l l max ⁡ 0 otherwise (9) \begin{aligned} & v_{ij}^{wall}=v_{ij}^{frict}(C-1) \\ & =\left\{ \begin{matrix} ({{v}_{is}}-v_{is}^{shill\max })\cdot \frac{{{v}_{i}}-{{v}_{s}}}{{{v}_{is}}} & \text{if }{{v}_{is}}>v_{is}^{shall\max } \\ 0 & \text{otherwise} \\ \end{matrix} \right. \end{aligned} \tag{9} ​vijwall​=vijfrict​(C−1)={(vis​−visshillmax​)⋅vis​vi​−vs​​0​if vis​>visshallmax​otherwise​​(9)

  其中不允許壁的速度松弛，是以将誤差比例項（ C s h i l l C^{shill} Cshill）保持為1，以實作最強的牆壁對齊。在上面的等式中， s s s是指分别為所有牆多邊形邊緣定義的代理； r i s = ∣ r i − r s ∣ r_{is} = | r_i-r_s | ris​=∣ri​−rs​∣，其中 r s r_s rs​是牆壁代理的位置，位于任意形狀的凸壁多邊形的邊緣，且相對于代理 i i i的最近點； v i s = ∣ v i − v s ∣ v_{is} = | v_i − v_s | vis​=∣vi​−vs​∣，其中 v s v_s vs​是競技場代理的速度，垂直于競技場指向内部，幅度為 v s h i l l v^{shill} vshill。

  可以使用相同的概念來避免在競技場内出現凸形障礙物，但是與上文針對競技場所描述的不同，這裡代理需要遠離障礙物而不是向其内移動。另一個差別是，所有競技場的牆壁會在其内部生成一個分離的代理，但障礙物卻是在障礙物靠近個體 i i i的表面生成一個代理。是以，對于每個智能體 i i i和障礙物 s s s，我們都可以定義速度分量障礙，其類似于方程式 9，使用與競技場相同的參數。

4.2.4 自推進項 Self-propelling term

  該項保證個體 i i i可以一直保持在運動狀态，與實際速度方向 v i v_i vi​相同，其大小為固定值 v f l o c k v^{flock} vflock。

4.2.5 最終速度

  最終個體 i i i的期望速度綜合上述各項，其定義為：

v ~ i d = v i ∣ v i ∣ v f l o c k + v i r e p + v i f r i c t + ∑ s v i s w a l l + ∑ s v i s o b s t a c l e \tilde{v}_{i}^{d}=\frac{{{v}_{i}}}{\left| {{v}_{i}} \right|}{{v}^{flock}}+v_{i}^{rep}+v_{i}^{frict}+\sum\limits_{s}{v_{is}^{wall}}+\sum\limits_{s}{v_{is}^{obstacle}} v~id​=∣vi​∣vi​​vflock+virep​+vifrict​+s∑​viswall​+s∑​visobstacle​

除此之外，最終速度仍需滿足限制條件，即，引入速度限制 v m a x v^{max} vmax如果超出極限，則減小其大小：

v i d = v ~ i d ∣ v ~ i d ∣ ⋅ min ⁡ { ∣ v ~ i d ∣ , v max ⁡ } v_{i}^{d}=\frac{\tilde{v}_{i}^{d}}{\left| \tilde{v}_{i}^{d} \right|}\cdot \min \{\left| \tilde{v}_{i}^{d} \right|,{{v}^{\max }}\} vid​=∣∣​v~id​∣∣​v~id​​⋅min{∣∣​v~id​∣∣​,vmax}