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

陳 剛 李志勇

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

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

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

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

1 問題描述和預(yù)備知識(shí)

1.1 問題描述

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

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

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

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

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

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

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

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

1.2 代數(shù)圖論

1.3 相關(guān)引理

下面的引理推廣文獻(xiàn)[29]中引理1,使得本文的控制參數(shù)不依賴?yán)绽咕仃嚨淖钚》橇闾卣髦?

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

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

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

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

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

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

對(duì)式(21)右側(cè)第1 項(xiàng)應(yīng)用引理2,可得

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

注 4.本文研究的分布式固定時(shí)間優(yōu)化問題假設(shè)通信拓?fù)涫菬o向連通的,該假設(shè)在現(xiàn)有分布式優(yōu)化問題的研究中是普遍的,如文獻(xiàn)[7-20,30-31]也使用相同的假設(shè).我們未來將進(jìn)一步考慮更一般的通信拓?fù)淝闆r,如文獻(xiàn)[3-5]考慮的聯(lián)合連通圖、文獻(xiàn)[6]考慮的強(qiáng)連通有向圖.

3 數(shù)值仿真

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

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

接下來,進(jìn)行智能體局部集合約束不同情形下的優(yōu)化仿真研究.4 個(gè)智能體的局部集合約束分別設(shè)置為 Ω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)點(diǎn).

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

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

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

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

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

4 結(jié)束語

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