張苗苗,葉茂嬌,鄭元世

(1.西安電子科技大學機電工程學院,陜西西安 710071;2.南京理工大學自動化學院,江蘇南京 210094)

1 引言

近二十幾年來,以多無人機、多傳感器等大規(guī)模網(wǎng)絡為代表的多智能體系統(tǒng)的協(xié)調控制與優(yōu)化問題得到了學者們的極大關注[1-3].其中,分布式優(yōu)化和納什均衡點搜索問題作為多智能體系統(tǒng)優(yōu)化問題中占據(jù)重要地位的兩類優(yōu)化問題,成為了近年來的研究熱點.在分布式優(yōu)化和非合作博弈問題中,每個智能體都攜帶一個目標函數(shù).但這兩類問題的區(qū)別是:在分布式優(yōu)化問題中,每個智能體的優(yōu)化目標均為所有智能體攜帶的目標函數(shù)之和[4].主要考慮智能體如何協(xié)同的利用局部信息實現(xiàn)全局目標函數(shù)的優(yōu)化.而在博弈問題中,每個智能體的優(yōu)化目標是不相同的,分布式納什均衡點搜索問題主要研究智能體如何依賴自身信息以及與鄰居智能體之間的信息交互優(yōu)化自身的目標函數(shù),因此優(yōu)化問題中智能體之間的行為是協(xié)同的,而納什均衡點求解問題中智能體之間的行為是從自身利益出發(fā)的.

近年來,各類分布式優(yōu)化方法相繼被提出.Nedic等人在局部信息有限的情況下提出了分布式次梯度算法,在該算法中,每個智能體通過與鄰居的通信更新自身的狀態(tài)以收斂到全局最優(yōu)解[5].由于通信環(huán)境中信息交換存在不可預測性,因此任意兩個節(jié)點之間存在通信鏈路是一個隨機事件,據(jù)此Lobel等人提出了隨機網(wǎng)絡上的分布式次梯度算法,并證明了該算法可以使得多智能體以概率1收斂到系統(tǒng)的最優(yōu)解[6].文獻[7]結合近似梯度和梯度跟蹤的思想提出了一種分布式優(yōu)化算法并證明了算法的收斂性.Nedic等人提出了一類subgradient-push算法[8]以解決非平衡通信網(wǎng)絡下的分布式優(yōu)化問題,該算法需要用到每個節(jié)點的出度信息,這一方法在push-sum算法[9]的基礎上演變得到的.文獻[10]基于梯度法與投影算子等解決了帶約束的分布式優(yōu)化問題.此外,文獻[11]還考慮了含不同凸集合約束的分布式優(yōu)化問題,基于次梯度投影算法提出了一類分布式優(yōu)化協(xié)議.而文獻[12]基于一致性和次梯度算法提出了一類連續(xù)時間的優(yōu)化算法,解決含不等式約束時的分布式優(yōu)化問題,并利用狀態(tài)轉移矩陣的性質得到了智能體的狀態(tài)與優(yōu)化問題最優(yōu)解的誤差上界.為了提高算法的收斂速度,文獻[13]通過改進梯度項,利用部分歷史梯度信息,提出了一類extra優(yōu)化算法使得智能體的狀態(tài)能夠精確收斂到系統(tǒng)的最優(yōu)解.文獻[14-15]針對智能體目標函數(shù)為光滑凸函數(shù)的分布式優(yōu)化問題,提出了快速分布式優(yōu)化方法.此外,文獻[16]和文獻[17-18]分別針對原始-對偶域(primal-dual)優(yōu)化方法和zero-gradientsum優(yōu)化方法開展研究.

另外,學者們從不同的角度出發(fā),在分布式納什均衡搜索方面做出了一些有意義的工作.文獻[19-20]基于領導者跟隨一致性(leader-following consensus)協(xié)議和梯度信息提出了一類分布式納什均衡點搜索算法,并證明了該算法可以使得智能體的狀態(tài)漸近收斂到納什均衡點.文獻[21]基于leader-following一致性協(xié)議和梯度信息解決了混雜博弈問題,并證明了所提出的算法呈指數(shù)收斂.文獻[22-23]針對雙網(wǎng)絡零和博弈問題開展研究,并基于梯度算法等提出了一類分布式協(xié)議尋找具有鞍點性質的納什均衡點.文獻[24]基于飽和函數(shù)、梯度法及一致性協(xié)議解決了有界控制輸入系統(tǒng)中的分布式納什均衡搜索問題.文獻[25]提出了可線性收斂的分布式納什均衡搜索方法.

需要指出,上述分布式優(yōu)化算法/分布式納什均衡搜索算法僅能保證智能體的狀態(tài)可以漸近/指數(shù)收斂到分布式優(yōu)化問題的最優(yōu)解解/納什均衡點.這表明,分布式優(yōu)化與非合作博弈問題的精確求解需要消耗無窮時間.然而在實際工程領域中,無窮時間的收斂并不利于實際應用,多智能體系統(tǒng)往往需要在精確時間內完成任務,這使得漸近收斂的方式無法滿足實際工程領域中收斂時間的要求.當前對這一類問題的研究文獻略少,設計可在有限時間內實現(xiàn)分布式優(yōu)化與博弈問題有效求解方法兼具理論意義與實際應用價值.為此,文獻[26]設計了基于符號函數(shù)的有限時間分布式優(yōu)化方法.文獻[27]基于有限時間一致性協(xié)議與連續(xù)時間零梯度和算法提出了一類有限時間的分布式連續(xù)時間算法,利用Lyapunov方法實現(xiàn)了分布式優(yōu)化問題在有限時間內的有效求解.此外,文獻[28]也考慮了有限時間分布式優(yōu)化問題.文獻[29]則研究了固定時間分布式納什均衡搜索方法.文獻[30]利用凸分析理論和Lyapunov穩(wěn)定性理論解決了固定時間的分布式資源分配問題.

雖然文獻[26-30]中所提出的方法可在有限時間內收斂到分布式優(yōu)化問題的解或納什均衡點,這將求解方法的收斂速度從無限時間轉為有限時間.然而,這些求解方法的收斂時間受智能體的初始狀態(tài)與系統(tǒng)參數(shù)的影響并且無法提前預測,在一定程度上限制了求解方法的實際適用性.為了解決上述問題,設計一類可在預設時間內收斂的分布式優(yōu)化方法與納什均衡點搜索方法是十分必要的.在本文研究的同時期,文獻[31]假設智能體在離散采樣時間進行交互,基于采樣數(shù)據(jù)的算法和輔助變量設計了一類的優(yōu)化協(xié)議,并通過利用離散采樣時間的Lyapunov理論解決了指定時間的帶等式約束的分布式優(yōu)化問題.實際上,預設時間的控制和優(yōu)化是近幾年的研究熱點.例如,文獻[32]研究了二階多智能體系統(tǒng)的預設時間一致性跟蹤問題,并證明了多智能體系統(tǒng)中的領導者與跟隨者在預設時間內達成了一致.文獻[33]基于Lyapunov函數(shù)等實現(xiàn)了預設時間多智能體系統(tǒng)的平均一致性和包圍控制.文獻[34]建立了一類預設時間的包圍控制協(xié)議,該協(xié)議可以保證多智能體系統(tǒng)中的跟隨者可在預先設定的時間內移動到領航者狀態(tài)所構成的凸包內.文獻[35]研究了預設時間的分布式納什均衡點求解問題,該方法是根據(jù)時間函數(shù)變換方法,從而嚴格保證了所提算法的全局收斂性.此外,文獻[36]提出了一種新的針對資源分配問題的預定時間分布式優(yōu)化協(xié)議,利用一個連續(xù)可微的時間函數(shù)實現(xiàn)了預定時間的收斂.文獻[37]研究了預設時間的分布式資源分配問題,該算法采用具有指數(shù)項的非齊次函數(shù),從而達到預定時間的收斂速度.文獻[38]建立了一種新的有限時間控制方法,所提的算法可以保證跟隨者可以在任意給定的有限時間內運動到領航者狀態(tài)所圍成的凸包內,這為本文研究預設時間下的分布式優(yōu)化求解方法和納什均衡搜索算法提供了思路.

本文考慮智能體之間存在合作與非合作的行為,分別研究了預設時間的分布式優(yōu)化求解方法與納什均衡搜索方法的設計與分析,特別地,收斂時間T可以預先設置并與智能體的初始狀態(tài)和系統(tǒng)參數(shù)無關.本文的主要貢獻如下:

1) 本文針對分布式優(yōu)化與納什均衡搜索問題分別提出一類預設時間分布式優(yōu)化方法和納什均衡搜索方法.與文獻[26-30]中的固定/有限時間分布式優(yōu)化方法/納什均衡搜索方法相比,本文所提出的分布式優(yōu)化方法和納什均衡搜索方法可在任意預設時間內收斂,并且該收斂時間獨立于智能體的初始狀態(tài)與系統(tǒng)參數(shù);

2) 基于Lyapunov穩(wěn)定性理論、圖論以及矩陣理論的相關知識,給出了保證所提出的算法可以使得智能體的狀態(tài)收斂到分布式優(yōu)化問題的解/非合作博弈問題的納什均衡點的充分條件.

本文的結構安排如下:第2節(jié)介紹了相關的圖論以及凸分析理論知識,并給出了一些基本的引理和假設;第3節(jié)介紹了預設時間的分布式優(yōu)化問題,提出一類預設時間分布式優(yōu)化算法并給出了收斂性證明;第4節(jié)介紹了預設時間的分布式納什均衡點求解問題,給出了預設時間的分布式納什均衡點求解協(xié)議并證明了該協(xié)議的收斂性;第5節(jié)通過仿真算例驗證了所提分布式協(xié)議的有效性;最后給出了本文的結論.

為了便于表示,在下表中給出了文中出現(xiàn)數(shù)學符號的具體含義.

2 預備知識

本節(jié)將介紹一些預備知識,文中符號說明見表1.首先給出有關圖論以及矩陣論的相關知識:

表1 符號說明Table 1 List of symbols

無向圖若圖G中的每條邊都是沒有方向的,則稱G=(V,E,A)為無向圖,其中V={1,2,···,n}表示圖的頂點集,E ?V ×V是邊集,A=(aij)n×n為圖的鄰接矩陣,其中如果(j,i)∈E,則aij ＞0,否則aij=0,且A一定是對稱矩陣(aij=aji).智能體i的鄰居集定義為Vi={j ∈V|(j,i)∈E}[39].

拉普拉斯矩陣(Laplacian)L=D-A定義為圖的拉普拉斯矩陣,其中D為圖的度矩陣,A為圖的鄰接矩陣.拉普拉斯矩陣的基本性質為:L1n=0n,0是它的一個特征值,1n是0特征值所對應的特征向量[37].

定義1(強凸函數(shù))[40]假設S ?Rn是一個非空的凸集,f是定義在S上的實函數(shù),如果對于?x1,x2∈S及每個數(shù)λ ∈(0,1),都有

則稱f為S上的強凸函數(shù),特別地m=0時,f為凸函數(shù).

定義2(納什均衡)[19]在一個博弈過程中,如果在其他所有參與者策略確定的情況下,任意一位參與者其選擇的策略是最優(yōu)的,那么這個策略組合就被定義為納什均衡.即:是納什均衡點當且僅當

為證明本文所提協(xié)議的收斂性,下面給出一些基本的引理以及必要的假設條件.

假設1通信拓撲圖G為無向連通圖.

引理1[41]在假設1成立的前提下,矩陣Q=L+W是正定實對稱矩陣,其中L是圖G的拉普拉斯矩陣,W是正定實對角矩陣,即:W=diag{wi},wi ＞0.

引理2[42]如果矩陣Q是正定實對稱矩陣,則有以下不等式成立:

其中常數(shù)m ＞0稱為強凸函數(shù)f(x)的凸性參數(shù).

3 預設時間的分布式優(yōu)化

本節(jié)考慮智能體之間的行為是合作的,研究了基于多智能體系統(tǒng)的預設時間分布式優(yōu)化問題.考慮有n個智能體的多智能體系統(tǒng):V={1,2,···,n},在該系統(tǒng)中,每個智能體都會攜帶一個目標函數(shù)fi(z),并且對于所有的智能體i ∈V,只有智能體i能夠獲得目標函數(shù)fi(z)的信息,所有智能體通過與鄰居的交互協(xié)同的最小化每個智能體目標函數(shù)的和函數(shù).據(jù)此,分布式優(yōu)化問題描述如下:

在該優(yōu)化問題中,每個智能體通過與鄰居的交互獲得鄰居的信息從而更新自身的狀態(tài).本文的目的是設計一類預設時間的分布式優(yōu)化協(xié)議能夠使得智能體在預設時間T內通過局部信息收斂到全局目標函數(shù)的最優(yōu)解.為了設計該分布式協(xié)議,假設每個智能體i都產生一個變量xi(t)用以估計優(yōu)化問題(2)的最優(yōu)解.

因此,針對問題(2),本文在文獻[12]的基礎上結合一致性協(xié)議和梯度下降算法,提出了一類在預設時間內收斂的分布式優(yōu)化協(xié)議

其中:xi(t)∈R表示智能體i的狀態(tài),μ ＞0為控制增益,常數(shù)c ＞0,aij是鄰接矩陣A中i行j列的元素,?fi(xi(t))表示智能體i的目標函數(shù)fi(z)在z=xi(t)處的梯度,T為預設的收斂時間.

假設2智能體i的目標函數(shù)fi(z)是二階連續(xù)可微的強凸函數(shù),i ∈V.

注1由于智能體i的目標函數(shù)fi(z)是二階連續(xù)可微函數(shù),因此微分方程(3)的解存在,且也是強凸函數(shù),則z*是唯一的最小值點.因此所有智能體的狀態(tài)不僅可以在預設時間收斂到優(yōu)化問題的最優(yōu)解z*,還能夠在預設時間內達到一致.

下面給出預設時間分布式優(yōu)化問題的主要結果.

定理1如果假設1-2成立,則在協(xié)議(3)下,所有智能體的狀態(tài)在預設時間T內收斂到問題(2)的最優(yōu)解.即存在z* ∈Z*,使得=z*成立.

證此定理的證明可以通過以下步驟形成:首先,將式(3)寫成如下矩陣的形式:

其中對任意的μ ＞0,都可以選擇一個正定對角矩陣W使得以下式子成立:

則根據(jù)式(5)有

因此,當t→T時,V(t)→0,則可得當t→T時,‖δ(t)‖→0,即:=z*成立,綜上可得,協(xié)議(3)可以使得多智能體的狀態(tài)在預設時間內收斂到優(yōu)化問題(2)的最優(yōu)解. 證畢.

注2本文與文獻[31]中的兩種方法均能實現(xiàn)預設時間的收斂,并且兩種方法得到的收斂時間均獨立于系統(tǒng)參數(shù)與初始條件.但與該文獻不同的是,本文研究的是一般的分布式優(yōu)化問題min,其中z為所有局部目標函數(shù)fi的共享決策變量.因此,每個智能體i需要產生局部變量xi去估計優(yōu)化問題(2)的最優(yōu)解.并且當xi達到最優(yōu)解時,智能體的局部估計值能夠達到一致狀態(tài)(i.e.,x1=x2=···=xn=z*).而文獻[31]研究的是一類特殊的分布式優(yōu)化問題min,其中每個目標函數(shù)fi只與自身的決策變量zi有關.因此文獻[31]中的方法無法使用于本文所考慮的分布式優(yōu)化問題.

4 預設時間的分布式納什均衡求解

本節(jié)研究了預設時間下的分布式納什均衡點求解問題,與分布式優(yōu)化問題不同的是,該問題中智能體之間的行為是從自身利益出發(fā)的.考慮有n個智能體的多智能體系統(tǒng):V={1,2,···,n}表示,每個智能體i均利用局部信息調整自身的行為使得其成本最小,該問題描述如下:

其中fi(·)為每個智能體i的成本函數(shù).記為智能體i收斂到納什均衡點時成本函數(shù)的最優(yōu)值,ui為控制輸入.

在非合作博弈問題(6)中,由于假設每個智能體僅能獲得其鄰居的信息,無法得到那些非鄰居智能體的行為狀態(tài),因此每個智能體會對其他智能體的行為產生一個估計值,并利用與鄰居之間的信息交互更新估計值,然后基于梯度方法更新自身的行為狀態(tài).本文的目的是設計一類搜索協(xié)議使得每個智能體在預設時間T內通過局部信息調整自己的行為收斂到納什均衡點,從而最小化自身的成本.

在文獻[19]的基礎上,本文基于一致性協(xié)議和梯度算法,提出了一類預設時間的分布式納什均衡點求解協(xié)議

注3在假設4的條件下,問題(6)的納什均衡點存在且唯一,其中R(x)=0n的充要條件是x=x*[19].

下面給出預設時間分布式納什均衡點求解問題的主要結論.

定理2如果假設1,3-4成立,則在協(xié)議(7)下,存在一個正常數(shù)k*,使得增益k ∈(0,k*)時,所有智能體的狀態(tài)在預設時間T內能收斂到問題(6)的納什均衡,即

證此定理的證明可以通過以下步驟形成:首先,式(7)可以寫成如下矩陣的形式:

最后,對上式在[0,t]上積分得到

因此,根據(jù)式(10)可以得到

5 仿真

在本節(jié)中,本文通過兩個例子來驗證理論結果的有效性.

例1考慮由4個智能體{1,2,3,4}構成的多智能體系統(tǒng),假設智能體的通訊拓撲圖由圖1所示,每個智能體僅與自己的鄰居通信,且通信拓撲圖為無向連通圖,對應的鄰接矩陣和拉普拉斯矩陣為

圖1 例1中智能體的通信拓撲圖Fig.1 The communication topology of all agents in example 1

假設每個智能體的目標函數(shù)如下:

圖2 在協(xié)議(3)下,智能體的狀態(tài)xi(t)(i={1,2,3,4})軌跡圖(T=3)Fig.2 Under protocol (3),the trajectories of the agent’s states value xi(t)(i={1,2,3,4})(T=3)

圖3 誤差δ的收斂軌跡圖(T=3)Fig.3 Trajectories of convergence errors δ(T=3)

從仿真結果可以看出,選定的初始狀態(tài)雖然與最優(yōu)解的相差很大,但是在所設計的協(xié)議下均能夠在預設時間收斂到最優(yōu)解,這也驗證了定理1的有效性.

例2考慮由5個智能體{1,2,···,5}構成的多智能體系統(tǒng),智能體的通信拓撲圖由圖4所示,每個智能體僅與自己的鄰居通信,且通信拓撲圖為無向連通圖,對應的鄰接矩陣和拉普拉斯矩陣為

圖4 例2中智能體的通信拓撲圖Fig.4 The communication topology of all agents in example 2

從圖4中可以看出每個智能體僅與自己的鄰居通信且成本函數(shù)僅受鄰居和其自身決策的影響,假設每個智能體的成本函數(shù)如下:

其中每個成本函數(shù)fi(xi,x-i)滿足假設3-4.令系統(tǒng)參數(shù)c=1,收斂時間為T=6.

設置智能體的初始值為:x(0)=[3 2-12/37-4/9 1/2]T,yi(0)=[0 0 0 0 0]T.每個智能體根據(jù)協(xié)議(7)更新自身的狀態(tài),并存在一個正常數(shù)k*,使得k ∈(0,k*),此時得到了與理論一致的結果.

圖5表示智能體i的行為xi(t)在預設時間T=6收斂到非合作博弈問題minfi(x)的納什均衡點:x*=[0.5063 0.2564-0.0769-0.0256-0.0298]T,i={1,2,3,4,5}(令偽梯度向量R(x)=05得到唯一的納什均衡點).

圖5 協(xié)議(7)下,智能體的狀態(tài)xi(t)(i={1,2,3,4,5})軌跡圖Fig.5 Under protocol(7),the trajectories of the agent’s states value xi(t)(i={1,2,3,4,5})

圖7表示在初始估計值均為0的情況下,智能體i對智能體j的估計值yij(t)在預設時間T=6 收斂到xj(t),而每個xj(t)在預設時間收斂到納什均衡點,因此yij(t)在預設時間收斂到納什均衡點.圖6和圖8分別表示智能體的行為xi(t)與納什均衡的點的誤差和智能體i對智能體j的估計值yij(t)與納什均衡的點的誤差在預設時間T=6收斂到0,即θ和φ在預設時間T=6收斂到0.

圖6 誤差θ的收斂軌跡圖(T=6)Fig.6 Trajectories of convergence errors θ(T=6)

圖7 在協(xié)議(7)下,每個智能體對其他智能體估計值yij(t)的軌跡圖,即T=6時yij(t)→xj(t)Fig.7 Under protocol (7),the trajectories of the agent’s states value yij(t),i.e.yij(t)→xj(t)as T=6

圖8 誤差φ的收斂軌跡圖(T=6)Fig.8 Trajectories of convergence errors φ(T=6)

由仿真結果可以得到,在給定智能體的初始狀態(tài)后,智能體是可以在預設時間搜索到納什均衡點,因此驗證了定理2的有效性.

6 結論

本文基于無向圖解決了預設時間下的分布式優(yōu)化/納什均衡點求解問題,針對分布式優(yōu)化問題/納什均衡點問題結合一致性和梯度協(xié)議提出了一類預設時間的優(yōu)化算法/納什均衡點求解算法.在每個智能體僅能獲得有限信息的情況下,當智能體的目標函數(shù)是強凸函數(shù)時,通過選取適當?shù)腖yapunov函數(shù)證明了多智能體系統(tǒng)可以在預設時間內收斂到優(yōu)化問題的最優(yōu)解/非合作博弈問題的納什均衡點,特別地,收斂時間獨立于多智能體的初始狀態(tài)與系統(tǒng)參數(shù),并且可以預先設計收斂時間.仿真算例驗證了所提算法的收斂性,結果表明給定智能體的初始狀態(tài)后,智能體均能夠在所提協(xié)議下實現(xiàn)預設時間的收斂.