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

時俠圣 楊 濤 林志赟 王雪松

隨著控制技術的發展,將控制技術與優化算法相結合,以分布式方式求解網絡優化問題成為近年來的研究熱點[1-7].作為網絡優化領域里一個重要分支,資源分配在網絡系統中有很廣泛的應用,例如能源系統中的經濟調度和通訊網絡中的網絡利用率最優化等問題.

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

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

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

本文所提算法創新點如下:

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

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

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

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

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

1 問題描述及預備知識

1.1 問題描述

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

1.2 代數圖論

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

2 分布式連續時間控制算法

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

2.1 算法設計

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

2.2 算法收斂性分析

3 案例仿真

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

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

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

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

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

表1 案例1 各節點參數Table 1 System parameters in case 1

案例2.針對4 節點環形網絡,其中資源決策變量xi∈R2,且節點目標函數分別為

其中

虛擬資源量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,算法控制參數設定為α=2,β=75,γ=30,μ= 0.2,ν=2.其仿真曲線分別如圖4 和圖5 所示,星點表示各節點的最優解位置.通過仿真案例2 可以發現,本文所設計算法對高維資源分配問題亦是有效的.為了展示各算法在二維資源分配問題上的收斂速度,現將本文所設計算法與文獻[43]進行對比,收斂速度圖展示在圖6,從圖中可以看出,指數收斂算法 (9)比漸近收斂算法 (8)收斂稍快,該結果與一維資源問題圖3 所得結論一致.

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

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

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

案例3.針對IEEE-39 總線系統,包含10 個發電單元,各發電單元的通信鏈路及其權重如下圖7 所示.各發電單元的發電成本為且有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.各節點的局部不等式約束和虛擬分配量分別為xi∈[0,300] 和di=250.以零初始狀態出發,在控制參數α=2.75,β=380,γ=30作用下,算法 (8)和 (9)各自對應的狀態軌跡如圖8 和圖9 所示.此外兩種算法的誤差e軌跡如圖10所示,其中誤差e定義同案例1.從圖10可知,上述系統最終收斂到最優分配方案x*=[243.6524,300,216.5298,268.1785,289.1107,251.5626,275.1839,238.0504,143.4557,274.2760].

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

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

圖9 案例3 中算法 (9)各節點仿真結果軌跡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 總結

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