朱志斌,王付永,尹艷輝,劉忠信,陳增強(qiáng)

(南開大學(xué)人工智能學(xué)院,天津 300350;天津市智能機(jī)器人技術(shù)重點(diǎn)實(shí)驗(yàn)室,天津 300350)

1 引言

近年來,隨著計(jì)算機(jī)技術(shù)和網(wǎng)絡(luò)技術(shù)的不斷發(fā)展,有關(guān)多智能體系統(tǒng)協(xié)同控制方面的研究越來越多.多智能體系統(tǒng)具有單個(gè)智能體無法比擬的優(yōu)勢,可以完成單個(gè)智能體無法完成的任務(wù),因而具有更廣泛的應(yīng)用,例如:無人飛行器編隊(duì)控制、衛(wèi)星姿態(tài)控制和移動(dòng)多機(jī)器人等[1–5].

多智能體系統(tǒng)(multi-agent systems,MASs)的一致性是復(fù)雜動(dòng)力學(xué)系統(tǒng)中一個(gè)具有理論和實(shí)踐意義的重要問題.現(xiàn)有的一致性問題主要分為兩類:無領(lǐng)導(dǎo)者多智能體系統(tǒng)的一致性和領(lǐng)導(dǎo)–跟隨多智能體系統(tǒng)的一致性.對于無領(lǐng)導(dǎo)者的多智能體系統(tǒng),當(dāng)所有智能體的狀態(tài)收斂至同一值時(shí),則系統(tǒng)達(dá)到一致;對于領(lǐng)導(dǎo)–跟隨的多智能體系統(tǒng),當(dāng)系統(tǒng)中所有跟隨者的狀態(tài)趨于領(lǐng)導(dǎo)者的狀態(tài),則系統(tǒng)達(dá)到一致.基于多智能體系統(tǒng)的一致性和協(xié)同控制方面的研究[6],文獻(xiàn)[7]利用動(dòng)態(tài)輸出反饋的控制方法研究了在固定和切換拓?fù)湎露嘀悄荏w系統(tǒng)的一致性,并提出了相應(yīng)的一致性算法.為了解決線性異構(gòu)多智能體系統(tǒng)在切換拓?fù)湎碌囊恢滦詥栴},文獻(xiàn)[8]設(shè)計(jì)了一種分布式分級控制協(xié)議.對于二階非線性多智能體系統(tǒng)的一致性問題,文獻(xiàn)[9]推導(dǎo)出固定網(wǎng)絡(luò)拓?fù)湓诓糠珠g歇通信的情況下達(dá)到一致的充分條件.假設(shè)系統(tǒng)同時(shí)存在網(wǎng)絡(luò)時(shí)延與狀態(tài)時(shí)延,文獻(xiàn)[10]研究了一類二階馬爾可夫切換多智能體系統(tǒng)的一致性問題.然而,上述研究均是在模型參數(shù)已知的條件下,而面對現(xiàn)實(shí)中復(fù)雜的物理系統(tǒng),絕對精確的數(shù)學(xué)模型是難以得到的.所以,為了避免建模難度大或者模型未知的問題,設(shè)計(jì)一種基于數(shù)據(jù)的分布式控制律則更為有效.

強(qiáng)化學(xué)習(xí)作為機(jī)器學(xué)習(xí)的一種方法[11–12],以環(huán)境反饋?zhàn)鳛檩斎氩⑼ㄟ^不斷的試錯(cuò)來尋找最優(yōu)的行為策略.不同于監(jiān)督學(xué)習(xí),智能體并不知道如何做出正確的行為策略,但可以通過強(qiáng)化學(xué)習(xí)的方法對行為策略進(jìn)行評估,并根據(jù)有效反饋信息對行為策略進(jìn)行改善.同時(shí),強(qiáng)化學(xué)習(xí)的獎(jiǎng)勵(lì)函數(shù)對系統(tǒng)信息的需求更少,也更容易設(shè)計(jì),因此,強(qiáng)化學(xué)習(xí)適合解決復(fù)雜的控制問題.在有關(guān)強(qiáng)化學(xué)習(xí)的基礎(chǔ)數(shù)學(xué)研究取得突破之后,對強(qiáng)化學(xué)習(xí)的研究也越來越多[13–14].

強(qiáng)化學(xué)習(xí)還可以解決最優(yōu)控制問題,例如帶有約束的最優(yōu)控制[15–16]、帶有時(shí)延的最優(yōu)控制[17–18]、最優(yōu)跟蹤控制[19–20]、最優(yōu)一致性控制[21]等.作為強(qiáng)化學(xué)習(xí)中一種重要的方法,Q-leaning是一種無模型的學(xué)習(xí)方法.目前,已經(jīng)有很多關(guān)于Q-learning的研究,例如:跟蹤控制[22]、零和博弈[23]、魯棒控制[24]等.

經(jīng)過上述討論可知,在系統(tǒng)模型已知的前提下,文獻(xiàn)[7–10]可以很好地解決多智能體系統(tǒng)的一致性問題,但是當(dāng)系統(tǒng)模型未知時(shí),解決這一問題將變得困難.為了避免復(fù)雜的機(jī)理建模,本文提出一種Q-learning方法解決離散時(shí)間多智能體系統(tǒng)的一致性問題,主要貢獻(xiàn)如下:

1) 將Q-learning方法從單智能體拓展應(yīng)用到多智能體系統(tǒng)中,解決了離散時(shí)間多智能體系統(tǒng)模型未知時(shí)的一致性控制問題;

2) 對于多智能體強(qiáng)化學(xué)習(xí),本文在文獻(xiàn)[26]的基礎(chǔ)上對值函數(shù)的結(jié)構(gòu)進(jìn)行了優(yōu)化改進(jìn),提出了一種新的關(guān)于誤差的值函數(shù).

本文結(jié)構(gòu)安排如下:第2部分將給出基礎(chǔ)代數(shù)圖理論和問題描述;第3部分將給出的Q-learning一致性算法,并對所提算法進(jìn)行了收斂性和穩(wěn)定性分析;第4部分將通過計(jì)算機(jī)仿真驗(yàn)證所提算法的有效性;最后,第5部分將對全文工作進(jìn)行總結(jié)和展望.

2 問題描述

2.1 代數(shù)圖論

令G=(V,E,A)表示一個(gè)有向加權(quán)圖.其中:V={v1,v2,···,vN}表示具有N個(gè)節(jié)點(diǎn)的集合,E ?V ×V表示邊集,節(jié)點(diǎn)下標(biāo)集合為I={1,2,···,N}.定義矩陣A=[aij]是圖G的非負(fù)鄰接矩陣,矩陣元素aij≥0表示節(jié)點(diǎn)vi和vj之間的連接權(quán)重.當(dāng)節(jié)點(diǎn)vi可以收到來自節(jié)點(diǎn)vj的信息傳遞時(shí),則aij≥0;否則aij=0,本文所討論的圖中,aii=0,?i,j ∈I.如果aij=aji,則稱圖G是無向的,顯然無向圖對應(yīng)的加權(quán)鄰接矩陣A=[aij]是對稱的.節(jié)點(diǎn)vi的鄰居下標(biāo)集合為Ni={j|vj ∈V(vj,vi)∈E}且鄰居的個(gè)數(shù)表示為|Ni|.定義度矩陣為D=diag{di,i=1,2,···,N},為矩陣A的第i行元素的和,節(jié)點(diǎn)vi的入度和出度分別定義為.若圖G中每個(gè)節(jié)點(diǎn)的入度都等于出度,則稱圖G是平衡圖.定義圖G的Laplace矩陣為L=D ?A.對于圖中的節(jié)點(diǎn)vi和vj,存在有序下標(biāo)集合{k1,k2,···,kl},若,則稱節(jié)點(diǎn)vi和vj之間存在一條有向連接路徑.如果對于圖中任意的兩個(gè)節(jié)點(diǎn)vi和vj之間存在至少一條有向連接路徑,則稱圖G是強(qiáng)連通的.

2.2 問題描述

假設(shè)多智能體系統(tǒng)由N個(gè)智能體組成,且智能體間的通信網(wǎng)絡(luò)拓?fù)涫枪潭?、無向和連通的.給出下面的離散時(shí)間系統(tǒng)的一致性算法:

其 中:A ∈Rn×n,B ∈Rn×m和K ∈Rm×n,xi(k)∈Rn是智能體i在k=1,2,3,···時(shí)刻的狀態(tài),ui(k)∈Rm是其控制律,ε ∈(0,1/Δ)是系統(tǒng)的控制參數(shù),Δ=為網(wǎng)絡(luò)節(jié)點(diǎn)的最大出度.

假設(shè)1假設(shè)本文中的系統(tǒng)模型是確定且未知的.

控制律(2)可以用每個(gè)智能體自身信息和其鄰居智能體的信息求得,那么每個(gè)智能體和其鄰居智能體的局部誤差定義如下:

根據(jù)式(3)可以得到全局誤差向量

本文目標(biāo)是求解最優(yōu)控制律(2),使得當(dāng)k →∞時(shí),‖δ(k)‖→0,所有智能體的狀態(tài)達(dá)到一致,即

各個(gè)智能體的最終狀態(tài)滿足[6]

同時(shí)使后面第2.3節(jié)中的目標(biāo)函數(shù)式(4)最小.

2.3 值函數(shù)的定義

對于每個(gè)智能體定義一個(gè)如下所示的目標(biāo)函數(shù):

上式中的效用函數(shù)Ui(δi(k),ui(k),uj(k))定義如下:

其中:Qii >0∈Rn×n,而Rii >0∈Rm×m,Rij >0∈Rm×m均為正定對稱矩陣,0<γ≤1為折扣因子.

對每個(gè)智能體及其鄰居智能體給定控制律(ui(l),uj(l)),每個(gè)智能體的值函數(shù)定義如下

注1目標(biāo)函數(shù)(4)用來評價(jià)智能體i的性能,智能體i的值函數(shù)(6)可以收集局部信息.

定義1(容許控制[25]) 如果控制律ui(k),?i ∈I不僅可以使系統(tǒng)穩(wěn)定,還可以保證目標(biāo)函數(shù)有界,則稱其為容許控制.

在滿足容許控制律的條件下,值函數(shù)可以改寫成貝爾曼方程的形式

引理1(二次型值函數(shù)) 在滿足容許控制律的條件下,智能體i的值函數(shù)式(6)可以改寫為如下二次型的形式

證此引理的證明可以通過以下步驟完成:

步驟1根據(jù)式(3),智能體i和鄰居智能體的局部誤差動(dòng)力學(xué)方程為

根據(jù)式(9)可得

將式(11)代入式(10),得到

步驟2定義兩個(gè)塊對角矩陣

步驟3根據(jù)式(11)–(12),式(6)可以改寫為

其中

證畢.

基于貝爾曼最優(yōu)性原則,智能體i的最優(yōu)值函數(shù)滿足離散時(shí)間的Hamilton-Jacobi-Bellman(HJB)方程

定義2(納什均衡解[25]) 如果包含N個(gè)控制律的控制序列是N個(gè)智能體博弈的全局納什均衡解,那么滿足

根據(jù)定義2,智能體i的耦合離散時(shí)間HJB方程為

3 基于Q-learning的多智能體系統(tǒng)的一致性算法

對于模型未知的多智能體系統(tǒng),已有的基于模型的算法是無效的.盡管可以通過系統(tǒng)信息建立模型,但是實(shí)際系統(tǒng)中的不確定因素導(dǎo)致難以建立準(zhǔn)確的系統(tǒng)模型.由于Q-learning算法不需要構(gòu)建系統(tǒng)模型,可以利用多智能體系統(tǒng)產(chǎn)生的數(shù)據(jù)在線實(shí)時(shí)更新控制律,故本文采用此方法解決多智能體系統(tǒng)一致性問題.

3.1 Q-learning算法

基于貝爾曼方程的離散時(shí)間Q函數(shù)定義如下:

其中Q函數(shù)由智能體i及其鄰居智能體的狀態(tài)信息和控制律構(gòu)成.根據(jù)式(17),可以得到

構(gòu)造Q函數(shù)的二次型的形式

由式(21)(23)可知,在策略評估和策略迭代時(shí)不需要任何系統(tǒng)模型信息.矩陣Hi可以通過最小二乘法實(shí)時(shí)迭代求解[26].將策略迭代直接應(yīng)用到所提Q-learning算法中,給出如下算法:

步驟1初始化:對于每個(gè)智能體i,給定初始容許控制律u0i(k),?i=1,2,···,N;r=0,r表示迭代次數(shù),總的迭代次數(shù)為R;

步驟2策略評估:根據(jù)式(23)迭代求解每個(gè)智能體i的第r+1次矩陣Hi

步驟3策略迭代:利用求得的矩陣Hi更新第r+1迭代控制律

步驟4若r=R,停止迭代;否則,r=r+1并返回步驟2.

注2為了確保數(shù)據(jù)訓(xùn)練過程中對狀態(tài)空間有更充分的探索,策略迭代算法一般需要一定的激勵(lì)條件ξ,ξ是會(huì)隨著迭代次數(shù)的增加而逐漸衰減至0的.

3.2 算法的收斂性分析

為了保證系統(tǒng)穩(wěn)定,下面對所提的算法進(jìn)行收斂性分析.

假設(shè)2假設(shè)智能體之間的通信網(wǎng)絡(luò)拓?fù)鋱DG是固定、無向且連通的.

引理2[27]對i ∈I和?r ∈N值函數(shù)和控制律分別通過式(24)–(25)進(jìn)行更新.如果智能體i給定的初始控制律是容許的,那么迭代控制律也是容許的,則不僅可以使系統(tǒng)(1)穩(wěn)定,還可以保證目標(biāo)函數(shù)(4)有界.

引理3對于?i ∈I和?r ∈N,給定一個(gè)初始容許控制律(2),即,分別通過式(24)–(25)計(jì)算和,可以得到函數(shù)是單調(diào)非遞增的,即

證此引理的證明可以通過以下步驟完成:

3.3 穩(wěn)定性分析

定理2在假設(shè)1和假設(shè)2成立的條件下,系統(tǒng)(1)的每個(gè)智能體i的和分別滿足耦合離散時(shí)間HJB方程(16)和最優(yōu)控制律(15).智能體i和其鄰居的局部誤差δi(k)是漸近穩(wěn)定的,并且當(dāng)k →∞時(shí),δi(k)→0,此時(shí)所有智能體的狀態(tài)達(dá)到一致.

證根據(jù)式(21)可以得到

定義Lyapunov函數(shù)的差分

根據(jù)式(40),式(41)可改寫為

上述式(42)表明智能體i和其鄰居的誤差δi(k)是漸近穩(wěn)定的,即當(dāng)k →∞,δi(k)→0,i=1,2,···,N.最終,所有智能體的狀態(tài)將趨于一致.

證畢.

4 仿真

本節(jié)用MATLAB仿真驗(yàn)證所提算法的有效性.假設(shè)多智能體系統(tǒng)的通信網(wǎng)絡(luò)拓?fù)淙鐖D1所示,該網(wǎng)絡(luò)是一個(gè)固定無向圖,且系統(tǒng)模型未知.5個(gè)頂點(diǎn)分別代表5個(gè)智能體,智能體之間的連接權(quán)值均為1.每個(gè)智能體的動(dòng)力學(xué)方程滿足式(1),令

圖1 多智能體系統(tǒng)的通信拓?fù)銯ig.1 The communication topology of multi-agent systems

下面的圖2給出了多智能體系統(tǒng)的一致性誤差動(dòng)態(tài)曲線,可以看出在前1000次的迭代過程中,由于缺少模型信息,5個(gè)智能體之間的一致性誤差較大;在迭代至1000次至2000次時(shí),隨著不斷的獲取鄰居智能體的信息并學(xué)習(xí)過往積累的數(shù)據(jù)信息,智能體之間的一致性誤差開始減小.迭代至2000次之后,智能體之間的一致性誤差逐漸趨于0.

圖2 智能體的一致性誤差Fig.2 The consensus error of the MASs

下面的圖3給出了關(guān)于控制律的動(dòng)態(tài)曲線,可以看出在前1200次迭代過程中,由于迭代次數(shù)少還無法學(xué)習(xí)到較好的控制策略,智能體的控制律還不理想.但值得注意的是,因?yàn)檫x取了初始容許控制律,所以控制律的更新始終是有界的.從1500次迭代開始,根據(jù)過往積累的數(shù)據(jù)信息和鄰居智能體的信息,智能體開始逐漸學(xué)習(xí)并優(yōu)化控制律,但智能體之間的狀態(tài)誤差是非0的,所以智能體的控制律需要不斷更新且不為0.

圖3 智能體的控制律Fig.3 The controller of the MASs

下面的圖4給出了每個(gè)智能體狀態(tài)的動(dòng)態(tài)變化曲線,可以看出在迭代至0～1500次時(shí),由于缺少模型信息,智能體的狀態(tài)無法達(dá)到一致;從1500次開始,經(jīng)過學(xué)習(xí)過往積累的數(shù)據(jù)信息不斷更新控制律ui(k),每個(gè)智能體的狀態(tài)開始逐漸趨于一致.圖5是智能體狀態(tài)的三維坐標(biāo)圖.

圖4 智能體的狀態(tài)Fig.4 The dynamics of the MASs

圖5 智能體狀態(tài)三維坐標(biāo)圖Fig.5 3-D phase plane plot of the dynamics of the MASs

5 結(jié)論

本文研究在系統(tǒng)模型未知的情況下一類離散時(shí)間多智能體系統(tǒng)的一致性問題.論文提出了一種Q-learning的方法,這種方法避免了復(fù)雜的系統(tǒng)建模與HJB方程求解,利用系統(tǒng)數(shù)據(jù)進(jìn)行策略迭代得到理想控制律,實(shí)現(xiàn)多智能體系統(tǒng)的狀態(tài)一致.為了保證系統(tǒng)穩(wěn)定,論文給出了所提算法的收斂性和穩(wěn)定性分析.最后,通過MATLAB仿真驗(yàn)證了所提方法的有效性.未來研究工作可以針對如何利用強(qiáng)化學(xué)習(xí)方法解決一類模型隨機(jī)的多智能體系統(tǒng)的一致性問題進(jìn)行研究.