基于事件觸發的聚類分析方法在多智能體任務協同中的研究

田承東，楊璧竹

（中國電子科技集團公司信息科學研究院北京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 結語

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