最小事件間隔時間可設計的分布式事件觸發優化算法

摘要針對多智能體系統中的分布式凸優化問題，本文提出一種基于自適應事件觸發機制的零梯度和優化算法．基于虛擬時鐘設計了一種自適應事件觸發條件，當每個智能體的虛擬時鐘滿足該條件時才觸發條件，有效地降低了控制器的更新次數和系統的通信負擔．通過構造李雅普諾夫函數，證明了在該算法下所有智能體的狀態能漸近收斂到全局最優解．此外，所設計的事件觸發條件使得最小事件觸發間隔時間可設計，有效地排除Zeno行為．最后，通過仿真驗證了該算法的有效性．關鍵詞分布式優化;多智能體系統;凸優化;事件觸發控制

中圖分類號TP273

文獻標志碼A

0引言

近年來，多智能體系統因其在微電網控制與運行［1］、傳感器調度［2］、無人機協調［3］、軌跡跟蹤控制［4］等多個領域的應用而受到了廣泛關注．分布式優化問題作為多智能體系統基本問題成為當前的一個研究熱點［5-6］，其目標是通過智能體之間的分布式協作以實現全局目標函數最小化．

在分布式優化問題的求解方面，學者們提出了一系列的分布式優化算法．早期的算法研究成果主要是基于離散時間模型［7-9］，例如：文獻［7］基于離散時間一致性和分布式梯度下降法來解決分布式優化問題;文獻［8］針對成本函數未知的分布式優化問題，利用兩點梯度估計器設計了一種隨機無梯度算法．連續時間分布式優化算法同樣得到了廣泛研究：文獻［10］研究了固定無向網絡上的連續時間優化算法;文獻［11］給出了一種基于零梯度和原理的連續時間算法，使得智能體的狀態指數收斂到全局最優值;文獻［12］進一步提出有限時間零梯度和優化算法，實現了最優解的有限時間收斂性．上述文獻中的算法需要智能體之間進行連續通信，但智能體的通信資源通常是有限的，連續通信對實際的多智能體系統通信帶寬依然是一種挑戰．

事件觸發機制作為一種事先給定觸發條件的控制方式能夠有效減低智能體之間的通信頻率．近年來，事件觸發機制已經被廣泛應用于一致性問題中［13-18］．文獻［13］針對離散系統上的一致性問題，提出一種基于事件觸發機制的一致性算法;文獻［14］進一步給出連續時間上的分布式動態事件觸發一致性算法，有效地降低了智能體之間的通信負擔．然而，上述文獻無法有效處理Zeno行為．文獻［15］基于周期采樣控制提出一種分布式事件觸發算法，事件僅在周期采樣時刻檢測，有效地避免了Zeno行為;文獻［16-17］采用自適應事件觸發控制策略來解決無向網絡上的一致性問題，使得每個智能體事件觸發間隔時間可設計．目前，事件觸發機制已經被擴展到分布式優化問題中［19-24］．文獻［19］提出一種分布式事件觸發優化算法有效地解決了智能體之間的連續通信問題，文獻［22］將事件觸發機制和零梯度和原理應用于分布式優化問題，它們盡管在理論上避免了Zeno行為，然而無法提供明確的最小事件間隔時間．文獻［23］進一步提出一種基于采樣數據的分布式事件觸發零梯度和優化算法，保證事件觸發間隔時間是采樣周期，Zeno行為很容易被排除在外．為了進一步擴大事件觸發間隔時間，文獻［24］提出一種基于動態事件觸發的分布式優化算法，有效地降低了系統的通信負擔．然而，文獻［23-24］需要進行嚴格的時鐘同步．

受文獻［16-17，24］的啟發，本文針對無向圖下的多智能體分布式優化問題，提出一種分布式自適應事件觸發零梯度和優化算法，在所設計事件觸發條件下，每個智能體事件觸發間隔時間可設計．本文的主要貢獻如下：

1）設計了一種具有新型事件觸發條件的零梯度和優化算法來解決無向圖上的分布式優化問題，所有智能體的狀態都可在不使用任何全局信息的情況下收斂到全局最優值，并可有效地降低系統的通信負擔;

2）智能體采用分布式異步事件觸發機制，不需要時鐘同步;

3）所提出的事件觸發機制可有效排除Zeno現象，且每個智能體最小事件觸發間隔時間可設計．

1預備知識及問題描述

1.1圖論

多智能體系統可以用無向圖G=（V，E）來建模，其中V=｛v1，…，vn｝表示智能體的集合，E∈｛V×V｝為邊的集合．定義A=［aij］∈Rn×n為圖G的加權鄰接矩陣，如果（vi，vj）∈E，則權重aij=1，否則aij=0，不考慮自環的情況，所以aii=0．令D=diag｛d1，d2，…，dn｝表示入度矩陣，其中di=∑nj=1aij．定義L=［lij］n×n為圖G的拉普拉斯矩陣，它滿足L=D-A．

1.2凸函數

如果一個二次連續可微函數gi：Rn→R是局部強凸的，則對于凸緊集ΩRn中任意值都有：

gi（x′）-gi（x）-gi（x）T（x′-x）≥φi2‖x′-x‖2，x，x′∈Ω;（1）

（gi（x′）-gi（x））T（x′-x）≥φi2‖x′-x‖2，x，x′∈Ω;（2）

2gi（x）≥φiIn.（3）

其中，φi是一個正常數，gi（x）：Rn→Rn是gi的梯度，2gi（x）：Rn→Rn×n是黑森矩陣．

1.3問題描述

本文所研究的優化問題如下：

x*=arg minx∈R F（x）.（4）

其中，x*為全局最優值．F（x）=∑ni=1fi（x），局部代價函數fi（x），i=1，…，n，是二次連續可微且強凸的．

本文的目的是設計一種分布式事件觸發優化算法來解決上述優化問題，同時減少控制器的更新次數，降低多智能體之間的通信頻率．因此，基于事件觸發機制設計了一種新型零梯度和優化算法解決優化問題（4）．

2算法設計及主要結果

本節詳細介紹所提出的分布式優化算法，并給出該算法的主要結果．

2.1分布式優化算法

定義｛tik：k∈N｝為智能體i的第k次事件觸發時刻．為了方便起見，對于t∈［tik，tik+1），定義i（t）=xi（tik）．

本文設計的分布式優化算法如下：

i（t）=（2fi（xi（t）））-1ui（t）.（5）

其中：xi（0）=x*i，x*i 為智能體i成本函數優化值;ui（t）為控制輸入，ui（t）表示為

ui（t）=∑j∈Niaij（j（t）-i（t））.（6）

2.2事件觸發條件

對于t∈［tik，tik+1），設計偏差變量為

ei（t）=xi（t）-i（t）.（7）

進一步，定義一個受限制的虛擬變量0≤βi（t）lt;1，

i（t）=γi=mini，0-σi，‖ei（t）‖≠0；

-σi，‖ei（t）‖=0.（8）

其中，σigt;0為正常數，i為待設計的參數．虛擬變量βi（t）本質上是一個計時器，當βi（t）≤0時，智能體i將它的狀態信息傳遞給它的鄰居，更新i（t）=xi（t），并且重置βi（t）為它的最大值．

因此，事件觸發條件被設計為

tik+1=min｛t′≥tik |βi（t′）≤0｝.（9）

定理1假設圖G是無向連通圖，分布式優化算法（5）在事件觸發條件（9）下可以解決優化問題（4），即limt→0 x1（t）=…=limt→0 xn（t）=x*，其中x*為系統全局優化值．

證明定義Lyapunov函數

V（t）=∑ni=1（fi（x*）-fi（xi（t））-f′i（xi（t））（x*-xi（t）））+12e（t）Tβ（t）e（t）.（10）

其中，e（t）=［e1（t），e2（t），…，en（t）］T，β（t）=diag｛β1（t），β2（t），…，βn（t）｝．

令V1=∑ni=1（fi（x*）-fi（xi（t））-f′i（xi（t））（x*-xi（t））），V2（t）=12e（t）Tβ（t）e（t），式（10）可以被寫為V（t）=V1（t）+V2（t）.（11）

由式（1）可得：

V1（t）≥∑ni=1φi2（x*-xi（t））2≥0.（12）

由于βi（t）≥0，可以得到：

V2（t）≥0.（13）

由式（12）和（13）可得：

V（t）=V1（t）+V2（t）≥0.（14）

因此，李雅普諾夫函數是正定的．

對V1（t）求導，結合式（5）可得：1（t）=∑ni=1（-f′i（xi（t））i（t）-f″i（xi（t））i（t）（x*-xi（t））+f′i（xi（t））i（t））=∑ni=1-f″i（xi（t））i（t）（x*-xi（t））.（15）

由式（5）可知，式（15）可表示為

1（t）=∑ni=1-f″i（xi（t））（-f″i（xi（t））-1∑j∈Niaij（i（t）-j（t）））（x*-xi（t））=∑ni=1（∑j∈Niaij（i（t）-j（t）））（x*-xi（t））.（16）

由于圖G是強連通和平衡的，可以得到：

∑ni=1∑j∈Niaij（i（t）-j（t））x*=0.（17）

由式（16）和（17）可知：

1（t）=-xT（t）L（t）=-（（t）+e（t））TL（t）.（18）

其中，x（t）=［x1（t），x2（t），…，xn（t）］T，（t）=［1（t），2（t），…，n（t）］T．

對V2（t）求導可得：

2（t）=-eT（t）βL（t）+12eT（t）Γe（t）.（19）

其中，Γ=diag｛γ1，γ2，…，γn｝．

由式（18）和（19）可得：

（t）=-（t）TL（t）-e（t）TL（t）-eT（t）βL（t）+12eT（t）Γe（t）=-12∑ni=1yi（t）-e（t）TL（t）-eT（t）βL（t）+12eT（t）Γe（t）.（20）

其中，yi（t）=∑nj=1aij（i（t）-j（t））2．當‖ei（t）‖=0時，（t）=-12∑ni=1yi（t）≤0．因此只考慮‖ei（t）‖≠0的情況．由于

eT（t）L（t）=∑ni=1ei（t）∑nj=1Lijj（t）=∑ni=1∑j∈Niei（t）aij（i（t）-j（t））.（21）

根據楊氏不等式可得：

eT（t）L（t）≤∑ni=1∑j∈Niaije2i（t）+14aij（i（t）-j（t））2≤∑ni=1die2i（t）+14∑ni=1∑j∈Niaij（i（t）-j（t））2≤∑ni=1diei（t）2+14∑ni=1yi（t）.（22）

將式（22）代入（20）可得：

（t）≤-12∑ni=1yi（t）+∑ni=1die2i （t）+14∑ni=1yi（t）-eT（t）βL（t）+12eT（t）Γe（t）≤-14∑ni=1yi（t）+∑ni=1die2i （t）-eT（t）βL（t）+12eT（t）Γe（t）.（23）

由于eT（t）βL（t）=∑ni=1ei（t）βi（t）∑nj=1Lijj（t）≤∑ni=1βi∑j∈Niaije2i（t）+14∑j=Niaij（i（t）-j（t））2≤∑ni=1βi（t）die2i （t）+∑ni=1βi4yi（t）.（24）

可以得到：

≤-14∑ni=1yi（t）+∑ni=1die2i （t）+∑ni=1βi（t）die2i （t）+∑ni=1βi（t）4yi（t）+12eT（t）Γe（t）≤-∑ni=11-βi（t）4yi（t）+∑ni=1（1+βi（t））die2i （t）+∑ni=1γi2e2i.（25）

當-1-βi（t）4yi（t）+（1+βi（t））die2i （t）+γie2i （t）2lt;0時，可得（t）lt;0．當yi（t）≠0和ei（t）≠0時，選擇γi的最大值為

i=（1-βi（t））2yi（t）ei2（t）-2（1+βi（t））di.（26）

由式（8）和（26）可知（t）lt;0．

因此可以得到（t）≤0．根據拉塞爾不變集原理可知，當（t）=0時，有limt→∞ 1（t）=…=limt→∞ n（t）=c.（27）

由于（t）=0，且有ei（t）=0，然后可以得到：

limt→∞ x1（t）=…=limt→∞ xn（t）=c.（28）

基于算法（5）可得：

∑ni=1d（f′i（xi（t）））dt=-∑ni=1∑j∈Niaij（j-i）=-1TL（t）=0.（29）其中，1=［1，1，…，1］n．等式（29）意味著

∑ni=1fi（xi（t））=∑ni=1fi（xi（0））=∑ni=1f′i（x*i）=0.（30）

由于F（x）=∑ni=1fi（x）是強凸函數，所以可以得到F（x）只有一個全局最優值x*，使得∑ni=1f′i（x*）=F′（x*）=0．因此，有

limt→∞ x1（t）=…=limt→∞ xn（t）=c=x*.（31）

定理1證明完畢．

定理2假設圖G是無向連通圖，分布式優化算法（5）在事件觸發條件（9）下可以避免Zeno現象，且每個智能體的最小事件觸發間隔時間都是可設計的，即：

Δt=12diln1+2dii2di+σigt;0.（32）

其中，和σi是可設計的參數．

證明2由式（8）和limei→0 min｛i，0｝=0可得：-2（1+βi（t））di-σi≤γ≤-σi.（33）

因此，可以得到對于t∈［tik，tik+1），有βi（t）≥φi（t），其中φi（t）滿足：i（t）=-2（1+i（t））di-σi（34）和i（ti+k）=βi（ti+k）.（35）進一步可以得到：

i（t）=e2diti（0）+e2dit∫t0e-2diτ（-2di-σi）dτ=e2diti（0）+2di+σi2di-2di+σi2die2dit.（36）

其中，i（0）=i．當事件觸發條件滿足時，有i（t′）=0，即：e2diΔti+2di+σi2di-2di+σi2die2diΔt=0.（37）

進而推導出

Δt=12diln2dii+（2di+σi）2di+σi=12diln1+2dii2di+σigt;0.（38）

這意味著Zeno行為可以被有效避免，且每個智能體的相鄰事件觸發間隔的下界都是可設計的．

定理2證明完畢．

3仿真結果

本文通過由4個智能體構成的多智能體系統驗證所提出的算法的有效性，智能體之間的通信拓撲如圖1所示．所采用的智能體的成本函數如下所示：

fi（x）=（x-i）4+8i（x-i）2，i=1，2，3，4．

參數設置如下：σ1=σ2=σ3=σ4=0.001;虛擬變量βi（t）的最大值被設置為1=0.5，2=0.6，3=0.7和4=0.5;每個代理的初始狀態值為x1（0）=x*1=1，x2（0）=x*2=2，x3（0）=x*3=3，x4（0）=x*4=4．

對于每個智能體，當滿足其事件觸發條件時，該事件將被觸發．也就是說，當βi=0時，事件觸發條件成立，該事件就會觸發，βi被重置為i，每個智能體觸發過程如圖3—6所示．

i的演化過程如圖7所示，它是一個分段常數函數，只在智能體i及其鄰居的觸發時刻進行更新．圖8展示了每個智能體的事件觸發時刻的分布情況．可以看出，每個智能體的事件觸發時刻都非常稀疏，這有效地減少了代理之間的通信負擔，Zeno現象被有效排除．

4結論

本文針對多智能體系統分布式凸優化問題，設計了一種基于事件觸發策略的零梯度和優化算法，在所提出的優化算法下，所有智能體的狀態可以在不使用任何全局信息的情況下收斂全局最優值．此外，在所提出的事件觸發條件下，每個智能體的相鄰事件觸發間隔時間的下界都是可設計的，Zeno現象被有效排除，每個智能體只需在其自身及其鄰居事件觸發時刻更新自身狀態信息，大大減少了智能體之間的通信成本．在未來的研究中，嘗試將該方法應用于有向圖上的分布式優化問題．

參考文獻

References

［1］鄭偉，胡長斌，丁麗，等.基于多智能體系統微電網分布式控制研究［J］.高壓電器，2019，55（3）：177-184

ZHENG Wei，HU Changbin，DING Li，et al.Research on distributed control of microgrid based on multi-agent system［J］.High Voltage Apparatus，2019，55（3）：177-184

［2］Han D，Wu J F，Zhang H S，et al.Optimal sensor scheduling for multiple linear dynamical systems［J］.Automatica，2017，75：260-270

［3］Pantelimon G，Tepe K，Carriveau R，et al.Survey of multi-agent communication strategies for information exchange and mission control of drone deployments［J］.Journal of Intelligent and Robotic Systems，2019，95（3／4）：779-788

［4］胡金波，劉智偉，葛明峰.基于采樣分布式估計器的多無人艇軌跡跟蹤控制［J］.南京信息工程大學學報（自然科學版），2018，10（4）：443-449

HU Jinbo，LIU Zhiwei，GE Mingfeng.Consensus tracking control of multi-USV system based on distributed estimator under sampled interactions［J］.Journal of Nanjing University of Information Science ＆ Technology （Natural Science Edition），2018，10（4）：443-449

［5］Basir Khan M R，Jidin R，Pasupuleti J.Multi-agent based distributed control architecture for microgrid energy management and optimization［J］.Energy Conversion and Management，2016，112：288-307

［6］朱亞楠，溫廣輝.權重平衡有向網絡下分布式約束優化的連續時間算法設計［J］.南京信息工程大學學報（自然科學版），2020，12（5）：549-555

ZHU Yanan，WEN Guanghui.Continuous-time algorithm design for distributed constrained optimization over weight-balanced directed networks［J］.Journal of Nanjing University of Information Science ＆ Technology （Natural Science Edition），2020，12（5）：549-555

［7］Nedic A，Ozdaglar A.Distributed subgradient methods for multi-agent optimization［J］.IEEE Transactions on Automatic Control，2009，54（1）：48-61

［8］Pang Y P，Hu G Q.Randomized gradient-free distributed optimization methods for a multiagent system with unknown cost function［J］.IEEE Transactions on Automatic Control，2020，65（1）：333-340

［9］Liu H Z，Yu W W.Discrete-time algorithm for distributed unconstrained optimization problem with finite-time computations［J］.IEEE Transactions on Circuits and Systems II：Express Briefs，2021，68（1）：351-355

［10］Lin P，Ren W，Farrell J A.Distributed continuous-time optimization：nonuniform gradient gains，finite-time convergence，and convex constraint set［J］.IEEE Transactions on Automatic Control，2017，62（5）：2239-2253

［11］Lu J，Tang C Y.Zero-gradient-sum algorithms for distributed convex optimization：the continuous-time case［J］.IEEE Transactions on Automatic Control，2012，57（9）：2348-2354

［12］Song Y F，Chen W S.Finite-time convergent distributed consensus optimisation over networks［J］.IET Control Theory ＆ Applications，2016，10（11）：1314-1318

［13］Zhu W，Pu H Z，Wang D D，et al.Event-based consensus of second-order multi-agent systems with discrete time［J］.Automatica，2017，79：78-83

［14］Dimarogonas D V，Frazzoli E，Johansson K H.Distributed event-triggered control for multi-agent systems［J］.IEEE Transactions on Automatic Control，2012，57（5）：1291-1297

［15］Seyboth G S，Dimarogonas D V，Johansson K H.Event-based broadcasting for multi-agent average consensus［J］.Automatica，2013，49（1）：245-252

［16］Berneburg J，Nowzari C.Robust dynamic event-triggered coordination with a designable minimum inter-event time［C］／／IEEE Transactions on Automatic Control.September 1，2020，IEEE，2020：3417-3428

［17］Qian Y Y，Wan Y.Design of distributed adaptive event-triggered consensus control strategies with positive minimum inter-event times［J］.Automatica，2021，133：109837

［18］王譽達，查利娟，劉金良，等.基于事件觸發和欺騙攻擊的多智能體一致性控制［J］.南京信息工程大學學報（自然科學版），2019，11（4）：380-389

WANG Yuda，ZHA Lijuan，LIU Jinliang，et al.Event-based consensus of multi-agent systems with deception attacks［J］.Journal of Nanjing University of Information Science ＆ Technology （Natural Science Edition），2019，11（4）：380-389

［19］楊濤，徐磊，易新蕾，等.基于事件觸發的分布式優化算法［J］.自動化學報，2022，48（1）：133-143

YANG Tao，XU Lei，YI Xinlei，et al.Event-triggered distributed optimization algorithms［J］.Acta Automatica Sinica，2022，48（1）：133-143

［20］Kia S S，Cortés J，Martínez S.Distributed convex optimization via continuous-time coordination algorithms with discrete-time communication［J］.Automatica，2015，55：254-264

［21］趙中原，陳剛.基于事件驅動的二次凸優化問題分布式優化算法［J］.控制與決策，2019，34（8）：1635-1644

ZHAO Zhongyuan，CHEN Gang.Distributed event-triggered algorithm for quadratic convex optimization problem［J］.Control and Decision，2019，34（8）：1635-1644

［22］Liu J Y，Chen W S.Distributed convex optimisation with event-triggered communication in networked systems［J］.International Journal of Systems Science，2016，47（16）：3876-3887

［23］Zhao Z Y，Chen G.Event-triggered scheme for zero-gradient-sum optimisation under directed networks with time delay［J］.International Journal of Systems Science，2021，52（1）：47-56

［24］Du W，Yi X L，George J，et al.Distributed optimization with dynamic event-triggered mechanisms［C］／／2018 IEEE Conference on Decision and Control （CDC）.December 17-19，2018，Miami，FL，USA.IEEE，2019：969-974

Distributed event-triggered optimization algorithm with

designable minimum inter-event time

YANG Zhiqiang1JIA Hongyun1WEI Mengli2JI Qiutong2ZHAO Zhongyuan1

1School of Automation，Nanjing University of Information Science ＆ Technology，Nanjing 210044，China

2School of Cyber Science and Engineering，Southeast University，Nanjing 211189，China

AbstractAiming at the distributed convex optimization problem in multi-agent systems，a zero-gradient-sum optimization algorithm based on adaptive event-triggered mechanism is proposed in this paper.The adaptive event-triggered condition is designed based on virtual clock，and the condition will not be triggered until the virtual clock of each agent meets the condition，which effectively reduces the update times of the controller as well as the communication burden of the system.Through constructing the Lyapunov function，it is proved that the states of all agents can converge asymptotically to the global optimal solution under the algorithm.In addition，the designed event-triggered condition makes the minimum inter-event time designable，which effectively excludes the Zeno behavior.Finally，simulation results verify the effectiveness of the algorithm.

Key wordsdistributed optimization;multi-agent system;convex optimization;event-triggered control