基于事件觸發(fā)的聚類分析方法在多智能體任務(wù)協(xié)同中的研究

田承東，楊璧竹

（中國電子科技集團公司信息科學(xué)研究院北京100098）

0 引言

隨著物聯(lián)網(wǎng)技術(shù)的發(fā)展，多智能體系統(tǒng)協(xié)同完成指定任務(wù)，已經(jīng)成為人工智能物聯(lián)網(wǎng)（AIOT）領(lǐng)域的研究熱點。為確保完成特定任務(wù)，不同智能體間恰當(dāng)?shù)膮f(xié)同與合作至關(guān)重要，如果說模擬人的行為是單智能體的目標(biāo)，那么模擬人類社會的協(xié)同行為則是多智能體系統(tǒng)的最終目標(biāo)[1]。多智能體研究的核心在于如何使智能體協(xié)調(diào)行動解決問題，即使個體之間通過相互影響、相互作用形成強大的群體智慧來解決復(fù)雜的問題。由智能體組成的多節(jié)點網(wǎng)絡(luò)動態(tài)控制比較復(fù)雜，因此，如何分析這些復(fù)雜網(wǎng)絡(luò)行為和設(shè)計控制算法成為研究的熱點。同時，在實際系統(tǒng)中控制對象是運動的，要完成運動目標(biāo)的跟蹤及控制，需要根據(jù)被跟蹤者的信息隨時調(diào)整策略并且相互配合完成任務(wù)[2][3]。

聚類分析已經(jīng)被廣泛應(yīng)用在許多智能體協(xié)同場景中，作為多智能體協(xié)同的預(yù)處理步驟，可以簡化計算量，提高協(xié)同效率。隨著聚類算法在工程實踐中應(yīng)用的深入和系統(tǒng)復(fù)雜性的增加，待處理的數(shù)據(jù)量也越來越大，針對多智能體系統(tǒng)中動態(tài)區(qū)分的不同類別個體，需要提升聚類區(qū)分效率以及不同聚類下智能體的一致性，從而達(dá)到整個智能體中的有效協(xié)同[3]。本文提出了一種基于事件驅(qū)動的改進(jìn)型聚類算法，使智能體在與環(huán)境的交互中，可以根據(jù)觀測的變化來觸發(fā)通信和學(xué)習(xí)過程。在相同時間內(nèi)，采用事件驅(qū)動可以降低數(shù)據(jù)傳輸次數(shù)，節(jié)約通信資源，提升聚類效率。最后，對算法進(jìn)行了驗證，結(jié)果表明事件驅(qū)動可以有效提升聚類算法的效率，促進(jìn)多智能體分類基礎(chǔ)上完成任務(wù)的一致性[4][5]。

1 多智能體協(xié)同中的一致性問題

在多智能體協(xié)同控制中，存在幾個作為研究熱點的重要問題：多智能體系統(tǒng)模型、多智能體一致性、多智能體任務(wù)分配、多智能體沖突識別與消解、多智能體系統(tǒng)安全。多智能體的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)隨著智能體的運動，處于不斷變化當(dāng)中，多智能體系統(tǒng)中的一個基本問題就是一致性問題。一致性問題來源于多智能體系統(tǒng)的協(xié)調(diào)合作控制問題。一致性協(xié)議是智能體之間相互作用、傳遞信息的規(guī)則，針對任務(wù)的需求，智能體之間對某個或某幾個與任務(wù)相關(guān)的量值達(dá)到近似或相同的狀態(tài)，它描述了每個智能體和與其相鄰的智能體的信息交換過程。聚類同步就是首先給多智能體系統(tǒng)分類，然后在每個類中都實現(xiàn)一致性，即多一致性問題[6]。具體包括：

（1）有領(lǐng)導(dǎo)者的多智能體系統(tǒng)的一致性問題

在多智能體系統(tǒng)中，有個別智能體代表著整個多智能體系統(tǒng)的共同利益或者是其他智能體跟蹤的目標(biāo)，把這些智能體稱作是領(lǐng)導(dǎo)者，把其他的智能體稱作是跟隨者。帶有領(lǐng)導(dǎo)者的多智能體系統(tǒng)的一致性問題，也稱作是一致性跟蹤問題，就是通過合適的算法，使得領(lǐng)導(dǎo)者和跟隨者的最終狀態(tài)達(dá)到一致[7]。

（2）無領(lǐng)導(dǎo)者的多智能體系統(tǒng)一致性問題

在多智能體系統(tǒng)中，如果各智能體的地位和作用是平等的，稱這樣的系統(tǒng)是無領(lǐng)導(dǎo)者的多智能體系統(tǒng)。無領(lǐng)導(dǎo)者的系統(tǒng)也可以把其中一個智能體看作是虛擬的領(lǐng)導(dǎo)者，轉(zhuǎn)化成有領(lǐng)導(dǎo)者的一致性問題。無領(lǐng)導(dǎo)者系統(tǒng)中需要根據(jù)系統(tǒng)狀態(tài)來動態(tài)改變虛擬領(lǐng)導(dǎo)者的選擇，以達(dá)到解的最優(yōu)。

（3）隨機一致性問題

由于外部環(huán)境下隨機噪聲及外部系統(tǒng)的干擾，導(dǎo)致智能體之間的通信連接是隨機變化的。這時智能體之間的協(xié)同問題就是隨機一致性問題。當(dāng)智能體當(dāng)前時刻的狀態(tài)只依賴于前一時刻的狀態(tài)，則智能體系統(tǒng)的協(xié)同變化可以用馬爾可夫過程來處理。當(dāng)智能體之間各個狀態(tài)差值平方的期望趨于0時，稱作是多智能體系統(tǒng)的均方一致性問題[8][9]。

2 聚類分析方法及模型

2.1 幾種聚類分析方法

聚類就是將多智能體分類的過程，不同類別中的智能體相異度根據(jù)描述對象的屬性參數(shù)來計算，一般利用屬性的權(quán)重進(jìn)行度量。通過從多智能體屬性參數(shù)中尋找相似性，并依此對數(shù)據(jù)進(jìn)行分類，使得同一類個體之間的相異度盡可能小，不同類的個體間的相異度盡可能的大，從而實現(xiàn)對多智能體中隱含的有用信息或知識進(jìn)行分析?，F(xiàn)實當(dāng)中多智能體類型多種多樣，每種類型的維數(shù)、聚類的目的、方式都各不相同，因此不存在一種可以應(yīng)用于所有多智能體聚類需要的聚類算法。根據(jù)對目前理論研究中較為成熟的聚類算法的分析，主要可以劃分為如下幾類[10]：

（1）基于層次的方法

基于層次的聚類算法是將數(shù)據(jù)對象看成一棵聚類樹，采用自底向上不斷凝聚或是自頂向下不斷分裂而得出聚類結(jié)果。由于該算法過程屬于演進(jìn)形式，在對類進(jìn)行合并或者分裂之后，下一步的處理將在新的類樹上進(jìn)行，因而每一次得出的聚類結(jié)果都非常重要，因為它是下一步聚類的基礎(chǔ)，如果某一步?jīng)]有做出很好的合并或者分裂，很可能導(dǎo)致最終的聚類結(jié)果質(zhì)量比較低[11]。

（2）基于劃分的方法

劃分類算法的劃分原則是每個組至少包括一個數(shù)據(jù)對象，并且每個數(shù)據(jù)對象必須屬于且只屬于一個組，為了達(dá)到全局最優(yōu)，基于劃分的聚類算法會要求窮舉所有盡可能的劃分。屬于此類方法的有k-means算法[12]。

（3）基于密度的算法

這類方法是從數(shù)據(jù)分布密度的角度來進(jìn)行聚類的，即將數(shù)據(jù)對象空間劃分為數(shù)個數(shù)據(jù)密度不同的子空間，只要子空間鄰近區(qū)域的數(shù)據(jù)對象密度超過某個事先設(shè)定好的閾值就繼續(xù)聚類。

（4）基于網(wǎng)格的方法

該方法將數(shù)據(jù)對象空間變換為一個網(wǎng)格狀的空間，變換后的空間基本結(jié)構(gòu)為多個單元格。數(shù)據(jù)對象空間在經(jīng)過網(wǎng)格化后，所有的聚類操作都將在單元格上進(jìn)行。該方法的突出優(yōu)點是聚類速度較快，因為它進(jìn)行聚類時所花費的時間僅取決于變換后的空間中每一維上的單元格數(shù)目而不是原數(shù)據(jù)對象空間中數(shù)據(jù)對象的數(shù)目[13]。

（5）基于模型的方法

基于模型的聚類方法試圖對給定的數(shù)據(jù)和某些數(shù)學(xué)模型之間的適應(yīng)性進(jìn)行優(yōu)化，數(shù)據(jù)是基于潛在的概率分布而生成的。

2.2 聚類分析模型

多屬性決策是多目標(biāo)方案決策的一種，又稱有限方案多目標(biāo)決策，它是對具有多個屬性的有限方案按照某種決定準(zhǔn)則進(jìn)行多方案選擇和排序。其求解方法和屬性權(quán)重有密切的關(guān)系，因為它的合理性直接影響著多屬性決策排序的準(zhǔn)確性，所以在多屬性決策中，權(quán)重問題的研究占有重要的地位[14]。

假設(shè)待聚類的數(shù)據(jù)集合包含n個數(shù)據(jù)對象，通用的數(shù)據(jù)表示方法是矢量表示法，即通過一個多維空間中的矢量，來描述一個對象多方面的特征。矢量的每個維度描述對象的一個特征，多個對象的矢量構(gòu)成一個模式矩陣，矩陣中的每一行描述一個對象，每一列描述一個特征[15]。在此基礎(chǔ)上，聚類問題可簡單描述為：給定m維空間的n個向量，把每個向量歸屬到K個聚類中的某一個，使得每個向量與其聚類中心的距離最小，其數(shù)學(xué)模型具體描述如下：

已知模式樣本集{X}有n個樣本和K個模式分類{Sj，j=1，2，…，K}，每個樣本有m個特征指標(biāo)，由此得到一個樣本矩陣X如下：

矩陣X中，每一行為一個樣本，如矩陣X的第i行表示第i個樣本Xi，其中xij（i=1，2，…，m）為第i個樣本的第j個指標(biāo)的觀測值。以每個模式樣本到各自聚類中心的距離之和達(dá)到最小為標(biāo)準(zhǔn)，定義目標(biāo)函數(shù)為：

滿足：

其中K為聚類數(shù)目，表示j類樣本{Sj}的均值向量，wij的設(shè)置規(guī)則為：

確定wij之后，就可以計算每個類別的聚類中心計算如下：

在聚類中心確定的情況下，為了區(qū)分不同類別的多智能體，智能體的各個不同的特征屬性對聚類結(jié)果的貢獻(xiàn)程度是不同的。在多屬性智能體之間的距離計算中，不同的屬性很顯然對數(shù)據(jù)對象的內(nèi)在性質(zhì)有不同的貢獻(xiàn)，因此這需要算法在計算的時候體現(xiàn)出來，即可以通過對不同的屬性變量賦予不同權(quán)重的方式來解決，對每個變量根據(jù)其重要程度賦一個權(quán)重：

ωk是屬性的權(quán)重，dij是智能體之間的歐氏距離。在算法對數(shù)據(jù)對象進(jìn)行聚類分析時，數(shù)據(jù)對象屬性的個數(shù)的增加會使算法的計算量加大，影響效率。因此在進(jìn)行聚類時合理地運用加權(quán)歐氏距離，根據(jù)每個屬性對聚類結(jié)果貢獻(xiàn)的不同，給每個屬性賦一個權(quán)值，這樣既可以充分利用數(shù)據(jù)的分布特征，從而加快某些聚類算法的速度，同時又可以更準(zhǔn)確地反映數(shù)據(jù)對象的內(nèi)在性質(zhì)，進(jìn)而提高聚類結(jié)果的準(zhǔn)確性，對改進(jìn)聚類結(jié)果能起到較好的效果[16]。

3 多智能體任務(wù)協(xié)同一致性模型

如前所述，多智能體系統(tǒng)中通過優(yōu)化控制策略并調(diào)整自身行為，以適應(yīng)環(huán)境和任務(wù)的動態(tài)變化的特性叫做多智能體系統(tǒng)的協(xié)同適應(yīng)性。為了便于描述智能體的協(xié)同，提出信息協(xié)同一致性模型，即當(dāng)智能體系統(tǒng)中節(jié)點數(shù)目為有限多個，若其中任意互為鄰居節(jié)點的兩個智能體信息達(dá)成一致，則我們說智能體系統(tǒng)達(dá)到一致。因此，可以通過任意節(jié)點和與其有直接通信關(guān)系的所有鄰居節(jié)點相互作用，達(dá)到節(jié)點之間信息一致，進(jìn)而實現(xiàn)智能體系統(tǒng)的協(xié)同信息一致性[17]。多智能體網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可以由無向圖G={V，ε}刻畫（后簡稱圖），其中有限頂點集V={v1，v2，…，vn}代表n個智能體，邊集ε?V×V描述智能體之間的通信鏈路。如果vivj∈ε，則vi和vj是通信連接的，即vj是vi的鄰居節(jié)點。若節(jié)點i和節(jié)點j相鄰，則用（i，j）表示從節(jié)點i到節(jié)點j的邊。若在圖G中，任意i，j∈v可以推出（i，j）∈ε?（j，i）∈ε，則圖G為無向圖。對于無向圖，節(jié)點間通信鏈路是對稱存在的，即如果vivj∈ε，則vjvi∈ε，智能體vi的鄰居節(jié)點集描述為Ni={vj|vivj∈ε，j≠i}。一個長度為l的路徑是指起始于vio終止于vil的l+1個智能體{vio，vil}之間存在的通信鏈路。如果圖G中任意兩個智能體之間存在路徑，則圖G是連通圖。每個智能體的動力學(xué)方程描述為：

其中：xi（t）∈R和ui（t）∈R分別表示第i個智能體的狀態(tài)和輸入，n為智能體數(shù)目?？紤]包含N個個體的多智能體系統(tǒng)，第i個個體的動態(tài)方程為：

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

其中：xi（t），vi（t）分別表示第i個個體在t時刻的位置和速度；t≥0為系統(tǒng)中正在通信的兩個個體之間的通信時滯；k是耦合系數(shù)；xi，ψi都是連續(xù)的向量函數(shù)。多智能體一致性模型可以描述為：

式（11）所產(chǎn)生的一致性收斂點取決于多智能體初始信息狀態(tài)，是一個動態(tài)變化的值。為了優(yōu)化一致性算法的收斂性能，引入了一個虛基準(zhǔn)的概念[10]。在引入虛基準(zhǔn)后，智能體編隊中的節(jié)點不僅要與鄰居節(jié)點實現(xiàn)一致，也要與虛擬基準(zhǔn)實現(xiàn)一致。則式（11）應(yīng)改寫為：

式中：〈xR〉i為節(jié)點i的虛擬基準(zhǔn)，當(dāng)系統(tǒng)不存在指定基準(zhǔn)，虛擬基準(zhǔn)由鄰居節(jié)點的平均作用獲得；若系統(tǒng)存在外部指定基準(zhǔn)時，虛擬基準(zhǔn)取值為外部基準(zhǔn)值。由以上分析可知，式（10）和式（11）給出的信息一致性算法，只需要相鄰節(jié)點之間的相互作用，即任意一個節(jié)點的信息狀態(tài)依賴于其鄰居節(jié)點的信息狀態(tài)。

4 多智能體任務(wù)協(xié)同聚類分析中事件驅(qū)動機制的設(shè)計

針對多智能體協(xié)同的任務(wù)工作，考慮到智能體內(nèi)的分工機制，現(xiàn)實狀況下很多場景是智能體分組后再分別就各組內(nèi)進(jìn)行一致性協(xié)同的情形。所以需要同時考慮聚類和一致性兩種方法的結(jié)合。對于特定的多智能體系統(tǒng)，由于聚類算法和一致性協(xié)同在先后使用的過程中存在耗時較長的問題，因此我們使用事件驅(qū)動的聚類方法進(jìn)行優(yōu)化。

在事件驅(qū)動機制設(shè)計中，把智能體在聚類過程中得到的觀測誤差作為重要的評判標(biāo)準(zhǔn)，當(dāng)它超過一個預(yù)設(shè)的閾值時事件被觸發(fā)，首先根據(jù)智能體的各個屬性的重要程度而賦予不同的權(quán)重，對于聚類貢獻(xiàn)較大的特征屬性賦予較大的權(quán)重。事件觸發(fā)的關(guān)鍵在于對觸發(fā)函數(shù)的設(shè)計。智能體系統(tǒng)在進(jìn)行聚類時利用加權(quán)距離來確定節(jié)點之間的關(guān)聯(lián)程度，采用聯(lián)合觀測來判定智能體之間的耦合情況。觸發(fā)函數(shù)的設(shè)計核心在于確定當(dāng)智能體聚類進(jìn)行迭代時不足以分離出指定個數(shù)的智能體的歸屬時，函數(shù)得到觸發(fā)，將利用觸發(fā)函數(shù)計算出歸并類的近似最優(yōu)解，將聯(lián)合觀測值最優(yōu)解方差最低的情形中，加權(quán)距離最小的若干智能體歸為一類，從而加快迭代速度?？紤]一個由N個智能體構(gòu)成的連續(xù)時間的多智能體系統(tǒng)，在激活觸發(fā)函數(shù)的聚類方法后，通過計算分類中的智能體的虛擬基準(zhǔn)，提升協(xié)同效率，達(dá)到分類一致性。

定義加權(quán)向量ωk（k=1，2，…，m），計算樣本Xi到Xj之間的加權(quán)歐氏距離為：

假設(shè)在時刻t智能體系統(tǒng)獲得當(dāng)前的聯(lián)合觀測O（t）={O1（t），O2（t），…，On（t）}。此時，智能體系統(tǒng)從t-1時刻到t時刻的聯(lián)合觀測變化率定義為：

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

利用方差計算兩個時刻的誤差偏移程度，令聯(lián)合觀測變化率期望為方差為：

H（t）表示該智能體系統(tǒng)中所有智能體與智能體中心聯(lián)合觀測下的歐氏加權(quán)距離差分值。可以定義智能體系統(tǒng)的事件驅(qū)動函數(shù)為：

根據(jù)智能體分布情況取值，驅(qū)動函數(shù)的觸發(fā)與驅(qū)動函數(shù)的計算值有直接關(guān)系，設(shè)定觸發(fā)常數(shù)值為θ，表示每次聚類分離導(dǎo)致的分離數(shù)因子。d0為常數(shù)，表示加權(quán)距離最小下的取值。Ti（t）＜0時，說明智能體聚類分離的效果未達(dá)到，此時觸發(fā)函數(shù)被觸發(fā)。參數(shù)θ的數(shù)值越大，事件驅(qū)動函數(shù)的觸發(fā)次數(shù)越多，為了避免無效觸發(fā)，θ的取值與d0有正相關(guān)性。在方差D（t）最小的情況下可得出當(dāng)前的各智能體的狀態(tài)值{x0，x1，…，xn}，以此可以計算出加權(quán)距離dij≤d0中的若干智能體，將此時得到的智能體歸并到同一類中。

設(shè)定ε0為基于θ下的基準(zhǔn)誤差值，ε0=，通過多智能體xj的聚類中心計算公式計算第j聚類的偏離誤差是第j個聚類中的第i個分量值。誤差值計算若ε≤ε0成立，則停止聚類過程。

5 實驗結(jié)果及分析

為了驗證基于事件驅(qū)動的聚類算法效果，我們選取一個規(guī)模為N的多智能體系統(tǒng)。實驗的數(shù)據(jù)集是采用隨機生成的人工模擬多智能體數(shù)據(jù)集合和參考UCI的多智能體數(shù)據(jù)集兩大類。數(shù)據(jù)集中每個節(jié)點被一個向量描述。測試算法的收斂性中沒有對緊密性和均勻性的約束，每個節(jié)點所考慮的唯一問題就是如何最大化它們的效用。在實驗中考察了本文方法中相關(guān)參數(shù)對聚類性能的影響，最終確定了合適的相關(guān)參數(shù)，然后在數(shù)據(jù)集上進(jìn)行實驗，將本文所述的實驗方法與傳統(tǒng)的層次聚類算法和K-means算法作比較。

首先對實驗數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化和歸一化處理。選取的多智能體數(shù)據(jù)集D1為人工構(gòu)造的二維數(shù)據(jù)樣本集，D1包含三種類型的數(shù)據(jù)集，含有150個數(shù)據(jù)。在選取的參考UCI的多智能體數(shù)據(jù)集中，設(shè)定Motor數(shù)據(jù)集、Evaluation數(shù)據(jù)集的數(shù)據(jù)特征如表1所示。

表1 模擬智能體樣本數(shù)據(jù)

基于以上的數(shù)據(jù)集，利用加權(quán)距離確定多智能體的聚類中心。在基于以上智能體樣本數(shù)環(huán)境下，根據(jù)實驗條件和效果，綜合設(shè)定事件觸發(fā)參數(shù)θ=1.2，d0=0.8。利用是否加入觸發(fā)判斷的條件，多智能體系統(tǒng)中，聚類測量值H（t）的變化曲線如圖1所示。從圖中可以看出在加入事件驅(qū)動函數(shù)后，多智能體的聚類收斂更快。

圖1 算法聚類收斂曲線

表2列出了多智能體事件觸發(fā)次數(shù)及一致性控制變更次數(shù)，顯然各智能體事件觸發(fā)次數(shù)遠(yuǎn)低于采樣次數(shù)。因為各智能體一致性控制協(xié)議同時利用自身及旁邊智能體的觸發(fā)信息，在自適應(yīng)事件觸發(fā)控制下，事件觸發(fā)的時間間隔縮短，事件更易被觸發(fā)。

表2 智能體聚類一致性觸發(fā)變更次數(shù)

如表3所示，從多智能體一致性協(xié)同的角度，驗證了在D1、Evaluation和Motor數(shù)據(jù)集智能體模型中聚類收斂的平均時長和數(shù)據(jù)一致性錯誤率，這里的錯誤率指聚類后的向量一致性誤差。

通過表3，可以看到改進(jìn)后的方法相比較原算法在聚類的時長和誤差上都有明顯的提升。主要原因是對聚類過程在加權(quán)的基礎(chǔ)上進(jìn)行了觸發(fā)函數(shù)操作，有效提升了效率。圖2是在模擬的N個智能體系統(tǒng)三次聚類操作的情況，將多智能體的虛擬基準(zhǔn)值做了區(qū)分調(diào)整，橫坐標(biāo)是時間，縱坐標(biāo)是各智能體與智能體聚類中心的虛擬基準(zhǔn)值，可以看到，利用本文提供方法所有智能體趨于一致基準(zhǔn)值的速度明顯要加快。

圖2 多智能體聚類一致性效果

6 結(jié)語

本文提出了一種基于事件驅(qū)動的多智能體聚類方法，側(cè)重基于分類多智能體情況下，提升協(xié)同一致性任務(wù)完成效率的研究。多智能體系統(tǒng)在與環(huán)境的交互中，可以根據(jù)觀測的變化來觸發(fā)優(yōu)化聚類過程。采用事件驅(qū)動可以提升聚類效率，有效減少計算資源消耗，提高了系統(tǒng)的控制性能，對不同類別的智能群體優(yōu)化其每個分類下的智能體一致性，從而達(dá)到多一致性的操作效果。最后，對方法進(jìn)行了論證，結(jié)果表明事件驅(qū)動可以在聚類過程中減少一定的通信次數(shù)，緩解通信和計算資源消耗，并利用基準(zhǔn)值的調(diào)整加快了一致性的協(xié)同。進(jìn)一步的工作主要是基于現(xiàn)有的研究，將事件驅(qū)動的思想應(yīng)用于不同類的多智能體系統(tǒng)中，并結(jié)合事件驅(qū)動的特點設(shè)計更合理的觸發(fā)函數(shù)。