張汝云，肖戈揚(yáng)，單麒赫，鄒濤，李丹，滕菲

（1.之江實(shí)驗(yàn)室智能網(wǎng)絡(luò)研究院，浙江 杭州 311121；2.大連海事大學(xué)航海學(xué)院，遼寧 大連 116026；3.信息工程大學(xué)信息技術(shù)研究所，河南 鄭州 450002；4.大連海事大學(xué)船舶電氣工程學(xué)院，遼寧 大連 116026）

0 引言

多智能體系統(tǒng)（MAS,multi-agent system）協(xié)同控制的研究在現(xiàn)階段科學(xué)發(fā)展中的應(yīng)用十分廣泛。例如編隊(duì)控制、避碰避障控制、通信組網(wǎng)設(shè)計(jì)等。隨著云計(jì)算、人工智能、通信網(wǎng)絡(luò)等領(lǐng)域的發(fā)展，MAS 協(xié)同控制與這些新興領(lǐng)域技術(shù)相互融合，已取得一些成果[1]。然而，MAS 協(xié)同控制方法仍然存在許多問題，比如不確定性、通信拓?fù)?、多一致性等?/p>

目前，MAS 協(xié)同控制的研究?jī)H對(duì)單邊主義通信網(wǎng)絡(luò)下的單個(gè)MAS 的協(xié)同控制進(jìn)行研究和設(shè)計(jì)。然而，由于多智能體實(shí)際工況下所處環(huán)境不斷變化且其所面臨任務(wù)也越來越復(fù)雜，導(dǎo)致僅單個(gè)MAS協(xié)作常常無法勝任。因此，在面對(duì)更大規(guī)模復(fù)雜任務(wù)時(shí)，需要多個(gè)不同功能的MAS（MMAS,mutiple-functional multi-agent system）實(shí)現(xiàn)多邊化的分布式協(xié)同控制來應(yīng)對(duì)和完成任務(wù)。MMAS 多邊化分布式協(xié)同控制的含義是通過構(gòu)建一個(gè)合理的通信拓?fù)浣Y(jié)構(gòu)，設(shè)計(jì)一個(gè)合適的分布式控制協(xié)議，使面向任務(wù)重新分組后各組內(nèi)所有智能體最終趨于一致，進(jìn)而實(shí)現(xiàn)多個(gè)具有不同功能的多智能體系統(tǒng)的協(xié)同控制。然而，在MMAS 多邊化分布式協(xié)同控制過程中，會(huì)存在以下問題。

1) MAS 協(xié)同控制一般要借助于通信網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)來實(shí)現(xiàn)，單個(gè)智能體通過與其鄰居之間進(jìn)行信息交互來實(shí)現(xiàn)協(xié)作，現(xiàn)階段研究?jī)H限于單邊主義通信網(wǎng)絡(luò)下單個(gè)MAS 實(shí)現(xiàn)協(xié)同控制。在面對(duì)大規(guī)模復(fù)雜任務(wù)和時(shí)變工況時(shí)，處在單邊主義通信網(wǎng)絡(luò)下的MAS 之間不能進(jìn)行信息交互，無法實(shí)現(xiàn)MMAS多邊化分布式協(xié)同控制，導(dǎo)致無法完成最終任務(wù)。

2) 即使MAS 之間可以實(shí)現(xiàn)信息交互，但簡(jiǎn)單地將MMAS 組網(wǎng)也不能保證實(shí)現(xiàn)多邊化分布式協(xié)同控制。MAS 通信拓?fù)浣Y(jié)構(gòu)需要滿足一定條件才能保證分布式協(xié)同控制的實(shí)現(xiàn)，面向復(fù)雜多樣化任務(wù)需要對(duì)MMAS 內(nèi)各個(gè)MAS 進(jìn)行分析和重組，設(shè)計(jì)一種合理的通信拓?fù)浣Y(jié)構(gòu)。

為了解決上述問題，本文針對(duì)多模態(tài)網(wǎng)絡(luò)下MMAS 提出一種通信拓?fù)渲貥?gòu)方法，為實(shí)現(xiàn)多邊化分布式協(xié)同控制奠定基礎(chǔ)，以應(yīng)對(duì)大規(guī)模復(fù)雜任務(wù)。對(duì)此，本文有以下貢獻(xiàn)。

1) 隨著新型網(wǎng)絡(luò)環(huán)境的發(fā)展，基于多模態(tài)網(wǎng)絡(luò)[2]構(gòu)建MMAS 多邊化分布式協(xié)同控制框架，以實(shí)現(xiàn)開放網(wǎng)絡(luò)環(huán)境下MMAS 協(xié)同控制，突破單個(gè)MAS協(xié)作無法完成日漸復(fù)雜和多樣化任務(wù)的局限性。

2) 基于外部公平劃分（EEP,external equitable partition）算法對(duì)MMAS 中多個(gè)MAS 進(jìn)行分組，提出MMAS 通信拓?fù)渲貥?gòu)方法，使在同一組內(nèi)各個(gè)MAS 趨于一致，整個(gè)MMAS 達(dá)到多一致性，進(jìn)而實(shí)現(xiàn)多邊化分布式協(xié)同控制。

1 相關(guān)工作

本文主要研究多模態(tài)網(wǎng)絡(luò)下MMAS 多邊化分布式協(xié)同控制問題，下面，分別從多智能體協(xié)同控制和多模態(tài)網(wǎng)絡(luò)兩方面進(jìn)行相關(guān)工作闡述。

1.1 多智能體協(xié)同控制

智能體是一種擁有獨(dú)立思考并在環(huán)境中自主調(diào)節(jié)的實(shí)體，是使人工智能技術(shù)實(shí)現(xiàn)的一種載體[3]。但是，隨著任務(wù)越來越復(fù)雜，單個(gè)智能體的處理能力有限，所以MAS 引起了相關(guān)領(lǐng)域研究者的關(guān)注。協(xié)同控制是MAS 領(lǐng)域的關(guān)鍵研究問題，其在編隊(duì)控制、集群控制等領(lǐng)域中都有廣泛的應(yīng)用，并有很多的研究成果。Borkar 等[4]提出多個(gè)智能體基于通信協(xié)議進(jìn)行信息交換，來達(dá)到協(xié)同控制，從而完成預(yù)期的復(fù)雜任務(wù)。Degroot[5]在控制領(lǐng)域中首次結(jié)合一致性的思想，提出了加權(quán)平均一致性算法，并且考慮了傳感器接收不確定性信息的問題。Viscek 等[6]建立了一種離散時(shí)間模型，每個(gè)粒子通過通信協(xié)議得到鄰居粒子的狀態(tài)信息，來改變自身運(yùn)動(dòng)狀態(tài)，從而使粒子群在有限時(shí)間內(nèi)速度收斂，并實(shí)現(xiàn)一致性。Jadbabaie 等[7]基于Viscek 模型，通過使用代數(shù)圖論，首次對(duì)一致性問題進(jìn)行理論性的研究，證明了MAS 中所有智能體最終收斂趨于一致。Moreau[8]基于凸理論、系統(tǒng)理論、圖論等知識(shí)研究了有向網(wǎng)絡(luò)下MAS 的一致性問題，并提出了智能體之間通信次數(shù)過多會(huì)影響系統(tǒng)的收斂速度。Olfati-saber 等[9]證明了MAS 的通信網(wǎng)絡(luò)拓?fù)溥B通度與其收斂速度有關(guān)。Ren 等[10]基于代數(shù)圖論進(jìn)一步探討了連續(xù)時(shí)間下的一致性，證明了系統(tǒng)收斂到一致狀態(tài)的充要條件。然而，當(dāng)通信網(wǎng)絡(luò)不連通或面對(duì)多種復(fù)雜任務(wù)時(shí)，MAS 無法達(dá)到一致性，因此需要對(duì)MAS 進(jìn)行通信拓?fù)浣Y(jié)構(gòu)設(shè)計(jì)。Olfati-saber 等[11]和Gambuzza 等[12]研究了MAS 網(wǎng)絡(luò)的多一致性控制問題，對(duì)一個(gè)具有單元間交互的基本有向圖和期望的多一致性MAS，基于EEP 來對(duì)MAS 進(jìn)行通信拓?fù)渲貥?gòu)，通過分布式控制來驅(qū)使MAS 朝著目標(biāo)狀態(tài)發(fā)展，為實(shí)現(xiàn)MAS 的多一致性提供了理論依據(jù)和解決方法。通信拓?fù)涞倪B通性是研究MAS 協(xié)同控制的理論前提[13]，對(duì)此Wang 等[14]和Liu 等[15]基于代數(shù)圖論和Warshall 算法針對(duì)復(fù)雜網(wǎng)絡(luò)提出了一種連通性判斷的算法。

隨著時(shí)間的推移，MAS 內(nèi)的所有個(gè)體的狀態(tài)最終均趨近于同一個(gè)狀態(tài)值，被稱為一致性。一致性問題是MAS 協(xié)同控制的基礎(chǔ)問題，但利用一致性完成多目標(biāo)任務(wù)時(shí)存在一定的局限性，系統(tǒng)在同一時(shí)間內(nèi)無法完成多個(gè)任務(wù)。而且在MAS 的實(shí)際應(yīng)用中，外部環(huán)境復(fù)雜多變，協(xié)作任務(wù)隨機(jī)分配，甚至?xí)r間的變化都有可能導(dǎo)致網(wǎng)絡(luò)中的智能體收斂到多個(gè)一致性的現(xiàn)象出現(xiàn)，這種狀態(tài)被稱為多一致性[16]。

1.2 多模態(tài)網(wǎng)絡(luò)

“構(gòu)建多模態(tài)網(wǎng)絡(luò)環(huán)境”發(fā)展理念是由鄔江興院士在2021 年首次提出的[17]，其基本思想是在面對(duì)逐漸復(fù)雜的網(wǎng)絡(luò)環(huán)境時(shí)，通過設(shè)計(jì)一種基于全維可定義平臺(tái)的開放式網(wǎng)絡(luò)架構(gòu)，來解決多元化網(wǎng)絡(luò)中出現(xiàn)的一系列問題。Li 等[18]提出獨(dú)立于IP 的新型網(wǎng)絡(luò)體系，即一種實(shí)現(xiàn)共治共管共享的后IP 時(shí)代的環(huán)境，達(dá)到了多邊共管、平等開放、性能高效、去中心化等目標(biāo)。在國(guó)家973 計(jì)劃“可重構(gòu)信息通信基礎(chǔ)網(wǎng)絡(luò)體系研究”的項(xiàng)目支持下，蘭巨龍等[19]提出了“可重構(gòu)網(wǎng)絡(luò)”的思想?；谏鲜稣J(rèn)識(shí)，李揮等[2]繼續(xù)提出一種開放的網(wǎng)絡(luò)架構(gòu)，突破了現(xiàn)有網(wǎng)絡(luò)技術(shù)對(duì)網(wǎng)絡(luò)拓?fù)?、通信、連接的技術(shù)難題，來滿足基于多邊主義下網(wǎng)絡(luò)多元化發(fā)展的需求。這些研究的出現(xiàn)，意味著當(dāng)前網(wǎng)絡(luò)環(huán)境有著革命性創(chuàng)新的發(fā)展趨勢(shì)[20]。

MAS 作為人工智能領(lǐng)域中熱門的研究方向，智能體之間通過分布式協(xié)同控制達(dá)成多一致性，以解決復(fù)雜的問題。近些年，隨著互聯(lián)網(wǎng)智能化和數(shù)字化發(fā)展的不斷升級(jí)，為了使工業(yè)網(wǎng)絡(luò)、家庭網(wǎng)絡(luò)、無人駕駛和智慧城市建設(shè)能更好地適應(yīng)新型的網(wǎng)絡(luò)環(huán)境，上述MAS 網(wǎng)絡(luò)的結(jié)構(gòu)需要升級(jí)重構(gòu)，并要符合多模態(tài)智慧網(wǎng)絡(luò)技術(shù)的發(fā)展需求——多元化、高性能、個(gè)性化、智能化[21]。MAS 在解決這些問題上有一定優(yōu)勢(shì)[22]，主要體現(xiàn)在以下幾點(diǎn)。

首先，MAS 具有獨(dú)立性與自主性。智能體在執(zhí)行任務(wù)時(shí)，可以自主地選擇相應(yīng)的策略來解決問題，最終使系統(tǒng)達(dá)到一致性。在設(shè)計(jì)MAS 時(shí)，對(duì)智能體進(jìn)行分層分組式管理，對(duì)同一任務(wù)配置多個(gè)智能體，從而降低單個(gè)智能體完成任務(wù)的復(fù)雜程度。在對(duì)大型系統(tǒng)或網(wǎng)絡(luò)進(jìn)行控制和管理時(shí)，通過拓?fù)湓O(shè)計(jì)，可對(duì)MAS 多模塊化處理，有效降低控制算法的復(fù)雜度。

其次，MAS 具有協(xié)作性。在MAS 中，各個(gè)智能體互相通信與協(xié)商，調(diào)整各自的行為，高效地完成復(fù)雜任務(wù)。面對(duì)規(guī)模較大、數(shù)量較多的任務(wù)時(shí)，可以將系統(tǒng)劃分成不同單元，單元之間相互協(xié)作，通過約束性算法完成這些復(fù)雜任務(wù)并達(dá)到多一致性。

最后，MAS 具有分布性和異構(gòu)性。每個(gè)智能體可以看作機(jī)器人、計(jì)算機(jī)、無人車等由不同的編程語言和開發(fā)理念設(shè)計(jì)出來的實(shí)體。

上述優(yōu)勢(shì)僅僅局限于單邊網(wǎng)絡(luò)環(huán)境，即一個(gè)MAS 就可勝任的復(fù)雜任務(wù)。但隨著多邊化網(wǎng)絡(luò)體系的發(fā)展，在面對(duì)更大規(guī)模的復(fù)雜任務(wù)時(shí)，其周圍環(huán)境也會(huì)隨著時(shí)間改變，未知的擾動(dòng)和影響會(huì)限制甚至阻礙單個(gè)MAS 的控制。為了突破單邊MAS 控制的局限性，結(jié)合多模態(tài)網(wǎng)絡(luò)環(huán)境下多邊共治的設(shè)計(jì)理念，基于上述認(rèn)知，本文針對(duì)多模態(tài)網(wǎng)絡(luò)下MMAS 提出一種通信拓?fù)渲貥?gòu)方法，為實(shí)現(xiàn)多邊化分布式協(xié)同控制奠定基礎(chǔ)，以應(yīng)對(duì)大規(guī)模復(fù)雜任務(wù)，所以未來的多智能體協(xié)同控制將會(huì)依賴于多模態(tài)網(wǎng)絡(luò)。

2 MMAS 多邊化分布式協(xié)同控制框架

MMAS 多邊化分布式協(xié)同控制是基于多模態(tài)網(wǎng)絡(luò)環(huán)境通過MAS 間交互信息來實(shí)現(xiàn)的，其框架如圖1 所示，具有分布式、多邊共管、即插即用、平等開放、結(jié)構(gòu)可擴(kuò)展等特點(diǎn)，可以實(shí)現(xiàn)復(fù)雜任務(wù)的快速響應(yīng)、高效處理，來更好地服務(wù)和推動(dòng)新型網(wǎng)絡(luò)技術(shù)的發(fā)展與升級(jí)。

圖1 中，MISSION 1 為系統(tǒng)當(dāng)前所執(zhí)行的任務(wù)，MISSION 2 為系統(tǒng)結(jié)束當(dāng)前任務(wù)后所執(zhí)行的下一個(gè)任務(wù)。由圖1 可知，MMAS 由多個(gè)具有不同功能的MAS 組成，分別是無人水面艇（USV,unmanned surface vessel）、無人機(jī)（UAV,unmanned aerial vehicle）和自主式水下潛器（AUV,autonomous underwater vehicle）。在面向復(fù)雜任務(wù)時(shí)，MMAS不再由單個(gè)MAS 完成，而是由上述多個(gè)MAS 通過多邊化分布式協(xié)同控制來實(shí)現(xiàn)的。

圖1 MMAS 多邊化分布式協(xié)同控制框架

MMAS 中的每個(gè)MAS 都是任務(wù)的執(zhí)行者和參與者，并存在于同一網(wǎng)絡(luò)層次中。針對(duì)不同任務(wù)需求，要求多個(gè)具有不同功能的MAS 進(jìn)行組隊(duì)來執(zhí)行。若遇到工況時(shí)變，參與任務(wù)的MAS 數(shù)量不夠，空閑適合的鄰居MAS 就可以隨時(shí)加入任務(wù)中。

MMAS多邊化分布式協(xié)同控制框架由2個(gè)層級(jí)組成，分別為任務(wù)發(fā)送方和任務(wù)執(zhí)行方。任務(wù)發(fā)送方是動(dòng)態(tài)的主體，在圖1 中，任務(wù)發(fā)送方解析和評(píng)估第三方提交任務(wù)的風(fēng)險(xiǎn)和難度等級(jí)，合理分配任務(wù)，并且將任務(wù)發(fā)送給其他任務(wù)發(fā)送方，在完成任務(wù)分配后，此任務(wù)發(fā)送方恢復(fù)為與其他任務(wù)發(fā)送方相同級(jí)別的通信水平，來向不同任務(wù)執(zhí)行方發(fā)送任務(wù)；任務(wù)執(zhí)行方，即圖1 中3 種不同的MAS（USV、UAV 和AUV），其可根據(jù)自身情況，通過信息交互選擇接受或拒絕附近任務(wù)發(fā)送方所分配的任務(wù)，在接受任務(wù)后，可與其他的MAS 建立合適的通信網(wǎng)絡(luò)組成MMAS，實(shí)現(xiàn)多邊化分布式協(xié)同控制。具體操作步驟如下。

步驟1任務(wù)受理。根據(jù)就近原則，距離第三方最近的任務(wù)發(fā)送方接受任務(wù)并臨時(shí)成為任務(wù)解析方，對(duì)任務(wù)的風(fēng)險(xiǎn)及難度進(jìn)行解析評(píng)估，并對(duì)其周圍處于不同單邊主義網(wǎng)絡(luò)環(huán)境下的任務(wù)發(fā)送方分配具體任務(wù)需求。

步驟2任務(wù)發(fā)送。任務(wù)解析方與其他的任務(wù)發(fā)送方進(jìn)行信息交互并通過網(wǎng)絡(luò)部署任務(wù)，在任務(wù)分配結(jié)束后，任務(wù)解析方恢復(fù)成與其他任務(wù)發(fā)送方同級(jí)別的通信水平，每個(gè)任務(wù)發(fā)送方均可與附近的一個(gè)或多個(gè)MAS 通信。

步驟3任務(wù)接受。各個(gè)任務(wù)執(zhí)行方，即合適的MAS接受任務(wù)（如圖1中的USV、UAV和AUV），通過通信網(wǎng)絡(luò)與其他接受任務(wù)的MAS 建立臨時(shí)通信，組成一個(gè)結(jié)構(gòu)簡(jiǎn)單的MMAS。

步驟4任務(wù)執(zhí)行。臨時(shí)組建的MMAS 需要滿足一定的通信拓?fù)浣Y(jié)構(gòu)條件，當(dāng)不滿足條件時(shí)，通過對(duì)MMAS 的通信拓?fù)浣Y(jié)構(gòu)進(jìn)行拓?fù)湓O(shè)計(jì)，使重構(gòu)后的MMAS 達(dá)到要求，進(jìn)而實(shí)現(xiàn)多邊化分布式協(xié)同控制，協(xié)作完成任務(wù)。

步驟5任務(wù)完成。在完成一次任務(wù)后，MMAS自行解散，并等待下一個(gè)任務(wù)的分配，再重新組隊(duì)。

上述提出的MMAS 多邊化分布式協(xié)同控制架構(gòu)的設(shè)計(jì)在多模態(tài)網(wǎng)絡(luò)環(huán)境下秉承著去中心化、即插即用、多邊共管的理念，實(shí)現(xiàn)了多個(gè)單邊主義網(wǎng)絡(luò)環(huán)境下MAS 面向任務(wù)的動(dòng)態(tài)組隊(duì)，通過多個(gè)MAS 的協(xié)作可以更加靈活地滿足復(fù)雜多樣的任務(wù)需求。

3 MMAS 通信拓?fù)渲貥?gòu)方法

MAS 實(shí)現(xiàn)協(xié)同控制需要依賴通信網(wǎng)絡(luò)，當(dāng)通信網(wǎng)絡(luò)是多模態(tài)網(wǎng)絡(luò)下的通信網(wǎng)絡(luò)時(shí)，才能構(gòu)建新的多智能體團(tuán)隊(duì)（即本文提到的MMAS）。這種情況下MMAS 可以實(shí)現(xiàn)多邊化分布式協(xié)同控制，所以多模態(tài)網(wǎng)絡(luò)下的通信拓?fù)渲貥?gòu)是實(shí)現(xiàn)多邊化多智能體分布式協(xié)同控制的基礎(chǔ)。

多模態(tài)網(wǎng)絡(luò)下的MMAS 在面向任務(wù)時(shí)需要通信拓?fù)渲貥?gòu)，本節(jié)提出一種通信拓?fù)渲貥?gòu)方法來對(duì)其進(jìn)行研究。

3.1 代數(shù)圖論和MAS 模型

MAS 網(wǎng)絡(luò)是一種基于底層網(wǎng)絡(luò)通信的復(fù)雜系統(tǒng)，用圖論中的G=(V,E,A) 來表示系統(tǒng)的網(wǎng)絡(luò)結(jié)構(gòu)，一種具有n個(gè)節(jié)點(diǎn)（或頂點(diǎn)）和e條邊（或鏈接）的圖，其中，V={w1,w2,…,wn}是一個(gè)有限的非空節(jié)點(diǎn)集；E?V×V是G中節(jié)點(diǎn)所構(gòu)成的邊集，簡(jiǎn)稱為邊。邊表示節(jié)點(diǎn)之間的鄰居關(guān)系，對(duì)于2 個(gè)節(jié)點(diǎn)wi,w j∈V，其中i≠j，有(wi,wj)∈E，稱wi和wj可以進(jìn)行通信；用表示鄰接矩陣，若(wi,wj)∈E，則wij=1，若(wi,wj)?E，則wij=0，其中i≠j；用D=diag{d1,d2,…,dn}表示度矩陣，其中。

對(duì)于無向圖，L=LT且L可對(duì)角化。在這種情況下，拉普拉斯矩陣是半正定的，所有特征值為零或正，如果拉普拉斯矩陣有一個(gè)零特征值對(duì)應(yīng)的特征向量為1，則圖是連通的。在有向情況下，拉普拉斯矩陣不一定是對(duì)稱的，但所有特征值都有半正實(shí)部。

定義1如果一個(gè)有向圖的無向型是連通的，也就是說，如果它的無向型在每對(duì)節(jié)點(diǎn)之間總是存在一條路徑，并且沒有不可到達(dá)的節(jié)點(diǎn)，則稱它為弱連通。

定義2如果一個(gè)有向圖的每對(duì)節(jié)點(diǎn)之間總是存在一條有向路徑，并且沒有不可到達(dá)的節(jié)點(diǎn)，則稱該有向圖為強(qiáng)連通圖，且rank(L)=n-1。

本文主要的研究對(duì)象是線性一階積分控制的多智能體系統(tǒng)，多智能體系統(tǒng)的狀態(tài)滿足如下動(dòng)態(tài)方程

其中，xi(t)∈Rn為智能體的狀態(tài)，u i(t)∈Rp為系統(tǒng)的控制輸入，A、B為合適維度的常數(shù)矩陣。

通過式(1)中的動(dòng)態(tài)方程，考慮其離散的一致性控制方程為

其中，L為MAS 的拉普拉斯算子。

3.2 MMAS 連通性判定

在對(duì)MMAS 設(shè)計(jì)時(shí)，需要對(duì)系統(tǒng)通信網(wǎng)絡(luò)的連通性進(jìn)行分析。當(dāng)系統(tǒng)通信網(wǎng)絡(luò)連通時(shí)，可以對(duì)其進(jìn)行控制；當(dāng)系統(tǒng)通信網(wǎng)絡(luò)不連通時(shí)，需要對(duì)其進(jìn)行通信拓?fù)渲貥?gòu)。

關(guān)于連通性的研究對(duì)設(shè)計(jì)多邊環(huán)境下的MMAS 網(wǎng)絡(luò)十分關(guān)鍵。在設(shè)計(jì)一個(gè)MMAS 網(wǎng)絡(luò)時(shí)既要符合節(jié)能節(jié)約的理念，也要避免網(wǎng)絡(luò)連通性被破壞。對(duì)此，本文通過對(duì)MMAS 網(wǎng)絡(luò)的鄰接矩陣的結(jié)構(gòu)進(jìn)行分析，基于可達(dá)矩陣算法[23]、Warshell算法[15]以及Wang 等[14]算法，來判斷鄰接矩陣的連通性，并設(shè)計(jì)特殊的隨機(jī)矩陣來模擬MAS 網(wǎng)絡(luò)，得出連通性和矩陣結(jié)構(gòu)之間的關(guān)系，從而達(dá)到優(yōu)化設(shè)計(jì)的目標(biāo)。

定義3設(shè)G=(V,E,A)為n階有向圖，定義矩陣P=(pij)n×n，有

則稱矩陣P是有向圖G的可達(dá)矩陣。

上述方法對(duì)于復(fù)雜的有向圖，即當(dāng)G的階數(shù)較大時(shí)，無法直接判斷。對(duì)此，通過鄰接矩陣A，也可以計(jì)算可達(dá)矩陣P。先計(jì)算B=A+A2+…+An，再通過

來構(gòu)造可達(dá)矩陣P。

對(duì)A中的每個(gè)節(jié)點(diǎn)i，找出通過有向邊到達(dá)節(jié)點(diǎn)i的所有節(jié)點(diǎn)j，其中i≠j，再將這些節(jié)點(diǎn)j所在行和節(jié)點(diǎn)i所在的行邏輯相加，作為這些節(jié)點(diǎn)j的新行，稱為Warshell 算法，該算法的連通性判定如算法1 所示。

算法1基于Warshell 算法的連通性判定

定義隨機(jī)鄰接矩陣As，對(duì)As中的每個(gè)節(jié)點(diǎn)i，找出通過有向邊到達(dá)節(jié)點(diǎn)i的所有節(jié)點(diǎn)j，其中i≠j，再將這些節(jié)點(diǎn)j所在行和節(jié)點(diǎn)i所在的行邏輯相加，作為這些節(jié)點(diǎn)j的新行。

Warshell 算法和可達(dá)矩陣算法都是面向網(wǎng)絡(luò)的直接搜索算法。Warshell 算法的優(yōu)點(diǎn)是結(jié)構(gòu)簡(jiǎn)單并運(yùn)用了高效的位運(yùn)算方法，但其復(fù)雜度高于O(2n3)，其中n是網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)，只限于判斷簡(jiǎn)單網(wǎng)絡(luò)圖的連通性?？蛇_(dá)矩陣算法的復(fù)雜度高于O(n4)，在大規(guī)模的實(shí)際網(wǎng)絡(luò)中很少使用。通過對(duì)比Warshell 算法和可達(dá)矩陣算法的優(yōu)缺點(diǎn)，本文基于Wang 等算法提出了一種針對(duì)復(fù)雜網(wǎng)絡(luò)連通性高效的判斷算法，來對(duì)通信網(wǎng)絡(luò)拓?fù)溥M(jìn)行判斷，通過判斷和排序以及n次加法運(yùn)算，其復(fù)雜度為O(n3+4.5n2)。相對(duì)于可達(dá)矩陣算法和Warshell 算法，Wang 等算法復(fù)雜度更小、應(yīng)用范圍更廣?；趶?fù)雜網(wǎng)絡(luò)連通性高效的判斷算法，本節(jié)設(shè)計(jì)了一種求隨機(jī)矩陣最優(yōu)連通率的算法，如算法2 所示。

算法2多邊化網(wǎng)絡(luò)最小鏈路設(shè)計(jì)連通性判定算法

定義n階隨機(jī)鄰接矩陣As，記鄰接矩陣As中元素為，W(As)為非零值的個(gè)數(shù)，設(shè)As中的每個(gè)智能體i與其他智能體j直接連接的概率為α(i≠j;i=1,2,…,n;0＜α＜1)。

通過實(shí)驗(yàn)數(shù)據(jù)，找出臨界的連接概率αc，當(dāng)α≥αc時(shí)，連通率γ=1，As是連通的。則對(duì)于每個(gè)n階隨機(jī)矩陣As，當(dāng)As中每個(gè)節(jié)點(diǎn)與其他節(jié)點(diǎn)的連接概率為αc，即α=αc時(shí)，此n階矩陣As是連通的。從實(shí)驗(yàn)數(shù)據(jù)中可得，每個(gè)n階矩陣對(duì)應(yīng)的臨界連接概率為αc。

通過上述實(shí)驗(yàn)結(jié)果對(duì)矩陣的階數(shù)n和臨界的連接概率αc進(jìn)行數(shù)據(jù)擬合，得出矩陣的階數(shù)n和連接概率αc的擬合函數(shù)為。

在MAS 通信網(wǎng)路中，節(jié)點(diǎn)之間通信連接的密度影響著網(wǎng)絡(luò)的連通性，節(jié)點(diǎn)通信連接的密度降低會(huì)使網(wǎng)絡(luò)失去連通性；通信連接的密度過大雖然會(huì)提高連通性，但網(wǎng)絡(luò)通信會(huì)發(fā)生阻塞，節(jié)點(diǎn)通信負(fù)擔(dān)增大，節(jié)點(diǎn)的能量消耗也增加，浪費(fèi)了有效資源，不符合多模態(tài)網(wǎng)絡(luò)環(huán)境中高效能的理念。通過對(duì)矩陣階數(shù)n和臨界概率αc進(jìn)行研究，得出每個(gè)節(jié)點(diǎn)最優(yōu)的連接鄰居的數(shù)量。

然而在多模態(tài)網(wǎng)絡(luò)環(huán)境下，MMAS 的任務(wù)要求各個(gè)MAS 自愿參與，若單個(gè)MAS 決定拒絕與其他MAS 合作，并且其狀態(tài)保持不變，即使其余MAS達(dá)到了一致性，整個(gè)任務(wù)也無法執(zhí)行；處在一個(gè)單元中的多個(gè)MAS 拒絕與其他MAS 合作，并且刪除這個(gè)單元的MAS 通信連接，可能會(huì)導(dǎo)致網(wǎng)絡(luò)連通性被破壞。在一個(gè)連接斷開的網(wǎng)絡(luò)中，所有MAS不可能達(dá)成一致性，因此MMAS 連通性的設(shè)計(jì)是研究多一致性的基礎(chǔ)。本文在MMAS 保持連通性的基礎(chǔ)上，通過對(duì)MMAS 的結(jié)構(gòu)進(jìn)行拓?fù)湓O(shè)計(jì)，讓MMAS 達(dá)到多一致性，從而滿足不同功能的設(shè)備之間通過分組作業(yè)完成預(yù)期的任務(wù)。

3.3 基于外部公平劃分的MMAS 通信拓?fù)渲貥?gòu)

當(dāng)MMAS 的通信網(wǎng)絡(luò)結(jié)構(gòu)不符合設(shè)計(jì)要求時(shí)，需要對(duì)MMAS 內(nèi)擁有相同結(jié)構(gòu)和算法的MAS 進(jìn)行分組、歸類。通過使用外部公平劃分的方法對(duì)MMAS 的通信網(wǎng)絡(luò)進(jìn)行拓?fù)渲貥?gòu)，來實(shí)現(xiàn)重新分組后處于同組內(nèi)的MAS 達(dá)成一致性，從而使整個(gè)MMAS 達(dá)到多一致性控制要求。

研究網(wǎng)絡(luò)動(dòng)態(tài)系統(tǒng)的一個(gè)重要問題是從網(wǎng)絡(luò)拓?fù)渲型茢嗄承┚W(wǎng)絡(luò)特性，無論是在分析還是在控制方面，網(wǎng)絡(luò)拓?fù)渫ǔＳ傻讓泳W(wǎng)絡(luò)有向圖表示，這一問題在集群同步的背景下得到了廣泛的研究。研究發(fā)現(xiàn)圖劃分的概念也是研究多智能體系統(tǒng)一致性的最短收斂時(shí)間、可控性和可觀測(cè)性的基礎(chǔ)。

圖劃分的一個(gè)典型例子是公平劃分，它將入度數(shù)量恒定的節(jié)點(diǎn)分組到單元中。EEP 的概念也被定義為幾乎公平劃分或?qū)捤晒絼澐帧?/p>

給定一個(gè)有向圖G和其頂點(diǎn)集V(G)，每一個(gè)劃分π都是一個(gè)頂點(diǎn)的映射，它將V劃分成m個(gè)不同的單元，即q1,q2,…,qm，有，其中i≠j。

定義4如果劃分π={q1,q2,…,qm}中任意2 個(gè)單元ql與qk，包括l=k，存在一個(gè)常數(shù)dlk，使每個(gè)在ql里的節(jié)點(diǎn)在qk中都有dlk個(gè)鄰居，則稱劃分π={q1,q2,…,qm}是公平的。

因此，公平劃分的概念要求一個(gè)單元內(nèi)的節(jié)點(diǎn)相對(duì)于任何其他單元具有相同的出度數(shù)。

定義5給定一個(gè)圖G和頂點(diǎn)集V(G)的劃分π={q1,q2,…,qm}，如果對(duì)于任意一對(duì)單元ql與qk，其中l(wèi)≠k，單元ql中每一個(gè)節(jié)點(diǎn)在qk中都有dlk個(gè)的鄰居，則稱π是EEP。

在EEP 中，由于劃分產(chǎn)生的圖是否規(guī)則并不重要，因此一個(gè)單元中的節(jié)點(diǎn)不一定具有相同數(shù)量的鄰居。雖然公平劃分的單元對(duì)每個(gè)單元都有相同的出度數(shù)，但在EEP 中，這只適用于不同單元之間的連接數(shù)。

定義6商圖。給定一個(gè)EEP，關(guān)聯(lián)商圖有若干個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)數(shù)量等于分區(qū)的大?。總€(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)分區(qū)的單元格），有向邊權(quán)重由分區(qū)單元格之間的出度給出，如圖2 所示。

圖2 無向圖和商圖

將給定的n圖G劃分成m個(gè)單元，每個(gè)單元都可以用特征矩陣P∈Rn×m表示

通過特征矩陣P，令N=PTP，其中N∈Rm×m，N的對(duì)角線上的元素為每一個(gè)單元|ql|的大小。因?yàn)镻TP的對(duì)角線上的元素不為零，所以PTP是可逆的。

文獻(xiàn)[21]中還提出圖的拉普拉斯算子L和商圖的拉普拉斯算子Lπ滿足關(guān)系式

并且得到

將式(5)代入式(4)可得

將式(6)兩邊同乘(PTP)-1PT，可得

定義相關(guān)特征矩陣為PH=P(PTP)-1PT，代入式(7)中，可得

通過有向圖的衍生定義，本節(jié)對(duì)圖拓?fù)溥M(jìn)行進(jìn)一步的說明。給定一個(gè)和圖G相關(guān)聯(lián)的拉普拉斯算子L，存在從節(jié)點(diǎn)wj到達(dá)節(jié)點(diǎn)wi的有向路徑，則對(duì)于節(jié)點(diǎn)wj，它的可達(dá)集R(wj)可定義為包含節(jié)點(diǎn)wj和所有wj通過有向路徑到達(dá)的節(jié)點(diǎn)wi。

設(shè)R1,R2,…,Rt表示圖G的可達(dá)集，定義Ri的排它部分集合H i=Ri∪j≠iRj，其中H i∩Hj=?；定義Ri的公共部分集合Ci=RiHi。

給出一個(gè)多智能體系統(tǒng)模型

其中，[x1(t),x2(t),…,xn(t)]T≡x(t)∈Rn，L表示MAS 連通的有向圖拉普拉斯算子，u表示分布式比例控制器。

式(10)被廣泛應(yīng)用于多智能體問題，如聚類、集群和每個(gè)節(jié)點(diǎn)涉及標(biāo)量變量的分布式估計(jì)[22]。

通過圖的劃分π={q1,q2,…,qm}，定義多一致性條件為

多智能體系統(tǒng)的劃分π的一致性軌跡漸進(jìn)穩(wěn)定流定義為

通過對(duì)MAS 的控制器u的拉普拉斯算子進(jìn)行設(shè)計(jì)可得

其中，Lπ=L+Lu。對(duì)Lπ的節(jié)點(diǎn)坐標(biāo)按=Tx進(jìn)行一定的置換，將排它集和公共集分開，并用下三角的樣式表示為

其中，Li是與Hi相關(guān)聯(lián)的hi×hi（hi:=|Hi|）拉普拉斯矩陣；矩陣；M是與所有公共部分的并集相關(guān)聯(lián)的δ階方陣，其對(duì)角線上的元素表示公共部分與排它部分的連接數(shù)量。

以上方法通過對(duì)MMAS 的控制器u進(jìn)行設(shè)計(jì)，使其對(duì)原系統(tǒng)的結(jié)構(gòu)圖進(jìn)行改變，并得出預(yù)期的拓?fù)浣Y(jié)構(gòu)圖Lπ；再對(duì)Lπ進(jìn)行轉(zhuǎn)置，得出轉(zhuǎn)置后的矩陣，能更加清晰地反映出分組后的信息以及拓?fù)浣Y(jié)構(gòu)的改變對(duì)MMAS 多一致性的影響。

4 實(shí)例分析

在多邊共管的網(wǎng)絡(luò)環(huán)境下，本文針對(duì)第2 節(jié)的步驟4，設(shè)計(jì)了一種海面協(xié)同搜救任務(wù)，如圖3 所示，其中，●、▲、■分別代表USV、UAV、AUV。因?yàn)? 個(gè)MAS 擁有不同的系統(tǒng)結(jié)構(gòu)和一致性算法，在由3 個(gè)USV、3 個(gè)UAV 和2 個(gè)AUV 構(gòu)成MMAS時(shí)，要對(duì)其通信網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行拓?fù)?，將結(jié)構(gòu)算法相同的MAS 分到一個(gè)單元中，以實(shí)現(xiàn)多一致性控制。將MMAS 通過代數(shù)圖論表示成一個(gè)交互的結(jié)構(gòu)圖，通過EEP 對(duì)系統(tǒng)進(jìn)行拓?fù)湓O(shè)計(jì)，使每個(gè)MAS 達(dá)到預(yù)期的一致性。

圖3 MMAS 結(jié)構(gòu)

MMAS 結(jié)構(gòu)圖的拉普拉斯算子為

設(shè)置系統(tǒng)的初始狀態(tài)x0=[1;3;6;0.5;2;9;5;7.5]，并設(shè)置時(shí)間t∈[1,10]，代入式(3)中動(dòng)力學(xué)方程(t)=-Lx(t)，得到系統(tǒng)未進(jìn)行劃分的時(shí)間演化圖，如圖4 所示。

圖4 系統(tǒng)未進(jìn)行劃分的時(shí)間演化圖

從圖4 可以看到，8 個(gè)MAS 無法在規(guī)定的時(shí)間內(nèi)達(dá)成預(yù)期的多一致性，為了實(shí)現(xiàn)第5、6 個(gè)MAS達(dá)到相同的一致性，且第7、8 個(gè)MAS 達(dá)到相同的一致性，本文對(duì)MMAS 進(jìn)行拓?fù)湓O(shè)計(jì)。

對(duì)MMAS 的結(jié)構(gòu)進(jìn)行如下劃分，添加鏈(7,8)、(8,7)，刪除鏈(8,4)、(4,6)，得到以下4 個(gè)單元，即q1={1,2,3}、q2={5,6}、q3={7,8}、q4={4}，并得到分組π={q1,q2,q3,q4}，以及拓?fù)湓O(shè)計(jì)后的結(jié)構(gòu)（如圖5 所示）和對(duì)應(yīng)的拉普拉斯算子。

圖5 拓?fù)湓O(shè)計(jì)后的結(jié)構(gòu)

通過式(9)設(shè)計(jì)控制器u，并通過特征矩陣P得到相關(guān)特征矩陣PH，將控制器u代入式(13)中，得出的結(jié)果滿足式(8)，則劃分π={q1,q2,q3,q4}是原圖的EEP，給出轉(zhuǎn)換矩陣T=[e1,e2,e3,e5,e6,e7,e8,e4]，得到分塊的拉普拉斯算子為

其中，排它集合為H={H1,H2,H3}={{1,2,3},{5,6},{7,8}}，公共集合為C≡{4}。

將初始狀態(tài)x0=[1;3;6;0.5;2;9;5;7.5]、時(shí)間t∈[1,10]，以及L+Lu代入式(3)中動(dòng)力學(xué)方程(t)=-Lx(t)，得到經(jīng)過劃分后的時(shí)間演化圖，如圖6 所示。

圖6 系統(tǒng)經(jīng)過劃分后的時(shí)間演化圖

由圖6 得知，在對(duì)系統(tǒng)的結(jié)構(gòu)進(jìn)行劃分后，實(shí)現(xiàn)了第1、2、3 個(gè)MAS 達(dá)到相同的一致性，第5、6 個(gè)MAS 達(dá)到相同的一致性，第7、8 個(gè)MAS 達(dá)到相同的一致性。

以上分析表明，MMAS 內(nèi)通過添加或刪減鏈路達(dá)到了預(yù)期的多一致性，不同的MAS 也分別形成預(yù)期的分組。

5 結(jié)束語

在多模態(tài)網(wǎng)絡(luò)環(huán)境下，智能化和數(shù)字化發(fā)展使工業(yè)生產(chǎn)的效率日漸提升?？紤]新型網(wǎng)絡(luò)中大規(guī)模復(fù)雜任務(wù)，本文構(gòu)建了具有多邊共管、即插即用、平等開放、結(jié)構(gòu)可擴(kuò)展等特點(diǎn)的多邊化分布式協(xié)同控制框架，提出了適用于多個(gè)具有不同功能的多智能體系統(tǒng)組網(wǎng)后的通信拓?fù)渲貥?gòu)方法?；谒O(shè)計(jì)的分布式控制協(xié)議實(shí)現(xiàn)多一致性，利用仿真算例驗(yàn)證了所提方法的有效性，為我國(guó)實(shí)現(xiàn)“通信技術(shù)強(qiáng)國(guó)”提供了技術(shù)支持和理論依據(jù)。