多智能体系统的包含控制研究

2020-02-03王雅

电子技术与软件工程 2020年11期

王雅

（成都工业学院教务处四川省成都市 611730）

1 引言

多智能体系统（multi-agent systems）的思想源自对生物群集自然现象的模拟，研究学者通过对该类自然现象的仿生研究提出了多智能体系统的概念，并从社会学、拓扑学以及控制理论等领域进行了深入探讨。由于多智能体系统采用分布式协同控制，因此与传统的集中式控制系统相比，多智能体系统具有功能更强大、鲁棒性能更好、设计更简单以及价格更便宜等优点。目前，多智能体系统的研究在切换通信拓扑、动态模型以及分布式包含控制协议等方面均取得了不错的研究成果。多智能体系统已在多个领域有了实际应用，例如传感器网络[1,2]、移动智能机器人编队控制[3,4]、无人机部署[5]、多机器人协作等。

近年来，随着通信、计算机学科以及人工智能等领域的迅猛发展，多智能体系统协同控制逐步发展为一门新兴的控制科学，激发了来自应用数学、智能控制、计算机应用等众多领域研究者们的兴趣。对于多智能体系统的协同控制，最初是对简单的一阶多智能体系统[6,7]进行研究，提出了相应的控制算法并实现了智能体的位置同步，紧接着进一步研究了二阶多智能体系统的协同控制[8,9，10]。目前,关于多智能体系统的研究主要涉及一致性问题[11-15]、包含控制问题[16,17]、编队控制问题[18,19]、蜂拥控制问题[20,21]、覆盖控制问题[22,23]等，其中，关于一致性问题的研究是多智能体系统协同控制中各类问题研究的重要理论基础。

多智能体系统的一致性指的是智能体之间通过分布式的控制协议进行信息交互，最终使得所有智能体的某些物理量（状态、速度、加速度等）达到相同的值。根据网络中领导者的不同数量，将多智能体系统的一致性划分为无领导者的一致性(简称为一致性)，一致性跟踪(有一个领导者)及集合跟踪(或称为包围，有多个领导者)[24]。包含控制(containment control)问题作为一致性问题的延伸，具有广泛的实际应用背景，因此也成为多智能体系统协同控制研究的一个热点问题，具有巨大的理论研究价值和实际研究意义。多智能体系统的包含控制是指多个智能体利用分布式网络传输局部信息，通过设计适当的控制协议，最终使得所有的跟随者进入到领导者张成的凸包内。在无法获取全局信息的情况下，多智能体系统的包含控制主要通过系统中智能体的局部信息交互来实现。目前，多智能体系统的包含控制理论己经在很多方面得到了实际应用，例如资源定位，联合救援和住宅保护等[25]。

近期关于一致性问题的研究已逐步深入并完善，目前作为分布式协同控制的一个重要研究方向的包含控制问题，受到越来越多研究学者的重点关注。为了实现多智能体系统的包含控制目标，需要针对不同的实际情况（例如考虑异步、拓扑切换及环境噪声等）来设计合适的算法，从而使得每个智能体通过局部信息传输，最终实现全部跟随者的状态能够收敛到由领导者所张成的凸包内。

2 包含控制研究的理论基础与问题阐述

2.1 图论相关知识

通常用加权有向图为多个智能体之间的信息交换建模，G={V,E,A}是一个加权有向图，其中V={1,...,n}是一个有限非空的节点集合，是边的集合，是具有非负元素的加权邻接矩阵。表示存在一条从节点j 到节点i 的边。加权有向图中的一条边(i,j)表示智能体j 能够从智能体i 获取信息，反之则不一定。节点i 的邻居集合用表示。

有向图G 中的有向路径是一个顶点序列(i1,...ik)，对于s=1,...,k-1,使得有向树是一个有向图，其中除了根节点的其余每个节点都仅有一个母节点。有向生成树是一个有向树，它由G 中所有节点和一些边组成。若在每对不同的顶点i,j 之间有一条从i 到j 的有向路径，则称有向图G 是强连通的。有向森林是由一个或多个有向树组成的有向图，其中任意两个有向树之间没有共同的顶点。有向生成树是由G 中的所有节点和一些边组成的有向森林。

G 的拉普拉斯矩阵定义如下：

节点i 的入度和出度分别定义如下：

度矩阵是一个n×n 矩阵，定义为D=[dij]，其中对于i=j，dij= degin(i)；否则dij=0。于是图G 的拉普拉斯矩阵可以写成L=D-A。

2.2 符号网络

利用图论的思想，符号网络（signed network）可以表示为一个图，其中的每条边具有正或负的符号属性。关于符号网络的三个基本问题是：它是否平衡？平衡边集的最大尺寸是多少？要使其平衡，必须删除的最小顶点数是多少？第一个问题很容易快速解决；第二个和第三个问题在计算上属于NP-hard 问题。

目前，关于多智能体系统一致性的研究成果大多是建立在完全合作网络（智能体之间体现为积极友好的关系）的基础上的，即在通信拓扑图中，描述个体之间信息交互的边的权值都假定为非负。而在现实世界中，网络中个体之间通常同时存在合作与竞争关系。与传统的完全合作网络下的完全一致性不同，符号网络在描述系统中个体之间的信息交互时，引入了具有负权值的边来描述消极的竞争或敌对关系，即通过构造符号函数来刻画个体之间的通信拓扑。符号网络(signed network)中的边（edge）可能具有正或负的符号属性,其中,带正号“+”的边代表积极的关系（例如朋友、信任、喜欢、支持等），带负号“-”的边代表消极的关系（例如敌人、质疑、讨厌、反对等）[26]。通常将实际的复杂系统抽象为符号网络进行描述与分析。因此，研究符号网络下多智能体系统的包含控制问题具有深刻的现实意义。

2.3 问题阐述

多智能体系统包含控制是指多个智能体利用分布式网络传输局部信息，通过设计适当的控制协议，最终使得所有的跟随者进入到领导者张成的凸包区域内。

符号网络下具有切换拓扑和时变时滞的一阶多智能体系统包围控制问题的数学模型如下：

领导者动力学：

跟随者动力学：

设计控制协议：

3 包含控制问题研究进展

对包含控制问题的研究起源于自然界以及社会实践过程中的潜在应用，例如公蚕蛾通过探测母蚕蛾间歇性释放的费洛蒙信息素[27]，最终停留在由母蚕蛾形成的凸包内，该文中研究了二分一阶多智能系统在切换通信拓扑条件下的包含控制问题。关于包含控制，最早是由Dimarogonas 等人在文献[28]中提出的，该文中将独轮车队作为多智能体系统，介绍了一种基于领导者的包含控制策略，基于控制律无论跟随者的状态如何，领导者们都能够收敛到理想的编队中。多智能体系统的包含控制问题的研究引起了众多研究学者的关注，陆续涌现出一系列丰硕的研究成果。

3.1 一阶多智能体系统包含控制问题

在文献[29]中给出了对包含控制的定义，即驱策一组智能体向给定的目的地行进，在到达目的地之前，多智能体系统的编队形状保持不变，即队形收到固定的几何图形（凸多胞形）所限制，因此能够保证在移动过程中多个智能体在有界的范围中移动。文中采用了偏差分方程理论，并提出了基于stop-go 规则的混合控制策略，从而使得跟随者进入由领导者张成的凸包内，并分析了所得系统的非零度，活跃性和收敛性。文献[30]研究了在有向网络拓扑下含有静态和动态领导者的多智能体系统在固定和切换拓扑下的分布式包含控制问题。当领导者是固定不动的时，无论拓扑图是固定还是切换的，都可以得到连续时间和离散时间下系统实现包含控制的充分必要条件。特别地，当网络拓扑固定时，跟随者的最终状态恒定；当网络拓扑切换时，跟随者的最终状态可能随着拓扑切换而发生变化。而当领导者是动态变化的时，文中提出了一种无需速度测量的分布式跟踪控制算法，并推导了网络拓扑和控制增益的条件，以确保所有跟随者最终都能收敛到由动态领导者针对任意初始状态形成的动态凸包。文献[31]中指出，当领导者静止并且所有跟随者共享一个惯性坐标系时，给出了在固定和切换有向网络拓扑下，在任何有限维的空间中使得任意初始状态的全部跟随者最终收敛到由静止领导者形成的静止凸包的充分必要条件。当有向网络拓扑固定时，对非对称拉普拉斯矩阵进行划分，并探索其性质以得出收敛结果。当有向网络拓扑切换时，基于Kronecker 积在高维空间中常用的去耦技术将不再适用，因此，文中提出了一种重要的坐标变换技术，以得出收敛结果。所提出的坐标变换技术在其他高维分布控制场景中也具有潜在的应用价值，当基于Kronecker 积的去耦技术无法应用时，可以利用该技术将高维系统的分析简化为一维系统的分析。当领导者是动态的并且所有跟随者共享一个惯性坐标系时，提出了一种无需速度测量的分布式跟踪控制算法。此外，还通过一些反例表明，在没有速度测量的情况下，通常不可能找到分布式包含控制算法，以确保在高维空间中所有跟随者最终都能在切换网络拓扑下收敛到动态领导者形成的凸包。

3.2 二阶多智能体系统包含控制问题

文献[32]研究了存在固定及动态领导者的双重积分器动力学行为的二阶多智能体系统分布式包含控制问题。在静态领导者的情况下，提出了一种分布式包含控制算法，并研究了网络拓扑和控制增益的条件，以保证在任何维空间中的渐近包含控制。对于动态领导者，研究了两种情况：速度相同的领导者和速度不同的领导者。对于速度相同的领导者，提出了一种分布式包含控制算法，以解决基于有向切换网络拓扑的渐近包含控制。特别地，如果网络拓扑是固定的，则对于任何维空间都可以实现渐进包含控制，如果网络拓扑是交换的，则仅可以对一维空间实现渐进包含控制。对于速度不同的领导者，提出了一种固定网络拓扑结构下的分布式包含控制算法，其中跟随者之间的通信模式是无向的，并推导了网络拓扑结构的条件和控制增益，以保证对任何维空间的渐近包含控制。最后通过在多机器人平台上的实验以验证了理论结果的有效性。文献[33]研究了包含多个静止不变或动态变化领导者的网络化多智能体系统的包含控制问题，其描述领导者和跟随者之间信息交互的拓扑是有向图。对于连续时间和基于采样数据协议，分别建立了保证包含控制实现的充分必要条件。当领导者静止时，连续时间协议的收敛完全取决于拓扑结构；而基于采样数据协议的收敛不仅取决于拓扑结构还与采样周期有关。当领导者动态变化时时，连续时间协议的收敛取决于拓扑结构和增益参数；而基于采样数据协议的收敛则不仅取决于拓扑结构和增益参数还与采样周期有关。而且，所有跟随者的最终状态完全由领导者的初始值和拓扑结构决定。在静止领导者的情况下，所有的跟随者将进入领导者所张成的凸包内，而在动态领导者的情况下，跟随者不仅将进入凸包，而且将以相同的速度与跟随者一起移动。最后，通过数值模拟验证了上述理论结果的有效性。文献[34]研究了一组自动驾驶汽车的分布式包含控制问题，该问题由具有多个动态领导者的双积分器动力学建模。其目的是在无法获得领导者和跟随者的速度和加速度的约束下，将跟随者推入由动态领导者跨越的凸包中，领导者只是跟随者子集的邻居，并且跟随者之间只有局部信息交互。提出了两种仅通过智能体的位置测量来进行控制的算法。理论分析表明，如果跟随者之间存在无向的网络拓扑，则跟随者将进入由动态领导者张成的凸包中。对于每个跟随者，至少有一个领导者具有指向该跟随者的有向路径，并且给出了恰当的算法参数。最后通过数值仿真验证其理论结果。更多关于一阶和二阶多智能体系统包含控制的研究可参考文献[35-39]。

3.3 一般线性多智能体系统包含控制问题

除了对一阶、二阶多智能体系统包含控制问题的研究之外，关于一般线性多智能体系统包含控制问题的研究也逐步展开。文献[40]使用交互拓扑研究了具有线性动力学的多智能体的行为。根据拓扑结构，将智能体分为了两类，即内部智能体和边界智能体。所涉及的包容控制问题是使得同一强分量中的边界智能体渐近一致，且所有的内部智能体收敛到边界元所张成的凸包内。此外，通过在多智能体系统中引入领导者，设计了部分智能体的牵制控制策略，使得所有的智能体都能渐近地与领导者达成一致。文中还说明了如何选择与领导者进行局部信息交互的智能体，以便达成一致，并使所选智能体的数量最少。以后所有的结果的有效性都通过一些数值模拟得到了验证。此外，文献[41]考虑了在有向通信拓扑下具有一般线性动力学的连续时间和离散时间多智能体系统的包含控制问题。针对连续时间和离散时间情况，都构造出了基于相邻智能体的相对输出的分布式动态包含控制器，并给出了关于这些动态控制器存在的充分条件。并对依赖于相邻智能体相对状态的静态包含控制器进行了讨论。文献[42]研究了当领导者之间没有交互情况下的包含控制问题，考虑了在有向通信拓扑下具有一般线性动力学的连续时间和离散时间多智能体系统的包含控制问题。针对连续时间和离散时间情况，都构造了基于相邻智能体相对输出的基于分布式降阶观察者的包含控制器，在这种情况下，跟随者的状态将渐近收敛到由领导者的状态形成的凸包，并给出了关于这些包含控制器存在的充分条件。

在近期的研究中，文献[43-45]给出了更多关于一般线性多智能体系统包含控制的相关成果。文献[43]研究了具有弱连通信息拓扑的线性多智能体系统的包含控制问题。文献[44]讨论了由于个体之间信息交换的不连续性而导致的非周期性采样问题。文献[45]通过谱半径分析和矩阵理论获得了一些充分必要条件。文献[46,47]研究了没有任何结构性限制的一般网络拓扑的多智能体系统包含控制问题，其中领导者和跟随者完全由网络拓扑决定。文献[48,49]讨论了异步条件下静态领导者的二阶多智能体系统包含控制问题。更多有关一般线性多智能体系统的包含控制问题研究可参考文献[50-53]。