集合約束下多智能體系統(tǒng)分布式固定時間優(yōu)化控制

陳 剛 李志勇

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

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

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

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

1 問題描述和預備知識

1.1 問題描述

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

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

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

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

為實現(xiàn)多智能體系統(tǒng)(1)在固定時間內(nèi)求解優(yōu)化問題(3),本文給出如下假設.

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

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

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

1.2 代數(shù)圖論

1.3 相關引理

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

2 分布式固定時間優(yōu)化控制算法

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

2.1 相同局部集合約束下的分布式優(yōu)化

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

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

證明.選擇如下李雅普諾夫函數(shù)

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

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

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

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

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

2.2 不同局部集合約束下的分布式優(yōu)化

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

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

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

證明.選取如下李雅普諾夫函數(shù)

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

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

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

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

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

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

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

3 數(shù)值仿真

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

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

接下來,進行智能體局部集合約束不同情形下的優(yōu)化仿真研究.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 函數(shù)求得最優(yōu)解為[x1,x2]≈[4.00,4.29].圖2 給出控制協(xié)議(43)下智能體的狀態(tài)軌跡.由圖可知,所有智能體的狀態(tài)在1.9 s 內(nèi)收斂到公共約束集合內(nèi)的最優(yōu)點.

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

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

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

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

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

4 結(jié)束語

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