基于事件触发的聚类分析方法在多智能体任务协同中的研究

田承东，杨璧竹

（中国电子科技集团公司信息科学研究院北京100098）

0 引言

随着物联网技术的发展，多智能体系统协同完成指定任务，已经成为人工智能物联网（AIOT）领域的研究热点。为确保完成特定任务，不同智能体间恰当的协同与合作至关重要，如果说模拟人的行为是单智能体的目标，那么模拟人类社会的协同行为则是多智能体系统的最终目标[1]。多智能体研究的核心在于如何使智能体协调行动解决问题，即使个体之间通过相互影响、相互作用形成强大的群体智慧来解决复杂的问题。由智能体组成的多节点网络动态控制比较复杂，因此，如何分析这些复杂网络行为和设计控制算法成为研究的热点。同时，在实际系统中控制对象是运动的，要完成运动目标的跟踪及控制，需要根据被跟踪者的信息随时调整策略并且相互配合完成任务[2][3]。

聚类分析已经被广泛应用在许多智能体协同场景中，作为多智能体协同的预处理步骤，可以简化计算量，提高协同效率。随着聚类算法在工程实践中应用的深入和系统复杂性的增加，待处理的数据量也越来越大，针对多智能体系统中动态区分的不同类别个体，需要提升聚类区分效率以及不同聚类下智能体的一致性，从而达到整个智能体中的有效协同[3]。本文提出了一种基于事件驱动的改进型聚类算法，使智能体在与环境的交互中，可以根据观测的变化来触发通信和学习过程。在相同时间内，采用事件驱动可以降低数据传输次数，节约通信资源，提升聚类效率。最后，对算法进行了验证，结果表明事件驱动可以有效提升聚类算法的效率，促进多智能体分类基础上完成任务的一致性[4][5]。

1 多智能体协同中的一致性问题

在多智能体协同控制中，存在几个作为研究热点的重要问题：多智能体系统模型、多智能体一致性、多智能体任务分配、多智能体冲突识别与消解、多智能体系统安全。多智能体的网络拓扑结构随着智能体的运动，处于不断变化当中，多智能体系统中的一个基本问题就是一致性问题。一致性问题来源于多智能体系统的协调合作控制问题。一致性协议是智能体之间相互作用、传递信息的规则，针对任务的需求，智能体之间对某个或某几个与任务相关的量值达到近似或相同的状态，它描述了每个智能体和与其相邻的智能体的信息交换过程。聚类同步就是首先给多智能体系统分类，然后在每个类中都实现一致性，即多一致性问题[6]。具体包括：

（1）有领导者的多智能体系统的一致性问题

在多智能体系统中，有个别智能体代表着整个多智能体系统的共同利益或者是其他智能体跟踪的目标，把这些智能体称作是领导者，把其他的智能体称作是跟随者。带有领导者的多智能体系统的一致性问题，也称作是一致性跟踪问题，就是通过合适的算法，使得领导者和跟随者的最终状态达到一致[7]。

（2）无领导者的多智能体系统一致性问题

在多智能体系统中，如果各智能体的地位和作用是平等的，称这样的系统是无领导者的多智能体系统。无领导者的系统也可以把其中一个智能体看作是虚拟的领导者，转化成有领导者的一致性问题。无领导者系统中需要根据系统状态来动态改变虚拟领导者的选择，以达到解的最优。

（3）随机一致性问题

由于外部环境下随机噪声及外部系统的干扰，导致智能体之间的通信连接是随机变化的。这时智能体之间的协同问题就是随机一致性问题。当智能体当前时刻的状态只依赖于前一时刻的状态，则智能体系统的协同变化可以用马尔可夫过程来处理。当智能体之间各个状态差值平方的期望趋于0时，称作是多智能体系统的均方一致性问题[8][9]。

2 聚类分析方法及模型

2.1 几种聚类分析方法

聚类就是将多智能体分类的过程，不同类别中的智能体相异度根据描述对象的属性参数来计算，一般利用属性的权重进行度量。通过从多智能体属性参数中寻找相似性，并依此对数据进行分类，使得同一类个体之间的相异度尽可能小，不同类的个体间的相异度尽可能的大，从而实现对多智能体中隐含的有用信息或知识进行分析。现实当中多智能体类型多种多样，每种类型的维数、聚类的目的、方式都各不相同，因此不存在一种可以应用于所有多智能体聚类需要的聚类算法。根据对目前理论研究中较为成熟的聚类算法的分析，主要可以划分为如下几类[10]：

（1）基于层次的方法

基于层次的聚类算法是将数据对象看成一棵聚类树，采用自底向上不断凝聚或是自顶向下不断分裂而得出聚类结果。由于该算法过程属于演进形式，在对类进行合并或者分裂之后，下一步的处理将在新的类树上进行，因而每一次得出的聚类结果都非常重要，因为它是下一步聚类的基础，如果某一步没有做出很好的合并或者分裂，很可能导致最终的聚类结果质量比较低[11]。

（2）基于划分的方法

划分类算法的划分原则是每个组至少包括一个数据对象，并且每个数据对象必须属于且只属于一个组，为了达到全局最优，基于划分的聚类算法会要求穷举所有尽可能的划分。属于此类方法的有k-means算法[12]。

（3）基于密度的算法

这类方法是从数据分布密度的角度来进行聚类的，即将数据对象空间划分为数个数据密度不同的子空间，只要子空间邻近区域的数据对象密度超过某个事先设定好的阈值就继续聚类。

（4）基于网格的方法

该方法将数据对象空间变换为一个网格状的空间，变换后的空间基本结构为多个单元格。数据对象空间在经过网格化后，所有的聚类操作都将在单元格上进行。该方法的突出优点是聚类速度较快，因为它进行聚类时所花费的时间仅取决于变换后的空间中每一维上的单元格数目而不是原数据对象空间中数据对象的数目[13]。

（5）基于模型的方法

基于模型的聚类方法试图对给定的数据和某些数学模型之间的适应性进行优化，数据是基于潜在的概率分布而生成的。

2.2 聚类分析模型

多属性决策是多目标方案决策的一种，又称有限方案多目标决策，它是对具有多个属性的有限方案按照某种决定准则进行多方案选择和排序。其求解方法和属性权重有密切的关系，因为它的合理性直接影响着多属性决策排序的准确性，所以在多属性决策中，权重问题的研究占有重要的地位[14]。

假设待聚类的数据集合包含n个数据对象，通用的数据表示方法是矢量表示法，即通过一个多维空间中的矢量，来描述一个对象多方面的特征。矢量的每个维度描述对象的一个特征，多个对象的矢量构成一个模式矩阵，矩阵中的每一行描述一个对象，每一列描述一个特征[15]。在此基础上，聚类问题可简单描述为：给定m维空间的n个向量，把每个向量归属到K个聚类中的某一个，使得每个向量与其聚类中心的距离最小，其数学模型具体描述如下：

已知模式样本集{X}有n个样本和K个模式分类{Sj，j=1，2，…，K}，每个样本有m个特征指标，由此得到一个样本矩阵X如下：

矩阵X中，每一行为一个样本，如矩阵X的第i行表示第i个样本Xi，其中xij（i=1，2，…，m）为第i个样本的第j个指标的观测值。以每个模式样本到各自聚类中心的距离之和达到最小为标准，定义目标函数为：

满足：

其中K为聚类数目，表示j类样本{Sj}的均值向量，wij的设置规则为：

确定wij之后，就可以计算每个类别的聚类中心计算如下：

在聚类中心确定的情况下，为了区分不同类别的多智能体，智能体的各个不同的特征属性对聚类结果的贡献程度是不同的。在多属性智能体之间的距离计算中，不同的属性很显然对数据对象的内在性质有不同的贡献，因此这需要算法在计算的时候体现出来，即可以通过对不同的属性变量赋予不同权重的方式来解决，对每个变量根据其重要程度赋一个权重：

ωk是属性的权重，dij是智能体之间的欧氏距离。在算法对数据对象进行聚类分析时，数据对象属性的个数的增加会使算法的计算量加大，影响效率。因此在进行聚类时合理地运用加权欧氏距离，根据每个属性对聚类结果贡献的不同，给每个属性赋一个权值，这样既可以充分利用数据的分布特征，从而加快某些聚类算法的速度，同时又可以更准确地反映数据对象的内在性质，进而提高聚类结果的准确性，对改进聚类结果能起到较好的效果[16]。

3 多智能体任务协同一致性模型

如前所述，多智能体系统中通过优化控制策略并调整自身行为，以适应环境和任务的动态变化的特性叫做多智能体系统的协同适应性。为了便于描述智能体的协同，提出信息协同一致性模型，即当智能体系统中节点数目为有限多个，若其中任意互为邻居节点的两个智能体信息达成一致，则我们说智能体系统达到一致。因此，可以通过任意节点和与其有直接通信关系的所有邻居节点相互作用，达到节点之间信息一致，进而实现智能体系统的协同信息一致性[17]。多智能体网络拓扑结构可以由无向图G={V，ε}刻画（后简称图），其中有限顶点集V={v1，v2，…，vn}代表n个智能体，边集ε⊆V×V描述智能体之间的通信链路。如果vivj∈ε，则vi和vj是通信连接的，即vj是vi的邻居节点。若节点i和节点j相邻，则用（i，j）表示从节点i到节点j的边。若在图G中，任意i，j∈v可以推出（i，j）∈ε⇔（j，i）∈ε，则图G为无向图。对于无向图，节点间通信链路是对称存在的，即如果vivj∈ε，则vjvi∈ε，智能体vi的邻居节点集描述为Ni={vj|vivj∈ε，j≠i}。一个长度为l的路径是指起始于vio终止于vil的l+1个智能体{vio，vil}之间存在的通信链路。如果图G中任意两个智能体之间存在路径，则图G是连通图。每个智能体的动力学方程描述为：

其中：xi（t）∈R和ui（t）∈R分别表示第i个智能体的状态和输入，n为智能体数目。考虑包含N个个体的多智能体系统，第i个个体的动态方程为：

初始条件为：[xi（t），vi（t）]=（φi，ψi），-τ≤t＜0

其中：xi（t），vi（t）分别表示第i个个体在t时刻的位置和速度；t≥0为系统中正在通信的两个个体之间的通信时滞；k是耦合系数；xi，ψi都是连续的向量函数。多智能体一致性模型可以描述为：

式（11）所产生的一致性收敛点取决于多智能体初始信息状态，是一个动态变化的值。为了优化一致性算法的收敛性能，引入了一个虚基准的概念[10]。在引入虚基准后，智能体编队中的节点不仅要与邻居节点实现一致，也要与虚拟基准实现一致。则式（11）应改写为：

式中：〈xR〉i为节点i的虚拟基准，当系统不存在指定基准，虚拟基准由邻居节点的平均作用获得；若系统存在外部指定基准时，虚拟基准取值为外部基准值。由以上分析可知，式（10）和式（11）给出的信息一致性算法，只需要相邻节点之间的相互作用，即任意一个节点的信息状态依赖于其邻居节点的信息状态。

4 多智能体任务协同聚类分析中事件驱动机制的设计

针对多智能体协同的任务工作，考虑到智能体内的分工机制，现实状况下很多场景是智能体分组后再分别就各组内进行一致性协同的情形。所以需要同时考虑聚类和一致性两种方法的结合。对于特定的多智能体系统，由于聚类算法和一致性协同在先后使用的过程中存在耗时较长的问题，因此我们使用事件驱动的聚类方法进行优化。

在事件驱动机制设计中，把智能体在聚类过程中得到的观测误差作为重要的评判标准，当它超过一个预设的阈值时事件被触发，首先根据智能体的各个属性的重要程度而赋予不同的权重，对于聚类贡献较大的特征属性赋予较大的权重。事件触发的关键在于对触发函数的设计。智能体系统在进行聚类时利用加权距离来确定节点之间的关联程度，采用联合观测来判定智能体之间的耦合情况。触发函数的设计核心在于确定当智能体聚类进行迭代时不足以分离出指定个数的智能体的归属时，函数得到触发，将利用触发函数计算出归并类的近似最优解，将联合观测值最优解方差最低的情形中，加权距离最小的若干智能体归为一类，从而加快迭代速度。考虑一个由N个智能体构成的连续时间的多智能体系统，在激活触发函数的聚类方法后，通过计算分类中的智能体的虚拟基准，提升协同效率，达到分类一致性。

定义加权向量ωk（k=1，2，…，m），计算样本Xi到Xj之间的加权欧氏距离为：

假设在时刻t智能体系统获得当前的联合观测O（t）={O1（t），O2（t），…，On（t）}。此时，智能体系统从t-1时刻到t时刻的联合观测变化率定义为：

式中：ei（t）=|Oi（t）-Oi（t-1）|/Oi（t-1）。

利用方差计算两个时刻的误差偏移程度，令联合观测变化率期望为方差为：

H（t）表示该智能体系统中所有智能体与智能体中心联合观测下的欧氏加权距离差分值。可以定义智能体系统的事件驱动函数为：

根据智能体分布情况取值，驱动函数的触发与驱动函数的计算值有直接关系，设定触发常数值为θ，表示每次聚类分离导致的分离数因子。d0为常数，表示加权距离最小下的取值。Ti（t）＜0时，说明智能体聚类分离的效果未达到，此时触发函数被触发。参数θ的数值越大，事件驱动函数的触发次数越多，为了避免无效触发，θ的取值与d0有正相关性。在方差D（t）最小的情况下可得出当前的各智能体的状态值{x0，x1，…，xn}，以此可以计算出加权距离dij≤d0中的若干智能体，将此时得到的智能体归并到同一类中。

设定ε0为基于θ下的基准误差值，ε0=，通过多智能体xj的聚类中心计算公式计算第j聚类的偏离误差是第j个聚类中的第i个分量值。误差值计算若ε≤ε0成立，则停止聚类过程。

5 实验结果及分析

为了验证基于事件驱动的聚类算法效果，我们选取一个规模为N的多智能体系统。实验的数据集是采用随机生成的人工模拟多智能体数据集合和参考UCI的多智能体数据集两大类。数据集中每个节点被一个向量描述。测试算法的收敛性中没有对紧密性和均匀性的约束，每个节点所考虑的唯一问题就是如何最大化它们的效用。在实验中考察了本文方法中相关参数对聚类性能的影响，最终确定了合适的相关参数，然后在数据集上进行实验，将本文所述的实验方法与传统的层次聚类算法和K-means算法作比较。

首先对实验数据进行标准化和归一化处理。选取的多智能体数据集D1为人工构造的二维数据样本集，D1包含三种类型的数据集，含有150个数据。在选取的参考UCI的多智能体数据集中，设定Motor数据集、Evaluation数据集的数据特征如表1所示。

表1 模拟智能体样本数据

基于以上的数据集，利用加权距离确定多智能体的聚类中心。在基于以上智能体样本数环境下，根据实验条件和效果，综合设定事件触发参数θ=1.2，d0=0.8。利用是否加入触发判断的条件，多智能体系统中，聚类测量值H（t）的变化曲线如图1所示。从图中可以看出在加入事件驱动函数后，多智能体的聚类收敛更快。

图1 算法聚类收敛曲线

表2列出了多智能体事件触发次数及一致性控制变更次数，显然各智能体事件触发次数远低于采样次数。因为各智能体一致性控制协议同时利用自身及旁边智能体的触发信息，在自适应事件触发控制下，事件触发的时间间隔缩短，事件更易被触发。

表2 智能体聚类一致性触发变更次数

如表3所示，从多智能体一致性协同的角度，验证了在D1、Evaluation和Motor数据集智能体模型中聚类收敛的平均时长和数据一致性错误率，这里的错误率指聚类后的向量一致性误差。

通过表3，可以看到改进后的方法相比较原算法在聚类的时长和误差上都有明显的提升。主要原因是对聚类过程在加权的基础上进行了触发函数操作，有效提升了效率。图2是在模拟的N个智能体系统三次聚类操作的情况，将多智能体的虚拟基准值做了区分调整，横坐标是时间，纵坐标是各智能体与智能体聚类中心的虚拟基准值，可以看到，利用本文提供方法所有智能体趋于一致基准值的速度明显要加快。

图2 多智能体聚类一致性效果

6 结语

本文提出了一种基于事件驱动的多智能体聚类方法，侧重基于分类多智能体情况下，提升协同一致性任务完成效率的研究。多智能体系统在与环境的交互中，可以根据观测的变化来触发优化聚类过程。采用事件驱动可以提升聚类效率，有效减少计算资源消耗，提高了系统的控制性能，对不同类别的智能群体优化其每个分类下的智能体一致性，从而达到多一致性的操作效果。最后，对方法进行了论证，结果表明事件驱动可以在聚类过程中减少一定的通信次数，缓解通信和计算资源消耗，并利用基准值的调整加快了一致性的协同。进一步的工作主要是基于现有的研究，将事件驱动的思想应用于不同类的多智能体系统中，并结合事件驱动的特点设计更合理的触发函数。