基于多機器人競爭行為的分布式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?？梢钥吹剿岢龅姆植际絢-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]可能是一個改進方向,而多機械臂的分布式協同運動可能是一個研究應用方向。