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

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

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

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

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

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

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

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

1 多智能體復雜網絡中的一致性問題

(1)

(2)

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

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

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

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

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

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

由引理2知，多智能體系統(tǒng)的拓撲結構決定了系統(tǒng)一致性問題的收斂速度特性，而與拓撲結構相對應的拉譜拉斯矩陣L的最小非零特征值λ2的大小度量了該系統(tǒng)的一致性收斂速度。

2 網絡拓撲結構及其一致性問題分析

下面分析最臨近耦合網絡、星網絡和全耦合網絡的網絡拓撲結構及其λ2的特性，從而進一步分析相應的多智能體系統(tǒng)一致性收斂速度的特性。

2.1最鄰近耦合網絡

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

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

則當N?m時:

(3)

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

2.2星網絡

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

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

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

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

2.3全耦合網絡

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

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

3 網絡一致性收斂速度的仿真研究

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

φ(x)=xTLx

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

圖1 誤差函數(shù) 圖2 全耦合網絡的誤差函數(shù)

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

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

4 結 語

筆者對多智能體系統(tǒng)在最臨近耦合網絡、星網絡和全耦合網絡中的一致性收斂速度進行了研究。通過理論分析和數(shù)字仿真發(fā)現(xiàn)，星網絡在通信連接較少(平均度約為2)的情況下，具有很快的收斂速度，其收斂速度要比與其具有相同節(jié)點數(shù)和相近平均度的最臨近耦合網絡快很多倍；全耦合網絡的一致性收斂速度是最快，所有節(jié)點在1s左右即可達到一致性，且和節(jié)點數(shù)無關，但全耦合網絡結構的網絡通信連邊數(shù)太多，當網絡規(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年大學畢業(yè)，博士，副教授，現(xiàn)主要從事復雜動態(tài)網絡和復雜非線性系統(tǒng)以及檢測技術與自動化裝置等方面的教學與研究工作。