控制与决策  2019, Vol. 34 Issue (1): 157-161  
0

引用本文 [复制中英文]

陈世明, 李海英, 邵赛, 夏振刚. 基于二分图最大匹配的多机器鱼可控包含控制[J]. 控制与决策, 2019, 34(1): 157-161.
[复制中文]
CHEN Shi-ming, LI Hai-ying, SHAO Sai, XIA Zhen-gang. Controllable containment control of multiple robotic fish based on bipartite graph maximum matching[J]. Control and Decision, 2019, 34(1): 157-161. DOI: 10.13195/j.kzyjc.2017.0972.
[复制英文]

基金项目

国家自然科学基金项目(11662002, 61364017);江西省创新驱动“5511”优势科技创新团队项目(20165BCB19011);江西省重点研发计划-制造业信息化科技工程一般项目(20161BBE53008);江西省自然科学基金项目(20171BAB202029)

作者简介

陈世明(1977-), 男, 教授, 博士, 从事复杂网络理论、多智能体系统、优化算法等研究;
李海英(1993-), 女, 硕士生, 从事多智能体一致性的研究。

通讯作者

陈世明, E-mail: c1977318@hotmail.com

文章历史

收稿日期:2017-07-20
修回日期:2017-11-03
基于二分图最大匹配的多机器鱼可控包含控制
陈世明, 李海英, 邵赛, 夏振刚    
华东交通大学 电气与自动化工程学院,南昌 330013
摘要:考虑水下机器鱼的运动学约束及包含控制中的领导者选择问题, 将可控性理论与包含控制相结合, 针对有向多机器鱼系统, 提出一种基于二分图最大匹配的多机器鱼可控包含控制算法.首先, 针对有向多机器鱼网络拓扑结构, 利用二分图最大匹配算法求得满足系统可控的驱动节点, 即为领导者, 其余节点为跟随者; 其次, 针对2D仿真机器鱼模型设计相应的包含控制协议, 从而实现多机器鱼的可控包含控制, 且最终跟随者鱼体前端刚体长边方向与领导者保持一致, 并应用Lyapunov稳定性理论证明系统的稳定性; 最后, 基于URWPGSim2D多机器鱼仿真平台进行两组仿真实验, 一组随机选取领导者, 另一组采用二分图最大匹配算法确定领导者, 对比仿真结果表明, 所提算法能够有效地实现多机器鱼的可控包含控制.
关键词多机器鱼系统    二分图最大匹配    可控性    包含控制    URWPGSim2D仿真平台    有向拓扑    
Controllable containment control of multiple robotic fish based on bipartite graph maximum matching
CHEN Shi-ming, LI Hai-ying, SHAO Sai, XIA Zhen-gang    
School of Electrical and Automation Engineering, East China Jiaotong University, Nanchang 330013, China
Abstract: The kinematic constraints of underwater robotic fish and the leader selection in containment control are considered in this paper. Combining the controllability theory with containment control, for the directed multiple robotic fish system, a controllable containment control algorithm of multiple robotic fish based on bipartite graph maximum matching is proposed. Firstly, aiming at the directed network topology of multiple robotic fish, the maximum matching algorithm of bipartite graph is used to get the driving nodes satisfying the system controllable as leaders, the others are followers. Then, the corresponding containment control protocol is designed for the model of 2D simulation robotic fish. Thus, the controllable containment control of multiple robotic fish system is achieved and the rigid body long side direction of follower fish is consistent with leaders. The Lyapunov stability theory is used to prove the stability of the system. Finally, two groups of simulation experimet on the URWPGSim2D multiple robotic fish simulation platform are carried out. One group randomly selects leaders, and the other group uses the bipartite maximum matching algorithm to determine the leaders. Simulation results show that the proposed algorithm can effectively realize the controllable containment control of multiple robotic fish.
Keywords: multiple robotic fish system    bipartite graph maximum matching    controllability    containment control    URWPGSim2D simulation platform    directed topology    
0 引言

一致性问题作为多智能体分布式协同控制中的主要研究方向之一, 已经取得大量的研究成果[1-2].根据领导者数目的不同可分为无领导者一致性、领导-跟随一致性以及多领导者一致性等.包含控制近年来受到了学者们的广泛关注[3-4], 其主要是使系统内的跟随者个体的状态收敛到由多个领导者组成的凸包中, 是一种具有多领航者的类一致性问题.

包含控制在环境探索、科学采样、监测和侦查等任务中具有极大的应用价值.文献[5]提出了一种基于预测器的神经动态表面控制方法来实现多AVU的包含控制; 文献[6]考虑到多智能体在复杂环境中其通信可能会随机失效, 研究了有向随机网络下的多智能体的领导跟随包含控制问题; 文献[7]针对高阶LTI群集系统的编队包含控制问题进行了研究, 通过所提出的协议使得领导者能够实现预定的时变编队, 并驱使跟随者运动至由领导者构成的凸包, 此外, 文中还指出了包含问题、编队控制问题、一致性以及一致性追踪等问题均可以视作特殊的编队包含控制问题; 文献[8]进一步针对具有时延的高阶LTI系统的编队包含控制问题进行了研究.此外, 由于多智能体系统可控性具有重要的应用价值, 近年来受到诸多学者的广泛关注:文献[9]对复杂有向网络的结构可控性进行了研究; 文献[10]对领导者角色的选取以及对边的权值调整进行了研究, 从而改善了系统的可控性.

随着我国海洋开发和应用领域的不断发展, 协同技术的研究工作与实际应用将会得到更加快速的发展[11].文献[12]指出, 机器人的应用已不再局限于简单的动作重复, 未来机器人的高度智能化在群体协调作业中将发挥重要作用; 文献[13]研究了蜂拥算法在多机器鱼系统中的应用; 文献[14]结合模糊增强学习构建了一个混合集中式系统来完成水下机器鱼的协同合作; 针对机器鱼多关节连接的结构造成的众多流体力学参数获取难等问题, 文献[15]提出了一种数据驱动的动态建模方法, 并证明了该方法在探索参数以及动态仿真中具有更好的稳定性.

考虑到目前针对水下机器鱼的可控包含控制的研究较少, 本文主要考虑机器鱼的运动学约束及控制机制等, 将可控性理论应用于多机器鱼包含控制中的领导者与跟随者可控配置问题中.利用二分图最大匹配算法求得满足系统可控的驱动节点, 即为领导者, 其余节点为跟随者.再针对2D仿真机器鱼模型设计相应的控制协议, 使得所有跟随者能够收敛到由领导者构成的凸包中, 且最终跟随者鱼体方向与领导者保持一致.

1 预备知识和问题描述 1.1 代数图论

考虑由N条机器鱼组成的系统, 采用图G=(V, E)表示该系统的通信拓扑.其中: V ={v1, v2, ..., vN}表示机器鱼集合, 节点vi表示第i条机器鱼, E ={eij=(vi, vj)|vi, vjV}表示机器鱼之间连边的集合.网络的可控性一般是指:给系统内的某个或某几个领导者施加外部控制输入信息, 而系统内的其他跟随者则依靠自组织及其与邻域个体的相互合作, 从而实现由随机给定的初始状态运动演化至所要求的最终状态.给出如下系统:

其中: x(t) =(x1(t), x2(t), ..., xN(t))T为状态向量; u(t) =(u1(t), u2(t), ..., uM(t))Tt时刻M个个体的控制输入; A =(aij)N × NB =(bij)N × M分别为邻接矩阵和输入矩阵.判断可控性的一个充分必要条件为

可以发现, 系统可控的关键在于其拓扑结构和外界输入信息, 即与AB相关.

假设1  多机器鱼网络拓扑结构中含有有向生成树.即对于任意一个跟随者, 至少存在一个领导者到其有一条有向路径.

有向图(V, E)的“子图”(Vs, Es)是指满足VsVEsE ∩(Vs × Vs)的一种图, (V, E)的有向生成树(Vs, Es)是指(Vs, Es)为有向树并且Vs = V.如果有一簇有向生成树是(V, E)的子图, 则称图(V, E)含有一簇有向生成树[16].

引理1[16]   图G对应的Laplacian矩阵为L, 在假设1成立的前提下, 矩阵L是非奇异矩阵且L的非零特征值的实部均大于0.

定义1  设X = {x1, x2, ..., xN}是实矢量空间VRN的集合, 对于X = {x1, x2, ..., xN}的凸包用Co{X}表示, 即

1.2 二分图最大匹配算法

控制一个有向网络所需的最少输入(或驱动节点)由该网络中的最大匹配决定[9]. M为有向图G=(V, E)的边集的一个子集, 若M中的任意两条边都没有公共的起点和终点, 则称M是一个匹配.如果一个节点是M中的一条边的一个终点, 则该节点就是匹配节点, 否则为非匹配节点, 非匹配节点即为驱动节点.通常采用二分图最大匹配算法求取网络中的驱动节点.将图G转化为二分图H, 有

其中: V+ ={v1+, v2+, ..., vN+}, V-= {v1-, v2-, ..., vN-}分别为二分图各列的节点集合, E = {(vi, vj)|aij ≠ 0}为边集.利用所述算法求取驱动节点的过程如图 1所示.

图 1 驱动节点求取过程

图 1(a)图 1(b)所示即为将有向图转化为二分图的过程, 由图 1(c)可以发现, 一组最大匹配边集为1+ → 5-, 2+ → 3-, 6+ → 4-, 可得节点1, 2, 6为非匹配节点, 即为所求驱动节点, 节点3, 4, 5为普通节点.

1.3 机器鱼模型

考虑2D仿真机器鱼模型如图 2所示, 其结构和尺寸与实体机器鱼比例基本一致, 鱼体前进的推进力主要依靠鱼体后半部分尾鳍的摆动.建立其运动学模型[13]如下:

图 2 机器鱼模型
(1)

其中: θi(t) ∈ [0, 2π)为沿X轴逆时针旋转的方向角; ai(t) ∈ R为前进加速度; bi(t) ∈ R为旋转加速度.鱼体几何中心为Ci, 质量中心为Mi, 不考虑个体差异, 假设对于i = 1, 2, ..., N都有li = ld, 其中ld为正常数.

ti= [cosθi, sinθi]T, ni= [-sinθi, cosθi]T为两个正交向量, 式(1)进一步表示成矩阵形式

(2)

其中: Hi = [ti, ni]T; iu = [ai, bi]T为机器鱼的控制输入; pi = [xi(t), yi(t)]TR2为机器鱼it时刻的位置向量; qi = [vi(t), liωi(t)]T = [vi(t), ϑi(t)]T为速度向量; vi(t) ∈ Rωi(t) ∈ R分别为鱼的前进速度和角速度; ϑi(t) = liωi(t)为切向速度.

2 包含控制协议设计

对于由N条机器鱼组成的有向多机器鱼网络, 通过第1.2节所述算法确定的领导者集合和跟随者集合分别表示为L ={x1, x2, ..., xm}, F ={xm + 1, xm + 2, ..., xN}.针对iL, 有

(3)

即对于iL, 个体以固定的前进速度vl和角速度ωl运动.针对iF, 设计控制协议为

(4)

其中aij为个体间的邻接关系.引入, 结合, 则控制协议(4)可进一步描述为

(5)

定理1   考虑如式(1)所示的模型构成的有向多机器鱼系统, 利用二分图最大匹配算法求得满足系统可控的驱动节点即为领导者, 其余节点为跟随者, 若系统符合假设条件1, 则在控制协议(3)和控制协议(4)的作用下, 可以实现多机器鱼系统的可控包含控制.

证明  构造李雅普诺夫函数如下:

(6)

其中

则有

故对式(6)求导后可得

(7)

由式(2)、(5)和(7)可得

(8)

由于, 可得

(9)

则式(8)可进一步简化为

(10)

Q = [q1, q2, ..., qN], P = [p1, p2, ..., pN], 可得

结合引理1可知, LN为半正定矩阵, IN - m为(N-m) ×(N - m)单位矩阵, 即可得

综上可得, 系统和控制协议是渐近稳定的.

3 仿真实验

本节主要基于URWPGSim2D平台进行多机器鱼可控包含控制算法仿真分析, 从而验证所提出算法的有效性. URWPGSim2D仿真系统可以很好地模拟水下机器鱼的运动状态, 也可用于对各种控制策略的验证.多机器鱼网络通信拓扑结构如图 3所示.

图 3 有向网络拓扑结构
3.1 随机选取领导者

针对如图 3所示的多机器鱼网络拓扑结构, 首先任意选取fish2, fish3, fish6作为领导者, 其余为跟随者, 观察其包含控制运动过程, 如图 4所示.

图 4 任意选取领导者时机器鱼包含控制运动

随机选取fish2, fish3, fish6为领导者时, 观察图 4(a)所示的包含控制运动及图 4(b)对应的各条鱼的运动轨迹, 可以发现fish4没有运动到凸包内, 结合图 3的拓扑结构分析, fish4无法接收任一领导者的信息, 故无法实现有效的可控包含控制.同时领导者机器鱼最终的鱼体方向为0.942 rad, fish5的鱼体方向为1.325 rad, 这是由于受到fish1, fish2, fish4, fish6的影响, 其鱼体方向无法达到与领导者一致的状态.

3.2 利用二分图最大匹配求取领导者

针对图 3所示的多机器鱼网络拓扑, 利用第1.2节所述算法确定满足网络可控的领导者集合为fish2, fish4, fish6, 跟随者集合为fish1, fish3, fish5.多机器鱼实现可控包含控制的过程如图 5(a)所示.在控制协议的作用下, 跟随者机器鱼最终运动至由领导者构成的凸包内, 且鱼体方向与领导者保持一致.各条鱼的运动轨迹如图 5(b)所示.

图 5 二分图最大匹配求取领导者时机器鱼包含控制运动
4 结论

本文针对水下机器鱼的运动学约束及控制机制等问题, 将可控性理论应用于多机器鱼包含控制中的领导者与跟随者可控配置问题中.利用二分图最大匹配算法求得满足系统可控的驱动节点即为领导者, 其余节点为跟随者.并针对2D仿真机器鱼模型设计相应的控制协议, 最终实现水下机器鱼的可控包含控制.两组实验结果对比验证了本文所提出算法的有效性.未来的研究中可进一步考虑实际应用中水下通信难等问题对机器鱼运动产生的影响.

参考文献
[1]
Meng Z, Ren W, Cao Y, et al. Leaderless and leader-following consensus with communication and input delays under a directed network topology[J]. IEEE Trans on Systems, Man, and Cybernetics, Part B, 2011, 41(1): 75-88. DOI:10.1109/TSMCB.2010.2045891
[2]
宋海裕, 俞立, 胡鸿翔. 牵制控制下的多智能体系统群一致性[J]. 控制理论与应用, 2012, 29(6): 765-772.
(Song H Y, Yu L, Hu H X. Group consensus in multi-agent systems via pinning control[J]. Control Theory & Applications, 2012, 29(6): 765-772.)
[3]
陈世明, 王培, 赖强, 等. 二阶有向多智能体网络的可控包含控制[J]. 控制与决策, 2016, 31(4): 745-749.
(Chen S M, Wang P, Lai Q, et al. Controllable containment control of second order directed multi-agent networks[J]. Control and Decision, 2016, 31(4): 745-749.)
[4]
Chen S M, Wang P, Li H Y, et al. Controllable containment control of multi-agent systems with strongly connected sub-graph[J]. Control Theory & Applications, 2017, 34(3): 401-407.
[5]
Peng Z, Wang D, Wang J. Containment control of networked autonomous underwater vehicles guided by multiple leaders using predictor-based neural DSC approach[C]. The 5th Int Conf on Intelligent Control and Information Processing(ICICIP). Dalian: IEEE, 2014: 360-365.
[6]
Kan Z, Shea J M, Dixon W E. Leader-follower containment control over directed random graphs[J]. Automatica, 2016, 66(4): 56-62.
[7]
Dong X W, Shi Z Y, Lu G, et al. Formation-containment analysis and design for high-order linear time-invariant swarm systems[J]. Int J of Robust and Nonlinear Control, 2015, 25(17): 3439-3456.
[8]
Dong X W, Li Q D, Ren Z, et al. Formation-containment control for high-order linear time-invariant multi-agent systems with time delays[J]. J of the Franklin Institute, 2015, 352(9): 3564-3584. DOI:10.1016/j.jfranklin.2015.05.008
[9]
Liu Y Y, Slotine J J, Barabási A L. Controllability of complex networks[J]. Nature, 2011, 473(7346): 167-173. DOI:10.1038/nature10011
[10]
Zhao B, Guan Y, Wang L. Controllability improvement for multi-agent systems: Leader selection and weight adjustment[J]. Int J of Control, 2016, 89(10): 2008-2018. DOI:10.1080/00207179.2016.1146970
[11]
Xu B, Bai J L, Hao Y L, et al. The research status and progress of cooperative navigation for multiple AUVs[J]. Acta Automatica Sinica, 2015, 41(3): 445-461.
[12]
谭民, 王硕. 机器人技术研究进展[J]. 自动化学报, 2013, 39(7): 963-972.
(Tan M, Wang S. Research progress on robotics[J]. Acta Automatica Sinica, 2013, 39(7): 963-972.)
[13]
Jia Y, Wang L. Leader-follower flocking of multiple robotic fish[J]. IEEE/ASME Trans on Mechatronics, 2015, 20(3): 1372-1383. DOI:10.1109/TMECH.2014.2337375
[14]
Yu J, Wang C, Xie G. Coordination of multiple robotic fish with applications to underwater robot competition[J]. IEEE Trans on Industrial Electronics, 2016, 63(2): 1280-1288. DOI:10.1109/TIE.2015.2425359
[15]
Yu J, Yuan J, Wu Z, et al. Data-driven dynamic modeling for a swimming robotic fish[J]. IEEE Trans on Industrial Electronics, 2016, 63(9): 5632-5640. DOI:10.1109/TIE.2016.2564338
[16]
Ren W, Beard R W. Distributed consensus in multi-vehicle cooperative control: Theory and applications[M]. London: Springer-Verlag London, 2008: 28-38.