集合約束下多智能體系統分布式固定時間優化控制

陳 剛 李志勇

分布式優化在多機器人系統、傳感器網絡、機器學習等領域應用前景廣闊,因此成為了當前的一個研究熱點[1-2].基于多智能體系統框架的各種分布式算法被相繼提出并用于解決各類優化問題[3-16].文獻[3]利用離散時間一致性和次梯度法求解無約束分布式優化問題.文獻[4]采用分布式投影次梯度法解決帶集合約束的優化問題.基于原始對偶最優解的鞍點特征,文獻[5]設計分布式原始對偶次梯度算法,求解帶等式和不等式約束的優化問題.文獻[6]采用一種近似梯度算法求解無精確梯度信息的受約束分布式凸優化問題.文獻[7]利用一種基于投影梯度的分布式分層算法求解受集合約束的大規模多簇優化問題.文獻[8]應用一種分布式優化最小化方法來解決拉普拉斯正則化問題.利用連續時間動力學系統分析工具[9-16],分布式連續時間算法也得到廣泛的關注.文獻[10]采用一種基于零梯度和原理的分布式連續時間算法求解無約束優化問題.文獻[11]給出一種分布式連續時間算法,使得智能體狀態量收斂到約束集合內的最優一致值.基于拉格朗日乘子法和KKT (Karush-Kuhn-Tucker)條件,文獻[12]給出一種求解帶局部不等式約束的分布式連續時間優化算法.文獻[13]采用基于神經動力學的分布式計算方法求解帶全局耦合約束的凸優化問題.文獻[14]采用分布式比例積分協議求解受約束最優化問題.文獻[15]研究時變目標函數下的分布式無約束優化問題.

收斂速率是評價算法性能的重要指標之一.基于線性協議的分布式優化算法[3-16]僅實現漸近或指數收斂,理論上在時間趨于無窮時獲得最優解,這導致實際應用中只能得到次優解.然而,一些實際應用需要快速求取優化解,例如燃料有限的宇宙飛船交會對接問題,能源系統的在線實時調度等問題.為加速算法的收斂速度,近年來分布式有限時間收斂算法得到廣泛關注[17-20].基于分布式零梯度和優化算法[10]和有限時間一致性方法,文獻[17]給出一種有限時間分布式一致性優化算法.文獻[18]針對時變目標函數優化問題,提出一種基于二階多智能體系統的分布式有限時間算法.文獻[19]利用梯度符號信息,提出一種分布式有限時間優化算法.文獻[17-19]僅考慮無約束優化問題.文獻[20]提出的分布式有限時間優化算法能處理非一致梯度增益和集合約束.雖然有限時間控制擁有收斂速率快、干擾抑制性好、魯棒性強等優點[21-23],但其收斂時間的上界取決于系統初始狀態,且隨著初始值的增大而增大.當系統初始狀態未知時,收斂時間難以預先估計.

為克服有限時間控制的不足,文獻[24]提出了固定時間穩定的概念,固定時間控制使得收斂時間的上界不依賴系統初始狀態,僅與控制參數相關.分布式固定時間一致性算法已得到廣泛研究[25-29].對于帶約束的優化問題,分布式固定時間一致性算法往往不能直接用于求解.目前關于分布式固定時間優化算法還未得到廣泛研究.對于無約束優化問題,文獻[30]的分布式算法能實現智能體狀態量的固定時間一致性,而最優解為漸近收斂.文獻[31]利用分布式固定時間算法求解帶等式約束的優化問題.

受現有研究的啟發,本文利用時變增益法和固定時間投影法,提出一類新的分布式算法,用于求解集合約束下多智能體系統凸優化問題.提出的固定時間投影法既能處理智能體相同局部集合約束的情況,也易于處理智能體不同局部集合約束的情形.不同于現有漸進收斂算法[3-16],本文的算法能在固定時間內收斂于最優解.采用固定時間李雅普諾夫函數法嚴格證明了算法的固定時間收斂特性.在滿足全局目標函數強凸的條件下,本算法允許局部目標函數是非凸的.

1 問題描述和預備知識

1.1 問題描述

考慮由n個智能體組成的多智能體系統,每個智能體的動力學模型由如下的連續時間單積分器描述

其中,xxxi ∈Rm表示第i個智能體的狀態,uuui ∈Rm為第i個智能體的控制輸入.本文將設計控制輸入uuui使得多智能體系統在固定時間內求解如下帶集合約束的優化問題

其中,全局目標函數f(xxx)為每個智能體的局部目標函數fi(xxx):Rm →R 之和;Ωi ?Rm為閉凸集合,表示第i個智能體的局部集合約束;fi(xxx) 和 Ωi為第i個智能體的局部信息.優化問題(2)等價于如下優化問題

優化問題(2) 和(3) 有廣闊的工程應用范圍.例如,智能電網中儲能系統的優化管理和電力負載的最優分配[12,30,32],傳感器網絡中未知參數的估計和未知目標的定位[32-33],機器學習中基于損失函數最小化的模型擬合[1].

為實現多智能體系統(1)在固定時間內求解優化問題(3),本文給出如下假設.

假設 1.局部目標函數fi(xxx)是連續可微的,全局目標函數f(xxx)是強凸的.

假設 2.所有局部閉凸集合 Ωi的交集是非空的,即 Ω?.

注 1.假設1 和假設2 意味著優化問題(2)有唯一最優解[35].全局目標函數的強凸性不要求所有局部目標函數是強凸的(或者凸),這意味著本文的假設允許某些局部目標函數是非凸的,仿真實例將進一步說明.

1.2 代數圖論

1.3 相關引理

下面的引理推廣文獻[29]中引理1,使得本文的控制參數不依賴拉普拉斯矩陣的最小非零特征值.

2 分布式固定時間優化控制算法

在本節,首先解決智能體相同局部集合約束下的優化問題(2),即 Ωi=Ωj=Ω 時的情形;然后考慮局部約束集合不同的情形.

2.1 相同局部集合約束下的分布式優化

其中,k1,k2,c1,c2為正的增益,T2,T3為設定的時間參數.由引理5 和后續的分析過程可知,時變增益的時間參數T直接影響控制器的收斂時間.理論上,時間參數T2,T3可以設置為任意正常數以滿足任務需求;而實際應用中,時間參數會受物理設備的約束.因此,該參數可在物理允許的范圍內根據期望的收斂時間值直接設置.

引理 6.當假設1 和假設2 成立,在控制協議(15)的作用下,每個智能體的狀態量在固定時間內收斂到約束集合,即存在一個固定時間T1,當t ≥T1時,xxxi=PΩ(xxxi),?i.

證明.選擇如下李雅普諾夫函數

對式(21)右側第1 項應用引理2,可得

引理 7.如果多智能體系統的無向通信拓撲是連通的,且假設1 和假設2 成立,多智能體系統(1)在控制協議(15)作用下,且增益k3≥2n時,所有智能體的狀態量在固定時間T1+T2內實現一致.

證明.由引理6 可知,當t≥T1時,有xxxi=PΩ(xxxi).因此當t≥T1時,智能體的動態特性可描述為

對式(28)右側的第ItemⅠ項,考慮到通信圖G是無向且連通的,可得

應用引理5 可知,V3在固定時間T3內收斂到0,即當t≥T1+T2+T3時,有xxxi=xxx*(?i),這表明智能體的狀態量在固定時間內收斂到最優解.因此控制協議(15)作用下的多智能體系統(1)在固定時間內求解相同局部集合約束下的優化問題(2).□

2.2 不同局部集合約束下的分布式優化

本小節進一步推廣控制協議(15)以處理不同局部集合約束下的優化問題(2).此時,控制協議uuui設計為

其中,各個參數的定義與式(15)一致.不同于協議(15)只能解決所有智能體具有相同局部集合約束下的優化問題,協議(43)通過等式右側第2 項來處理不同局部約束投影的影響,使得協議(43)能解決不同智能體具有不同局部集合約束下的優化問題.因此協議(43)解決的問題比協議(15)更廣泛.而從另一方面看,由于協議(15)比協議(43)少一項,在解決相同局部集合約束下的優化問題(2)時,協議(15)有相對少的計算量.

引理 8.當假設1 和假設2 成立,在控制協議(43)作用下,每個智能體狀態量在固定時間內收斂到約束集合,即存在一個固定時間T1,當t≥T1時,?i,xxxi=PΩi(xxxi).

證明.選取如下李雅普諾夫函數

定理 2.如果多智能體系統的無向通信拓撲是連通的,且假設1 和假設2 成立,多智能體系統(1)在控制協議(43)作用下,且增益k3≥2n時,智能體的狀態量在固定時間內收斂于不同局部集合約束下優化問題(2)的解.

證明.由引理8 可知,當t≥T1時,智能體的動態特性可描述為

對式(47)應用引理7 可知,智能體的狀態在固定時間T1+T2內實現一致,即xxxi=∈Ω.因此當t ≥T1+T2,智能體的動力學特性為

最后,采用與定理1 相同的分析可得,在固定時間T1+T2+T3后,所有智能體的狀態滿足xxxi=xxx*.因此控制協議(43)下的多智能體系統(1)在固定時間求解不同局部集合約束下的優化問題(2).□

注 2.文獻[29]固定時間一致性協議的增益參數依賴于拉普拉斯矩陣的最小非零特征值;而本文的控制協議放寬了該條件.基于改進的引理5,控制協議(15)和(43)的控制增益參數k3只與智能體的個數有關.如果智能體個數是未知的,可以利用固定時間一致性協議來估計.例如,每個智能體賦予一個輔助變量,令一個智能體的輔助變量初值為1且其余智能體的輔助變量初值為0,應用固定時間平均一致性協議,可得到平均值 1/n,從而獲得智能體的個數.因此,本文提出的算法能以全分布式的方式實現.

注 3.注意到本文證明過程中所選擇的李雅普諾夫函數V1,V2,V3,V4均不依賴通信拓撲.因此,這些函數能作為公共李雅普諾夫函數來分析固定時間優化算法在時變拓撲下的穩定性.

注 4.本文研究的分布式固定時間優化問題假設通信拓撲是無向連通的,該假設在現有分布式優化問題的研究中是普遍的,如文獻[7-20,30-31]也使用相同的假設.我們未來將進一步考慮更一般的通信拓撲情況,如文獻[3-5]考慮的聯合連通圖、文獻[6]考慮的強連通有向圖.

3 數值仿真

首先進行相同局部集合約束下的優化仿真研究.仿真中,所有智能體的局部集合約束均設置為Ω={xxx ∈R2|5≤x1≤13,5≤x2≤13}.為說明分布式算法的正確性,通過MATLAB 的fmincon 函數求得最優解為 [x1,x2]≈[5.00,5.00].根據定理1,對任意初始狀態,控制協議(15)在固定時間1.9 s內求解優化問題.由圖1 的仿真結果可見,所提出的分布式協議(15)在1.9 s 內使得所有智能體的狀態到達集合約束內的最優點,即在固定時間內求解優化問題.

圖1 相同局部集合約束下優化問題(2)的仿真結果Fig.1 Simulation results for optimization problem (2) with a common constraint set

接下來,進行智能體局部集合約束不同情形下的優化仿真研究.4 個智能體的局部集合約束分別設置為 Ω1={xxx ∈R2|0≤x1≤10,0≤x2≤8},Ω2={xxx ∈R2|-4≤x1≤12,1≤x2≤10},Ω3={xxx ∈R2|2≤x1≤14,-4≤x2≤12},Ω4={xxx ∈R2|4≤x1≤16,3≤x2≤14}.通過fmincon 函數求得最優解為[x1,x2]≈[4.00,4.29].圖2 給出控制協議(43)下智能體的狀態軌跡.由圖可知,所有智能體的狀態在1.9 s 內收斂到公共約束集合內的最優點.

圖2 不同局部集合約束下優化問題(2)的仿真結果Fig.2 Simulation results for optimization problem (2)with nonidentical local constraint sets

為展示本文提出的優化控制算法的優越性,下面進行本文算法與文獻[17,30]算法的比較研究.為方便,文獻[17]提出的分布式有限時間零梯度和優化算法與文獻[30]提出的基于固定時間一致性的分布式優化算法分別寫為

正如引言中所述,傳統有限時間一致性算法(如文獻[21-23,25-29])通常無法直接解決優化問題.從式(50)和式(51)可知,文獻[17]的算法是一種基于時變權重的有限時間加權一致性優化算法,文獻[30]的算法是一種結合固定時間一致性和梯度法的漸近優化算法.在這個仿真中,采用前一個案例研究的通信拓撲,算法的增益參數設置為相同值,每個智能體的成本函數為

圖3 展示了幾種算法在不同初始條件下狀態誤差范數‖XXX -XXX*‖2隨時間的變化過程,其中由圖3 可知,本文提出的分布式優化算法在設計的固定時間內從任意初始點收斂到最優點;文獻[17]的分布式優化算法在有限時間內收斂到最優點,但收斂時間隨初值的增長而增長;文獻[30]的分布式優化算法漸近的收斂到最優點.因此,固定時間優化比漸近時間優化和有限時間優化有優勢.此外應注意兩點:一是文獻[17]和文獻[30]的算法僅解決無約束優化問題,而本文提出的算法解決帶集合約束的優化問題;二是文獻[17]的算法需要每個局部目標函數是二次連續可微的強凸函數,文獻[30]的算法需要每個局部目標函數是類二次型的,而本文提出的算法僅需要連續可微的全局目標函數是強凸的,允許局部目標函數是非凸的.

圖3 幾種算法在不同初始條件下狀態誤差范數‖XXX -XXX*‖2 隨時間的變化Fig.3 The state errors norm of several algorithms‖XXX -XXX*‖2 with time for various initial conditions

4 結束語

本文研究帶集合約束優化問題的分布式快速求解算法.首先,對于智能體相同局部集合約束下的優化問題,基于固定時間投影和時變增益技術,提出一個分布式固定時間優化算法.接著,該算法推廣到智能體不同局部集合約束情形.所提出的分布式算法使得多智能體系統在固定時間內解決帶集合約束的優化問題,算法的收斂時間能根據任務需求來預先設計.在后續研究中,我們將進一步考慮有向通信拓撲和高階動態系統下的分布式固定時間優化問題.