量化狀態(tài)信息下多智能體Gossip算法及分布式優(yōu)化

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

?

量化狀態(tài)信息下多智能體Gossip算法及分布式優(yōu)化

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

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

基于量化狀態(tài)信息的異步隨機(jī)Gossip算法大多以均勻選擇概率的時(shí)間模型為基礎(chǔ)，未充分考慮網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對局部信息傳遞的影響。為此，該文提出了一種以非均勻選擇概率為時(shí)間模型的改進(jìn)算法。首先給出了非均勻選擇概率下的多智能體系統(tǒng)時(shí)間模型，在隨機(jī)性量化策略下給出了一致性誤差的收斂性質(zhì)；并討論了量化精度和概率化權(quán)重矩陣第2大特征值對一致性誤差收斂速度的影響，進(jìn)而利用投影次梯度給出了選擇概率的分布式優(yōu)化方法。仿真結(jié)果表明，該基于量化狀態(tài)信息的算法可通過選擇概率的分布式優(yōu)化，提高一致性誤差的收斂速度。

多智能體系統(tǒng)；量化；分布式一致；非均勻選擇概率；優(yōu)化

1 引言

隨著多智能體系統(tǒng)在機(jī)器人編隊(duì)控制[1]、無人機(jī)協(xié)調(diào)控制[2]、多傳感器狀態(tài)估計(jì)[3]等領(lǐng)域的廣泛應(yīng)用，分布式一致問題吸引了眾多國內(nèi)外學(xué)者，成為當(dāng)前熱點(diǎn)研究領(lǐng)域之一[4,5]。在多智能體系統(tǒng)中，分布式一致是指各個(gè)具有感知、通信和決策能力的智能體在沒有協(xié)調(diào)中心的情況下，僅通過局部的信息交互最終使其狀態(tài)達(dá)到全局一致。隨機(jī)分布式一致是多智能體中一個(gè)重要的研究分支。在這類問題中，通信拓?fù)浔唤３呻S機(jī)圖，各智能體之間隨機(jī)建立通信鏈路。這種隨機(jī)拓?fù)浣Y(jié)構(gòu)可有效避免信道沖突，降低單個(gè)智能體的計(jì)算和通信負(fù)擔(dān)。

在多智能體系統(tǒng)中，受網(wǎng)絡(luò)信道通信容量和各智能體數(shù)據(jù)儲存、計(jì)算能力的限制，各智能體之間只能處理、傳遞有限字節(jié)的信息量，因此，研究量化狀態(tài)信息下隨機(jī)分布式一致性具有更大的現(xiàn)實(shí)意義。2009年，Lavaei等人[13,14]利用凸優(yōu)化方法研究了量化狀態(tài)信息下ARG算法的平均收斂時(shí)間。隨后，Carli等人[15]分別研究了確定性量化策略與隨機(jī)性量化策略下的ARG算法，指出隨機(jī)性量化優(yōu)于確定性量化；并根據(jù)智能體是否能夠獲得其自身非量化信息，討論了完全量化、部分量化、信息補(bǔ)償3種狀態(tài)更新方式下的收斂性。Yuan等人[16]研究了可變加權(quán)系數(shù)下的量化ARG算法，并討論了算法漸近誤差的上界與量化精度、加權(quán)系數(shù)的關(guān)系，并得出加權(quán)系數(shù)最優(yōu)取值為1/2。2012年，Cai等人[17]研究了通信拓?fù)錇橥耆邢驁D時(shí)的量化ARG算法，并給出了平均收斂時(shí)間。上述針對量化ARG算法的研究大多基于文獻(xiàn)[6]中以均勻選擇概率為基礎(chǔ)的時(shí)間模型，該模型未充分考慮網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對局部信息傳遞的影響。鑒于此，本文基于非均勻選擇概率的時(shí)間模型，給出了量化狀態(tài)信息下異步隨機(jī)Gossip算法；在概率意義下研究了多智能體系統(tǒng)一致性誤差的收斂性質(zhì)，分析了選擇概率和量化精度對多智能體收斂速度的影響，并給出了選擇概率的分布式優(yōu)化方法。

2 問題描述

2.1 網(wǎng)絡(luò)拓?fù)?/h3>

2.2量化策略

2.3 量化狀態(tài)信息下異步隨機(jī)Gossip算法

不難發(fā)現(xiàn)，不同于傳統(tǒng)的Gossip算法中所采用的時(shí)鐘模型，本文給出的模型將能以不同的概率選擇各智能體發(fā)起信息交互。

3 NQARG算法收斂性分析

根據(jù)文獻(xiàn)[16,18]的證明方法，易得上述結(jié)論。

其中

注意到

即

證畢

4 選擇概率分布式優(yōu)化

而在非均勻選擇概率下：

其中

不難發(fā)現(xiàn)，若智能體可獲取特征向量中所對應(yīng)的分量與其鄰居節(jié)點(diǎn)所對應(yīng)的分量，即可以分布式方式進(jìn)行優(yōu)化。根據(jù)文獻(xiàn)[18]和文獻(xiàn)[19]的研究結(jié)果，可利用圖1所示流程計(jì)算。

表1選擇概率分布式優(yōu)化算法

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

5 仿真分析

考慮在25×25的矩形區(qū)域內(nèi)隨機(jī)散布的10個(gè)智能體，并以10為各節(jié)點(diǎn)的最大通信半徑構(gòu)造無向連通網(wǎng)絡(luò)，如圖3所示。各智能體的初始狀態(tài)在區(qū)間[-100,100]中隨機(jī)取值。

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

比特位數(shù)1012141618 迭代次數(shù)k782681643626622

表3各智能體最優(yōu)選擇概率

智能體12345678910 概率000.21210.012000.26150.214200.30020

圖3 隨機(jī)生成的網(wǎng)絡(luò)拓?fù)鋱D

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

圖5 特征值優(yōu)化

表4各智能體最優(yōu)選擇概率

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

圖7 特征值優(yōu)化

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

表5特征值優(yōu)化結(jié)果對比

初值文獻(xiàn)[6]方法本文方法文獻(xiàn)[6]與本文方法聯(lián)合 0.98880.98110.98030.9774

6 結(jié)束語

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

[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] 王長城, 戚國慶, 李銀伢, 等. 傳感器網(wǎng)絡(luò)分布式一致性濾波算法[J]. 控制理論與應(yīng)用, 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] 朱旭, 閆建國, 屈耀紅. 不同延遲下離散多智能體系統(tǒng)的一致性[J]. 電子與信息學(xué)報(bào), 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年生，博士生，研究方向?yàn)槎嘣葱畔⑷诤稀⒎植际綘顟B(tài)估計(jì).

戚國慶： 男，1977年生，副研究員，研究領(lǐng)域?yàn)殡S機(jī)狀態(tài)估計(jì)與信息融合.

李銀伢： 男，1976年生，副教授，研究領(lǐng)域?yàn)槟繕?biāo)跟蹤、火力與指揮控制.

盛安冬： 男，1964年生，研究員，研究領(lǐng)域?yàn)槎嘣葱畔⑷诤侠碚摷皯?yīng)用.

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改回

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

王長城 w308101484@126.com