基于連續(xù)時間的二階多智能體分布式資源分配算法

時俠圣 楊 濤 林志赟 王雪松

隨著控制技術(shù)的發(fā)展,將控制技術(shù)與優(yōu)化算法相結(jié)合,以分布式方式求解網(wǎng)絡優(yōu)化問題成為近年來的研究熱點[1-7].作為網(wǎng)絡優(yōu)化領(lǐng)域里一個重要分支,資源分配在網(wǎng)絡系統(tǒng)中有很廣泛的應用,例如能源系統(tǒng)中的經(jīng)濟調(diào)度和通訊網(wǎng)絡中的網(wǎng)絡利用率最優(yōu)化等問題.

近些年來,基于離散時間算法的分布式優(yōu)化問題已經(jīng)得到了一些很好的結(jié)果.例如,文獻[8-10]等針對有約束或無約束最優(yōu)協(xié)調(diào)問題設計了一種基于梯度的算法.而對于強連通有向網(wǎng)絡下的資源分配問題,文獻[11-13]等基于多智能體一致性理論,分別設計一種基于余量和基于Push-sum (推和)的分布式優(yōu)化算法.更多離散時間算法可參考文獻[14-19]及它們的引用文獻,其中收斂速度最快的為文獻[17]的線性收斂,但是依然無法預知其收斂時間.另一方面,隨著信息物理系統(tǒng)和連續(xù)時間控制技術(shù)的發(fā)展[20-25],利用基于連續(xù)時間的分布式控制策略也已被廣泛應用于解決資源分配問題,特別是其中的有限/固定/預定時間收斂理論,更符合實際系統(tǒng)需求.為了解決無向網(wǎng)絡下的無約束資源分配問題,基于多智能體一致性理論,文獻[26]設計了一種指數(shù)收斂速度二階連續(xù)時間算法.不同于文獻[26]的漸近式收斂,文獻[27-30]分別設計一種基于固定時間和預定時間收斂的連續(xù)時間算法.在此基礎(chǔ)上,文獻[31-35]提出了一種考慮不等式約束的分布式算法,該算法利用映射算子將節(jié)點狀態(tài)限制在不等式約束集合內(nèi),從而得到了一種無初值約束分布式算法,并在文獻[35]中實現(xiàn)了固定時間收斂.與映射法不同,文獻[36-38]和文獻[39]利用精確罰函數(shù)法將局部等式約束轉(zhuǎn)移到目標函數(shù)中,分別設計了一階和二階連續(xù)時間算法.而對于有向網(wǎng)絡下的資源分配問題,也有很多學者提出了解決方法,例如奇異攝動算法[40]、原始對偶算法[41]、映射法[42]、二階連續(xù)時間算法[43]以及微分映射法[44].

從前面的討論可以看出,目前只有一階分布式優(yōu)化算法在連續(xù)時間和離散時間情況下都取得了顯著的效果.而有關(guān)二階多智能體分布式優(yōu)化算法的文獻不是很多.其中文獻[26,45-46]研究了無約束資源分配問題,并沒有將節(jié)點局部不等式約束考慮進來.但在許多工程應用中,節(jié)點的決策會受到局部約束,這些約束可能來自安全考慮、生產(chǎn)能力、執(zhí)行能力等,如電力系統(tǒng)中發(fā)電機的輸出功率的邊界限制[1].文獻[39]和文獻[43]分別利用精確罰函數(shù)法和微分映射法解決了資源分配問題中的局部不等式約束.但是上述兩篇文獻所提出的算法都對初始狀態(tài)進行限定.而這種初始化協(xié)調(diào)過程可能只適應于靜態(tài)網(wǎng)絡.然而對于一個動態(tài)網(wǎng)絡來說,一旦網(wǎng)絡發(fā)生變化或者節(jié)點生產(chǎn)約束發(fā)生突變時,就必須重新分配資源配置更改.因此這些優(yōu)化算法重新啟動時,必須重新進行初始化協(xié)調(diào),這大大降低了它們的適用性.此外,文獻[26,39,45-46]中考慮的都是無向網(wǎng)絡.

然而,由于通信延遲等造成的通信中斷會使得無向網(wǎng)絡變成有向網(wǎng)絡,進而可能會使得一些基于無向網(wǎng)絡的分布式算法失效.另外,無向網(wǎng)絡是有向平衡網(wǎng)絡的一個特例,在工程應用中,有向平衡網(wǎng)絡比無向網(wǎng)絡也更易于實現(xiàn),因此研究有向平衡網(wǎng)絡上的資源分配問題是有意義的.由于二階多智能體系統(tǒng)的廣泛存在,如:移動機器人、發(fā)電機等,本文考慮二階多智能體的分布式資源分配問題.針對有向平衡網(wǎng)絡下的資源分配問題,本文首先利用局部不等式及其梯度設計第一種算法,其次利用固定時間理論和映射算子設計第二種算法,其中映射算子用于處理不等式約束,且確保此不等式在固定時間內(nèi)即可滿足,此方法可推廣到同類型帶局部不等式約束的分布式優(yōu)化問題中.

本文所提算法創(chuàng)新點如下:

1) 相比于文獻[26,45-46],本文將二階多智能體節(jié)點的局部不等式約束考慮進來;

2) 與文獻[39]的無向網(wǎng)絡相比,我們研究有向平衡網(wǎng)絡下的資源分配問題;

3) 相比于文獻[43],本文所提兩種算法均對初始值無要求,且分別實現(xiàn)漸近和指數(shù)收斂;

4) 針對節(jié)點局部不等式約束,本文結(jié)合了固定時間收斂理論和映射算子,使得收斂速度上會比單純使用映射算子方法的算法要快,并通過案例仿真可以驗證此性質(zhì).

本文后續(xù)內(nèi)容結(jié)構(gòu)如下:在第1 節(jié)中,將完成問題描述以及預備知識,其中預備知識包括代數(shù)圖論、固定時間收斂理論等;在第2 節(jié)中,首先進行算法設計,分別是漸近收斂算法和指數(shù)收斂算法,其次給出相應的最優(yōu)性引理以及各自算法的收斂性分析;在第3 節(jié)中,給出3 個仿真案例;本文的總結(jié)與展望放在第4 節(jié)中.

1 問題描述及預備知識

1.1 問題描述

本文所研究的二階多智能體系統(tǒng)包含n個智能體節(jié)點,每個智能體i都采用如下動力學模型:

1.2 代數(shù)圖論

針對式 (1)所示的多智能體系統(tǒng),智能體節(jié)點間的通信鏈路可以用圖G=(V,E,A) 表示,其中V={1,2,···,n} 表示節(jié)點集合,E表示節(jié)點間的通信鏈路集合,A表示各節(jié)點間的通信權(quán)重.若存在有向?qū)?(i,j)∈E,則表示節(jié)點i能夠接收到來自節(jié)點j的信息,此時就有aij＞0.此外,本文中不考慮節(jié)點存在自環(huán),即aii=0.若網(wǎng)絡G中存在一組有向?qū)?(i,i1),(i1,i2),···,(ik,j),則稱節(jié)點j到節(jié)點i是可達的.若網(wǎng)絡G任意一點到其他節(jié)點都是可達的,則稱網(wǎng)絡G是強連通的.定義網(wǎng)絡G的拉普拉斯矩

2 分布式連續(xù)時間控制算法

針對問題 (2),基于多智能體固定時間理論,本節(jié)將設計兩種基于映射的分布式優(yōu)化算法,首先設計一類漸近收斂算法,其次設計一類指數(shù)收斂算法,并給出算法的收斂性分析.

2.1 算法設計

由引理1 可知,解決問題 (2)的關(guān)鍵是找到最優(yōu)拉格朗日乘子.為實現(xiàn)算法分布式演化,本文為每個智能體都分配一個本地拉格朗日乘子λi∈Rm,基于狀態(tài)反饋和梯度下降法,利用局部不等式約束的梯度信息,每個節(jié)點將通過以下算法自主收斂到問題 (2)的最優(yōu)分配方案:

2.2 算法收斂性分析

3 案例仿真

現(xiàn)在我們提供仿真案例來驗證之前所提算法的有效性.第一個案例數(shù)據(jù)來自文獻[43],第二個仿真案例數(shù)據(jù)來自文獻[44].

案例 1.針對6 發(fā)電機系統(tǒng),每個發(fā)動機的代價函數(shù)采用如下二次函數(shù)形式:各發(fā)電機代價函數(shù)系數(shù)、初始值xi(0)、期望功率di和輸出功率約束總結(jié)在表1 中.令算法(8)和算法(9)中控制參數(shù)為α=2.75,β=380,γ=30,μ=0.5,ν=2.從任意初始狀態(tài)出發(fā),詳細的仿真軌跡分別如如圖1和圖2所示,從圖中可知問題的最優(yōu)值為x*=[23.01;35;50;31.01;45.78;30.19]T,此結(jié)果與文獻[43]一致.相比于算法(8)中的梯度法,由于算法(9)采用映射算子和固定時間收斂理論處理問題(2)中的局部不等式約束,所以算法(9)可以很快地將超出約束范圍的節(jié)點快速拉回到約束范圍內(nèi).所以圖1 相比圖2,在算法到達約束邊界時,有更大的波動性.基于案例1 中的數(shù)據(jù),接下來從同一初始狀態(tài)出發(fā),將本文所設計算法與文獻[43]和文獻[39]進行收斂速度對比,結(jié)果如圖3 所示(文獻[43]中控制參數(shù)設置與本文相同).其中算法誤差定義為,其中最優(yōu)值由集中式拉格朗日乘子法求得.則e表示算法運行解與理論最優(yōu)解的差值.從圖3 可以看出,本文所設計算法下誤差下降較快,即擁有更快的收斂速度,且算法在穩(wěn)定點時有更好的穩(wěn)定性.而文獻[39]由于在端點處梯度不唯一,會導致算法在穩(wěn)定點時有輕微波動.此外,算法 (9)和文獻[39]在邊界點的波動性導致其誤差e要比算法 (8)和文獻[43]中的誤差稍大.

圖1 案例1 中算法(8)的各發(fā)電機曲線圖Fig.1 The trajectories of each generator by algorithm (8) in case 1

圖2 案例1 中算法(9)的各發(fā)電機曲線圖Fig.2 The trajectories of each generator by algorithm (9) in case 1

圖3 基于案例1 數(shù)據(jù)的算法性能對比Fig.3 The comparison between the existence algorithms and ours based on case 1

表1 案例1 各節(jié)點參數(shù)Table 1 System parameters in case 1

案例2.針對4 節(jié)點環(huán)形網(wǎng)絡,其中資源決策變量xi∈R2,且節(jié)點目標函數(shù)分別為

其中

虛擬資源量d設定為d1=[2,1]T,d2=[2,3]T,d3=[2,4]T,d4=[1,5]T.算法初始值設定為x1(0)=[2,0]T,x2(0)=[1.5,0.5]T,x3(0)=[1,1]T,x4=[4,6]T,算法控制參數(shù)設定為α=2,β=75,γ=30,μ= 0.2,ν=2.其仿真曲線分別如圖4 和圖5 所示,星點表示各節(jié)點的最優(yōu)解位置.通過仿真案例2 可以發(fā)現(xiàn),本文所設計算法對高維資源分配問題亦是有效的.為了展示各算法在二維資源分配問題上的收斂速度,現(xiàn)將本文所設計算法與文獻[43]進行對比,收斂速度圖展示在圖6,從圖中可以看出,指數(shù)收斂算法 (9)比漸近收斂算法 (8)收斂稍快,該結(jié)果與一維資源問題圖3 所得結(jié)論一致.

圖4 案例2 中算法 (8)的各節(jié)點仿真結(jié)果軌跡Fig.4 The trajectories of each agent by algorithm (8) in case 2

圖5 案例2 中算法 (9)各節(jié)點仿真結(jié)果軌跡Fig.5 The trajectories of each agent by algorithm (9) in case 2

圖6 基于案例2 數(shù)據(jù)的算法性能對比Fig.6 The comparison between the existence algorithms and ours based on case 2

案例3.針對IEEE-39 總線系統(tǒng),包含10 個發(fā)電單元,各發(fā)電單元的通信鏈路及其權(quán)重如下圖7 所示.各發(fā)電單元的發(fā)電成本為且有a1=[0.096 0.082]T∈R10和a2=[1.22,3.41,2.53,4.02,2.90,0.072,0.105,0.082,0.078,0.90,0.085,0.092,0.155,2.72,1.22,4.20,3.53,3.02]T∈R10,其中a1=[a1,1,···,an,1],a2=[a1,1,···,an,1]∈R10.各節(jié)點的局部不等式約束和虛擬分配量分別為xi∈[0,300] 和di=250.以零初始狀態(tài)出發(fā),在控制參數(shù)α=2.75,β=380,γ=30作用下,算法 (8)和 (9)各自對應的狀態(tài)軌跡如圖8 和圖9 所示.此外兩種算法的誤差e軌跡如圖10所示,其中誤差e定義同案例1.從圖10可知,上述系統(tǒng)最終收斂到最優(yōu)分配方案x*=[243.6524,300,216.5298,268.1785,289.1107,251.5626,275.1839,238.0504,143.4557,274.2760].

圖7 案例3 中各發(fā)電單元的通信鏈路Fig.7 The communication links of each generator in case 3

圖8 案例3 中算法 (8)的各節(jié)點仿真結(jié)果軌跡Fig.8 The trajectories of each agent by algorithm (8) in case 3

圖9 案例3 中算法 (9)各節(jié)點仿真結(jié)果軌跡Fig.9 The trajectories of each agent by algorithm (9) in case 3

圖10 案例3 中算法 (8)和 (9)的收斂速度比較Fig.10 The convergence rate comparison between algorithms (8) and (9) in case 3

4 總結(jié)

本文針對有向平衡網(wǎng)絡下的帶約束分布式資源分配問題,基于固定時間映射算子和基于多智能體一致性的梯度下降法,設計了兩種基于二階多智能體系統(tǒng)的連續(xù)時間算法.所設計算法對節(jié)點初始狀態(tài)無約束,并且控制參數(shù)全為常數(shù).通過對一維和二維資源分配問題數(shù)值仿真,本文所提算法的有效性也得以保證.然而在實際系統(tǒng)中,通信網(wǎng)絡通常會存在信息交互延遲,而信息延遲給算法分析帶來了很大的困難.此外,非平衡有向網(wǎng)絡在實際系統(tǒng)中也是存在的,所以在后續(xù)研究中,我們將考慮由通信延遲等造成的有向非平衡網(wǎng)絡下二階多智能體資源分配問題.