吳正平 (三峽大學(xué)電氣信息學(xué)院 ，湖北 宜昌 443002)

謝學(xué)文 (大慶鉆探工程公司測井二公司完井大隊，吉林 松原 138003)

規(guī)則網(wǎng)絡(luò)中多智能體系統(tǒng)一致性收斂速度研究

吳正平 (三峽大學(xué)電氣信息學(xué)院 ，湖北 宜昌 443002)

謝學(xué)文 (大慶鉆探工程公司測井二公司完井大隊，吉林 松原 138003)

通過分析和仿真，對最臨近耦合網(wǎng)絡(luò)、星網(wǎng)絡(luò)和全耦合網(wǎng)絡(luò)的一致性收斂速度進行了研究。研究結(jié)果表明，最臨近耦合網(wǎng)絡(luò)的收斂速度是最慢的，星網(wǎng)絡(luò)作為一個邊較少的網(wǎng)絡(luò)具有很快的一致性收斂速度，而全耦合網(wǎng)絡(luò)是所有網(wǎng)絡(luò)中一致性收斂速度最快的。該研究對多智能體網(wǎng)絡(luò)的設(shè)計具有指導(dǎo)意義。

規(guī)則網(wǎng)絡(luò)；多智能體系統(tǒng)；一致性

1 多智能體復(fù)雜網(wǎng)絡(luò)中的一致性問題

(1)

(2)

式中，x(t)={x1,x2,…,xN}為狀態(tài)矢量；A={aij} ∈RN×N稱為網(wǎng)絡(luò)的耦合矩陣。記L=-A，則L為圖G的拉譜拉斯矩陣。矩陣A表示網(wǎng)絡(luò)的通信拓?fù)浣Y(jié)構(gòu)，如果智能體i和智能體j(i≠j)之間有通信連接，則aij=aji=1；否則，aij=aji=0(i≠j)。如果節(jié)點i的度記為ki,則有:

為了分析的方便，給出下面引理。

引理1[7]對于網(wǎng)絡(luò)系統(tǒng)(2)，當(dāng)A為對稱不可約矩陣時，則系統(tǒng)(2)是收斂的。

根據(jù)引理1，筆者研究的幾種規(guī)則網(wǎng)絡(luò)對應(yīng)的矩陣耦合A為對稱不可約矩陣，因此相應(yīng)的多智能體系統(tǒng)的一致性問題都是收斂的。

在開發(fā)房地產(chǎn)之前，必須要考慮好供求關(guān)系，這對于房價、成本計算以及開發(fā)時間和房屋的數(shù)量等起到了重要的價值，也可以促進房地產(chǎn)行業(yè)的發(fā)展。可以促進城市的建設(shè)，在規(guī)劃當(dāng)中，還需要控制風(fēng)險來讓規(guī)劃變得更具有可行性。

引理2[8]設(shè)圖L(L=-A)是強連接和平衡的，則在系統(tǒng)(2)中，x以速度β=λ2(L)收斂到x*。其中，λ2為L的最小非零特征值。

由引理2知，多智能體系統(tǒng)的拓?fù)浣Y(jié)構(gòu)決定了系統(tǒng)一致性問題的收斂速度特性，而與拓?fù)浣Y(jié)構(gòu)相對應(yīng)的拉譜拉斯矩陣L的最小非零特征值λ2的大小度量了該系統(tǒng)的一致性收斂速度。

2 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)及其一致性問題分析

下面分析最臨近耦合網(wǎng)絡(luò)、星網(wǎng)絡(luò)和全耦合網(wǎng)絡(luò)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)及其λ2的特性，從而進一步分析相應(yīng)的多智能體系統(tǒng)一致性收斂速度的特性。

2.1最鄰近耦合網(wǎng)絡(luò)

在最鄰近耦合網(wǎng)絡(luò)中，N個節(jié)點圍成一個環(huán)狀，其中任一節(jié)點i和它相鄰的節(jié)點i±1,i±2,…,i±l(l為一正整數(shù))相連。相應(yīng)的耦合矩陣Anc=(aij)N×N可以表示為:

拉普拉斯矩陣L=-Anc，其特征值為:

則當(dāng)N?m時:

(3)

從式(3)可以看出，最臨近耦合網(wǎng)絡(luò)的λ2值是較小的，因此其一致性速度很慢。

2.2星網(wǎng)絡(luò)

在星形耦合結(jié)構(gòu)中，所有的節(jié)點連接到一個節(jié)點上，該節(jié)點稱為中心節(jié)點。星網(wǎng)絡(luò)相應(yīng)的耦合矩陣為:

拉普拉斯矩陣L=-Asc，其特征值為:

λ1=0λ2=λ3=…=λN-1=1λN=N

星網(wǎng)絡(luò)的λ2=1，因此其一致性收斂速度遠遠大于與其具有相近平均度的最臨近耦合網(wǎng)絡(luò)。該網(wǎng)絡(luò)的主要特點是網(wǎng)絡(luò)連邊少，網(wǎng)絡(luò)構(gòu)建成本低，一致性收斂速度快。但從其網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)來看，當(dāng)中心節(jié)點癱瘓時，整個網(wǎng)絡(luò)也就癱瘓了，因此該網(wǎng)絡(luò)對蓄意攻擊魯棒性差。

2.3全耦合網(wǎng)絡(luò)

全耦合網(wǎng)絡(luò)中每一對節(jié)點都是直接相連的網(wǎng)絡(luò)，其相應(yīng)的耦合矩陣為:

拉普拉斯矩陣L=-Agc有一單0特征值，其他的特征值均為N，因此λ2=N。在全耦合網(wǎng)絡(luò)中，λ2的值最大，網(wǎng)絡(luò)的一致性收斂速度最快。但全耦合網(wǎng)絡(luò)是連邊數(shù)最多的網(wǎng)絡(luò)，因而也被認(rèn)為是最復(fù)雜、構(gòu)建成本最高的網(wǎng)絡(luò)。

3 網(wǎng)絡(luò)一致性收斂速度的仿真研究

下面，通過仿真來進一步研究最鄰近耦合網(wǎng)絡(luò)、相應(yīng)的星網(wǎng)絡(luò)(平均度約為2)和全耦合網(wǎng)絡(luò)的一致性收斂速度。一致性問題的狀態(tài)方程如式(2)所示，誤差評價函數(shù)定義為[7]:

φ(x)=xTLx

初始條件均為xi(0)=i，i=0,1,…,N；節(jié)點數(shù)N=200，平均度k=2。仿真結(jié)果如圖1和圖2所示。

圖1 誤差函數(shù) 圖2 全耦合網(wǎng)絡(luò)的誤差函數(shù)

從圖1可以看出，對于節(jié)點數(shù)為200，平均度為2的最臨近耦合網(wǎng)絡(luò)，當(dāng)誤差函數(shù)值達到0.01以下時大約需要1400s，而與其節(jié)點數(shù)相同、平均度近似的星網(wǎng)絡(luò)則只需要約8s的時間，可見，星網(wǎng)絡(luò)的一致性收斂速度遠遠大于與其節(jié)點數(shù)相同、平均度近似的最臨近耦合網(wǎng)絡(luò)。

由圖2可以看出，全耦合網(wǎng)絡(luò)的收斂速度是最快的，并且和網(wǎng)絡(luò)的規(guī)模(節(jié)點數(shù))無關(guān)，它的一致性問題的誤差函數(shù)都能在1s左右收斂到0.01以下。仿真結(jié)果與上面分析一致。

4 結(jié) 語

筆者對多智能體系統(tǒng)在最臨近耦合網(wǎng)絡(luò)、星網(wǎng)絡(luò)和全耦合網(wǎng)絡(luò)中的一致性收斂速度進行了研究。通過理論分析和數(shù)字仿真發(fā)現(xiàn)，星網(wǎng)絡(luò)在通信連接較少(平均度約為2)的情況下，具有很快的收斂速度，其收斂速度要比與其具有相同節(jié)點數(shù)和相近平均度的最臨近耦合網(wǎng)絡(luò)快很多倍；全耦合網(wǎng)絡(luò)的一致性收斂速度是最快，所有節(jié)點在1s左右即可達到一致性，且和節(jié)點數(shù)無關(guān)，但全耦合網(wǎng)絡(luò)結(jié)構(gòu)的網(wǎng)絡(luò)通信連邊數(shù)太多，當(dāng)網(wǎng)絡(luò)規(guī)模較大的時候，實現(xiàn)起來比較困難。

[1]Estrada E, Rodriguez-Velazquez J A. Subgraph centrality in complex networks[J].Phys Rev E， 2005，71:056103～056111.

[2]Estrada E, Rodriguez-Velazquez J A.Spectral measure of bipartivity in complex networks[J].Phys Rev E, 2005，72: 046105～046110.

[3]Zhengping Wu, ZhiHong Guan, Xianyong Wu，etal.Consensus Based Formation Control and Trajectory Tracing of Multi-Agent Robot Systems, Journal of Intelligent and Robotic Systems[J].Springer Netherlands, 2007, 48:397～410.

[4]Zhengping Wu, ZhihongGuan , Xianyong Wu.Consensus problem in Multi-Agent Systems with physical position neighborhood evolving network[J].Physica A,2007, 379:681～690.

[5]Saber R O. Ultrafast consensus in small-world network[A].Proc. ACC, Portland, OR, 2005, 4:2371～2378.

[6]Saber R O, Murray R M. Consensus problems in networks of agents with switching topology and time-delays[J].IEEE Trans Automat Contr, 2004, 49(9):1520～1533.

[7]Ren W , Beard R W. Consensus of information under dynamically changing interaction topologies[A].Proc 2004 ACC, Boston, MA,2004.4939～4944.

[8]Saber R O, Murray R M. Agreement problems in networks with directed graphs and switching topology[A].In Proc 2003 CDC, 2003,4:4126～4132.

[編輯] 易國華

TP273

A

1673-1409(2009)02-N060-03

2009-02-24

吳正平(1966-)，男，1988年大學(xué)畢業(yè)，博士，副教授，現(xiàn)主要從事復(fù)雜動態(tài)網(wǎng)絡(luò)和復(fù)雜非線性系統(tǒng)以及檢測技術(shù)與自動化裝置等方面的教學(xué)與研究工作。