杜宇凡

(廣東工業(yè)大學計算機學院 廣東省廣州市 510006)

近年來，多智能體系統(tǒng)協(xié)同控制方面的研究取得了突破性的進展。一致性協(xié)議是多智能體理論中的一個核心問題。設計一致性協(xié)議旨在使得智能體狀態(tài)在協(xié)議控制下最終能達到一致性。

Krause等人[1]提出了一種基于切換拓撲的離散時間一致性協(xié)議，即經(jīng)典的Hegselmann—Krause模型，各智能體取其通信范圍內(nèi)的鄰居智能體的狀態(tài)平均值作為下一次迭代狀態(tài)。在該協(xié)議下，多智能體系統(tǒng)通常不能始終保持連通，系統(tǒng)最終會演化成多個小群體，每個小群體之間的距離超過通信范圍，不再相互通信。

Zheng等人[2]提出了一種基于切換拓撲的離散時間一致性協(xié)議，各智能體取其自身狀態(tài)與通信范圍內(nèi)的鄰居智能體的組合狀態(tài)作為下一次迭代狀態(tài)。Zheng[2]等人證明了，在該協(xié)議下，如果多智能體系統(tǒng)能始終保持連通，且調(diào)整因子滿足小于時，系統(tǒng)最終能收斂到全局的狀態(tài)平均值。

Xie等人[3]提出了一種基于切換拓撲的離散時間一致性協(xié)議，各智能體取其自身狀態(tài)與通信范圍內(nèi)的最近鄰居智能體的組合狀態(tài)作為下一次迭代狀態(tài)。該方法只需考慮兩側(cè)的最近鄰居智能體的狀態(tài)信息，大大減少了計算量。Xie等人[3]證明了，在該協(xié)議下，如果多智能體系統(tǒng)能始終保持連通，且調(diào)整因子滿足小于時，系統(tǒng)最終能收斂到全局的狀態(tài)平均值。調(diào)整因子的范圍進一步擴大，這樣有助于加快系統(tǒng)的收斂速度。

然而，怎樣才能保證多智能體系統(tǒng)始終保持連通？上述一致性協(xié)議都沒有涉及到這個關鍵問題。一旦系統(tǒng)在演化過程中喪失了連通性，智能體的狀態(tài)值就不能達成一致。本文從保持連通性的角度出發(fā)，設計了一種改進的Hegselmann-Krause一致性協(xié)議，使得多智能體系統(tǒng)可以始終保持連通，并最終一定能達成一致。

本文的章節(jié)安排如下：II章節(jié)主要介紹一些閱讀本文所必需的基礎知識，包括圖論與矩陣論，離散一致性協(xié)議等等，并在末尾對本文研究的主要問題做了簡單的闡述。III章節(jié)陳述了本文的主要結(jié)果，提出了一種基于切換拓撲的離散時間一致性協(xié)議。IV章節(jié)通過仿真實驗驗證了該協(xié)議的有效性。最后，V章節(jié)給出了本文的結(jié)論和未來的研究展望。

1 預備知識及問題描述

1.1 圖論與矩陣論

我們把一個具有n個智能體的多智能體系統(tǒng)描述為一個具有n個頂點的無向圖其中V是圖G的頂點集，滿足是頂點的順序標號。E是圖G的邊集，滿足圖G的一條邊表示一對頂點i和j互為鄰居，鄰居之間可以彼此接收到對方發(fā)送出的信息。頂點i的鄰居集可表示為是圖G的鄰接矩陣，其元素與邊相關：。

引理 圖G的拉普拉斯矩陣L具有以下性質(zhì)：

（1）0是矩陣L的一個特征值，1是其對應的特征向量，滿足L1=0；

（2）如果圖G是連通無向圖，那么0是矩陣L的單一特征值；

（3）如果圖G是連通無向圖，那么矩陣L是對稱正半定矩陣且有n個非負實數(shù)特征值，可按升序排列為其中被稱為圖G的代數(shù)連通度。

1.2 離散一致性協(xié)議

考慮一個具有n個智能體的多智能體系統(tǒng)，這些智能體的狀態(tài)值處于一個實數(shù)集R。我們用G={V,E,A}表示智能體所對應的圖結(jié)構(gòu)，每個智能體的狀態(tài)值用xi(k)表示，其中k為迭代次數(shù)。

Krause等人[1]提出了一種基于切換拓撲的離散時間一致性協(xié)議：

即智能體i下一次的狀態(tài)為所有鄰居智能體（包括自身）的狀態(tài)平均值。系統(tǒng)不能達成一致性，會演化成多個觀點值。

Zheng等人[2]提出了一種基于切換拓撲的離散時間一致性協(xié)議：

即智能體i下一次的狀態(tài)為其自身狀態(tài)與通信范圍內(nèi)的鄰居智能體的組合狀態(tài)。Zheng[2]等人通過李雅普諾夫函數(shù)理論證明了在該協(xié)議下，若多智能體系統(tǒng)能始終保持連通，且調(diào)整因子a滿足小于時，系統(tǒng)最終能收斂到全局的狀態(tài)平均值。

Xie等人[3]提出了一種基于切換拓撲的離散時間一致性協(xié)議：

即智能體i下一次的狀態(tài)為其自身狀態(tài)與通信范圍內(nèi)的最近鄰居智能體的組合狀態(tài)，是智能體i兩側(cè)的最近鄰居智能體的狀態(tài)。Xie等人[3]通過李雅普諾夫函數(shù)理論證明了在該協(xié)議下，若多智能體系統(tǒng)能始終保持連通，且調(diào)整因子a滿足小于時，系統(tǒng)最終能收斂到全局的狀態(tài)平均值。以上兩個一致性協(xié)議(2),(3)都是假設系統(tǒng)能保持連通，但是系統(tǒng)往往不能始終保持連通。一旦系統(tǒng)連通性不能保持，一致性就不能達成。我們在下文中提出了一種離散一致性協(xié)議，保證系統(tǒng)能始終保持連通，并能穩(wěn)定地達成一致性。

1.3 問題描述

對于任意的智能體初始狀態(tài)向量x(0)，和智能體i,j=1,...,n，如果存在離散一致性協(xié)議使得各智能體狀態(tài)在有限次迭代次數(shù)內(nèi)最終趨于一致，則稱該協(xié)議解決了一致性問題。

2 主要結(jié)果

我們給出如下定義：

智能體i下一次的狀態(tài)為自身狀態(tài)和兩側(cè)最遠鄰居智能體狀態(tài)的平均值。若智能體i的左鄰域為空集，即左側(cè)沒有最遠鄰居，則忽略左鄰域，只考慮右側(cè)的最遠鄰居；若智能體i的右鄰域為空集，即右側(cè)沒有最遠鄰居，則忽略右鄰域，只考慮左側(cè)的最遠鄰居。

以上描述用一致性協(xié)議描述如下：

接下來，我們將證明，對于初始時刻連通的初始拓撲，在一致性協(xié)議（4）下系統(tǒng)一定能保持連通性，并最終一定能達成一致性。

定理1：如果兩個智能體i,j在第k次迭代中具有相同的狀態(tài)，那么這兩個智能體i,j在第k+1次迭代中具有相同的狀態(tài)。即如果

證明：如果兩個智能體i,j在第k次迭代中具有相同的狀態(tài)，它們就有著相同的兩側(cè)最遠鄰居，那么在k+1次迭代中，兩個智能體i,j也會具有相同的狀態(tài)。

特別地，如果兩個智能體i,j在第k次迭代中具有相同的狀態(tài)，那么它們在隨后的迭代中就有相同的狀態(tài)。

定理2：對于初始時刻連通的初始拓撲，在第k次迭代中，邊界智能體（狀態(tài)值最大的和最小的智能體）有且僅有一個鄰居，其余智能體有且僅有兩個鄰居。狀態(tài)值最小的智能體，其左鄰域為空集，在右鄰域上有且僅有一個鄰居；狀態(tài)值最大的智能體，其右鄰域為空集，在左鄰域上有且僅有一個鄰居。

證明：基于初始時刻連通的初始拓撲，對于除了邊界智能體以外的智能體，它們在左右鄰域上一定能搜索到智能體作為它的鄰居，所以它們一定會有兩個鄰居。而狀態(tài)值最小的智能體在左鄰域上搜索不到鄰居，只有在右鄰域上能搜索到鄰居；狀態(tài)值最大的智能體在右鄰域上搜索不到鄰居，只有在左鄰域上搜索到鄰居。

定理3：對于初始時刻連通的初始拓撲，假設有兩個非邊界智能體i,j，滿足那么智能體i,j在其左右鄰域的最遠鄰居滿足：

定理4：對于初始時刻連通的初始拓撲，在一致性協(xié)議（4）下系統(tǒng)一定能保持連通性。即如果系統(tǒng)在第k次迭代中是連通的，系統(tǒng)在第k+1次迭代中就一定是連通的。

證明：假設在第k次迭代中系統(tǒng)n個智能體的狀態(tài)值為

由于系統(tǒng)在第k次迭代中是連通的，因此依次有序的兩智能體的狀態(tài)值的差值均小于r，即

則根據(jù)定理2，智能體i和j均有兩個鄰居，那么有

然后我們討論邊界智能體xn(k)在k+1次迭代中可能會發(fā)生的情況。

于是我們可知，如果系統(tǒng)在第k次迭代中是連通的，系統(tǒng)在第k+1次迭代中就一定是連通的。證畢。

定理5：對于初始時刻連通的初始拓撲，在一致性協(xié)議（4）下系統(tǒng)一定能達成一致性。

證明：我們首先證明，在每一次的系統(tǒng)迭代中，系統(tǒng)的最大狀態(tài)值單調(diào)遞減，系統(tǒng)的最小狀態(tài)值單調(diào)遞增。

于是我們又在每一次的系統(tǒng)迭代中，系統(tǒng)的最大狀態(tài)值單調(diào)遞減，類似地，系統(tǒng)的最小狀態(tài)值單調(diào)遞增。系統(tǒng)的區(qū)間長度在不斷減小。

而根據(jù)定理4，系統(tǒng)在迭代過程中又能一直保持連通，那么在有限次的迭代次數(shù)中，必定存在一個迭代次數(shù)t，使得系統(tǒng)的區(qū)間長度小于r。

當?shù)竭_這個迭代次數(shù)t時，狀態(tài)值最大的智能體在左鄰域上選擇的鄰居就是狀態(tài)值最小的智能體，狀態(tài)值最小的智能體在右鄰域上選擇的鄰居就是狀態(tài)值最大的智能體。于是，在t+1次迭代中，這兩個智能體的狀態(tài)發(fā)生了重合，它們的狀態(tài)值等于在t次迭代中這兩個智能體的狀態(tài)平均值。

在后續(xù)的迭代次數(shù)中，系統(tǒng)的區(qū)間長度仍在不斷減小。但是系統(tǒng)中智能體的狀態(tài)值至少會兩兩重合一次。那么經(jīng)過有限次的迭代次數(shù)后，系統(tǒng)中的所有智能體的狀態(tài)值會完全相同，即系統(tǒng)一定能達成一致性。

于是我們可知，對于初始時刻連通的初始拓撲，在一致性協(xié)議（4）下系統(tǒng)一定能達成一致性。證畢。

3 仿真實驗

本文的仿真實驗是基于Matlab數(shù)學軟件來進行的。在仿真實驗中，以智能體的位置信息作為狀態(tài)值，以智能體進行匯聚為例，考慮初始時刻系統(tǒng)的初始拓撲是連通的。我們以Xie等人在[3]中提出的基于切換拓撲的離散時間一致性協(xié)議作為對比對象，主要討論本文提出的一致性協(xié)議和該協(xié)議在性能上的共同點和不同點。

對于兩種一致性協(xié)議而言，每一個智能體在進行狀態(tài)演化的過程中，都只需要存儲和計算自身和兩個鄰居智能體的狀態(tài)信息（[3]中的協(xié)議（3）是選擇兩個與自身狀態(tài)差值最近的智能體，而本文是選擇兩個與自身狀態(tài)差值最遠的智能體），因此在每一步的迭代過程的計算量都只需要兩次，兩種協(xié)議在系統(tǒng)演化所需要的計算資源上是相同的。

但是，當系統(tǒng)的初始拓撲是隨機分布的情形時，[3]中的協(xié)議不一定能保證系統(tǒng)拓撲在智能體的狀態(tài)演化過程中始終保持連通，系統(tǒng)拓撲可能不會收斂到一致性。而本文提出的一致性協(xié)議（4），經(jīng)過了嚴格的證明分析，無論系統(tǒng)的初始拓撲是何種情形，系統(tǒng)拓撲在智能體的狀態(tài)演化過程中一定能保持連通，并能收斂到一致性。而且，本文的鄰域選取策略是選擇兩個與自身狀態(tài)差值最遠（而非最近）的鄰居智能體，因此一致性協(xié)議（4）的收斂速度上比[3]中的協(xié)議（3）有較明顯的加快。

接下來，我們通過對[3]中的一致性協(xié)議（3）和本文提出的一致性協(xié)議（4）進行四組仿真實驗，作出對比分析。每一組仿真實驗中智能體的初始狀態(tài)信息是相同的，即1)和2），3)和4)，5)和6)，7)和8)中的多智能體系統(tǒng)具有相同的初始拓撲。

1.一致性協(xié)議（3）：11個智能體的狀態(tài)值均勻分布在[0,5]的區(qū)間內(nèi)，通信半徑r=1，調(diào)整因子。在智能體的狀態(tài)演化過程中系統(tǒng)拓撲始終保持連通，經(jīng)過約100次迭代后，11個智能體的狀態(tài)值達成一致，匯聚在一個點2.5上，具體情況如圖1所示。

2.一致性協(xié)議（4）：11個智能體的狀態(tài)值均勻分布在[0,5]的區(qū)間內(nèi)，通信半徑r=1。在智能體的狀態(tài)演化過程中系統(tǒng)拓撲始終保持連通，經(jīng)過約15次迭代后，11個智能體的狀態(tài)值達成一致，匯聚在一個點2.5上，具體情況如圖2所示。

3.一致性協(xié)議（3）：20個智能體的狀態(tài)值均勻分布在[0,10]的區(qū)間內(nèi)，通信半徑r=1，調(diào)整因子。在智能體的狀態(tài)演化過程中系統(tǒng)拓撲始終保持連通，經(jīng)過約300次迭代后，20個智能體的狀態(tài)值達成一致，匯聚在一個點5上，具體情況如圖3所示。

圖1：協(xié)議（3）下初始拓撲均勻分布在區(qū)間[0,5]的演化過程

圖2：協(xié)議（4）下初始拓撲均勻分布在區(qū)間[0,5]的演化過程

圖3：協(xié)議（3）下初始拓撲均勻分布在區(qū)間[0,10]的演化過程

圖4：協(xié)議（4）下初始拓撲均勻分布在區(qū)間[0,10]的演化過程

4.一致性協(xié)議（4）：20個智能體的狀態(tài)值均勻分布在[0,10]的區(qū)間內(nèi)，通信半徑r=1。在智能體的狀態(tài)演化過程中系統(tǒng)拓撲始終保持連通，經(jīng)過約50次迭代后，20個智能體的狀態(tài)值達成一致，匯聚在一個點5上，具體情況如圖4所示。

5.一致性協(xié)議（3）：11個智能體的狀態(tài)值隨機分布在[0,5]的區(qū)間內(nèi)，通信半徑r=1，調(diào)整因子。在智能體的狀態(tài)演化過程中系統(tǒng)拓撲不能始終保持連通，經(jīng)過約50次迭代后，11個智能體的狀態(tài)值分裂成兩個集群，分別是點0.9和點3.4，具體情況如圖5所示。

6.一致性協(xié)議（4）：11個智能體的狀態(tài)值隨機分布在[0,5]的區(qū)間內(nèi)，通信半徑r=1。在智能體的狀態(tài)演化過程中系統(tǒng)拓撲始終保持連通，經(jīng)過約15次迭代后，11個智能體的狀態(tài)值達成一致，匯聚在一個點2.5上，具體情況如圖6所示。

7.一致性協(xié)議（3）：20個智能體的狀態(tài)值隨機分布在[0,10]的區(qū)間內(nèi)，通信半徑r=11，調(diào)整因子。在智能體的狀態(tài)演化過程中系統(tǒng)拓撲不能始終保持連通，經(jīng)過約80次迭代后，20個智能體的狀態(tài)值分裂成四個集群，分別是點1.3，點3.2，點5.8和點8，具體情況如圖7所示。

8.一致性協(xié)議（4）：20個智能體的狀態(tài)值隨機分布在[0,10]的區(qū)間內(nèi)，通信半徑r=1。在智能體的狀態(tài)演化過程中系統(tǒng)拓撲始終保持連通，經(jīng)過約50次迭代后，20個智能體的狀態(tài)值達成一致，匯聚在一個點4.8上，具體情況如圖8所示。

通過以上仿真，可以觀察到，當系統(tǒng)的初始拓撲是隨機分布時，系統(tǒng)拓撲可能不能始終保持連通性，因而會分裂成多個集群。而在本文提出的一致性協(xié)議（4）下，無論系統(tǒng)的初始拓撲是均勻分布還是隨機分布，系統(tǒng)拓撲在智能體的狀態(tài)演化過程中一定能保持連通，并且各智能體的狀態(tài)值一定能漸近收斂到初始時刻的全局幾何中心，即達成一致性。而且，由于智能體的鄰域選取策略是選擇兩個與自身狀態(tài)差值最遠（而非最近）的鄰居智能體，系統(tǒng)的收斂速度明顯加快。

4 結(jié)束語

在本文中，我們針對通信范圍有限的多智能體系統(tǒng)，提出了一種離散時間一致性協(xié)議。在一維情形下，對于任意初始時刻連通的初始拓撲，基于該協(xié)議，智能體都能保持連通性，并一定能漸近收斂到它們的初始狀態(tài)平均值。

我們未來的工作是設計一個更好的切換拓撲下的離散時間一致性協(xié)議。有三點值得進一步研究：

（1）尋找更好的方法來保持切換拓撲的連通性；

（2）設計更簡潔合理的一致性協(xié)議；

（3）更快的收斂速度。

圖5：協(xié)議（3）下初始拓撲隨機分布在區(qū)間[0,5]的演化過程

圖6：協(xié)議（4）下初始拓撲隨機分布在區(qū)間[0,5]的演化過程

圖7：協(xié)議（3）下初始拓撲隨機分布在區(qū)間[0,10]的演化過程

圖8：協(xié)議（4）下初始拓撲隨機分布在區(qū)間[0,10]的演化過程