拓扑连通性保持下的多智能体系统群集控制研究

摘 要： 对群集动态行为的涌现机制进行深入研究，提出了一种新颖的基于骨干网络的系统层次型组织拓扑结构的分布式建模方法，进而以层次型网络模型为基础，在骨干网络层内部采用分布式人工势场函数实现骨干网络内部的连通性保持和拓扑结构重构，然后利用领航跟随控制思想，将基于势函数的梯度控制算法和基于调和流函数的避障控制算法有机结合，巧妙地解决了网络的跨层连通性保持与对障碍物的光滑规避，实现了骨干网络层与非骨干网络层之间的跨层协调控制，减少了冗余通信约束，降低通信和计算代价，显著增强了整个系统的灵活性和适应性。

关键词： 多智能体系统； 群集； 拓扑连通性； 人工势场函数； 骨干网络?Ⅱ

中图分类号： TN919?34； TM417 文献标识码： A 文章编号： 1004?373X（2016）19?0033?04

Abstract： Based on the deep study on the emergence mechanism of cluster dynamic behavior， a new distributed modeling method of system hierarchical topology structure based on backbone network is proposed. On the basis of the hierarchical network structure， the distributed artificial potential function inside the backbone network is used to realize the connectivity maintenance and topological reconstruction inside the backbone network. And then the plot follow control thought is used to integrate the gradient control algorithm based on potential function and obstacle avoidance algorithm based on harmonic stream function organically， which can solve the cross?layer connectivity maintenance of the network and smooth circumvention of the obstacle， realize the cross?layer coordination control between the backbone network layer and non?backbone network layer， reduce the constraint of the redundancy communication， communication and calculation costs， and enhance the flexibility and adaptability of the whole system.

Keywords： multi?agent system； cluster； topology connectivity； artificial potential function； backbone network Ⅱ

0 引 言

在现实应用中通常只能保证多智能体系统通信拓扑的初始连通性，而无法保证系统在后续的演化过程中始终保持连通[1]。因此，在保证拓扑连通性约束始终得到满足的条件下，对多智能体系统进行分布式群集运动控制是一个贴近实际需求、面向典型应用的理论研究，相关研究成果对涌现性群集行为的理解及其在大规模复杂群体系统的应用，具有重大的理论意义和实践指导价值[2]。

本文重点研究障碍环境下多智能体系统群集控制中的连通性保持和避障控制问题。大多数相关控制算法存在的不足包括：连通性保持控制算法采用的网络模型均为平面型对等网络；系统在动态演化过程中同时实现连通性保持与避障控制至今仍然是一个开放性问题[3]。

为克服上述缺陷，将上述问题分解为互相紧密耦合的两个子问题：即离散拓扑空间的拓扑连通性保持问题和连续位形空间中的群集运动与避障控制问题[4]。首先，引入一种新颖的基于骨干网络的系统拓扑控制算法以实现系统层次型网络模型的分布式构建，进而设计一类分布式骨干网络拓扑自裁剪算法（BSPA），使得在保持网络整体连通性的条件下减少冗余通信/运动约束，该算法仅用到不超过每个智能体的两跳通信邻域内的局部信息，具有良好的可扩展性[5]。然后，基于构建出的精简骨干网络，将调和流函数和人工势场函数有机结合，给出了一类分布式群集运动与避障控制算法，使得系统中所有的智能体可以实现速度的渐近同步，同时实现网络的连通性保持和智能体间的碰撞规避。

1 问题描述

控制目标是在网络拓扑初始连通的条件下，为多智能体系统设计一类分布式群集控制协议，使得所有的智能体能够实现速度渐近趋同，智能体间以及智能体与障碍物间的碰撞规避，同时保持网络拓扑在系统演化全过程中的连通性[6]。

2 总体控制策略

将原始问题进行巧妙分解，从而给出一种新颖的分布式闭环反馈控制框架。首先在离散拓扑空间中研究通信网络的拓扑控制算法以实现基于骨干网络的系统层次型网络模型的分布式构建；其次基于层次型骨干网络模型，通过将人工势场函数与调和流函数有机结合，有效解决在连续位形空间中系统的跨层运动协调控制中的拓扑连通性保持问题，同时可以驱使系统沿着光滑的轨线运动以实现对静态障碍物的规避。

3 系统层次型拓扑构建

多智能体通信骨干网络给出了一种一般化的系统层次型组织拓扑结构的建模方法，本质上是一种具有动态性和临时性的主干结构，网络中各节点可根据环境和任务的变化以及节点本身的能力实时调整其在网络结构中的功能角色。

为避免构造原系统的最小连通支配集（MCDS），选择构建系统的极小连通支配集，即以引入一定数目的冗余顶点为代价来简化解决问题的复杂度，即通过寻求问题的次优解来取代最优解，可在最大限度保持结果精度的同时显著降低了算法的计算复杂度。具体地，从运动控制的角度出发使用启发式优先级排序算法（HPOC）实现网络分簇以提取出原始网络的通信骨干子网。HPOC采用多准则综合性的节点优先级评估方案解决骨干智能体和非骨干智能体的选取问题。通过综合考虑智能体的ID、节点度数、通信质量、智能体与障碍物的远近程度等指标来定义智能体的任务优先级权重。

4 系统跨层群集运动与避障控制

4.1 系统跨层协同控制基本框架

从网络分布式跨层协同控制的角度设计分布式群集运动与避障控制协议，以驱使智能体渐近实现系统的速度同步，避碰和避障等控制任务。当前时刻系统基础网络拓扑在骨干网络相邻两次切换间网络中的所有通信连接均可以得到保持。因此，采用基于势函数的梯度控制策略来解决上述问题，整个多智能体系统的拓扑连通性保持可通过如下方法加以实现：

（1） 骨干网络中的通信连接可通过为每个骨干智能体设计连通性保持运动控制律加以解决；

（2） 通过将领航?跟随跟踪控制策略引入到层次型骨干网络中，不仅可以解决非骨干智能体与之所附属的骨干智能体间的通信连通性保持，而且可以驱使骨干智能体跟踪流线上对应的虚拟领导者实现光滑的避障控制。

此后，将上述控制策略称为基于骨干网络的系统连通性保持框架（BBCM）。

4.2 骨干智能体群集控制律设计

由于网络的初始连通性并不能保证网络在系统演化全过程中的连通性，因而需要为每个骨干智能体设计相应的人工势场函数来同时保证骨干网络中各骨干智能体间彼此避免碰撞和整个骨干网络在连续运动过程中的拓扑连通性保持。

4.3 非骨干智能体群集控制律设计

对于任一非骨干智能体，将与其自身在同一簇内所附属的骨干智能体视为领导者，并保持彼此之间的通信连接，同时还需避免与其他智能体发生相互碰撞。因此，对于任一非骨干智能体，其所受到的运动约束如图3所示，其中FA表示非骨干跟随者智能体，DA表示该非骨干智能体所附属的骨干领导者智能体。

5 数值仿真

5.1 基于BBCM的群集运动与避障控制仿真

数值仿真实例以验证本节提出的BBCM群集算法的有效性。仿真中使用20个在二维平面上满足运动学方程的智能体组成多智能体系统，每个智能体均用黑色圆点表示。控制目标为使所有的智能体都能够在控制律（3）和（4）的作用下以紧凑的连通网络的形式聚集在期望的目标位置，同时避免与环境中的障碍物发生碰撞，智能体的初始位置和速度随机设置且可保证网络初始连通。仿真中使用的具体参数为：位形空间90 m[×]90 m；智能体数目[N=20；]仿真时间为30 s；目标位置（80 m，80 m）；通信半径为5 m；加边延迟阈值为0.6 m；期望距离为3 m；避碰距离阈值为2 m，最大速度为0.5 m/s； 初始位置[0 m，20 m]×[0 m，20 m]；更新周期[TB=2；]流场强度[U=3， C=1.5；]控制增益[k1=2，][k2=4；]障碍物质心[q10=]（36，33） m，[q20=]（38，35） m。

提出的基于BBCM的系统群集运动与避障控制的仿真结果如图4所示。为验证算法在系统进行避障控制过程中的有效性（无局部极小点），仿真中刻意将多智能体系统的质心，障碍物的质心以及期望目标点三者位于同一直线上。

图4（a）和（b）给出了系统的原始平面型网络模型和对应的层次型骨干网络模型，其中主导智能体、中继智能体和非骨干智能体分别由黑色圆点、红色圆点以及白色圆点表示。蓝色实线表示网络中的通信连接。可以看出[GB]所包含的所有[C3]和C4的冗余通信连接均被有效删除，因而验证了所提出的BSPA算法的有效性。

5.2 层次型网络与平面型网络的性能对比仿真

在任务完成时间方面的对比结果，如图5所示，其中网络的规模[N]范围从20～80。从图5中可以看出，针对任意规模为[N]的多智能体系统，层次型骨干网络较平面型对等网络在任务完成的时间效率方面均具有显著优势，可以显著降低系统的任务完成时间，提高系统的协同作业效率。

BBCM算法在执行复杂的空间分布式任务时更加具有灵活性和高效性。这是由于BBCM算法可从本质上刻划系统的核心拓扑结构，并且将系统中存在的冗余通信约束和运动约束降低到近似最小限度，因而有助于系统实现灵活的拓扑结构重构以适应环境和任务的变化。最后，在相同的初始条件下给出对比仿真以突出层次型骨干网络较平面型对等网络在系统总体通信代价方面的优势。

5.3 滞 点

尽管使用流函数进行避障控制可以克服基于传统人工势函数避障方法中存在局部极值点的固有缺陷。但仍有另外一个问题值得关注，即滞点（SP）问题。因为在任一滞点处，流体的速度为零并且若任一智能体正好落入滞点，其将保持静止。为了解决上述问题，可以采用随机游走（RandomWalk）算法使智能体脱离滞点。在流体力学中，涡流的复势[v=Ciln（z）]被用来在两个同心圆柱体间产生旋转运动，将上述涡流的复势加入到原来流场的复势中会改变原系统滞点的位置。由于滞点的位置可以通过调整涡流强度[C]来加以调整，当智能体停在某一滞点处，下一控制周期内可以通过设置新的涡流强度以更新该智能体的位置，从而使其脱离当前滞点。

6 结 论

基于极小连通支配集理论，提出了一种新颖的系统层次型精简骨干网络模型的分布式构建方案，从而给出了对于原始网络一种高效的组织拓扑结构的表达方式。基于调和流函数的避障路径规划方法可以产生没有局部极小点的光滑避障路径；基于人工势场函数的连通性保持方法可以用来保持层次型骨干网络内部的所有通信连接以及骨干网络层与非骨干网络层之间的所有通信连接，避免智能体间彼此发生碰撞。

与平面型对等网络模型相比，本文所提出的基于层次型骨干网络的分布式跨层协同群集运动与避障控制机制的突出特性表现在其可以将系统中的冗余通信约束和运动约束降低到近似最低限度，因而可显著降低系统的通信代价和计算代价，有效增强整个系统对环境和任务变化的灵活性和适应性。最后，对比数值仿真结果验证了理论结果的正确性和控制算法的有效性。

参考文献

[1] REN W， CAO Y C. Distributed coordination of multi?agent networks： emergent problems， models， and issues [M]. London： Springer?Verlag， 2012.

[2] LEE D， SPONG M W. Stable flocking of multiple inertial agents on balanced graphs [J]. IEEE transactions on automatic control， 2007， 22（8）： 1469?1475.

[3] CAO Y C， REN W. Distributed coordinated tracking via a variable structure approach?part Ⅱ： swarm tracking [C]// Proceedings of 2010 American Control Conference. Baltimore： IEEE， 2010： 4750?4755.

[4] CAO Y C， REN W. Distributed coordinated tracking with reduced interaction via a variable structure approach [J]. IEEE transactions on automatic control， 2012， 57（1）： 33?47.

[5] CAO Y C， REN W. Containment control with multiple stationary or dynamic leaders under a directed interaction graph [C]// Proceedings of 2009 28th IEEE Conference on Decision and Control. Shanghai， China： IEEE， 2009： 3014?3019.

[6] 周香.大规模无人系统集群智能控制方法综述[J].信息系统工程，2015（2）：19.