Swarm Flocking 经典蜂拥模型大全

淡淡的烟草味﹌ 2023-06-23 07:59 2阅读 0赞

### 文章目录 ###

*  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∑kaij(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 模型定义 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2Nzc1Mjkz_size_16_color_FFFFFF_t_70]  
  个体在原点中心处，并将其周围空间划分为三个区域： 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)⋅rijri−rj0if rij<r0repotherwise  
其中 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时的的排斥速度项。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2Nzc1Mjkz_size_16_color_FFFFFF_t_70 1]  
因此，个体 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/p2if 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)⋅vijvi−vj0if vij>vijfrictmaxotherwise

在上面的等式中， 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)⋅visvi−vs0if vis>visshallmaxotherwise(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∣vivflock\+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\}

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2Nzc1Mjkz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191218110051925.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2Nzc1Mjkz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2Nzc1Mjkz_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191218155210502.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2Nzc1Mjkz,size_16,color_FFFFFF,t_70