经典蜂拥模型稳定性分析

超、凢脫俗 2023-07-05 10:25 1阅读 0赞

# 运动模型 #

考虑一个包含 N N N个智能体的群体，其中每个节点的运动方程均形同，如下：  
 \{ q ˙ i ( t ) = p i ( t ) p ˙ i ( t ) = u i ( t ) \\left\\\{ \\begin\{matrix\} \{ \{ \{\\dot\{q\}\}\}\_\{i\}\}(t)=\{ \{p\}\_\{i\}\}(t) \\\\ \{ \{ \{\\dot\{p\}\}\}\_\{i\}\}(t)=\{ \{u\}\_\{i\}\}(t) \\\\ \\end\{matrix\} \\right. \{ q˙i(t)=pi(t)p˙i(t)=ui(t)  
其中 i = 1 , 2 , ⋯   , N i=1,2,\\cdots ,N i=1,2,⋯,N， p i ( t ) p\_i(t) pi(t)和 q i ( t ) q\_i(t) qi(t)分别代表节点 i i i在时间时 t t t的速度和位置, u i u\_i ui代表该节点的控制输入向量。

# 输入向量 #

移动节点的输入控制量为：  
 u i = ∑ j ∈ N i ϕ ( ∥ q j − q i ∥ σ ) n i j + ∑ j ∈ N i ( p j − p i ) a i j + β 1 ( q k − q i ) + β 2 ( p k − p i ) (1) \{ \{u\}\_\{i\}\}=\\sum\\limits\_\{j\\in \{ \{N\}\_\{i\}\}\}\{\\phi (\{ \{\\left\\| \{ \{q\}\_\{j\}\}-\{ \{q\}\_\{i\}\} \\right\\|\}\_\{\\sigma \}\})\{ \{n\}\_\{ij\}\}\}+\\sum\\limits\_\{j\\in \{ \{N\}\_\{i\}\}\}\{(\{ \{p\}\_\{j\}\}-\{ \{p\}\_\{i\}\})\{ \{a\}\_\{ij\}\}\}+\{ \{\\beta \}\_\{1\}\}(\{ \{q\}\_\{k\}\}-\{ \{q\}\_\{i\}\})+\{ \{\\beta \}\_\{2\}\}(\{ \{p\}\_\{k\}\}-\{ \{p\}\_\{i\}\}) \\text \{(1)\} ui=j∈Ni∑ϕ(∥qj−qi∥σ)nij\+j∈Ni∑(pj−pi)aij\+β1(qk−qi)\+β2(pk−pi)(1)  
其中 ∥ ⋅ ∥ σ \{ \{\\left\\| \\cdot \\right\\|\}\_\{\\sigma \}\} ∥⋅∥σ是一种新的范数，其定义如下：  
 ∥ z ∥ σ = \[ 1 + ε ∥ z ∥ 2 − 1 \] / ε \{ \{\\left\\| z \\right\\|\}\_\{\\sigma \}\}=\\left\[ \\sqrt\{1+\\varepsilon \{ \{\\left\\| z \\right\\|\}^\{2\}\}\}-1 \\right\]/\\varepsilon ∥z∥σ=\[1\+ε∥z∥2−1\]/ε  
其倒数 σ ε ( z ) = ∇ ∥ z ∥ σ \{ \{\\sigma \}\_\{\\varepsilon \}\}(z)=\\nabla \{ \{\\left\\| z \\right\\|\}\_\{\\sigma \}\} σε(z)=∇∥z∥σ可以表示为：  
 σ ε ( z ) = z 1 + ε ∥ z ∥ 2 = z 1 + ε ∥ z ∥ σ \{ \{\\sigma \}\_\{\\varepsilon \}\}(z)=\\frac\{z\}\{\\sqrt\{1+\\varepsilon \{ \{\\left\\| z \\right\\|\}^\{2\}\}\}\}=\\frac\{z\}\{1+\\varepsilon \{ \{\\left\\| z \\right\\|\}\_\{\\sigma \}\}\} σε(z)=1\+ε∥z∥2z=1\+ε∥z∥σz  
 a i j \{ \{a\}\_\{ij\}\} aij是空间邻接矩阵 A ( q ) A(q) A(q)中的元素 a i j \{ \{a\}\_\{ij\}\} aij，其可以表示为：  
 a i j ( q ) = ρ h ( ∥ q j − q i ∥ / r α ) ∈ \[ 0 , 1 \] ,   j ≠ i \{ \{a\}\_\{ij\}\}(q)=\{ \{\\rho \}\_\{h\}\}(\\left\\| \{ \{q\}\_\{j\}\}-\{ \{q\}\_\{i\}\} \\right\\|/\{ \{r\}\_\{\\alpha \}\})\\in \\left\[ 0,1 \\right\],\\text\{ \}j\\ne i aij(q)=ρh(∥qj−qi∥/rα)∈\[0,1\], j=i  
其中 r α = ∥ r ∥ σ \{ \{r\}\_\{\\alpha \}\}=\{ \{\\left\\| r \\right\\|\}\_\{\\sigma \}\} rα=∥r∥σ。 ϕ α ( z ) \{ \{\\phi \}\_\{\\alpha \}\}(z) ϕα(z)是势场函数（a smooth pairwise attractive/repulsive potential），其定义为：  
 ϕ α ( z ) = ρ h ( z / r α ) ϕ ( z − d α ) ϕ ( z ) = 1 2 \[ ( a + b ) σ 1 ( z + c ) + ( a − b ) \] \\begin\{aligned\} & \{ \{\\phi \}\_\{\\alpha \}\}(z)=\{ \{\\rho \}\_\{h\}\}(z/\{ \{r\}\_\{\\alpha \}\})\\phi (z-\{ \{d\}\_\{\\alpha \}\}) \\\\ & \\phi (z)=\\frac\{1\}\{2\}\\left\[ (a+b)\{ \{\\sigma \}\_\{1\}\}(z+c)+(a-b) \\right\] \\\\ \\end\{aligned\} ϕα(z)=ρh(z/rα)ϕ(z−dα)ϕ(z)=21\[(a\+b)σ1(z\+c)\+(a−b)\]  
其中 σ 1 ( z ) = z / 1 + z 2 \{ \{\\sigma \}\_\{1\}\}(z)=z/\\sqrt\{1+\{ \{z\}^\{2\}\}\} σ1(z)=z/1\+z2，\[\\phi (z)\]是一个不均匀的s形函数，参数 0 < a ≤ b 0<a\\le b 0<a≤b， c = a − b / 4 a b c=a-b/\\sqrt\{4ab\} c=a−b/4ab，以确保 ϕ ( 0 ) = 0 \\phi (0)=0 ϕ(0)=0。 n i j \{ \{n\}\_\{ij\}\} nij表示从 q i \{ \{q\}\_\{i\}\} qi指向 q j \{ \{q\}\_\{j\}\} qj的方向向量，其计算方式为：  
 n i j = ( q j − q i ) / 1 + ε ∥ q j − q i ∥ 2 \{ \{n\}\_\{ij\}\}=(\{ \{q\}\_\{j\}\}-\{ \{q\}\_\{i\}\})/\\sqrt\{1+\\varepsilon \{ \{\\left\\| \{ \{q\}\_\{j\}\}-\{ \{q\}\_\{i\}\} \\right\\|\}^\{2\}\}\} nij=(qj−qi)/1\+ε∥qj−qi∥2

# 系统性能证明 #

定理1：考虑一个运行在指定区域内包含 N N N个移动节点的智能群体，移动节点的输入控制量如公式(1.1)所示。假设该区域内只有一个运动速度为 p k \{ \{p\}\_\{k\}\} pk的目标 k k k并且系统的初始结构能量满足 Q 0 < ( m + 1 ) ψ α ( 0 ) \{ \{Q\}\_\{0\}\}<(m+1)\{ \{\\psi \}\_\{\\alpha \}\}(0) Q0<(m\+1)ψα(0)，其中 m ∈ Z + m\\in \{ \{Z\}^\{+\}\} m∈Z\+。那么一下三条规则均可以成立：

1.  每个移动节点 i i i和目标 k k k之间的距离都不大于 2 Q o / β 1 \\sqrt\{2\{ \{Q\}\_\{o\}\}/\{ \{\\beta \}\_\{1\}\}\} 2Qo/β1；
2.  每个节点最终速度都接近目标速度 p k \{ \{p\}\_\{k\}\} pk；
3.  该群体中最多有 m m m对智能体可能发生碰撞。

# 证明： #

根据Olfati-Saber等人在文章"Flocking for multi-agent dynamic systems: Algorithms and theory"和Su 等人在文章"Flocking of multi-agents with a virtual leader"文中给出的动力学分析，群体控制的输入量可以改写为：  
 u = − ∇ Γ ( q ) − L ^ ( q ) p + f t ( q , p , q , p ) u=-\\nabla \\Gamma (q)-\\hat\{L\}(q)p+\{ \{f\}^\{t\}\}(q,p,q,p) u=−∇Γ(q)−L^(q)p\+ft(q,p,q,p)  
这里 Γ ( q ) \\Gamma (q) Γ(q)是一个平滑的势函数：  
 Γ ( q ) = 1 2 ∑ i ∑ j , j ≠ i ∇ ψ α ( ∥ q j − q i ∥ σ ) \\Gamma (q)=\\frac\{1\}\{2\}\\sum\\limits\_\{i\}\{\\sum\\limits\_\{j,j\\ne i\}\{\\nabla \{ \{\\psi \}\_\{\\alpha \}\}(\{ \{\\left\\| \{ \{q\}\_\{j\}\}-\{ \{q\}\_\{i\}\} \\right\\|\}\_\{\\sigma \}\})\}\} Γ(q)=21i∑j,j=i∑∇ψα(∥qj−qi∥σ)  
其中 ψ α ( z ) = ∫ d α z ϕ α ( s ) d s \{ \{\\psi \}\_\{\\alpha \}\}(z)=\\int\_\{ \{ \{d\}\_\{\\alpha \}\}\}^\{z\}\{ \{ \{\\phi \}\_\{\\alpha \}\}(s)ds\} ψα(z)=∫dαzϕα(s)ds。 L ^ ( q ) \\hat\{L\}(q) L^(q)是无向图 G G G的正半定拉普拉斯算子，其定义为：  
 L ^ ( q ) = L ( q ) ⊗ I N = ( Δ ( A ( G ) ) − A ( G ) ) ⊗ I N \\hat\{L\}(q)=L(q)\\otimes \{ \{I\}\_\{N\}\}=\\left( \\Delta \\left( A(G) \\right)-A(G) \\right)\\otimes \{ \{I\}\_\{N\}\} L^(q)=L(q)⊗IN=(Δ(A(G))−A(G))⊗IN  
其中 f t ( q , p , q , p ) \{ \{f\}^\{t\}\}(q,p,q,p) ft(q,p,q,p)是群体中所有节点和目标 k k k之间的群体导航反馈量。使用哈密顿函数定义节点和目标 k k k之间的势能函数和动能之和：  
 Q ( q , p ) = ∑ i = 1 N \[ U i ( q ) + K i ( q ) \] Q(q,p)=\\sum\\limits\_\{i=1\}^\{N\}\{\\left\[ \{ \{U\}\_\{i\}\}(q)+\{ \{K\}\_\{i\}\}(q) \\right\]\} Q(q,p)=i=1∑N\[Ui(q)\+Ki(q)\]  
其中  
 U i ( q ) = 1 2 ∑ j = 1 , j ≠ i N ψ α ( ∥ q j − q i ∥ σ ) + 1 2 β 1 ( q k − q i ) T ( q k − q i ) K i ( q ) = 1 2 ( p k − p i ) T ( p k − p i ) \\begin\{aligned\} & \{ \{U\}\_\{i\}\}(q)=\\frac\{1\}\{2\}\\sum\\limits\_\{j=1,j\\ne i\}^\{N\}\{ \{ \{\\psi \}\_\{\\alpha \}\}(\{ \{\\left\\| \{ \{q\}\_\{j\}\}-\{ \{q\}\_\{i\}\} \\right\\|\}\_\{\\sigma \}\})\}+\\frac\{1\}\{2\}\{ \{\\beta \}\_\{1\}\}\{ \{(\{ \{q\}\_\{k\}\}-\{ \{q\}\_\{i\}\})\}^\{T\}\}(\{ \{q\}\_\{k\}\}-\{ \{q\}\_\{i\}\}) \\\\ & \{ \{K\}\_\{i\}\}(q)=\\frac\{1\}\{2\}\{ \{(\{ \{p\}\_\{k\}\}-\{ \{p\}\_\{i\}\})\}^\{T\}\}(\{ \{p\}\_\{k\}\}-\{ \{p\}\_\{i\}\}) \\\\ \\end\{aligned\} Ui(q)=21j=1,j=i∑Nψα(∥qj−qi∥σ)\+21β1(qk−qi)T(qk−qi)Ki(q)=21(pk−pi)T(pk−pi)  
沿着节点到目标 k k k方向上 Q ( q , p ) Q(q,p) Q(q,p)的导数为：  
 Q ˙ ( q , p ) = − p T \[ ( L ^ ( q ) + β 2 I 2 ) ⊗ I N \] p \\dot\{Q\}(q,p)=-\{ \{p\}^\{T\}\}\\left\[ \\left( \\hat\{L\}(q)+\{ \{\\beta \}\_\{2\}\}\{ \{I\}\_\{2\}\} \\right)\\otimes \{ \{I\}\_\{N\}\} \\right\]p Q˙(q,p)=−pT\[(L^(q)\+β2I2)⊗IN\]p  
因为其中 L ^ ( q ) \\hat\{L\}(q) L^(q)是一个半正定矩阵，因此有：  
 Q ˙ ( q , p ) < 0 , ∀ ≥ 0 \\dot\{Q\}(q,p)<0,\\forall \\ge 0 Q˙(q,p)<0,∀≥0  
由此可知 Q ( q , p ) Q(q,p) Q(q,p)函数是一个递减函数，，即 Q ( q , p ) ≤ Q 0 , ∀ t ≥ 0 Q(q,p)\\le \{ \{Q\}\_\{0\}\},\\forall t\\ge 0 Q(q,p)≤Q0,∀t≥0。  
对于追踪目标 k k k的任意一节点，根据公式(1.10)以及 β 1 > 0 \{ \{\\beta \}\_\{1\}\}>0 β1>0可得：  
 1 2 β 1 ( q k − q i ) T ( q k − q i ) ≤ Q 0 \\frac\{1\}\{2\}\{ \{\\beta \}\_\{1\}\}\{ \{(\{ \{q\}\_\{k\}\}-\{ \{q\}\_\{i\}\})\}^\{T\}\}(\{ \{q\}\_\{k\}\}-\{ \{q\}\_\{i\}\})\\le \{ \{Q\}\_\{0\}\} 21β1(qk−qi)T(qk−qi)≤Q0  
因此每个节点与目标之间的距离都不大于 2 Q 0 / β 1 \\sqrt\{2\{ \{Q\}\_\{0\}\}/\{ \{\\beta \}\_\{1\}\}\} 2Q0/β1,即证明了第一条规则。

根据拉塞尔不变性原理，即当 Q ˙ ( q , p ) = 0 \\dot\{Q\}(q,p)=0 Q˙(q,p)=0时，系统中的每个运算解都渐进收敛于最大的速度不变量。对于群体中任意追踪目标 k k k的节点，基于公式(1.11)后一个公式以及 Q ˙ ( q , p ) = 0 \\dot\{Q\}(q,p)=0 Q˙(q,p)=0，则有 p i − p k ≡ 0 \{ \{p\}\_\{i\}\}-\{ \{p\}\_\{k\}\}\\equiv 0 pi−pk≡0。因此可以得到：  
 p 1 ≡ p 2 ≡ ⋯ p N ≡ p k \{ \{p\}\_\{1\}\}\\equiv \{ \{p\}\_\{2\}\}\\equiv \\cdots \{ \{p\}\_\{N\}\}\\equiv \{ \{p\}\_\{k\}\} p1≡p2≡⋯pN≡pk  
则第二条规则得证。  
假设 Q 0 < ( m + 1 ) ψ α ( 0 ) \{ \{Q\}\_\{0\}\}<(m+1)\{ \{\\psi \}\_\{\\alpha \}\}(0) Q0<(m\+1)ψα(0)，并且有超过 m m m个不同的移动节点在时间 t ′ ≥ 0 \{t\}'\\ge 0 t′≥0时发生碰撞。由于在时间 t ′ \{t\}' t′时，至少有 m + 1 m+1 m\+1个移动节点对发生碰撞，这表示群体的总势能至少是 ( m + 1 ) ψ α ( 0 ) (m+1)\{ \{\\psi \}\_\{\\alpha \}\}(0) (m\+1)ψα(0)。  
根据公式(1.13)且函数 Q ( q , p ) Q(q,p) Q(q,p)不是递减函数，则有：  
 Q 0 = Q ( q ( 0 ) , p ( 0 ) ) ≥ Q ( q ( t ′ ) , p ( t ′ ) ) ≥ ( m + 1 ) ψ α ( 0 ) \{ \{Q\}\_\{0\}\}=Q\\left( q(0),p(0) \\right)\\ge Q\\left( q(\{t\}'),p(\{t\}') \\right)\\ge (m+1)\{ \{\\psi \}\_\{\\alpha \}\}(0) Q0=Q(q(0),p(0))≥Q(q(t′),p(t′))≥(m\+1)ψα(0)  
显然这与 Q 0 < ( m + 1 ) ψ α ( 0 ) \{ \{Q\}\_\{0\}\}<(m+1)\{ \{\\psi \}\_\{\\alpha \}\}(0) Q0<(m\+1)ψα(0)的假设矛盾。因此，在 t > 0 t>0 t>0时，该网络中最多有 m m m个不同的移动节点可能会发生碰撞。尤其是当 m = 0 m=0 m=0时，任意两个节点之间都不会发生碰撞。第三条准则得证。