多智能體系統(tǒng)的包含控制研究

王雅

（成都工業(yè)學(xué)院 教務(wù)處 四川省成都市 611730）

1 引言

多智能體系統(tǒng)（multi-agent systems）的思想源自對生物群集自然現(xiàn)象的模擬，研究學(xué)者通過對該類自然現(xiàn)象的仿生研究提出了多智能體系統(tǒng)的概念，并從社會學(xué)、拓?fù)鋵W(xué)以及控制理論等領(lǐng)域進(jìn)行了深入探討。由于多智能體系統(tǒng)采用分布式協(xié)同控制，因此與傳統(tǒng)的集中式控制系統(tǒng)相比，多智能體系統(tǒng)具有功能更強(qiáng)大、魯棒性能更好、設(shè)計更簡單以及價格更便宜等優(yōu)點。目前，多智能體系統(tǒng)的研究在切換通信拓?fù)洹討B(tài)模型以及分布式包含控制協(xié)議等方面均取得了不錯的研究成果。多智能體系統(tǒng)已在多個領(lǐng)域有了實際應(yīng)用，例如傳感器網(wǎng)絡(luò)[1,2]、移動智能機(jī)器人編隊控制[3,4]、無人機(jī)部署[5]、多機(jī)器人協(xié)作等。

近年來，隨著通信、計算機(jī)學(xué)科以及人工智能等領(lǐng)域的迅猛發(fā)展，多智能體系統(tǒng)協(xié)同控制逐步發(fā)展為一門新興的控制科學(xué)，激發(fā)了來自應(yīng)用數(shù)學(xué)、智能控制、計算機(jī)應(yīng)用等眾多領(lǐng)域研究者們的興趣。對于多智能體系統(tǒng)的協(xié)同控制，最初是對簡單的一階多智能體系統(tǒng)[6,7]進(jìn)行研究，提出了相應(yīng)的控制算法并實現(xiàn)了智能體的位置同步，緊接著進(jìn)一步研究了二階多智能體系統(tǒng)的協(xié)同控制[8,9，10]。目前,關(guān)于多智能體系統(tǒng)的研究主要涉及一致性問題[11-15]、包含控制問題[16,17]、編隊控制問題[18,19]、蜂擁控制問題[20,21]、覆蓋控制問題[22,23]等，其中，關(guān)于一致性問題的研究是多智能體系統(tǒng)協(xié)同控制中各類問題研究的重要理論基礎(chǔ)。

多智能體系統(tǒng)的一致性指的是智能體之間通過分布式的控制協(xié)議進(jìn)行信息交互，最終使得所有智能體的某些物理量（狀態(tài)、速度、加速度等）達(dá)到相同的值。根據(jù)網(wǎng)絡(luò)中領(lǐng)導(dǎo)者的不同數(shù)量，將多智能體系統(tǒng)的一致性劃分為無領(lǐng)導(dǎo)者的一致性(簡稱為一致性)，一致性跟蹤(有一個領(lǐng)導(dǎo)者)及集合跟蹤(或稱為包圍，有多個領(lǐng)導(dǎo)者)[24]。包含控制(containment control)問題作為一致性問題的延伸，具有廣泛的實際應(yīng)用背景，因此也成為多智能體系統(tǒng)協(xié)同控制研究的一個熱點問題，具有巨大的理論研究價值和實際研究意義。多智能體系統(tǒng)的包含控制是指多個智能體利用分布式網(wǎng)絡(luò)傳輸局部信息，通過設(shè)計適當(dāng)?shù)目刂茀f(xié)議，最終使得所有的跟隨者進(jìn)入到領(lǐng)導(dǎo)者張成的凸包內(nèi)。在無法獲取全局信息的情況下，多智能體系統(tǒng)的包含控制主要通過系統(tǒng)中智能體的局部信息交互來實現(xiàn)。目前，多智能體系統(tǒng)的包含控制理論己經(jīng)在很多方面得到了實際應(yīng)用，例如資源定位，聯(lián)合救援和住宅保護(hù)等[25]。

近期關(guān)于一致性問題的研究已逐步深入并完善，目前作為分布式協(xié)同控制的一個重要研究方向的包含控制問題，受到越來越多研究學(xué)者的重點關(guān)注。為了實現(xiàn)多智能體系統(tǒng)的包含控制目標(biāo)，需要針對不同的實際情況（例如考慮異步、拓?fù)淝袚Q及環(huán)境噪聲等）來設(shè)計合適的算法，從而使得每個智能體通過局部信息傳輸，最終實現(xiàn)全部跟隨者的狀態(tài)能夠收斂到由領(lǐng)導(dǎo)者所張成的凸包內(nèi)。

2 包含控制研究的理論基礎(chǔ)與問題闡述

2.1 圖論相關(guān)知識

通常用加權(quán)有向圖為多個智能體之間的信息交換建模，G={V,E,A}是一個加權(quán)有向圖，其中V={1,...,n}是一個有限非空的節(jié)點集合，是邊的集合，是具有非負(fù)元素的加權(quán)鄰接矩陣。表示存在一條從節(jié)點j 到節(jié)點i 的邊。加權(quán)有向圖中的一條邊(i,j)表示智能體j 能夠從智能體i 獲取信息，反之則不一定。節(jié)點i 的鄰居集合用表示。

有向圖G 中的有向路徑是一個頂點序列(i1,...ik)，對于s=1,...,k-1,使得有向樹是一個有向圖，其中除了根節(jié)點的其余每個節(jié)點都僅有一個母節(jié)點。有向生成樹是一個有向樹，它由G 中所有節(jié)點和一些邊組成。若在每對不同的頂點i,j 之間有一條從i 到j(luò) 的有向路徑，則稱有向圖G 是強(qiáng)連通的。有向森林是由一個或多個有向樹組成的有向圖，其中任意兩個有向樹之間沒有共同的頂點。有向生成樹是由G 中的所有節(jié)點和一些邊組成的有向森林。

G 的拉普拉斯矩陣定義如下：

節(jié)點i 的入度和出度分別定義如下：

度矩陣是一個n×n 矩陣，定義為D=[dij]，其中對于i=j，dij= degin(i)；否則dij=0。于是圖G 的拉普拉斯矩陣可以寫成L=D-A。

2.2 符號網(wǎng)絡(luò)

利用圖論的思想，符號網(wǎng)絡(luò)（signed network）可以表示為一個圖，其中的每條邊具有正或負(fù)的符號屬性。關(guān)于符號網(wǎng)絡(luò)的三個基本問題是：它是否平衡？平衡邊集的最大尺寸是多少？要使其平衡，必須刪除的最小頂點數(shù)是多少？第一個問題很容易快速解決；第二個和第三個問題在計算上屬于NP-hard 問題。

目前，關(guān)于多智能體系統(tǒng)一致性的研究成果大多是建立在完全合作網(wǎng)絡(luò)（智能體之間體現(xiàn)為積極友好的關(guān)系）的基礎(chǔ)上的，即在通信拓?fù)鋱D中，描述個體之間信息交互的邊的權(quán)值都假定為非負(fù)。而在現(xiàn)實世界中，網(wǎng)絡(luò)中個體之間通常同時存在合作與競爭關(guān)系。與傳統(tǒng)的完全合作網(wǎng)絡(luò)下的完全一致性不同，符號網(wǎng)絡(luò)在描述系統(tǒng)中個體之間的信息交互時，引入了具有負(fù)權(quán)值的邊來描述消極的競爭或敵對關(guān)系，即通過構(gòu)造符號函數(shù)來刻畫個體之間的通信拓?fù)洹７柧W(wǎng)絡(luò)(signed network)中的邊（edge）可能具有正或負(fù)的符號屬性,其中,帶正號“+”的邊代表積極的關(guān)系（例如朋友、信任、喜歡、支持等），帶負(fù)號“-”的邊代表消極的關(guān)系（例如敵人、質(zhì)疑、討厭、反對等）[26]。通常將實際的復(fù)雜系統(tǒng)抽象為符號網(wǎng)絡(luò)進(jìn)行描述與分析。因此，研究符號網(wǎng)絡(luò)下多智能體系統(tǒng)的包含控制問題具有深刻的現(xiàn)實意義。

2.3 問題闡述

多智能體系統(tǒng)包含控制是指多個智能體利用分布式網(wǎng)絡(luò)傳輸局部信息，通過設(shè)計適當(dāng)?shù)目刂茀f(xié)議，最終使得所有的跟隨者進(jìn)入到領(lǐng)導(dǎo)者張成的凸包區(qū)域內(nèi)。

符號網(wǎng)絡(luò)下具有切換拓?fù)浜蜁r變時滯的一階多智能體系統(tǒng)包圍控制問題的數(shù)學(xué)模型如下：

領(lǐng)導(dǎo)者動力學(xué)：

跟隨者動力學(xué)：

設(shè)計控制協(xié)議：

3 包含控制問題研究進(jìn)展

對包含控制問題的研究起源于自然界以及社會實踐過程中的潛在應(yīng)用，例如公蠶蛾通過探測母蠶蛾間歇性釋放的費洛蒙信息素[27]，最終停留在由母蠶蛾形成的凸包內(nèi)，該文中研究了二分一階多智能系統(tǒng)在切換通信拓?fù)錀l件下的包含控制問題。關(guān)于包含控制，最早是由Dimarogonas 等人在文獻(xiàn)[28]中提出的，該文中將獨輪車隊作為多智能體系統(tǒng)，介紹了一種基于領(lǐng)導(dǎo)者的包含控制策略，基于控制律無論跟隨者的狀態(tài)如何，領(lǐng)導(dǎo)者們都能夠收斂到理想的編隊中。多智能體系統(tǒng)的包含控制問題的研究引起了眾多研究學(xué)者的關(guān)注，陸續(xù)涌現(xiàn)出一系列豐碩的研究成果。

3.1 一階多智能體系統(tǒng)包含控制問題

在文獻(xiàn)[29]中給出了對包含控制的定義，即驅(qū)策一組智能體向給定的目的地行進(jìn)，在到達(dá)目的地之前，多智能體系統(tǒng)的編隊形狀保持不變，即隊形收到固定的幾何圖形（凸多胞形）所限制，因此能夠保證在移動過程中多個智能體在有界的范圍中移動。文中采用了偏差分方程理論，并提出了基于stop-go 規(guī)則的混合控制策略，從而使得跟隨者進(jìn)入由領(lǐng)導(dǎo)者張成的凸包內(nèi)，并分析了所得系統(tǒng)的非零度，活躍性和收斂性。文獻(xiàn)[30]研究了在有向網(wǎng)絡(luò)拓?fù)湎潞徐o態(tài)和動態(tài)領(lǐng)導(dǎo)者的多智能體系統(tǒng)在固定和切換拓?fù)湎碌姆植际桨刂茊栴}。當(dāng)領(lǐng)導(dǎo)者是固定不動的時，無論拓?fù)鋱D是固定還是切換的，都可以得到連續(xù)時間和離散時間下系統(tǒng)實現(xiàn)包含控制的充分必要條件。特別地，當(dāng)網(wǎng)絡(luò)拓?fù)涔潭〞r，跟隨者的最終狀態(tài)恒定；當(dāng)網(wǎng)絡(luò)拓?fù)淝袚Q時，跟隨者的最終狀態(tài)可能隨著拓?fù)淝袚Q而發(fā)生變化。而當(dāng)領(lǐng)導(dǎo)者是動態(tài)變化的時，文中提出了一種無需速度測量的分布式跟蹤控制算法，并推導(dǎo)了網(wǎng)絡(luò)拓?fù)浜涂刂圃鲆娴臈l件，以確保所有跟隨者最終都能收斂到由動態(tài)領(lǐng)導(dǎo)者針對任意初始狀態(tài)形成的動態(tài)凸包。文獻(xiàn)[31]中指出，當(dāng)領(lǐng)導(dǎo)者靜止并且所有跟隨者共享一個慣性坐標(biāo)系時，給出了在固定和切換有向網(wǎng)絡(luò)拓?fù)湎拢谌魏斡邢蘧S的空間中使得任意初始狀態(tài)的全部跟隨者最終收斂到由靜止領(lǐng)導(dǎo)者形成的靜止凸包的充分必要條件。當(dāng)有向網(wǎng)絡(luò)拓?fù)涔潭〞r，對非對稱拉普拉斯矩陣進(jìn)行劃分，并探索其性質(zhì)以得出收斂結(jié)果。當(dāng)有向網(wǎng)絡(luò)拓?fù)淝袚Q時，基于Kronecker 積在高維空間中常用的去耦技術(shù)將不再適用，因此，文中提出了一種重要的坐標(biāo)變換技術(shù)，以得出收斂結(jié)果。所提出的坐標(biāo)變換技術(shù)在其他高維分布控制場景中也具有潛在的應(yīng)用價值，當(dāng)基于Kronecker 積的去耦技術(shù)無法應(yīng)用時，可以利用該技術(shù)將高維系統(tǒng)的分析簡化為一維系統(tǒng)的分析。當(dāng)領(lǐng)導(dǎo)者是動態(tài)的并且所有跟隨者共享一個慣性坐標(biāo)系時，提出了一種無需速度測量的分布式跟蹤控制算法。此外，還通過一些反例表明，在沒有速度測量的情況下，通常不可能找到分布式包含控制算法，以確保在高維空間中所有跟隨者最終都能在切換網(wǎng)絡(luò)拓?fù)湎率諗康絼討B(tài)領(lǐng)導(dǎo)者形成的凸包。

3.2 二階多智能體系統(tǒng)包含控制問題

文獻(xiàn)[32]研究了存在固定及動態(tài)領(lǐng)導(dǎo)者的雙重積分器動力學(xué)行為的二階多智能體系統(tǒng)分布式包含控制問題。在靜態(tài)領(lǐng)導(dǎo)者的情況下，提出了一種分布式包含控制算法，并研究了網(wǎng)絡(luò)拓?fù)浜涂刂圃鲆娴臈l件，以保證在任何維空間中的漸近包含控制。對于動態(tài)領(lǐng)導(dǎo)者，研究了兩種情況：速度相同的領(lǐng)導(dǎo)者和速度不同的領(lǐng)導(dǎo)者。對于速度相同的領(lǐng)導(dǎo)者，提出了一種分布式包含控制算法，以解決基于有向切換網(wǎng)絡(luò)拓?fù)涞臐u近包含控制。特別地，如果網(wǎng)絡(luò)拓?fù)涫枪潭ǖ模瑒t對于任何維空間都可以實現(xiàn)漸進(jìn)包含控制，如果網(wǎng)絡(luò)拓?fù)涫墙粨Q的，則僅可以對一維空間實現(xiàn)漸進(jìn)包含控制。對于速度不同的領(lǐng)導(dǎo)者，提出了一種固定網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)下的分布式包含控制算法，其中跟隨者之間的通信模式是無向的，并推導(dǎo)了網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的條件和控制增益，以保證對任何維空間的漸近包含控制。最后通過在多機(jī)器人平臺上的實驗以驗證了理論結(jié)果的有效性。文獻(xiàn)[33]研究了包含多個靜止不變或動態(tài)變化領(lǐng)導(dǎo)者的網(wǎng)絡(luò)化多智能體系統(tǒng)的包含控制問題，其描述領(lǐng)導(dǎo)者和跟隨者之間信息交互的拓?fù)涫怯邢驁D。對于連續(xù)時間和基于采樣數(shù)據(jù)協(xié)議，分別建立了保證包含控制實現(xiàn)的充分必要條件。當(dāng)領(lǐng)導(dǎo)者靜止時，連續(xù)時間協(xié)議的收斂完全取決于拓?fù)浣Y(jié)構(gòu)；而基于采樣數(shù)據(jù)協(xié)議的收斂不僅取決于拓?fù)浣Y(jié)構(gòu)還與采樣周期有關(guān)。當(dāng)領(lǐng)導(dǎo)者動態(tài)變化時時，連續(xù)時間協(xié)議的收斂取決于拓?fù)浣Y(jié)構(gòu)和增益參數(shù)；而基于采樣數(shù)據(jù)協(xié)議的收斂則不僅取決于拓?fù)浣Y(jié)構(gòu)和增益參數(shù)還與采樣周期有關(guān)。而且，所有跟隨者的最終狀態(tài)完全由領(lǐng)導(dǎo)者的初始值和拓?fù)浣Y(jié)構(gòu)決定。在靜止領(lǐng)導(dǎo)者的情況下，所有的跟隨者將進(jìn)入領(lǐng)導(dǎo)者所張成的凸包內(nèi)，而在動態(tài)領(lǐng)導(dǎo)者的情況下，跟隨者不僅將進(jìn)入凸包，而且將以相同的速度與跟隨者一起移動。最后，通過數(shù)值模擬驗證了上述理論結(jié)果的有效性。文獻(xiàn)[34]研究了一組自動駕駛汽車的分布式包含控制問題，該問題由具有多個動態(tài)領(lǐng)導(dǎo)者的雙積分器動力學(xué)建模。其目的是在無法獲得領(lǐng)導(dǎo)者和跟隨者的速度和加速度的約束下，將跟隨者推入由動態(tài)領(lǐng)導(dǎo)者跨越的凸包中，領(lǐng)導(dǎo)者只是跟隨者子集的鄰居，并且跟隨者之間只有局部信息交互。 提出了兩種僅通過智能體的位置測量來進(jìn)行控制的算法。理論分析表明，如果跟隨者之間存在無向的網(wǎng)絡(luò)拓?fù)洌瑒t跟隨者將進(jìn)入由動態(tài)領(lǐng)導(dǎo)者張成的凸包中。對于每個跟隨者，至少有一個領(lǐng)導(dǎo)者具有指向該跟隨者的有向路徑，并且給出了恰當(dāng)?shù)乃惴▍?shù)。最后通過數(shù)值仿真驗證其理論結(jié)果。更多關(guān)于一階和二階多智能體系統(tǒng)包含控制的研究可參考文獻(xiàn)[35-39]。

3.3 一般線性多智能體系統(tǒng)包含控制問題

除了對一階、二階多智能體系統(tǒng)包含控制問題的研究之外，關(guān)于一般線性多智能體系統(tǒng)包含控制問題的研究也逐步展開。文獻(xiàn)[40]使用交互拓?fù)溲芯苛司哂芯€性動力學(xué)的多智能體的行為。根據(jù)拓?fù)浣Y(jié)構(gòu)，將智能體分為了兩類，即內(nèi)部智能體和邊界智能體。所涉及的包容控制問題是使得同一強(qiáng)分量中的邊界智能體漸近一致，且所有的內(nèi)部智能體收斂到邊界元所張成的凸包內(nèi)。此外，通過在多智能體系統(tǒng)中引入領(lǐng)導(dǎo)者，設(shè)計了部分智能體的牽制控制策略，使得所有的智能體都能漸近地與領(lǐng)導(dǎo)者達(dá)成一致。文中還說明了如何選擇與領(lǐng)導(dǎo)者進(jìn)行局部信息交互的智能體，以便達(dá)成一致，并使所選智能體的數(shù)量最少。以后所有的結(jié)果的有效性都通過一些數(shù)值模擬得到了驗證。此外，文獻(xiàn)[41]考慮了在有向通信拓?fù)湎戮哂幸话憔€性動力學(xué)的連續(xù)時間和離散時間多智能體系統(tǒng)的包含控制問題。針對連續(xù)時間和離散時間情況，都構(gòu)造出了基于相鄰智能體的相對輸出的分布式動態(tài)包含控制器，并給出了關(guān)于這些動態(tài)控制器存在的充分條件。并對依賴于相鄰智能體相對狀態(tài)的靜態(tài)包含控制器進(jìn)行了討論。文獻(xiàn)[42]研究了當(dāng)領(lǐng)導(dǎo)者之間沒有交互情況下的包含控制問題，考慮了在有向通信拓?fù)湎戮哂幸话憔€性動力學(xué)的連續(xù)時間和離散時間多智能體系統(tǒng)的包含控制問題。針對連續(xù)時間和離散時間情況，都構(gòu)造了基于相鄰智能體相對輸出的基于分布式降階觀察者的包含控制器，在這種情況下，跟隨者的狀態(tài)將漸近收斂到由領(lǐng)導(dǎo)者的狀態(tài)形成的凸包，并給出了關(guān)于這些包含控制器存在的充分條件。

在近期的研究中，文獻(xiàn)[43-45]給出了更多關(guān)于一般線性多智能體系統(tǒng)包含控制的相關(guān)成果。文獻(xiàn)[43]研究了具有弱連通信息拓?fù)涞木€性多智能體系統(tǒng)的包含控制問題。文獻(xiàn)[44]討論了由于個體之間信息交換的不連續(xù)性而導(dǎo)致的非周期性采樣問題。文獻(xiàn)[45]通過譜半徑分析和矩陣?yán)碚摣@得了一些充分必要條件。文獻(xiàn)[46,47]研究了沒有任何結(jié)構(gòu)性限制的一般網(wǎng)絡(luò)拓?fù)涞亩嘀悄荏w系統(tǒng)包含控制問題，其中領(lǐng)導(dǎo)者和跟隨者完全由網(wǎng)絡(luò)拓?fù)錄Q定。文獻(xiàn)[48,49]討論了異步條件下靜態(tài)領(lǐng)導(dǎo)者的二階多智能體系統(tǒng)包含控制問題。更多有關(guān)一般線性多智能體系統(tǒng)的包含控制問題研究可參考文獻(xiàn)[50-53]。

4 發(fā)展趨勢分析及未來研究方向

綜上所述，從國內(nèi)外有關(guān)多智能體系統(tǒng)包含控制問題的研究現(xiàn)狀來看，目前關(guān)于多智能體系統(tǒng)包含控制問題的研究主要發(fā)展趨勢大致總結(jié)如下：

（1）一般線性、非線性多智能體系統(tǒng)包含控制問題研究；

（2）考慮不同環(huán)境條件（存在時滯、切換拓?fù)湟约霸肼暤惹闆r）下不確定度的多智能體系統(tǒng)包含控制問題研究；

（3）考慮競爭消極關(guān)系的多智能體系統(tǒng)包含控制問題研究；

（4）異構(gòu)的多智能體系統(tǒng)包含控制問題研究；

（5）三維空間中的多智能體系統(tǒng)包含控制問題研究。

由于多智能體系統(tǒng)包含控制問題的研究具有關(guān)鍵的理論意義和非凡的應(yīng)用價值。因此，在未來的研究工作中，作者擬從符號網(wǎng)絡(luò)下多智能體系統(tǒng)包含控制的關(guān)鍵問題入手，以期為無人機(jī)編隊、機(jī)器人協(xié)同等實際應(yīng)用提供理論支撐，預(yù)期實現(xiàn)以下目標(biāo)：

（1）基于非負(fù)矩陣?yán)碚摗D論和控制理論等相關(guān)知識，對符號網(wǎng)絡(luò)下一階和二階多智能體系統(tǒng)的包含控制問題進(jìn)行全面的理論分析；

（2）研究切換拓?fù)湎碌姆柧W(wǎng)絡(luò)以及隨時間變化的通信時滯對多智能體系統(tǒng)包含控制性能的影響；

（3）設(shè)計合適的分布式控制協(xié)議，研究符號網(wǎng)絡(luò)的二分包含控制問題，在現(xiàn)有結(jié)構(gòu)平衡的條件下，進(jìn)一步得到通信拓?fù)浣嵌鹊某浞謼l件。