王常虹，劉 博，李清華

(哈爾濱工業(yè)大學(xué)空間控制與慣性技術(shù)研究中心， 哈爾濱 150001)

0 引言

隨著社會的進(jìn)步與發(fā)展，人們對機器人系統(tǒng)的依賴也越來越強，需要機器人系統(tǒng)完成的任務(wù)也日趨復(fù)雜，特別是重復(fù)性、危險性較高的工作，對機器人系統(tǒng)的需求更為明顯。雖然目前在單機器人領(lǐng)域有了較為長足的進(jìn)步，但是由于任務(wù)的多樣化、復(fù)雜化，單個機器人常常無法完成部分人們指定的任務(wù)。為了解決這些復(fù)雜困難的任務(wù)，多機器人系統(tǒng)(Multi-Robot System, MRS)應(yīng)運而生。MRS是由多個在同一環(huán)境中相互作用的機器人組成的系統(tǒng)。相較于單機器人系統(tǒng) ，MRS具有如下幾方面的優(yōu)勢：

1)MRS個體可分布于空間的不同位置。

2)任務(wù)并行處理：群體中的個體間既有耦合又相互獨立。在任務(wù)內(nèi)個體間相互耦合，任務(wù)間個體相互獨立。MRS根據(jù)任務(wù)形成了相應(yīng)的MRS子集并行處理問題，提高了任務(wù)完成效率。

3)魯棒性：MRS可適應(yīng)不同的任務(wù)環(huán)境，且當(dāng)環(huán)境具有不確定性時，MRS具有一定的容錯性。由于個體間功能的冗余性，當(dāng)某個或者某些機器人出現(xiàn)故障甚至完全損壞時，系統(tǒng)仍然可能正常工作。

由于MRS的高效性和魯棒性，具有廣泛的應(yīng)用場景，但目前MRS發(fā)展還不完善，大多數(shù)MRS成果還停留在理論研究和實驗室演示階段，因此MRS的實際應(yīng)用成果較少，主要集中在大范圍環(huán)境態(tài)勢感知[1]、集群協(xié)同作戰(zhàn)、復(fù)雜環(huán)境救援[2]、無人機集群編隊表演和工廠協(xié)同裝配等幾個方面。

1 MRS研究現(xiàn)狀簡述

自20世紀(jì)60年代法國生物學(xué)家Grasse通過觀察白蟻的筑巢行為，提出了共識自主性的概念，學(xué)術(shù)界對于集群系統(tǒng)的研究逐步發(fā)展起來。進(jìn)入21世紀(jì)后，隨著美國國防部高級研究計劃局(Defense Advanced Research Projects Agency, DARPA)和歐盟信息社會項目提出越來越多有關(guān)MRS的項目需求，MRS研究進(jìn)入了高速發(fā)展的階段。

對于MRS，除了單個機器人涉及的問題外(如軌跡規(guī)劃、控制等)，還涉及機器間如何實現(xiàn)交互、如何解決機間路徑?jīng)_突、一致性控制和復(fù)雜任務(wù)分解和分配等諸多問題。Bond和Gasser[3]兩位學(xué)者總結(jié)了MRS的相關(guān)問題：

1)如何在個體中用公式表示、描述、分解和分配任務(wù)；

2)個體間如何交流和互相影響；

3)如何確保個體行為的連貫性；

4)個體間如何辨認(rèn)和處理相互的沖突。

要解決這些問題，需要建立合適的系統(tǒng)模型，理解MRS運動的發(fā)生機理，研究個體與系統(tǒng)間的關(guān)系。目前較為常用的MRS建模研究思路可以分為自頂向下和自底向上兩種。

自頂向下的方法主要基于分而治之的分層思路，將MRS問題分解為多個子問題，如任務(wù)分配、航跡規(guī)劃、控制等多個層次。針對每個層次分別進(jìn)行建模求解，有效降低了問題求解的難度和復(fù)雜度。以P.R.Chandler[4-5]所提出的分層遞階結(jié)構(gòu)為例，如圖 1所示，該遞階結(jié)構(gòu)包括3個決策層和1個控制層。第3層進(jìn)行任務(wù)分配，在滿足約束條件的前提下，將任務(wù)分配給具有不同能力的個體(群)；第2層進(jìn)行個體間任務(wù)協(xié)調(diào)，包括協(xié)同攻擊、協(xié)同分類、沖突消解等；第1層負(fù)責(zé)任務(wù)的執(zhí)行與航跡規(guī)劃，包括路徑規(guī)劃、軌跡優(yōu)化及路徑?jīng)_突解決；第0層為控制層，負(fù)責(zé)解決軌跡跟蹤與底層控制問題。雖然在圖 1中相鄰兩層相互影響，但是在實際研究中，鮮有將相鄰層次耦合求解，通常為完全解耦求解，以求得次優(yōu)解。

圖1 分層遞階結(jié)構(gòu)Fig.1 Hierarchical decomposition

采用分層遞階結(jié)構(gòu)有效降低了MRS決策與控制的復(fù)雜性，是目前主流的研究方法。對于這種問題的建模和求解，主要是針對任務(wù)分配與航跡規(guī)劃解耦求解。從數(shù)學(xué)角度來看，任務(wù)分配(亦稱為任務(wù)規(guī)劃、任務(wù)調(diào)度)屬于復(fù)雜的組合優(yōu)化問題，目前已有多份優(yōu)秀的研究綜述[6-8]，本文不再贅述。而針對航跡規(guī)劃問題，主要是解決個體間空間與時間層面的沖突及動態(tài)避障的問題[9]，總體呈現(xiàn)百家爭鳴的態(tài)勢，非本文研究重點，可查看近期研究綜述[10-11]。

不同于自頂向下的研究方法，自底向上的方法主要基于自組織方法的研究思路，通過個體的微觀模型，從個體對環(huán)境的感知、交互、決策協(xié)調(diào)入手，對整個MRS產(chǎn)生宏觀調(diào)控的效果。這種分布式調(diào)控的方式還可以解決分層遞階結(jié)構(gòu)求解時對動態(tài)環(huán)境響應(yīng)較慢的問題。

自底向上的MRS建模方法，最初起源于對生物界群集行為的研究，如鳥群[12]、魚群[13](見圖2)、蟻群[14]等，后來通過模擬生物群體的行為，對系統(tǒng)進(jìn)行建模，從而實現(xiàn)了MRS的自組織策略，這種方式計算簡單且魯棒性好。在Jadbabaie和Olfati-Saber等的推動下，擬生物方法逐步形成了MRS一致性控制理論。一致性控制理論是指隨著時間的推移，MRS中的所有個體的某項或者某些狀態(tài)趨于一致。由于分布式的一致性控制與基于生物的自組織策略具有類似特點，且有數(shù)學(xué)理論支撐，因此越來越多的學(xué)者對一致性控制理論產(chǎn)生了濃厚的研究興趣。

圖2 魚群行為研究Fig.2 Study on the movement of fish schools

雖然現(xiàn)階段國內(nèi)外研究人員已取得了一些研究成果，但是大部分仍處于只關(guān)注工程實現(xiàn)，采用拼湊的方法解決簡單的問題，或是采用集中分配求解方法，不利于充分發(fā)揮MRS的優(yōu)勢。本文將從自底向上的研究方法入手，對當(dāng)前自組織MRS建模形式進(jìn)行總結(jié)與分析。

2 自組織MRS建模

MRS較個體建模更加復(fù)雜，除個體模型外，通常情況還需考慮系統(tǒng)個體模型間的關(guān)系，即拓?fù)淠Ｐ?，個體模型表示為拓?fù)淠Ｐ椭械墓?jié)點。故MRS控制系統(tǒng)模型一般包含兩部分：拓?fù)淠Ｐ秃凸?jié)點模型。拓?fù)淠Ｐ蜎Q定了個體間的連接關(guān)系，現(xiàn)階段通常用圖表示，如：無向圖、有向圖、加權(quán)圖等。節(jié)點模型則用于描述個體的狀態(tài)。本節(jié)將主要從擬生物行為模型、一致性控制模型和多智能體強化學(xué)習(xí)系統(tǒng)模型3個方面對自組織MRS建模方法進(jìn)行總結(jié)與分析。

2.1 MRS擬生物行為模型

MRS最初起源于對生物界群集行為的研究，生物學(xué)的理論和方法對MRS建模研究具有重要影響。在生物群體中，通過個體間或個體與環(huán)境的相互作用實現(xiàn)自組織，從而完成特定任務(wù)，如螞蟻搭橋[14]、蜜蜂尋巢[15]、狼群圍獵[16]等。類似地，MRS主要研究機器人之間和機器人與環(huán)境之間如何通過有限感知和局部交互，涌現(xiàn)出期望的群集行為。而對生物群體建模，是MRS模仿生物群體行為智能決策和智能涌現(xiàn)的前提。

最早的MRS模型是Reynolds[12]于1987年提出的Boids模型，該模型用計算機來模擬群體行為，并給出了智能集群系統(tǒng)滿足的3個規(guī)則：

1)速度匹配：個體盡量與鄰居速度和方向的平均值保持一致；

2)聚集：盡量向鄰居的平均位置運動；

3)避免碰撞：相鄰個體間避免發(fā)生碰撞。

2001年，Reynolds將Boids模型所有資料公布于網(wǎng)站1

1http://www.red3d.com/cwr/boids/上，包括程序、示例、相關(guān)論文等。在Boids模型的基礎(chǔ)上，1995年Vicsek等[17]將其簡化，提出了一種離散MRS模型—Vicsek模型，用于模擬大量粒子涌現(xiàn)的現(xiàn)象，其實質(zhì)是Boids模型中速度匹配的動力學(xué)表示。Vicsek模型刻畫了多個粒子構(gòu)成的自治系統(tǒng)的同步運動。在這個模型中粒子遵循如下規(guī)則：

1)系統(tǒng)中運動的粒子具有常速率v；

2)粒子存在一個影響半徑r，即系統(tǒng)中的任意一對粒子，只有這對粒子之間的直線距離小于r時，他們才存在相互的影響；

3)粒子每一時刻的運動方向跟上一時刻影響半徑范圍內(nèi)的其他所有粒子的平均運動方向相同。

同時，Vicsek模型首次對MRS進(jìn)行了數(shù)學(xué)化描述，如式(1)所示

(1)

其中：xi(t)為個體i在t時刻的位置；vi(t)為個體i在t時刻的速度；θi(t)為個體i在t時刻的航向；<θi(t)>r為個體i及其周圍個體的航向平均值；Δi(t)為擾動項。引入φ評判是否同步

(2)

其中，φ為描述歸一化的平均速度的指標(biāo)，當(dāng)速度一致時φ=1；當(dāng)系統(tǒng)完全雜亂無章時φ=0，如圖 3所示。

圖3 左：φ=0；右：φ=1Fig.3 Left:φ=0；right: φ=1

考慮到大部分生物無法獲得360°的感知范圍，因此在Boids模型和Vicsek模型的基礎(chǔ)上，部分學(xué)者添加了有限視場角約束[18-19]， 建立了有限視場約束的Reynolds群集模型和有限視場約束的Vicsek模型。

與Reynolds同時期，加州大學(xué)的Beni與Hack-wood兩位教授[20]首次提出了群體智能的概念，而后Bonabeau和Dorigo 在其著作[14]中，將生物群體智能定義為：任何一種由昆蟲群體或其他動物社會行為機制而激發(fā)設(shè)計出的算法或分布式解決問題的策略。同時兩人還提出了另一種影響深遠(yuǎn)的擬生物群MRS模型——蟻群模型。昆蟲學(xué)家發(fā)現(xiàn)，雖然螞蟻視覺系統(tǒng)并不發(fā)達(dá)，但總可以通過感知種群中螞蟻個體釋放的信息素，選擇信息素濃度較高的路徑，不斷正向迭代，使蟻群逐漸沿著最短的路徑找到食物。在此基礎(chǔ)上，Dorigo[14]提出了蟻群模型，用于解決車輛路徑、調(diào)度優(yōu)化、指派和旅行商等問題[14,21]。以旅行商問題(Traveling Salesman Pro-blem, TSP)為例，蟻群群體數(shù)量為m，目標(biāo)數(shù)為n，節(jié)點i與節(jié)點j的距離為dij，2個節(jié)點間信息素濃度為τij(t)。根據(jù)τij(t)設(shè)計節(jié)點間轉(zhuǎn)移概率，根據(jù)dij設(shè)計城市間轉(zhuǎn)移的期望，從而完成模型的基本設(shè)計。螞蟻個體沿路徑信息素釋放模型可以根據(jù)問題進(jìn)行設(shè)計，常采用：與經(jīng)過路徑總長度成反比的ant cycle模型、僅與相鄰節(jié)點距離成反比的ant quantity模型，以及信息素濃度始終保持不變的ant density模型三類。

人工蜂群最早起源于生物學(xué)家對自然界蜂群行為的觀察[15]，常用于集體決策研究。該模型通過模擬偵察蜂搖擺舞行為，建立分布式?jīng)Q策模型。以尋找新?lián)c為例[22]，M. R. Myerscough建立了一套普適決策模型：根據(jù)潛在偵察蜂的總數(shù)以及在每個地點搖尾的次數(shù)，分配每個地點在各個時刻所需偵察蜂的數(shù)目。人工蜂群模型中個體完全獨立，通過個體的感知和決策，最終形成系統(tǒng)的統(tǒng)一決策。在此基礎(chǔ)上，逐步發(fā)展成為完善的人工蜂群算法，廣泛應(yīng)用于無人機偵察和打擊領(lǐng)域[23]。

在鴿群層級網(wǎng)絡(luò)自組織模型中[24]，通過模仿鴿群中的層級網(wǎng)絡(luò)，反映鴿群中的通信、各層級數(shù)目、智能化程度、個體間的連接關(guān)系等，從而使得群體通過微觀的個體之間的交互產(chǎn)生宏觀行為調(diào)控。根據(jù)生物學(xué)研究發(fā)現(xiàn)，鴿群交互模型為根據(jù)固定范圍確定網(wǎng)絡(luò)模型和固定鄰居數(shù)目的交互模型，因此可以構(gòu)建鴿群的層級引領(lǐng)網(wǎng)絡(luò)模型，模型描述與傳統(tǒng)一致性控制模型相似：由個體動力學(xué)模型及網(wǎng)絡(luò)拓?fù)淠Ｐ蜆?gòu)成，模型中個體被上層領(lǐng)導(dǎo)者領(lǐng)導(dǎo)，并對下層跟隨個體有引導(dǎo)作用[25]。

狼群在獵殺食物時[16,26]，常常可以獵殺體重數(shù)倍于自己的獵物，在獵殺過程中，狼群自主決策產(chǎn)生組織者，并根據(jù)狼群的個體情況，均衡分配任務(wù)追蹤和包圍獵物，直到獵物停止移動，最后以車輪戰(zhàn)的方式拖垮獵物。由狼群獵殺行為可以看出，狼群模型中個體間自治，角色可靈活轉(zhuǎn)換，無法區(qū)分，個體間交互信息為互相的位置信息，每個個體都具有任務(wù)管理和任務(wù)分配的能力，且每階段任務(wù)中，組織者均可能會發(fā)生改變，因此狼群模型具有極強的魯棒性。該模型包括當(dāng)前任務(wù)狀態(tài)、行為庫、策略庫、任務(wù)環(huán)境，以任務(wù)環(huán)境和當(dāng)前任務(wù)狀態(tài)作為輸入，通過策略庫從動作庫中選擇下一步動作，直至完成整個任務(wù)集。該模型廣泛應(yīng)用于軍事無人機圍堵、打擊和任務(wù)分配。

受到Wang等[27]2016年針對大象群體中氏族形成行為研究的啟發(fā)，Almufti等[28]構(gòu)建了象群優(yōu)化(Elephant Herding Optimizations, EHO)模型，該模型可分為2個部分：

1)種群更新：用于更新每個部落中大象和母族長的位置

Xnew,ci,j=Xci,j+α(Xbest ci-Xci,j)r

(3)

其中，Xnew,ci,j為ci氏族中個體j的位置更新；α∈[0,1]表示母族長對于個體Xci,j的影響程度；Xbest,ci表示族長的位置；r∈[0,1]則表示一種隨機分布，用于改善大象種群的多樣性。母族長的位置則由氏族重心所引導(dǎo)，不斷更新。

2)分離：在每一個象族中，公象在成年后都會離開族群獨自生活，進(jìn)而提高了下一個搜索階段的種群多樣性。

通過這種建模形式，Almufti等[28]有效解決了MRS中多旅行商的目標(biāo)分配問題。

C. Jada等[29]受到蝴蝶交流和尋找配偶等生物現(xiàn)象的啟發(fā)，構(gòu)建了meta-butterfly模型，并描述了蝴蝶群體模型。在模型中，基于歐氏距離確定周圍蝴蝶，更新自身信息素,并通過對不同個體釋放不同量的信息素與周圍蝴蝶交互，進(jìn)而完成選擇過程，根據(jù)移動策略(式(4))完成聚集。

(4)

其中，Bs為步長；xi(t)為t時刻蝴蝶i的位置。

除了動物的集體行為，細(xì)胞水平的生物現(xiàn)象也同樣可以在MRS的研究中被采用。H. Oh等[30]通過研究生物學(xué)中形態(tài)因子影響胚胎階段擴散到發(fā)育組織，并自動調(diào)整細(xì)胞的行為和反應(yīng)的現(xiàn)象，構(gòu)造了分布式的數(shù)學(xué)模型，形態(tài)因子通過機器人擴散模型描述

(5)

其中，Cbi為個體b中形態(tài)因子i的濃度；Di表示擴散率；ri為衰減速率；dbb′表示個體b到b′的距離；Nb表示與個體b相連接的個體數(shù)。

上面的擴散模型并未考慮個體間對形態(tài)因子的影響。當(dāng)考慮一個細(xì)胞的幾個形態(tài)因子與鄰近細(xì)胞的形態(tài)因子發(fā)生反應(yīng)時，將式(5)中引入反應(yīng)機制，則可以建立Reaction-diffusion模型

(6)

其中，wij為交互矩陣的元素；fij表示更新函數(shù)，通常采用sigmoid方程。

在Reaction-diffusion模型的基礎(chǔ)上，Y.Ike-moto等[31]利用一組機器人，成功生成并保持圓形、三角形、四邊形、六邊形等多種圖案。以圓形為例，機器人一旦形成一個圓形圖案，2個形態(tài)因子的信號就會在機器人之間交換，并通過一組Reaction-diffusion方程相互作用，穩(wěn)定為圓形圖案。

近年來，部分學(xué)者通過觀察細(xì)菌的生物學(xué)特性，建立相應(yīng)規(guī)則，形成MRS聚集行為。受到細(xì)菌趨光性質(zhì)的啟發(fā)，Li等[32]設(shè)計了一套僅靠周圍粒子根據(jù)環(huán)境變化情況實現(xiàn)運動的系統(tǒng)，個體根據(jù)環(huán)境的光照控制本體擴張與收縮，個體間相互推擠實現(xiàn)運動。這套系統(tǒng)即使20%的個體失效，仍能保持運動，展示了大規(guī)模MRS的強魯棒性。

至此可以看出，通過對生物群社會行為的研究和模仿，從而驗證了MRS的自組織方法對環(huán)境有較強適應(yīng)性，且系統(tǒng)具有較強的魯棒性，不會因為某些個體出現(xiàn)問題而導(dǎo)致系統(tǒng)崩潰，具有一定的自愈能力，同時這種方法通過簡單個體的協(xié)作，高效完成了復(fù)雜任務(wù)，也體現(xiàn)了系統(tǒng)智能的涌現(xiàn)。但是，這種擬生物群體方法的缺點也十分明顯。該方法源于對自然界生物群體社會性行為的觀察與模仿，相關(guān)數(shù)學(xué)分析比較缺乏，描述尚不完善，因此無法對結(jié)果和過程進(jìn)行完善的分析，進(jìn)而導(dǎo)致行為反應(yīng)不可完全預(yù)測、結(jié)果可信度較低。

2.2 MRS一致性控制模型

一致性問題起源于對自然界生物行為的研究，并在擬生物方法的基礎(chǔ)上逐步發(fā)展為MRS最重要的研究方向之一，是MRS最基本的控制問題。一致性算法的基本思想是個體利用網(wǎng)絡(luò)傳遞信息，設(shè)計合理的控制算法，實現(xiàn)系統(tǒng)內(nèi)個體狀態(tài)的一致或同步。MRS中的許多問題都可以歸結(jié)為一致性控制問題，如MRS的聚集問題和編隊隊形形成問題均可以描述為MRS個體位置一致性問題。最為常見的群集問題是指所有個體速度達(dá)到相同并避免碰撞，可以用速度一致性來描述。近些年MRS一致性控制問題快速發(fā)展，從傳統(tǒng)的低階積分模型演變到高階模型、一般系統(tǒng)模型和非線性模型，也逐漸從同質(zhì)系統(tǒng)演變到異質(zhì)系統(tǒng)，同時為提高采樣與控制效率，基于事件觸發(fā)[33-34]的MRS一致性問題研究也逐步興起。

2.2.1 低階一致性模型

在Reynolds[12]提出的Boids模型及Vicsek等[17]提出的Vicsek模型兩種擬生物群模型的基礎(chǔ)上，2003年，Jadbabaie等[35]在無噪聲的假設(shè)條件下對Vicsek模型進(jìn)行了簡化，用矩陣論和圖論(無向圖)給出了Vicsek模型的收斂性的理論證明，指出：只要滿足聯(lián)通，粒子的運動方向就能達(dá)到一致。與Vicsek描述類似，Jadbabaie引入了圖論，將無領(lǐng)導(dǎo)的模型描述為

(7)

(8)

當(dāng)需要領(lǐng)航員的情況下，bi(t)=1，否則bi(t)=0。集群系統(tǒng)模型自此從群體動力學(xué)模型時代進(jìn)入了網(wǎng)絡(luò)化系統(tǒng)與圖論描述時代。

Olfati-Saber等[36-38]將Jadbabaie的工作進(jìn)一步擴展，在其基礎(chǔ)上研究了系統(tǒng)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)與系統(tǒng)收斂性之間的關(guān)系，指出如果系統(tǒng)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是強連通的有向圖，則對于任意初始狀態(tài)，系統(tǒng)的狀態(tài)是漸近收斂的，且對于強連通有效拓?fù)浣Y(jié)構(gòu)下的MRS，平均一致收斂的充要條件是它的信息交換圖是平衡圖。

Olfati-Saber將系統(tǒng)描述為G=(V,ε,A)，其中V為節(jié)點，ε為邊，A為鄰接矩陣，它的元素均為非負(fù)。個體的集合為

NJ:=

(9)

建立個體動力學(xué)模型為

定義有向拉普拉斯矩陣為

L(G)=L=Δ-A

其中，Δ為入度矩陣。

針對切換拓?fù)涞哪Ｐ停琌lfati-Saber[38]建立模型

Γn={G=(V,ε,A):rank(L(G))

=n-1,1TL(G)=0}

(10)

第1個式子是對強連通網(wǎng)絡(luò)的描述，第2個式子是對系統(tǒng)的描述。其中s(t):R≥0→IΓn是切換信號。

在Olfati-Saber的基礎(chǔ)上，美國加州大學(xué)河濱分校的任偉教授等[39]在固定拓?fù)浣Y(jié)構(gòu)的假設(shè)下，將強連通拓?fù)錀l件弱化為只要在一段時間內(nèi)網(wǎng)絡(luò)拓?fù)渥訄D的聯(lián)合圖包含一條有向生成樹，則系統(tǒng)可實現(xiàn)一致性；在動態(tài)變化的交互拓?fù)湎?，如果有向交互圖的并集在系統(tǒng)演化過程中有足夠頻繁的生成樹，則也可以實現(xiàn)信息漸近一致，并建立了離散系統(tǒng)建模與連續(xù)模型。

同樣受到Vicsek和Jadbabaie工作的啟發(fā)，Cucker和Smale[40-41]提出了一個非常有意義的集群模型(Cucker-Smale模型, CS模型)，在模型中所有個體具有慣性，且整個系統(tǒng)完全驅(qū)動。在CS模型中，個體會對其速度進(jìn)行自我調(diào)節(jié)，即通過自己在t時刻的速度跟其他個體在t時刻的速度差的加權(quán)平均值來調(diào)節(jié)自己下一時刻的速度。之前的模型需要在無限時間序列上的一個假設(shè)，CS模型的收斂結(jié)果只依賴于初始狀態(tài)條件和影響參數(shù)。在CS模型中，也做了一些理想化處理：

1)所有個體之間都有相互影響；

2)個體間影響的強弱跟它們之間的絕對距離和速度差有關(guān)。

連續(xù)CS模型：考慮一個具有N個子個體的MRS，對于個體i，它在t時刻的位移記為xi(t)，速度記為vi(t)的模型滿足

(11)

其中

以CS模型中個體之間的影響機制為基礎(chǔ)，美國的Shen教授[42]提出了一個特殊的具有領(lǐng)導(dǎo)機制和分等級機制的集群(Hierarchical Leadership, HL)模型。HL模型中每個成員都屬于和它對應(yīng)的一個等級，對它們從高到低依次排序。成員們遵循一個低等級的成員只能夠被高等級的成員影響和領(lǐng)導(dǎo)的機制。與CS模型表述相同，僅加入了2組額外描述：

1)當(dāng)j

2)若個體i領(lǐng)導(dǎo)組成的集合表征為：L={aij(t) > 0}，那么對于任意的i> 0都有L≠?。

哈爾濱工業(yè)大學(xué)的Li等[41]在Shen的基礎(chǔ)上改進(jìn)了HL模型，建立了一個更為一般的單領(lǐng)航機制的多智能復(fù)雜系統(tǒng)集群模型(Cucker-Smale under Rooted Leadership, CSRL)。在這個模型中存在一個全局領(lǐng)導(dǎo)者，它不受其他個體的影響，但是直接或者間接地影響著其他所有個體。這個模型更好地揭示了全體的合作信息交換的優(yōu)點。

2011年,美國馬里蘭大學(xué)終身杰出教授Tadmor及其團(tuán)隊[43]改進(jìn)了CS模型，在CS模型的基礎(chǔ)上考慮生物集群特性，提出了一個新的MRS集群模型(Motsch-Tadmor, MT)。在這個模型中不僅考慮了個體數(shù)量,還考慮了個體在空間中的幾何關(guān)系。但是由于相對距離的引進(jìn)，使得原CS模型中的對稱性質(zhì)遭到破壞，Tadmor通過引進(jìn)一個新的分析方法對復(fù)雜MRS集群性質(zhì)進(jìn)行了開創(chuàng)性的研究。

在MT模型中，考慮一個具有N個子個體的MRS，對于個體i，它在t時刻的位移和速度分別為xi(t)和vi(t)，模型滿足

(12)

其中

2013年，哈爾濱工業(yè)大學(xué)的Dong等[44]在Shen的基礎(chǔ)上，研究了具有自由意志的離散HL模型，并給出了一個自由意志函數(shù)控制的條件以確保系統(tǒng)的集群性。在Dong和Tadmor工作的基礎(chǔ)上，2016年湖南大學(xué)的李樂博士[45]綜合了具有自由意志的離散HL模型[44]和MT模型[43]，提出了具有多領(lǐng)導(dǎo)者、等級制度且描述個體間影響的RH模型?？紤]一個有N個個體的MRS，假設(shè)系統(tǒng)中存在K個等級，等級Ri中存在Ni個個體。Ri中的個體i，在t時刻的位移和速度記為xi(t)和vi(t)。系統(tǒng)在MT個體模型的基礎(chǔ)上加入自由意志，并對不同層級個體分別進(jìn)行描述，驗證了11個個體模型的速度和位置一致性。

2.2.2 高階一致性模型

除上述較為常見的低階積分型線性模型外，更具有普適性的是線性定常模型(Linear Time-Invariant，LTI)，這種模型中每個個體有獨立的多輸入多輸出線性動力學(xué)模型，且階次任意，其模型可表達(dá)為

(13)

其中，xi∈Rn為狀態(tài)信息；ui∈Rp為控制輸入；yi∈Rq為可測的系統(tǒng)矩陣；A、B、C、D為常數(shù)矩陣。

在高階非線性模型研究中，有兩種典型的高階系統(tǒng)模型：Kuramoto模型[46-48]和Brunovsky模型[49]。Kuramoto模型是一種經(jīng)典的非線性動力學(xué)模型，主要用于描述相位或頻率的一致性問題，該模型由n個耦合振蕩器組成，其動力學(xué)方程[48]為

(14)

其中，B為具有N個節(jié)點、e個邊的有向圖的incidence矩陣，j傳輸?shù)絠時Bij=1，反之Bij=-1，無連接時Bij=1;θ和ω分別表示振蕩器的相位和固有頻率；K表示耦合強度。

Brunovsky模型是一種具有代表性的標(biāo)準(zhǔn)高階非線性集群系統(tǒng)[49]，其個體模型通過一個高階積分器耦合未知非線性動力學(xué)以及未知擾動來表示

(15)

其中，i=1，…，n，xij∈R是個體j的第i階狀態(tài)；xj=[x1j,…,xnj]T是個體j的狀態(tài)向量；未知函數(shù)f(·):Rn→R在Rn上局部Lipschitz，且f(0)=0；ζj∈R是未知的但是有界的外部擾動。

2.2.3 異質(zhì)MRS模型

MRS中往往存在不同類型的個體，即系統(tǒng)異構(gòu)或異質(zhì)。在控制系統(tǒng)模型中，通常是指個體動力學(xué)模型不同的系統(tǒng)，而并非是具有不同功能的個體，即異質(zhì)MRS模型。清華大學(xué)的王龍等[50]在2011年首次提出了異質(zhì)MRS模型，將一階和二階模型混合，建立系統(tǒng)模型

(16)

其中，xi∈R,vi∈R,ui∈R是個體i的位置、速度和控制信號。

在王龍[50]工作的基礎(chǔ)上，Kim等[51]則考慮了受環(huán)境因素影響，個體之間的通信連接可能中斷或重連的情況，他們把這種情況描述為一個伯努利概率序列的數(shù)學(xué)模型。根據(jù)通信中斷前的一步信息設(shè)計控制協(xié)議，然后利用線性矩陣不等式，解決了一階和二階異質(zhì)集群系統(tǒng)在離散時間情況下的均方一致性控制問題。

Liu則在王龍等[50]的基礎(chǔ)上，將異質(zhì)系統(tǒng)擴展到更為復(fù)雜的情況：即異質(zhì)系統(tǒng)由線性一階、線性二階和非線性Eulre-Lagrange三類個體動力學(xué)模型組合，并在非線性個體參數(shù)已知和非已知的情況下解決了異質(zhì)MRS的編隊和聚集問題。

(17)

其中，xi∈R,vi∈R,ui∈R是個體i的位置、速度和控制信號；Mi(xi)∈R為一般慣性矩陣；Ci(xi,vi)∈R為科氏力和離心力矩陣。且Eulre-Lagrange方程需滿足以下4個假設(shè)條件

(18)

2.2.4 考慮時延MRS一致性模型

在實際生活中，個體間通信、執(zhí)行計算、執(zhí)行器執(zhí)行等經(jīng)常存在時間延遲的情況，而時延往往會影響系統(tǒng)的穩(wěn)定性。M. M. Gulzar等[52]將時間延遲的情況劃分為四類，分別為：由于通信速度引起的通信時延、傳感器獲取感知信息的控制時延、用于計算控制輸入的計算時延以及執(zhí)行器執(zhí)行動作導(dǎo)致的執(zhí)行時延。

當(dāng)只考慮傳輸信息的狀態(tài)受到時延的影響，即通信時延，則個體的連續(xù)時間一致性模型可以被修改為

(19)

如果同時考慮控制時延、計算時延和執(zhí)行時延這類輸入延遲帶來的時延，個體的連續(xù)時間一致性模型可被修改為

(20)

式(19)和式(20)中，τij>0是個體i與個體j之間的時延。采用這兩種時延模型可以對上述章節(jié)的任意MRS一致性模型進(jìn)行修改，從而形成新的考慮時延的MRS一致性控制模型。以考慮時延的高階非線性Kuramoto模型[47]為例，考慮通信時延的模型可以被修改為

(21)

至此可以看出，基于一致性的MRS模型已得到十分深入且廣泛的研究。從簡單的一階積分系統(tǒng)，逐步擴展至一般線性系統(tǒng)、拓?fù)涓淖兊南到y(tǒng)、高階非線性系統(tǒng)、具有時延的系統(tǒng)和異質(zhì)MRS，且與擬生物行為的模型相比，一致性控制模型具有嚴(yán)格的數(shù)學(xué)基礎(chǔ)和理論依據(jù)，結(jié)果更可信。但是這種方法模型多為主從結(jié)構(gòu)，需要領(lǐng)導(dǎo)者或虛擬領(lǐng)導(dǎo)者。另外在控制過程中并未考慮系統(tǒng)避障的問題，個體間可能發(fā)生相互碰撞的情況。同時若考慮個體間的相互避碰及環(huán)境中的障礙物，暫時無法完全保證一致性模型MRS系統(tǒng)分析方法的收斂性。

2.3 多智能體強化學(xué)習(xí)模型

近些年，隨著強化學(xué)習(xí)的發(fā)展，多智能體強化學(xué)習(xí)(Multi-Agent Deep Reinforcement Learning，MARL)也成為研究MRS的重要方面。MARL首次由Littman[53]于1994年提出，Littman提出了基于零和對策的MARL方法—Minmax-Q，并利用線性規(guī)劃進(jìn)行求解，解決了2個個體的博弈問題。MARL至今已發(fā)展20余年，從整體來看，MARL算法與單個體強化學(xué)習(xí)算法發(fā)展基本一致，歷經(jīng)Q-Learning為基礎(chǔ)的值函數(shù)RL算法、策略梯度優(yōu)化、Actor-Critic方法。Mnih等[54]將深度學(xué)習(xí)(Deep Learning, DL)引入RL框架中后，MADRL算法[55-56]逐漸占據(jù)主流，與基礎(chǔ)RL算法不同，MARL除了RL自身的挑戰(zhàn)外，還需重點考慮個體間關(guān)系(合作、競爭、混合)、非穩(wěn)定性環(huán)境以及與博弈論或圖論等學(xué)科相交叉的問題。MARL方面的MRS建模主要圍繞馬爾可夫決策過程(Markov Decision Process, MDP)及其變體形式展開。

MDP可以由一個元組(S,A,c,P,ρ) 來表示，其中：S表示狀態(tài)空間；A表示動作空間；c(s,a)∈[0, ∞)為代價函數(shù)；P(s′|s,a)為狀態(tài)轉(zhuǎn)移概率；ρ(s)為初始狀態(tài)概率分布。

部分可觀的馬爾可夫決策過程(Partial Observable MDP, POMDP)是MDP 的更一般性描述。一般來說，POMDP中個體i可以描述為POMDPi=，其中：S為環(huán)境的有限狀態(tài)集；Ai為個體i的行為集；Ti為個體i在一種狀態(tài)下采取行為a，到達(dá)某一狀態(tài)的概率的集合；Oi為個體i的觀測；Oi為個體i的觀測函數(shù)，定義了給定動作的觀察概率；Ri為個體i的獎勵函數(shù)，代表i的偏好，R(s,a)表示狀態(tài)s下采取動作a的立即回報。

當(dāng)一組決策者需要以分散的方式做出選擇時，可以將問題建模為分散的部分可觀的馬爾可夫決策過程 (Decentralized POMDP, Dec-POMDP)[57]。雖然Dec-POMDP模型為不確定性下的協(xié)同順序決策提供了一個豐富的框架，但該模型的計算復(fù)雜度是一個重要的研究挑戰(zhàn)。它是POMDP框架的擴展。一般來說，Dec-POMDP中個體i可以描述為POMDPi=，S、Ti、Oi、Ri與POMDP描述一致，其中：I={1, …,n}為n個個體的集合；Ai為個體i的行為集，結(jié)連行為的集合A=×iAi；Oi為個體i的觀測，結(jié)連觀測的集合O=×iOi；h為問題的維度，始終為一個正整數(shù)。

與Dec-POMDP相似，多體MDP(Multi-MDP, MMDP)[57]的描述為：MMDPi=。

當(dāng)考慮到個體間相互競爭和合作的博弈關(guān)系時，一些研究人員通常會結(jié)合博弈論對MARL系統(tǒng)進(jìn)行建模，Hu 等[58]提出了Stochastic game模型，其中：I= {1, …,n}為n個個體的集合；S為環(huán)境的有限狀態(tài)集；對于個體i，有限行為集Ai，回報函數(shù)S×A→Ri，A=A1×A2×…×An；Ti為個體i在某狀態(tài)下采取行為a，到達(dá)另一狀態(tài)的概率S×A×S→[0, 1]。

與上述的模型不同，一般隨機博弈為了尋找一個Nash均衡點，其對于所有的策略滿足πi∈Πi

(22)

受到傳統(tǒng)的多智能體系統(tǒng)(Multi-Agent System, MAS)建模思想的影響，Zhang等[59]將圖論知識引入MARL建模中，提出了Networked Multi-Agent MDP模型，將系統(tǒng)描述為一個元組

(S,{Ai}i∈N,P,{Ri}i∈N,{Gt}t≥0)

(23)

在MARL的框架下，代爾夫特理工大學(xué)的Jelmer等[60]建立了一個最初的MAS框架(圖 4)。將系統(tǒng)分層級描述為particalsPi和動態(tài)個體Ai，Pi用于描述每個個體的物理特性，Ai則是采用MDP的形式描述系統(tǒng)的環(huán)境和智能特性。

圖4 Jelmer模型Fig.4 Jelmert’s model

除上述描述的建模方式外，部分學(xué)者通過對流體近似的研究，以平均場模型的形式建立了MAS控制模型[61]，并設(shè)計了控制策略。平均場模型包括常微分方程、偏微分方程和差分方程，具體取決于個體的狀態(tài)和時間變量是離散或連續(xù)。采用平均場構(gòu)建的宏觀模型與MRS中數(shù)量無關(guān)，與基于個體的群體微觀模型相比，具有更大的可擴展性。通常，平均場建模方法分為有限維模型與無限維模型，有限維模型又分為離散時間模型與連續(xù)時間模型，基于圖論和馬爾可夫鏈的性質(zhì)構(gòu)建流體/隨機系統(tǒng)模型；無限維模型通常設(shè)定初始個體無交互，采用隨機過程，以柯爾莫哥洛夫前向方程和?？似绽士藬U散模型[62]構(gòu)建系統(tǒng)模型。以A. Prorok等[63]的研究為例，其借鑒隨機系統(tǒng)的建模方法，通過?？似绽士藬U散模型提出了一種個體隨時間-空間分布模型，解決了由一組微型機器人執(zhí)行的檢查任務(wù)，并對系統(tǒng)性能做出了準(zhǔn)確的預(yù)測。倫敦大學(xué)學(xué)院的汪軍教授[64]也將平均場理論應(yīng)用于MARL的建模工作中，提出了一種基于博弈論中平均場理論的MARL(Mean Field MARL，MFMARL)算法，致力于極大規(guī)模的MARL問題，有效解決了大規(guī)模數(shù)量MARL問題，雖然有嚴(yán)格的理論證明，但是該模型并不是完全分布式的。

3 研究不足與展望

3.1 可擴展魯棒系統(tǒng)模型

上述方法中考慮的個體數(shù)目動態(tài)變化及分布式的系統(tǒng)模型較少。雖然目前針對聚集和群集2個問題已有部分模型可以解決，如Vicsek模型、Jadbabaie模型及其部分?jǐn)U展工作，但均是在個體等價的前提下進(jìn)行建模。然而在實際任務(wù)中，環(huán)境中的個體數(shù)量可以很大，并且是多種多樣的。此外，由于個體離開(被擊毀或出現(xiàn)故障等)或在執(zhí)行任務(wù)過程中進(jìn)入系統(tǒng)，個體的狀態(tài)數(shù)量也可能會發(fā)生變化，這種問題通常被稱為一個開放的MRS[65]。針對開放的MRS尚未有較完善的相關(guān)可擴展、具有魯棒性的建模方法和問題研究。

3.2 基于MARL的MRS收斂性問題

除3.1節(jié)中提出的問題外，目前MARL方法缺乏對其收斂性和收斂結(jié)果類型的理論認(rèn)識。博弈論均衡是一個可以用來促進(jìn)收斂的理論概念，如相關(guān)均衡和Nash均衡。雖然已有部分這方面的研究[58]，但這些方法的缺點是需要計算均衡解，以及均衡的非唯一性，這需要某種形式的協(xié)調(diào)均衡選擇。最近在這個方向上的研究中，Li等[66]使用了極大極小平衡的近似解，提出了一種新的魯棒MARL算法。Zhang等[59]研究了基于網(wǎng)絡(luò)的MARL問題，提出了兩種具有函數(shù)逼近的分散的actor-critic算法，采用線性函數(shù)逼近的方法對算法的收斂性進(jìn)行理論分析，并采用最大熵強化學(xué)習(xí)產(chǎn)生對MRS建模錯誤和分布轉(zhuǎn)移具有魯棒性的潛力。然而，到目前為止，對MARL方法的收斂性問題還缺乏詳細(xì)的理論探索及可靠的建模形式。

3.3 綜合系統(tǒng)能力與運動學(xué)建模

傳統(tǒng)的自組織MRS建模方式，大多數(shù)考慮了個體的動力學(xué)模型，但并未考慮個體的能力，也就是默認(rèn)了系統(tǒng)中個體能力相同，即為同構(gòu)。在MARL模型中，目前大部分的工作都集中于同構(gòu)MRS中，且一般不考慮個體的動力學(xué)模型。然而在實際任務(wù)中，系統(tǒng)中的個體常常具有不同的能力，也就是系統(tǒng)異構(gòu)，且需考慮個體的運動模型。在MRS異構(gòu)的環(huán)境中，綜合系統(tǒng)中個體能力及運動學(xué)特性，構(gòu)建完整的系統(tǒng)模型，快速有效地完成動態(tài)任務(wù)，這樣的模型屈指可數(shù)[67-68]，且都是僅在理論探索階段。

3.4 系統(tǒng)評估

目前的MRS建模方式幾乎沒有對系統(tǒng)性能及智能化水平的評價。通常只是根據(jù)任務(wù)直接進(jìn)行分配或控制，對于系統(tǒng)是否具備相應(yīng)的智能化水平，以及多樣性是否滿足均無評測，抑或是僅僅進(jìn)行定性分析。對系統(tǒng)的評估，往往有助于更加快速有效地完成系統(tǒng)任務(wù)，近些年A. Prorok[67]從度量多樣性定量評估系統(tǒng)性能，K. P.Valavanis[69]采用熵的方法評估系統(tǒng)的智能化程度。兩位學(xué)者做出了前期探索，但是如何系統(tǒng)建立可以評價系統(tǒng)多樣性和智能化水平的系統(tǒng)模型，以及采用什么方法去評價都是亟待解決的問題之一。

4 結(jié)論

隨著更多的國內(nèi)外團(tuán)隊加入MRS的研究，MRS建模將會越來越完善，本文從一致性控制理論建模方法、基于擬生物行為、強化學(xué)習(xí)的建模方法幾個方面進(jìn)行總結(jié)與分析。同時針對現(xiàn)有模型，總結(jié)了一些仍待解決的典型建模問題，如何建立可擴展、魯棒的異構(gòu)MRS模型，如何在復(fù)雜環(huán)境中應(yīng)用，如何建立可評價系統(tǒng)指標(biāo)的完整模型等。隨著這些問題的解決， MRS將更加廣泛地應(yīng)用于生產(chǎn)生活、軍事作戰(zhàn)之中，讓社會進(jìn)入更加自主化的時代。