量化狀態信息下多智能體Gossip算法及分布式優化

王長城 戚國慶 李銀伢 盛安冬

?

量化狀態信息下多智能體Gossip算法及分布式優化

王長城*戚國慶 李銀伢 盛安冬

(南京理工大學自動化學院 南京 210094)

基于量化狀態信息的異步隨機Gossip算法大多以均勻選擇概率的時間模型為基礎，未充分考慮網絡拓撲結構對局部信息傳遞的影響。為此，該文提出了一種以非均勻選擇概率為時間模型的改進算法。首先給出了非均勻選擇概率下的多智能體系統時間模型，在隨機性量化策略下給出了一致性誤差的收斂性質；并討論了量化精度和概率化權重矩陣第2大特征值對一致性誤差收斂速度的影響，進而利用投影次梯度給出了選擇概率的分布式優化方法。仿真結果表明，該基于量化狀態信息的算法可通過選擇概率的分布式優化，提高一致性誤差的收斂速度。

多智能體系統；量化；分布式一致；非均勻選擇概率；優化

1 引言

隨著多智能體系統在機器人編隊控制[1]、無人機協調控制[2]、多傳感器狀態估計[3]等領域的廣泛應用，分布式一致問題吸引了眾多國內外學者，成為當前熱點研究領域之一[4,5]。在多智能體系統中，分布式一致是指各個具有感知、通信和決策能力的智能體在沒有協調中心的情況下，僅通過局部的信息交互最終使其狀態達到全局一致。隨機分布式一致是多智能體中一個重要的研究分支。在這類問題中，通信拓撲被建模成隨機圖，各智能體之間隨機建立通信鏈路。這種隨機拓撲結構可有效避免信道沖突，降低單個智能體的計算和通信負擔。

在多智能體系統中，受網絡信道通信容量和各智能體數據儲存、計算能力的限制，各智能體之間只能處理、傳遞有限字節的信息量，因此，研究量化狀態信息下隨機分布式一致性具有更大的現實意義。2009年，Lavaei等人[13,14]利用凸優化方法研究了量化狀態信息下ARG算法的平均收斂時間。隨后，Carli等人[15]分別研究了確定性量化策略與隨機性量化策略下的ARG算法，指出隨機性量化優于確定性量化；并根據智能體是否能夠獲得其自身非量化信息，討論了完全量化、部分量化、信息補償3種狀態更新方式下的收斂性。Yuan等人[16]研究了可變加權系數下的量化ARG算法，并討論了算法漸近誤差的上界與量化精度、加權系數的關系，并得出加權系數最優取值為1/2。2012年，Cai等人[17]研究了通信拓撲為完全有向圖時的量化ARG算法，并給出了平均收斂時間。上述針對量化ARG算法的研究大多基于文獻[6]中以均勻選擇概率為基礎的時間模型，該模型未充分考慮網絡拓撲結構對局部信息傳遞的影響。鑒于此，本文基于非均勻選擇概率的時間模型，給出了量化狀態信息下異步隨機Gossip算法；在概率意義下研究了多智能體系統一致性誤差的收斂性質，分析了選擇概率和量化精度對多智能體收斂速度的影響，并給出了選擇概率的分布式優化方法。

2 問題描述

2.1 網絡拓撲

2.2量化策略

2.3 量化狀態信息下異步隨機Gossip算法

不難發現，不同于傳統的Gossip算法中所采用的時鐘模型，本文給出的模型將能以不同的概率選擇各智能體發起信息交互。

3 NQARG算法收斂性分析

根據文獻[16,18]的證明方法，易得上述結論。

其中

注意到

即

證畢

4 選擇概率分布式優化

而在非均勻選擇概率下：

其中

不難發現，若智能體可獲取特征向量中所對應的分量與其鄰居節點所對應的分量，即可以分布式方式進行優化。根據文獻[18]和文獻[19]的研究結果，可利用圖1所示流程計算。

表1選擇概率分布式優化算法

選擇概率分布式優化算法輸入：初始化選擇概率，最大迭代次數 輸出：最優選擇概率令迭代次數while do(1)根據圖1計算特征向量，智能體利用中對應的分量 與鄰節點對應的分量計算次梯度：(2)利用次梯度對選擇概率更新：(3)，計算到可行域 的投影：return 最優選擇概率

5 仿真分析

考慮在25×25的矩形區域內隨機散布的10個智能體，并以10為各節點的最大通信半徑構造無向連通網絡，如圖3所示。各智能體的初始狀態在區間[-100,100]中隨機取值。

表2不同量化比特位數下的收斂速度

比特位數1012141618 迭代次數k782681643626622

表3各智能體最優選擇概率

智能體12345678910 概率000.21210.012000.26150.214200.30020

圖3 隨機生成的網絡拓撲圖

圖4 不同量化比特位數下一致性誤差比較

圖5 特征值優化

表4各智能體最優選擇概率

智能體12345678910 概率 0.0470 0.0460 0.1783 0.0670 0.1151 0.0894 0.0950 0.0462 0.2035 0.1125

圖7 特征值優化

表5給出了不同優化方法下的結果對比。不難發現，通信概率優化方法對算法收斂速度的改進有限，其原因在于沒有充分考慮各智能體在網絡中獲取信息的差異。而本文方法基于非均勻選擇概率時間模型，可進一步對選擇概率進行優化，從而改善收斂速度。同時，單一的優化通信概率矩陣或優化選擇概率對收斂速度的提高均存在局限性，將兩者結合可獲得更好的結果。

表5特征值優化結果對比

初值文獻[6]方法本文方法文獻[6]與本文方法聯合 0.98880.98110.98030.9774

6 結束語

本文基于量化狀態信息，提出了一種非均勻選擇概率下的異步隨機Gossip算法，分析了算法的收斂性質，在分布式環境下給出了選擇概率的優化方法。結果表明，多智能體一致性收斂速度取決于概率化權重矩陣的第2大特征值和量化水平；在初始階段，誤差收斂速度主要依賴于權重矩陣的第2大特征值，隨著誤差的減小，量化水平對其影響占主導地位。其次，可通過對選擇概率的分布式優化提高收斂速度，且優化結果優于傳統的通信概率矩陣優化方法。同時，本文為突出重點假設所建立的通信鏈路是理想的，實際網絡系統中存在的信道隨機干擾、數據丟包等現象仍是值得進一步探討的問題。

[1] Do K D. Formation control of multiple elliptical agents with limited sensing ranges[J]., 2012, 48(7): 1330-1338.

[2] Manathara J G and Ghose D. Rendezvous of multiple UAVs with collision avoidance using consensus[J]., 2012, 25(4): 480-489.

[3] 王長城, 戚國慶, 李銀伢, 等. 傳感器網絡分布式一致性濾波算法[J]. 控制理論與應用, 2012, 29(12): 1645-1650.

Wang Chang-cheng, Qi Guo-qing, Li Yin-ya,.. Consensus-based distributed filtering algorithm in sensor networks[J].&, 2012, 29(12): 1645-1650.

[4] Zhou Z, Fang H, and Hong Y. Distributed estimation for moving target based on state-consensus strategy[J]., 2013, 58(8): 2096-2101.

[5] 朱旭, 閆建國, 屈耀紅. 不同延遲下離散多智能體系統的一致性[J]. 電子與信息學報, 2012, 34(6): 1516-1520.

Zhu Xu, Yan Jian-guo, and Qu Yao-hong. Consensus for the discrete-time multi-agent system with diverse delays[J].&, 2012, 34(6): 1516-1520.

[6] Boyd S, Ghosh A, Prabhakar B,.. Randomized gossip algorithms[J]., 2006, 52(6): 2508-2530.

[7] Dimakis A G, Sarwate A D, and Wainwright M J. Geographic gossip: efficient averaging for sensor networks[J]., 2008, 56(3): 1205-1216.

[8] Tuncer C A, Mehmet E Y, Anand D S,.. Broadcast gossip algorithms for consensus[J]., 2009, 57(7): 2748-2761.

[9] Ustebay D, Oreshkin B N, Coates M J,.. Greedy gossip with eavesdropping[J]., 2010, 58(7): 3765-3776.

[10] Kar S and Moura J M F. Gossip and distributed Kalman filtering: weak consensus under weak delectability[J]., 2011, 59(4): 1766-1784.

[11] Cai K and Ishii H. Average consensus on general strongly connected digraphs[J]., 2012, 48(11): 2750-2761.

[12] Lavaei J and Murray R M. Quantized consensus by means of gossip algorithm[J]., 2012, 57(1): 19-32.

[13] Lavaei J and Murray R M. On quantized consensus by means of gossip algorithm part I: convergence proof[C]. Proceedings of the American Control Conference, St. Louis, MO, 2009: 394-401.

[14] Lavaei J and Murray R M. On quantized consensus by means of gossip algorithm Part II: convergence time[C]. Proceedings of the American Control Conference, St. Louis, MO, 2009: 2958-2965.

[15] Carli R, Fagnani F, Frasca P,.. Gossip consensus algorithms with quantized communication[J]., 2010, 46(1): 70-80.

[16] Yuan D M, Xu S Y, Zhao H Y,.. Distributed average consensus via gossip algorithm with real-valued and quantized data for 0 < q < 1[J].&, 2010, 59(9): 536-542.

[17] Cai K and Ishii H. Convergence time analysis of quantized gossip consensus on digraphs[J]., 2012, 48(9): 2344-2351.

[18] Xiao L and Boyd S. Fast linear iterations for distributed averaging[C]. Proceedings of 2003 Conference on Decision and Control, Hawaii, 2003: 4997-5002.

[19] Kempe D and McSherry F. A decentralized algorithm for spectral analysis[C]. Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, 2003: 561-568.

王長城： 男，1985年生，博士生，研究方向為多源信息融合、分布式狀態估計.

戚國慶： 男，1977年生，副研究員，研究領域為隨機狀態估計與信息融合.

李銀伢： 男，1976年生，副教授，研究領域為目標跟蹤、火力與指揮控制.

盛安冬： 男，1964年生，研究員，研究領域為多源信息融合理論及應用.

Multi-agent Gossip Consensus Algorithm with Quantized Data and Distributed Optimizing

Wang Chang-cheng Qi Guo-qing Li Yin-ya Sheng An-dong

(,210094,)

As the traditional quantized asynchronous randomized gossip consensus algorithm is based on uniform selection probability time mode, the impact of network topology on local information transfer is not been fully considered. Thus, an improved quantized asynchronous randomized gossip consensus algorithm with non-uniform selection probability is proposed in this paper. Firstly, the asynchronous time model with non-uniform selection probability is proposed. Then the convergence of the algorithm is analyzed with randomized quantized information. The impact of the quantization resolution and the second largest eigenvalue of the probabilistic weighted matrix on convergence rate is also discussed. Furthermore, this paper proposes an optimization algorithm for selection probabilities with projection subgradient method in a distributed manner. The numerical example indicates that, the proposed algorithm improves the convergence rate by optimizing selection probabilities of agents.

Multi-agent system; Quantization; Distributed consensus; Non-uniform selection probability; Optimizing

TP391

A

1009-5896(2014)01-0128-07

10.3724/SP.J.1146.2013.00297

2013-03-12收到，2013-10-22改回

國家自然科學基金(61104186, 61273076)和江蘇省自然科學基金(BK2012801)資助課題

王長城 w308101484@126.com