基于多机器人竞争行为的分布式k-WTA算法

周俊文,孔 颖,Persevearance Marecha

(浙江科技大学 信息与电子工程学院,杭州 310023)

k-WTA(k-winners-take-all,k-赢者通吃)网络是一种能从一组输入数据中选择前k个最大值的竞争型神经网络。赢者通吃(winner-take-all,WTA)网络[1]作为k-WTA网络的一种特例,在图像分类[2]、模式识别[3]、神经网络电路[4]等领域得到了广泛的应用。在智能计算领域中,这类从输入数据中取最大值的操作是极其重要的。因此,国内外研究者对k-WTA网络开展了一系列研究,如Majani等[5]首次提出并研究了WTA网络的泛化形式k-WTA网络,保证了模型的局部稳定性。Calvert等[6]提出了模拟浩斯菲尔德神经网络,并通过完整的数学分析证明了它可以有效地识别实数列表中的前k个最大分量。

为了优化模型结构,Liu等[7]首次将k-WTA问题转换为一个等价的二次规划问题。进而动态神经网络、对偶神经网络、投影神经网络等陆续被开发应用[8],同时在引入激活函数[9]、收敛速度[10]等方面进行了改进。这些模型在处理常数输入的k-WTA运算时能实现有限时间收敛,但在处理时变输入信息时存在滞后误差,需通过设置足够大的参数来改善。Peng等[11]设计了具有非硬限制激活函数的k-WTA神经网络,极大地简化了模型结构,降低了计算成本。Qi等[12]设计并研究了利用饱和允许激活函数执行k-WTA操作的k-WTA神经网络,该网络具有较强的扰动鲁棒性。Liu等[13]设计并分析了具有较高精度和较强鲁棒性的k-WTA网络,并给出了多机器人系统中执行跟踪任务的应用,验证了该网络的有效性。

近年来,机器人技术在工程领域得到了迅速的发展,受到了广泛的关注,并取得了丰硕的成果。单个机器人虽然在很多方面满足了一些行业的需求,但在一些复杂或大规模作业中经济效益不高。针对这一不足,出现了多机器人系统,其明显的优点是能够通过机器人的协同,高效、灵活地完成任务。现有的多机器人系统大多采用集中式控制方法,依赖一个控制中心,除了存在潜在的不稳定因素外,还存在计算量大、通信负荷高的问题。与集中式方法相比,分布式方法只需要邻居对邻居的通信,大幅减轻了整体通信负荷,即使某些机器人失效,分布式方法仍能正常工作。到目前为止,对k-WTA的研究大多使用集中式控制方法,即没有加入任何拓扑约束,不能被直接用于具有任意拓扑结构的多智能体网络。Li等[14]首次考虑了多智能体网络的拓扑结构,提出了一种分布式WTA模型来解决网络中的动态竞争问题。Jin等[15-16]研究了基于k-WTA的多机器人分布式竞争协同,并采用了低通一致性滤波器来估计k-WTA模型中的动态项,使得单个机器人能够仅依靠其邻居信息计算出对整个系统输出信息的均值估计。这些成果指出了研究分布式k-WTA网络的必要性,为后续基于k-WTA思路的广泛应用奠定了基础。

但据现有文献,关于分布式k-WTA模型的研究还很少。针对分布式k-WTA问题,本研究首先提出了一种使用高通一致性滤波器的分布式k-WTA模型。然后利用拉塞尔不变性原理(Lasalle’s invariance principle)[17]计算出本模型有一个不变集,在不变集中本模型退化为现有的具有全局渐进收敛性的集中式k-WTA模型,证明了本模型全局渐进收敛于k-WTA问题的解。最后通过两个算例,验证了所提出的分布式k-WTA模型的性能。

1 k-WTA问题

1.1 集中式k-WTA模型

一般而言,k-WTA问题可以被表述为下列函数:

(1)

(2)

为解决上述二次规划问题,一种单状态变量k-WTA网络模型被定义为

(3)

式(3)中:ζ为辅助变量;ε>0为设计参数;gi(·)为激活函数g(·)的第i个元素,其可被描述为

在式(3)中可以发现,无论问题规模大小,模型只有一个状态变量ζ。由于ζ总是需要输入向量x中所有元素的信息,所以k-WTA模型式(3)是集中式的。上述属性也出现在许多模型中,如简化对偶神经网络模型[7]1502,改进对偶神经网络模型[8]2023,具有阶跃激活函数的k-WTA网络模型[9]1498和单神经元的递归神经网络模型[10]1141。在下一章提出的分布式模型将基于k-WTA模型式(3),因为它是现有模型中最简单的。

1.2 分布式k-WTA问题

受限通信拓扑可被定义为一个具有s个智能体的无向连接网络G(W,E,A),其中W表示点集,E表示边集,A表示邻接矩阵。设N(i)表示第i个智能体的邻居集,那么第i个智能体只能与邻居集N(i)中的对象交换信息。在这种情况下,k-WTA问题变成了如何借助智能体与邻居的竞争来在所有智能体中找到k个赢家。本研究的目的是寻找一种能够在受限通信条件下解决k-WTA问题的分布式模型。

2 分布式k-WTA模型

2.1 模型描述

(4)

结合所有智能体的控制输入,分布式k-WTA模型式(4)可以写成如下形式:

(5)

式(5)中:e为一个s维向量,所有元素都是1;L为通信图G的拉普拉斯矩阵,满足γ2min(L)≥7.5δ,γ2min(L)为L的第二个最小特征值。

2.2 理论分析

定理1假设q(0)=0,通信受限情况下的分布式k-WTA模型式(5)的输出值全局渐进收敛于k-WTA问题式(1)的解。

证明:定义函数h(p)=[h1(p1),h2(p2),…,hs(ps)]T,其元素hi(pi)定义如下:

定义如下辅助变量:

由式(5)我们可以得到:

(6)

根据式(5)和式(6),ω2的导数如下:

(7)

式(7)中:‖·‖1为1-范数。同时得到ω1的导数如下:

(8)

式(8)中:I为一个s维单位矩阵。对于一个无向连通图,拉普拉斯矩阵满足Le=eTL=0。利用拉普拉斯矩阵的性质,我们可以得到:

(9)

所以假设q(0)=0,我们可得eTω1≡0。根据以上性质,eTω1可以做出如下变化:

eTω1=(L+χeeT)ω1=Cω1。

(10)

式(10)中:C=L+χeeT;χ≥γ2min(L)/s;矩阵C满足γmin(C)=γ2min(L)>0,其中γmin(·)表示最小的特征值。因此,式(9)可以进一步写成:

(11)

定义一个如下的李雅普诺夫函数:

V=V1+sV2+V3。

(12)

由V1、V2和V3的定义,很容易知道:

(13)

由于拉普拉斯矩阵L中的每一行元素之和都为0,所以V3=0。因此V为正定函数。计算V的时间导数,可以得到:

(14)

(15)

将式(6)与式(15)结合可得:

(16)

(17)

应用Cauchy-Schwarz不等式,可以得到:

(18)

式(18)中:|·|为绝对值。对于不等式(16),可以进一步得到:

(19)

(20)

(21)

结合式(19)～(21)可得:

(22)

(23)

在式(23)两边同时左乘(eT/s)可得:

(24)

(25)

将式(24)和式(25)写为每个智能体的子公式,可以得到:

(26)

3 仿真验证

3.1 静态输入算例

在静态输入数值算例中,我们考虑使用分布式k-WTA模型在1个由10个智能体组成的受限通信网络中寻找2个赢家,即s=8,k=2。在静态输入算例中的通信拓扑如图1所示,其中每个节点代表1个智能体,节点间的连线代表这2个智能体之间可互相通信。为便于说明,暂不考虑通信的权重,即邻接矩阵A的元素满足aij∈{0,1}。

图1 在静态输入算例中的通信拓扑Fig.1 Communication topology in static inputs example

输入向量使用设定好的固定值,试验过程中赢家不会随时间t发生变化,将输入向量设置为

x=[6.5;1.9;2.9;17.4;14.8;7.3;20.0;11.6]。

可以看出,第4、7个智能体将是赢家。相应的参数设定为λ=109,δ=0.001,μ=0.1。p的初始值是随机的,并且根据定理1将q的初始值设为0。在静态输入算例中状态向量p的曲线图见图2。在静态输入算例中状态向量q的曲线图见图3。在静态输入算例中输出向量r的曲线图见图4。可以看到所提出的分布式k-WTA模型在6×10-4s内收敛于k-WTA问题的解。最终,输出向量中的第4、第7个元素均为1,其他元素均为0,表明所提出的分布式k-WTA模型成功选出了2个赢家。

图2 在静态输入算例中状态向量p的曲线图Fig.2 Profiles of state vector p in static inputs example

图3 在静态输入算例中状态向量q的曲线图Fig.3 Profiles of state vector q in static inputs example

图4 在静态输入算例中输出向量r的曲线图Fig.4 Profiles of output vector r in static inputs example

3.2 动态输入算例

在动态输入数值算例中,我们考虑使用分布式k-WTA模型在由4个智能体组成的受限通信网络中寻找1个赢家,即s=4和k=1。在动态输入算例中的通信拓扑如图5所示,其中连线上的值代表通信权值。输入向量使用随时间变化的函数,在试验过程中赢家会随输入向量变化而改变,将其设置为

图5 在动态输入算例中的通信拓扑Fig.5 Communication topology in dynamic inputsexample

xi(t)=10cos(4π(t+0.2(i-1))),i=1,2,3,4。

在动态输入算例中输入向量x的曲线图见图6。相应的参数设定为λ=109,δ=0.01,μ=0.1。p的初始值是随机的,并且根据定理1将q的初始值设为0。在动态输入算例中状态向量p的曲线图见图7。在动态输入算例中状态向量q的曲线图见图8。从图7和图8可以看出,状态向量p和q随着动态输入向量x周期性变化,从而找到新的赢家。在动态输入算例中输出向量r的曲线图见图9,将其与图6对比可以看出,本研究提出的分布式k-WTA模型可以在任何时刻找到正确的赢家。

图6 在动态输入算例中输入向量x的曲线图Fig.6 Profiles of input vector x in dynamic inputs example

图7 在动态输入算例中状态向量p的曲线图Fig.7 Profiles of state vector p in dynamic inputs example

图8 在动态输入算例中状态向量q的曲线图Fig.8 Profiles of state vector q in dynamic inputs example

图9 在动态输入算例中输出向量r的曲线图Fig.9 Profiles of output vector r in dynamic inputs example

4 结 语

本研究提出了一种新型分布式k-WTA模型来解决通信受限的智能体网络中的k-WTA问题。根据拉塞尔不变性原理,在不变集中将所提出的模型退化为现有的集中式k-WTA模型,并证明了本模型的全局渐进收敛性。静态输入和动态输入的两个数值算例验证了本研究所提模型的有效性和性能。在未来的研究中,将本模型扩展到复数域[20]可能是一个改进方向,而多机械臂的分布式协同运动可能是一个研究应用方向。