基于局部交互的群集行为动态可控性
李成凤1，洪伟1, 2，刘宗春1，田彦涛1, 2
(1. 吉林大学 通信工程学院，吉林 长春，130025；
2. 吉林大学 工程仿生教育部重点仿生实验室，吉林 长春，130025)
摘 要：
集系统局部交互规则的情况下群体速度动态可控的问题。在具有时变期望速度的群体非自治系统中加入多个动态领导者，设计基于局部信息交互的分布式控制器。为简化证明将群体拓扑结构图划分两类子图，利用Barbalat引理进行稳定性分析，证明在局部信息交互下通过对领导者施加控制，能够使系统中的所有个体的速度矢量收敛到时变期望值，使群体形成稳定结构，同时证明引入领导者越多，群体速度收敛越快。仿真实验结果表明该控制策略有效。
关键词：
中图分类号：TP24 文献标志码：A 文章编号：1672-7207(2011)S1-0536-08
Active controllability of flocking behavior based on local interaction
LI Cheng-feng1, Hong Wei1, 2, LIU Zong-chun1, Tian Yan-tao1, 2
(1. School of Communication Engineering, Jilin University, Changchun 130025, China;
2. Key Laboratory of Bionics Engineering, Ministry of Education, Jilin University, Changchun 130025, China)
Abstract: Active speed controllability for the swarm flocking system was studied without breaking the local interaction rules. First, multiple active leaders were introduced to the swarm non-autonomous system with time-varying expected speed, then a decentralized controller was designed based on local information interaction. In order to simplify the proof, the topology graph of swarm was divided into two types of subgraph, and the Barbalat Lemma was adopted in analysis of the system stability, and it is proofed that speed vectors of all robots can converge to the desired value through controlling the leaders and the swarm will form a stable structure following the local information interaction rules. It is also confirmed that the more leaders are introduced, the faster the swarm converges. Simulation results show that the designed control strategy is effective.
Key words: flocking behavior; multiple active leaders; controllability; distributed control; analysis of stability
受自然界中的动物群体行为[1]的启发，群集系统已在过去的几年内成为热门研究领域[2-12]。群体机器人系统主要基于群集模型来产生群体一致性行为，因此，具有分布式、自组织和涌现性等特性。但由于整个系统缺少外部信息反馈，仅靠个体之间的信息交互，使群集模型的一致性存在着一个显著的问题：其控制结果往往具有很大的随机性，很难达到一个期望状 态[13]。针对上述问题，定义群集系统的“可控性”为：在不改变群集模型现有规则的情况下，能够确定相应的控制策略与算法使得群体达到期望的速度(包括恒速和变速度)。Olfati-Sabe[14]在假设虚拟领导者的作用范围是全局的，且虚拟领导者以恒速运动的情况下，提出了一种基于领航反馈的群集算法，使群体能够跟踪上虚拟领导者。Su等[15]在此基础上，研究了没有上述假设条件的具有虚拟领导者的多智能体群集，但实际上也只实现了局部交互下群体跟踪以恒速运动的虚拟领导者的情况，而没有给出以变速运动的虚拟领导者的作用范围，是局部的理论分析。Hong等[16]解决了局部交互下的群体跟踪变速运动的领导者问题，但仍局限于一阶群体模型。本文作者针对上述问题，在群体中加入多个不破坏群体局部规则的领导者，对具有时变期望速度的群体非自治系统，设计局部控制策略，并利用Barbalat引理证明所设计的分布式控制器有效。
1 群体机器人模型与分布式控制
1.1 群体机器人模型
考虑在二维空间中运动的群体机器人，群体由N (N≥1)个机器人组成，第i个个体的动力学模型为
(1)
其中：i=1, 2, …, N；xi
R2，viR2和ui分别是机器人i的位置、速度和控制输入。假设个体间通信无时滞，没有扰动力作用在个体上。定义x= 
，
分别代表整个群体的位置和速度。
1.2 群体拓扑关系
群体中有N个机器人，M(M≥1)个领导者，共N+M个个体，个体间交换信息形成通信拓扑。
定义1：群体机器人系统中2个个体i与j称为邻居，当且仅当下式成立：
，其中d0为给定正常数，为机器人的通信范围半径。假设在此范围内，机器人可以准确感知其他机器人的信息以及领导者的信息。那么个体i的邻居集合为：
(2)
定义2：群体系统的有向拓扑结构图G中，N+M为顶点数即机器人个数，E为边的个数即群体中邻居范围内2个有序对或无序对。如果当前时刻个体i能得到j的信息，就称从j到i的边是连接的；否则从j到i没有连接的边。为简化证明，将图G分成子图Gi和
(l=N+1, N+2, …, N+M)，其中由所有机器人组成的子图为无向图G1，顶点个数为N，边个数为E1，即所有机器人之间只要是邻居就可通信；由所有机器人和领导者l组成的子图为有向图，顶点个数均为N+1，边个数为
并且机器人之间没有边，即子图中只有机器人能感知到领导者信息，领导者不受机器人影响，且机器人之间无通信。
子图G1的关联矩阵为：
(3)
其中：
。
子图的邻接矩阵为:
(4)
其中：
。
是子图G1的拉普拉斯矩阵，显然L1和
是对称正半定矩阵，并且L1零特征根的代数重数等于子图中的连通部分，则对于连通图，其有单一的零特征值，并且相应特征向量是1的n维向量1n [17]。
假设1：本文假设子图G1和图G连通。
1.3 势能函数
群集的一个基本要求是相邻个体保持一定间距。若个体间距太小，它们会试图分开，间距过大，内聚
力起作用。设个体i和j之间的距离为
，用
表示个体i和j之间的势能函数，并满足下列条件：1)非负，可导，且
；2)当
时，
有最大值；3)当
为一定值时，有最小值。从而可知个体i的总势能为：
。
1.4 分布式控制策略
如前所述，在具有N个机器人的群体加入M个具有相同时变速度的领导者，领导者动力学模型为：
(5)
其中：l=N+1，N+2，…，N+M；vl和al(t)分别是第l个领导者的速度和加速度；ve和ae(t)分别是群集群体的期望速度和加速度，且ve和ae(t)有界。从式(5)可以看出：群体中所加入的领导者可控，从而可以根据不同的任务要求对其进行控制，进而影响整个群体的运动实现控制目标。
根据文献[2]提出的规则，设计基于局部信息交互的分布式控制器如下：
(6)
其中：j=1, 2, …, N+M；k=1, 2, …, N；vi和vk分别是第i个和第k个机器人的速度；c1>0，c2>0。式中第1项保证群体中所有个体间的避碰，第2项实现所有个体的速度匹配，第3项和第4项保证群体系统的速度可控，进而使群体中所有个体达到期望的速度。从式(6)可以看出，领导者的加入没有破坏群体中个体的局部规则，即领导者的作用范围不是全局的。
2 稳定性分析
引理(Barbalat)：如果对于连续可导的函数
有下界，
半负定，且关于时间t是一致连续的，那么，
。
定理(群体速度可控性)：考虑由N(N≥1)个机器人组成的群集系统，在群中加入M(M≥1)个领导者，如果所有机器人的动力学特性由式(1)确定，控制规律由式(6)确定，领导者的运动学模型由式(5)确定，且M个领导者的速度矢量均为群体的时变期望速度ve，加速度矢量均为期望加速度ae(t)，那么在满足假设1的条件下，群体中所有机器人的速度矢量将收敛于该期望速度ve。
证明：定义所有机器人和领导者之间的总势能与相对动能之和如下：
定义机器人i的位置和速度与其邻居范围内的领导者平均位置和速度之间的偏差向量分别为：
(7)
为标记方便，定义整个群体的位置和速度偏差分别为：
，
。
定义第i个机器人和领导者之间的位置偏差向量和速度偏差向量分别为：
(8)
为标记方便，定义整个群体的位置和速度偏差分别为
，
。则：
(9)
令
，且
。显然
，因此群体势能可写为
。类似地，机器人i的控制协议可写为
(10)
并且非负值能量函数(6)可记为：
(11)
显然Ve是正半定函数。又因为
所以
(12)
因为L1(t)和
都是正半定矩阵，c1>0，c2>0，c1L1(t)和
也是正半定矩阵，因此，
，从而可得
，即Ve(t)是有界的，这意味着
和ev是有界的。由此及
和
、
的有界性可知
是有界的，
关于时间t是一致连续的。那么
应用Barbalat引理可得
。
把式(12)中的第1项写成二项式的形式：
(13)
其中：
和
分别是ev沿X轴和Y轴的分量。由于图G1是连通图，则L1相应于单一零特征值的特征向
量是1，进而
意味着
和
均属于
，即
由式(4)知：若机器人i与领导者l是邻居，则中相应对角元素
为1，否则为0；而其余非对角元素始终为0。为不失一般性，可假设N个机器人中仅有前Nl(0<>l<>转换成前Nl个对角线元素都是1，其余元素都是0的矩阵
，即
(14)
则式(12)中的第2项
(15)
意味着
(16)
从而由式(7)，(8)，(13)和(15)可得：当
时，有
，故对于所有的个体速度，有
(17)
推论1(群体结构稳定性)：当系统稳定时，群体中任意2个不同个体i和j之间的距离保持恒定。
证明：群体中任意2个不同个体i和j间距平方
则：
由式(17)得
，则
即任意2个不同个体i和j之间的距离的平方不变，也就是当系统稳定时，群体中任意2个不同个体i和j之间的距离保持恒定。
推论2(群体收敛快速性)： 当在定理中的群体里加入速度一致的领导者越多时，群体的收敛速度越快。
证明：当在定理的群体中加入M(M>1)个领导者时，能量函数的导数为：
当在定理的群体中加入M-1个领导者时，能量函数的导数为：
那么，
，且由定理知
，
。
又因为
是正半定矩阵，c2>0，
也是正半定矩阵，因此，
。则可知在定理的群体中加入M(M>1)个领导者比加入M-1个领导者收敛速度快，从而推论2得证。
定理及推论1说明：在满足群体拓扑结构连通的假设条件下，群体中引入的领导者能够引导所有个体逐渐接近期望速度，同时群体中任意2个不同个体的间距保持恒定，即通过引入领导者能够实现群体速度可控的目的，并且使群体的拓扑结构达到一个稳定状态；推论2说明群体中加入的领导者的个数对群体的收敛速度有影响，且领导者个数越多群体收敛速度越快，因此可通过增加领导者个数来提高群体收敛速度。
综上可见：本文作者设计的分布式控制器作用下，能够实现群体机器人群集系统的速度可控性，结构稳定性以及在引入多个领导者时具有的快速收敛性。
3 仿真实验与分析
仿真实验中模拟了分别具有不同数目领导者的群集系统在二维空间中的运动情况，分别从整个群体的运动轨迹、速度收敛曲线和速度偏差曲线来验证定理及推论的有效性。
在本实验中，群体中机器人的个数均为30个，其通信范围均为d0=6 m且所有机器人的初始位置在保证假设1成立的条件下在20 m×20 m的区域内随机给定，初始速度也在0～1之间随机获得。群体中所加入的领导者个数分别为1个、2个和3个，且所有领导者的位置初始位置也在保证假设1成立的条件下在20 m×20 m的区域内随机给定，所有领导者的速度均设置为随时间不断变化的群体期望速度ve= 
，初始速度均设置为
。并设置控制器式(6)中的
参数c1=3，c2=3。
在图1～3中，群体中所有个体的初始位置用星形表示，机器人和领导者的终止位置分别用空心圆和实心圆表示，运动轨迹分别用蓝色细线和红色粗线表示；在图4(a)～6(a)中，机器人和领导者的速度曲线分别用灰色实线和黑色虚线表示。
3.1 结构稳定性验证
图1(a)、图2(a)和图3(a)分别是具有1个、2个和3个领导者的机器人群体群集运动轨迹，图1(b)、图2(b)和图3(b)分别是相应的轨迹终点放大图。可以看出，群体能够在领导者的干预下，实现稳定的群集运动，任意2个个体之间的相对距离在误差允许的范围内保持恒定。此外还可以看出，无论群体中引入多少个领导者，群体的拓扑结构最终仍能够达到稳定的状态，验证了推论1的有效性。
3.2 速度可控性验证
图4(a)、图5(a)和图6(a)分别对应于具有1个、2个和3个领导者的群体群集速度变化曲线。由图可见，领导者在人为的控制作用下，以时变的期望速度运动，群体能够在领导者的干预下，实现群体中所有个体的群集速度矢量一致，且收敛于时变的期望速度，与定理的分析结果吻合。
3.3 收敛快速性验证
图4(b)、图5(b)和图6(b)所示分别对应于具有1个、2个和3个领导者的群体机器人群集系统的速度偏差变化曲线。由图可见：领导者的数量为3个的群体速度收敛最快，1个领导者的群体收敛速度最慢。总的来说，随着群体中领导者数量的增加，群体速度的收敛速度加快，与推论2中结论一致。
图1 具有1个领导者的群体群集运动轨迹和轨迹终点放大图
Fig.1 Trajectories and endpoints enlargement of swarm flocking with one controllable agent
图2 具有2个领导者的群体群集运动轨迹和轨迹终点放大图
Fig.2 Trajectories and endpoints enlargement of swarm flocking with two controllable agents
图3 具有3个领导者的群体群集运动轨迹和轨迹终点放大图
Fig.3 Trajectories and endpoints enlargement of swarm flocking with three controllable agents
图4 具有1个领导者的群体群集速度曲线和速度偏差曲线
Fig.4 Velocity and velocity errors of swarm flocking with one controllable agent
图5 具有2个领导者的群体群集速度曲线和速度偏差曲线
Fig.5 Velocity and velocity errors of swarm flocking with two controllable agents
图6 具有3个领导者的群体群集速度曲线和速度偏差曲线
Fig.6 Velocity and velocity errors of swarm flocking with three controllable agents
4 结论
(1) 为解决群集速度动态控制问题，在群体中引入多个动态领导者，通过对领导者速度的控制，使整个群体达到时变的期望速度，其优点是没有破坏群体的局部交互规则。
(2) 对具有时变期望速度的群体非自治系统，设计了控制器并利用代数图论和Barbalat引理进行了稳定性分析，证明了控制策略有效。
参考文献：
[1] Okubo A. Dynamical aspects of animal grouping: Swarms, schools, flocks and herds[J]. Adv Biophys, 1986, 22: 1-94.
[2] Reynolds C W. Flocks, birds, and schools: A distributed behavioral model[C]//Proceedings of the 14th annual conference on Computer Graphics and Interactive Techniques. New York, 1987: 25-34.
[3] Vicsek T, Czirok A, Ben-Jacob E, et al. Novel type of phase transition in a system of self-driven particles[J]. Physical Reviews Letter, 1995, 75(6): 1226-1229.
[4] Balch T, Arkin R C. Behavior-based formation control for multi-robot teams[J]. IEEE Trans on Robotics and Automation, 1998, 14(6): 926-939.
[5] Liu Yan-fei, Passino K M. Stable social foraging swarms in a noisy environment[J]. IEEE Trans on Autom Contr, 2004, 49(1): 30-44.
[6] Jin Dan, Gao Li-xin. Stability analysis of a double integrator swarm model related to position and velocity[J]. Transactions of the Institute of Measurement and Control, 2008, 30(3/4): 275-293.
[7] Jadbabaie A, Lin J, Morse A S. Coordination of groups of mobile autonomous agents using neighbor rules[J]. IEEE Transaction on Automatic Control, 2003, 48(6): 988-1001.
[8] Wang Zong-yao, Gu Dong-bing. Distributed leader-follower flocking control[J]. Asian Journal of Control, 2009, 11(4): 396-406.
[9] HAN Jin, LI Ming, GUO Lei. Soft control on collective behavior of a group of autonomous agents by a shill agent[J]. J Syst Sci Complex, 2006, 19(1): 54-62.
[10] 楚天广, 杨正东, 邓魁英, 等. 群体动力学与协同控制研究中的若干问题[J]. 控制理论与应用, 2010, 27(1): 86-93.
Chu Tian-guang, YANG Zheng-dong, DENG Kui-ying, et al. Problems in swarm dynamics and coordinated control[J]. Control Theory and Applications. 2010, 27(1): 86-93.
[11] 刘志新, 郭雷. 多个体系统的连通与同步[C]//第25届中国控制会议论文集, 哈尔滨: 北京航空航天大学出版社, 2006: 373-378.
LIU Zhi-xin, GUO Lei. Connectivity and synchronization of multi-agent systems[C]//Proceedings of the 25th Chinese Control Conference, Harbin: Beihang University Press, 2006: 373-378.
[12] Tanner H G, Jadbabaie A, Pappas G J. Flocking in fixed and switching networks[J]. IEEE Trans on Automat Contr, 2007, 52(5): 863-868.
[13] 雷斌. 群体机器人系统合作控制问题[D]. 武汉: 武汉理工大学物流工程学院, 2009: 84-97.
LEI Bin. Research on cooperative control problem of swarm robots system [D]. Wuhan: Wuhan University of Technology. School of Logistics Engineering, 2009: 84-97.
[14] Olfati-Sabe R. Flocking for multi-agent dynamic systems: Algorithms and theory[J]. IEEE Trans Automat Contr, 2006, 51(3): 401-420.
[15] Su Hou-sheng, Wang Xiao-fan, Lin Zong-li. Flocking of multi-agents with a virtual leader[J]. IEEE Trans on Automat Contr, 2009, 54(2): 293-306.
[16] Hong Yi-guang, Hu Jiang-ping, Gao Lin-xin. Tracking control for multi-agent consensus with an active leader and variable topology[J]. Automatica, 2006, 42: 1177-1182.
[17] Alavi Y, Chartrand G, Oellermann O R, et al. Graph theory, combinatorics, and applications[M]. New York: Wiley, 1991: 439-444.
(编辑 何运斌)
收稿日期：2011-04-15；修回日期：2011-06-15
基金项目：国家自然科学基金资助项目（60675057）；吉林大学“985工程”工程仿生科技创新平台项目(2010)
通信作者：田彦涛（1958-），男，吉林四平人，教授，博士生导师，从事分布式智能系统研究；电话：0431-85095769；E-mail：tianyt@jlu.edu.cn
摘要：研究在不破坏群集系统局部交互规则的情况下群体速度动态可控的问题。在具有时变期望速度的群体非自治系统中加入多个动态领导者，设计基于局部信息交互的分布式控制器。为简化证明将群体拓扑结构图划分两类子图，利用Barbalat引理进行稳定性分析，证明在局部信息交互下通过对领导者施加控制，能够使系统中的所有个体的速度矢量收敛到时变期望值，使群体形成稳定结构，同时证明引入领导者越多，群体速度收敛越快。仿真实验结果表明该控制策略有效。
