带通信中断的离散多智能体系统的免碰撞控制

刘 泽,刘易成

(国防科技大学理学院,湖南长沙 410073)

1 引言

近年来,多智能体系统的涌现行为和自组织行为,如鸟类的编队飞行、鱼类的洄游、细菌的聚集行为等,受到了许多学者的广泛关注.受到生物集群行为的启发,许多学者提出了各种各样的集群模型,这些模型在智能体控制、计算机科学、人工智能等领域发挥了重要的作用,见文献[1-2]中的例子.

如何通过简单的通信交互使多智能体系统实现集群是一个重要的问题,针对该问题已经取得了许多研究成果.Vicsek等人在文献[3]中首次提出了多智能体系统实现集群的3个原则,即吸引性、排斥性、速度匹配,并通过计算机仿真验证了集群现象.Cucker 和Smale在文献[4-5]中提出了Cucker-Smale模型,利用个体的位置和速度关系来研究集群行为.Motsch和Tadmor在文献[6]中考虑了多智能体间通信距离有限的情况,首次提出了具有局部通信交互的Motsch-Tadmor模型,并研究其集群行为.Jin在文献[7]中研究了一类具有通信中断的Motsch-Tadmor模型的集群行为.

在集群模型不断完善的过程中,许多学者开始关注多智能体系统的免碰撞问题.目前实现免碰撞的控制方法主要分为两种: 一种方法是通过添加奇异的排斥力f(s)实现免碰撞,其中f(s)可微并满足∫d+1d f(s)ds=∞和∫∞d+1f(s)ds＜∞,d＞0.Cucker和Dong在文献[8-9]中通过引入一类奇异的外力项,实现了Cucker-Smale模型的免碰撞,并提出了一种普适的免碰撞理论;另一种方法是利用奇异通信权重ψ(s)=1(s-δ)α实现免碰撞,其中:δ≥0,α＞0.Peszek在文献[10]中证明了当α ∈(0,1)时,Cucker-Smale模型将会产生粘滞和碰撞倾向.Carillo在文献[11]中证明了当α≥1时,一类Cucker-Smale模型可以实现有条件的集群和免碰撞.此外,还有许多学者利用奇异权重提出了不同的控制协议,在不同情形下实现了多智能体系统的免碰撞控制.Ahn在文献[12]中证明了当Cucker-Smale模型中存在结合力时,系统可以实现免碰撞和集群.Zhou等人在文献[13]证明了当Cucker-Smale模型中含有时变时滞时,系统可以实现免碰撞和集群.Ru等人在文献[14-15]证明了在离散状态下Cucker-Smale模型可以实现免碰撞和集群.Park等人和Kim在文献[16]中证明了的具有可变权重的Cucker-Smale模型可以实现免碰撞和分簇.

上述文献研究了许多情形下多智能体系统的集群和免碰撞问题,但在离散情形下,带有通信中断的多智能体系统的集群和免碰撞问题仍未解决.目前分析多智能体系统动力学行为的主要方法是Laplace矩阵特征值法和Lyapunov函数法,但在通信中断情况下,该方法将失效.同时,由于通信中断也会使得通信拓扑发生变化,这对动力学行为的分析造成困难.因此,本文针对上述问题,重点研究如何在离散的情形下平衡通信中断与通信拓扑稳定之间的关系,进而实现集群和免碰撞.

本文剩余章节的内容安排如下: 第2章介绍了所需的图论知识,相关假设和定义;第3章证明了系统在满足一定的初始条件且连通状态不随时间变化的情况下,可以实现免碰撞和集群.第4章通过数值仿真验证了定理的正确性;第5章对本文的工作进行了总结与展望.

2 基础知识

首先介绍本文研究的多智能体系统.

受文献[11]的启发,为了实现系统的免碰撞,文章引入如下的奇异通信权重:

其中:λ,α＞0代表调节参数,|*|代表欧氏距离.

受文献[7]的启发,文章引入如下的判别函数来刻画个体间的通信中断:

其中0＜L＜∞代表个体间的通信半径.

结合式(1)-(2),文章提出在离散形式下多智能体系统的控制协议,即

其中:xi(t)=xi(th)∈Rd,vi(t)=vi(th)∈Rd(i=1,···,N,d=2,3,···,M)代表在th时刻的i个体的位置与速度状态,h＞0代表迭代步长;Iij(t)=I(rij(t)),ϕij(t)=ϕ(rij(t)),其中rij(t)=|xi(t)-xj(t)|.Iij(t)=1代表个体i,j在th时刻的距离小于通信半径L,这意味着i,j直接通信.反之,Iij(t)=0意味着i,j间通信中断.根据式(3)中第2个等式可知,ϕij(t)代表个体i,j在th时的通信权重,当个体i,j距离小于L时,此时个体i,j的距离越小意味着两者间排斥作用越强.

注1符号i ↔j表示i,j的距离小于通信半径L,即两者直接通信.

接下来,本文将介绍一些相关的图论知识.考虑由N个智能体组成的系统,如果在th 时刻对于任意个体i,j都存在一组,2 ≤n≤N,使得成 立,则 称系统在th时刻处于连通状态,其中通信链路长度为n-1.特别地,当任意两个个体i,j间最长的通信链路不超过2时,此时系统处于2-连通状态.当任意两个个体i,j间的通信链路长度均为1时,此时系统处于全连通状态.如果在th时刻对于任意个体i,j都存在一个固定的k,使得i ↔k ↔j成立,则称系统在th时刻处于星状连通状态.

接下来提出3个假设,将在第3章发挥重要作用.

假设1假设当t=0时,系统(3)是星状连通的或对于任意i↔j ↔k↔m通信链路,都满足i↔m,其中i,j,k,m互不相同.

注2满足假设1的系统处于连通状态,且为2-连通.

不难发现Γ≥0,若Γ=0,则系统(3)处于临界状态,即系统的连通状态将被破坏.为避免系统的连通状态被破坏,本文提出以下假设.

假设3假设系统的初始状态满足Γ＞0.

最后给出多智能体系统免碰撞和渐近集群的定义.

则称系统(3)实现全局免碰撞.

3 渐近集群与免碰撞的分析

在本章中,首先证明系统(3)全局免碰撞.由于通信半径有限,存在个体i,j不能直接通信,即Iij(t)=0,此时通信权重无正下界,无法直接对个体的状态进行分析,详见文献[12,15,17].考虑到个体数目有限,利用有限长的连通链路来替代中断的通信链路从而解决这个问题.为了方便说明,记dv(t)=|vj(t)-vi(t)|.

证本文将通过数学归纳的思想来证明该定理.

在上式推导中利用了

根据定理条件,可以得知Iij(s)≡Iij(0)和假设1成立,因此,系统(3)是连通的,且连通状态不随时间变化.

此外由于Iii(s)≡1,利用式(5)-(6),可以得到

由于在i,j直接通信的情况下有rij(s)＜L,利用式(6)-(7)及ϕ的非增性,可以得到:

由于假设1成立,则系统处于2-连通状态,因此,对于任意的个体i,j,可以得到

如果任意个体i,j直接通信,结合式(4)-(5)(8),可以得到

根据假设1,知道至少存在着i,j,使得当p等于i或j时,Ijp(s)=Iip(s)=1成立.此时式(10)中的第一个不等式不为0,即意味着个体p,q直接通信.

在式(10)中,令c(s)=hϕjj(s),回顾式(5)和(7),可以得到

结合式(9)-(10),当s ∈(0,t)时,对任意的个体i,j,可以得到

利用式(12),令s=t,并进行迭代,可以得到

对于任意的个体i,j,可以得到

在上式推导中利用了

根据系统(3)中第2个等式,当t≥0时,可以得到

接下来,文章将证明系统(3)在合适的初始状态下可以实现集群和免碰撞的定理.

2) 系统(3)实现渐近集群,收敛速度上界满足

个体间最大距离上界满足

证首先,将采用反证法证明系统连通状态不随时间变化,假设在t1＜∞时刻,存在个体i*,j*使得系统的连通状态发生改变,接下来将证明在定理条件下t1=∞.

在上式推导中利用了式(14).

利用式(13)(16),可以得到对任意的个体i,在t≥0时,有下式成立:

这意味着当t→∞时,同时,回顾式(17),可以得到对任意的个体i,j,在t≥0时,

即得到rij(t)＜∞,结合式(19)-(20),回顾定义2,系统3 实现渐近集群.据此,结论(2)成立.证毕.

2) 系统(3)实现渐近集群,收敛速度上界满足

个体间最大距离上界满足:

4 数值仿真

在本章将通过数值仿真来验证结论的正确性.根据假设1,本文考虑以下两种情况:

1) 星状连通;

2) 对所有的i↔j ↔k↔m,都有i↔m.

选取N=7,其位置和速度见附录表1,调节参数α=0.5,λ=30,迭代步长h=0.001 s,图1-3对应通信半径L=20 m,连通方式满足条件1),此时δ ≈12.91 m;图4-6对应通信半径L=60 m,连通方式满足条件2),此时δ≈11.39 m.

图1展示了7个智能体的速度收敛到初始速度的平均值.图2展示了7个智能体间的最大距离随时间增加而达到上界,即验证了系统(3)实现渐近集群.图3展示了7个智能体间的最小距离随时间增加而达到下界,且始终大于12.91 m,即全局不会发生碰撞.图4展示了7个智能体的速度收敛到初始速度的平均值.图5展示了7个智能体间的最大距离随时间增加而达到上界,即验证了系统(3)实现渐近集群.图6展示了7个智能体间的最小距离随时间增加而达到下界,且始终大于11.39 m,即全局不会发生碰撞.

图2 7个智能体间最大距离图Fig.2 Maximum distance among 7 agents diagram

图3 7个智能体间最小距离图Fig.3 Minimum distance among 7 agents diagram

图4 7个体智能体速度范数变化图Fig.4 Velocity diameter variation diagram of 7 agents

图5 7个智能体间最大距离图Fig.5 Maximum distance among 7 agents diagram

图6 7个智能体间最小距离图Fig.6 Minimum distance among 7 agents diagram

通过对比图1和图4,当通信半径L增大时,系统(3)将更快实现集群和免碰撞.但目前相关研究只得到了收敛速度上界的估计,因此仍需要进一步研究如何精确地刻画收敛速度.

5 结论

本文针对离散情形下具有通信中断的多智能体系统的集群和免碰撞问题进行研究.文章通过引入具有截断特性的奇异通信函数,提出了新的控制协议,利用连通的通信链路替代通信中断的链路,结合分析的方法,克服了Laplace矩阵特征值法和Lyapunov函数法失效的问题.同时在系统(3)的初始状态满足一定条件时,本文保证了系统的初始通信拓扑结构不变,进而证明了系统(3)实现集群和免碰撞.

受分析方法和通信拓扑结构的影响,文章未能获得精确的收敛速度,即无法分析系统参数对收敛速度的具体影响.目前如何得到多智能体系统的精确收敛速度是集群领域研究的难点问题,笔者接下来将尝试新的分析方法,在某些特殊的通信拓扑下研究系统(3)的收敛速度,从而得到更准确的集群和免碰撞的结论.

附录

表A1 7个智能体的初始状态Table1 The initial states of 7 agents

表A1列出7个智能体在X,Y,Z3个正交方向上的初始位置和速度.