一種基于切換拓?fù)涞碾x散時(shí)間一致性協(xié)議

杜宇凡

(廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院 廣東省廣州市 510006)

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

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

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

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

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

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

1 預(yù)備知識(shí)及問題描述

1.1 圖論與矩陣論

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

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

（1）0是矩陣L的一個(gè)特征值，1是其對(duì)應(yīng)的特征向量，滿足L1=0；

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

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

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

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

Krause等人[1]提出了一種基于切換拓?fù)涞碾x散時(shí)間一致性協(xié)議：

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

Zheng等人[2]提出了一種基于切換拓?fù)涞碾x散時(shí)間一致性協(xié)議：

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

Xie等人[3]提出了一種基于切換拓?fù)涞碾x散時(shí)間一致性協(xié)議：

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

1.3 問題描述

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

2 主要結(jié)果

我們給出如下定義：

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

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

接下來(lái)，我們將證明，對(duì)于初始時(shí)刻連通的初始拓?fù)?，在一致性協(xié)議（4）下系統(tǒng)一定能保持連通性，并最終一定能達(dá)成一致性。

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

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

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

定理2：對(duì)于初始時(shí)刻連通的初始拓?fù)?，在第k次迭代中，邊界智能體（狀態(tài)值最大的和最小的智能體）有且僅有一個(gè)鄰居，其余智能體有且僅有兩個(gè)鄰居。狀態(tài)值最小的智能體，其左鄰域?yàn)榭占?，在右鄰域上有且僅有一個(gè)鄰居；狀態(tài)值最大的智能體，其右鄰域?yàn)榭占?，在左鄰域上有且僅有一個(gè)鄰居。

證明：基于初始時(shí)刻連通的初始拓?fù)?，?duì)于除了邊界智能體以外的智能體，它們?cè)谧笥亦徲蛏弦欢芩阉鞯街悄荏w作為它的鄰居，所以它們一定會(huì)有兩個(gè)鄰居。而狀態(tài)值最小的智能體在左鄰域上搜索不到鄰居，只有在右鄰域上能搜索到鄰居；狀態(tài)值最大的智能體在右鄰域上搜索不到鄰居，只有在左鄰域上搜索到鄰居。

定理3：對(duì)于初始時(shí)刻連通的初始拓?fù)?，假設(shè)有兩個(gè)非邊界智能體i,j，滿足那么智能體i,j在其左右鄰域的最遠(yuǎn)鄰居滿足：

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

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

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

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

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

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

定理5：對(duì)于初始時(shí)刻連通的初始拓?fù)?，在一致性協(xié)議（4）下系統(tǒng)一定能達(dá)成一致性。

證明：我們首先證明，在每一次的系統(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ū)間長(zhǎng)度在不斷減小。

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

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

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

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

3 仿真實(shí)驗(yàn)

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

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

但是，當(dāng)系統(tǒng)的初始拓?fù)涫请S機(jī)分布的情形時(shí)，[3]中的協(xié)議不一定能保證系統(tǒng)拓?fù)湓谥悄荏w的狀態(tài)演化過程中始終保持連通，系統(tǒng)拓?fù)淇赡懿粫?huì)收斂到一致性。而本文提出的一致性協(xié)議（4），經(jīng)過了嚴(yán)格的證明分析，無(wú)論系統(tǒng)的初始拓?fù)涫呛畏N情形，系統(tǒng)拓?fù)湓谥悄荏w的狀態(tài)演化過程中一定能保持連通，并能收斂到一致性。而且，本文的鄰域選取策略是選擇兩個(gè)與自身狀態(tài)差值最遠(yuǎn)（而非最近）的鄰居智能體，因此一致性協(xié)議（4）的收斂速度上比[3]中的協(xié)議（3）有較明顯的加快。

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

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

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

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

圖1：協(xié)議（3）下初始拓?fù)渚鶆蚍植荚趨^(qū)間[0,5]的演化過程

圖2：協(xié)議（4）下初始拓?fù)渚鶆蚍植荚趨^(qū)間[0,5]的演化過程

圖3：協(xié)議（3）下初始拓?fù)渚鶆蚍植荚趨^(qū)間[0,10]的演化過程

圖4：協(xié)議（4）下初始拓?fù)渚鶆蚍植荚趨^(qū)間[0,10]的演化過程

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

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

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

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

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

通過以上仿真，可以觀察到，當(dāng)系統(tǒng)的初始拓?fù)涫请S機(jī)分布時(shí)，系統(tǒng)拓?fù)淇赡懿荒苁冀K保持連通性，因而會(huì)分裂成多個(gè)集群。而在本文提出的一致性協(xié)議（4）下，無(wú)論系統(tǒng)的初始拓?fù)涫蔷鶆蚍植歼€是隨機(jī)分布，系統(tǒng)拓?fù)湓谥悄荏w的狀態(tài)演化過程中一定能保持連通，并且各智能體的狀態(tài)值一定能漸近收斂到初始時(shí)刻的全局幾何中心，即達(dá)成一致性。而且，由于智能體的鄰域選取策略是選擇兩個(gè)與自身狀態(tài)差值最遠(yuǎn)（而非最近）的鄰居智能體，系統(tǒng)的收斂速度明顯加快。

4 結(jié)束語(yǔ)

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

我們未來(lái)的工作是設(shè)計(jì)一個(gè)更好的切換拓?fù)湎碌碾x散時(shí)間一致性協(xié)議。有三點(diǎn)值得進(jìn)一步研究：

（1）尋找更好的方法來(lái)保持切換拓?fù)涞倪B通性；

（2）設(shè)計(jì)更簡(jiǎn)潔合理的一致性協(xié)議；

（3）更快的收斂速度。

圖5：協(xié)議（3）下初始拓?fù)潆S機(jī)分布在區(qū)間[0,5]的演化過程

圖6：協(xié)議（4）下初始拓?fù)潆S機(jī)分布在區(qū)間[0,5]的演化過程

圖7：協(xié)議（3）下初始拓?fù)潆S機(jī)分布在區(qū)間[0,10]的演化過程

圖8：協(xié)議（4）下初始拓?fù)潆S機(jī)分布在區(qū)間[0,10]的演化過程