摘 要：如何增強系統(tǒng)一致性是多智能體系統(tǒng)研究中的一個重要問題。傳統(tǒng)一致性協(xié)議通常未考慮拓撲中的關鍵節(jié)點，并且拓撲權重單一，從而導致系統(tǒng)更容易分裂?；谌穗H關系網(wǎng)絡中的關鍵人物可以促進不同社區(qū)信息交流的思想，提出了一種影響力網(wǎng)絡模型（influence network model，INM）。首先，提出了分布式的hub node識別算法（distributed hub node identify algorithm，DHNI），用于區(qū)分關鍵節(jié)點和非關鍵節(jié)點，可以應用在分布式多智能體系統(tǒng)中；其次，提出了基于分布式hub node的拓撲權重設計算法（distributed hub node-based topology reweighting algorithm，DHNTR），量化不同節(jié)點對其鄰居的影響力；最后提出了基于影響力網(wǎng)絡的一致性協(xié)議。設計了公共Lyapunov函數(shù)，分析了系統(tǒng)的全局穩(wěn)定性，證明了系統(tǒng)具有Lyapunov意義下的穩(wěn)定性。仿真實驗表明該協(xié)議可以增強系統(tǒng)一致性。

關鍵詞：多智能體系統(tǒng)； 一致性； 影響力網(wǎng)絡； 關鍵節(jié)點

中圖分類號：TN915.04文獻標志碼：A

文章編號：1001-3695（2023）08-033-2452-05

doi：10.19734/j.issn.1001-3695.2022.10.0633

Influence network model-based multi-agent consensus protocol

Xie Guangqiang， Zhang Haojin， Li Yang

（School of Computers， Guangdong University of Technology， Guangzhou 510006， China）

Abstract：How to enhance system consensus is an important problem in the research of multi agent systems. The conventional consensus protocols usually do not consider the hub nodes in the topology， and the topology weight is single， which make the system easier to split. Based on the idea that key figures in the interpersonal network could promote information exchange in different communities， this paper proposed an INM. Firstly， this paper proposed a DHNI algorithm to distinguish between hub nodes and non-hub nodes，which could be applied to distributed multi-agent system. Secondly， this paper proposed a DHNTR algorithm to quantify the influence of different nodes on their neighbors. Finally， this paper proposed an influence network-based multi-agent consensus protocol. This paper designed a common Lyapunov function and analyzed the global stability of the system， and proved the stability of the system in the sense of Lyapunov. Simulation results show that the protocol can enhance system consensus.

Key words：multi agent systems; consensus; influence network; hub node

0 引言

多智能體系統(tǒng)近些年受到了國內(nèi)外眾多學者的廣泛關注，相關研究成果層出不窮。多智能體系統(tǒng)作為分布式人工智能的一個重要領域，廣泛地應用在無人機、機器人等領域內(nèi)［1～4］。一致性問題可以為各類領域問題提供可靠的解決方案，可以使多智能體系統(tǒng)協(xié)調(diào)一致地實現(xiàn)既定目標。例如去中心化的傳感器網(wǎng)絡通過局部信息完成特定的任務，智能機器人通過感知其鄰域內(nèi)的智能機器人在復雜的環(huán)境下進行搜索、救援、地理勘測等任務。衛(wèi)星簇通過局部的協(xié)作通信推進地面通信和衛(wèi)星通信的融合，并最終為各類設施提供一致性服務。相關理論研究同樣備受關注，Olfati-Saber等人［5，6］基于矩陣理論、代數(shù)圖論和控制理論，分析了一階一致性問題，提出了一種多智能體系統(tǒng)一致性算法理論框架，并證明了拉普拉斯矩陣、非負隨機矩陣和有向圖的代數(shù)連通性在一致性算法的分析中至關重要。

網(wǎng)絡拓撲結構優(yōu)化對多智能體系統(tǒng)收斂性有重要的影響，引起了相關研究者的廣泛關注。Xie等人［7］通過劃分網(wǎng)絡拓撲，同時使用連通保持算法，使得系統(tǒng)在保持連通的情況下快速收斂一致。Zhang等人［8］通過研究有向生成樹的拓撲結構并結合Lyapunov函數(shù)給出了一致性問題的充要條件。Develer等人［9］研究了基于首層和次層子圖的一致性問題，并分析了多智能體系統(tǒng)的簇數(shù)和穩(wěn)定性。Cihan［10］在多智能體網(wǎng)絡中添加新智能體來修改網(wǎng)絡拓撲結構以此達到所期望的組一致性。Hu等人［11］在建立新的動態(tài)模型基礎上，設計了構造通信拓撲的詳細策略以研究一種新的一致性問題。Liu等人［12］研究了有向拓撲下的多智能體系統(tǒng)有無通信時延的廣義一致性問題。謝光強等人［13］通過分布式選取虛擬鄰居，同時在使用約束集的情況下設計了新的一致性協(xié)議。Yao等人［14］證明了基于二階鄰居信息的間歇控制協(xié)議在一定條件下比一般的間歇控制協(xié)議更快達到一致性。Wang等人［15］設計了一致性控制器以實現(xiàn)有向拓撲下非自治領導者的一致性。以上研究雖然都有助于多智能體系統(tǒng)的收斂，但都是從整個網(wǎng)絡上進行優(yōu)化，而忽視了拓撲中關鍵節(jié)點對系統(tǒng)一致性的影響。

拓撲結構優(yōu)化在社交網(wǎng)絡中同樣越來越得到重視，同時將社交網(wǎng)絡的思想應用到多智能體系統(tǒng)一致性中的相關研究也在不斷深入。社交網(wǎng)絡對于信息傳播發(fā)揮著重要的作用［16，17］。Zhang等人［18］通過拓撲優(yōu)化規(guī)則對原始拓撲進行優(yōu)化，運用社區(qū)分解的思想找出分解拓撲的樞紐節(jié)點，通過一定的規(guī)則加快系統(tǒng)的收斂速度?？紤]社會人際關系的不同成員，成員之間的影響由它們之間的邊的權重系數(shù)表示［19］。在一群初始意見不同的行為者中，人際影響網(wǎng)絡參與了行為者既定意見的形成［20］。Vegni等人［21］給出了hub nodes在車輛社交網(wǎng)絡場景下的定義。

智能體間的公共鄰居數(shù)量和智能體間的相似性是多智能體系統(tǒng)增強一致性研究的重點領域，受到眾多學者的關注。智能體和鄰居之間的連接在切換拓撲網(wǎng)絡中一旦斷開，就很難恢復［22］。Yang等人［23］發(fā)現(xiàn)在一致性演化過程中加入公共鄰居的概念后，提出的新協(xié)議中智能體通過對公共鄰居數(shù)量較少的鄰居給予更大的權重以減少和鄰居發(fā)生斷開的情況，增強了系統(tǒng)一致性［24，25］?；凇跋嗨菩宰躺?lián)系”的概念，Motsch等人［26］提出了“heterophily”的思想，認為和不同的人聯(lián)系更密切，而不是和相似的人聯(lián)系更緊密。

傳統(tǒng)的一致性協(xié)議通常沒有考慮拓撲中的關鍵節(jié)點，忽略了關鍵節(jié)點的重要性。并且網(wǎng)絡拓撲的邊都給予相同的權重，沒有考慮更深層次的信息去構建拓撲權重，從而導致系統(tǒng)在演化過程中更容易出現(xiàn)較多的簇。為此，提出了一種影響力模型（influence network model，INM），包括以下三方面：首先是分布式的hub node識別算法（distributed hub node Ldentify algorithm，DHNI）；其次是基于分布式hub node的拓撲權重設計算法（distributed hub node-based topology reweighting algorithm，DHNTR）；最后是基于影響力網(wǎng)絡的一致性協(xié)議。實驗結果表明，新協(xié)議增強了多智能體系統(tǒng)一致性。

本文主要工作與貢獻如下：

a）設計了DHNI。DHNI僅考慮當前節(jié)點鄰居集合，根據(jù)鄰居是否存在多個連通分量去識別該節(jié)點是否是關鍵節(jié)點，并以此將多智能體系統(tǒng)中的節(jié)點劃分為hub nodes和non-hub nodes。

b）設計了DHNTR。DHNTR在DHNI的基礎上，同時考慮節(jié)點間公共鄰居的數(shù)量以及節(jié)點與其鄰居的相似性，以構建網(wǎng)絡拓撲權重，從而量化不同節(jié)點對其鄰居的影響力。

c）提出了基于影響力網(wǎng)絡的一致性協(xié)議，減少了系統(tǒng)收斂的簇數(shù)，增強了系統(tǒng)一致性。設計了公共Lyapunov函數(shù)，分析了系統(tǒng)的全局穩(wěn)定性，系統(tǒng)最終可以到達穩(wěn)定的平衡狀態(tài)，同時通過仿真實驗驗證了該協(xié)議的有效性。

1 預備知識和問題描述

1.1 圖論與矩陣論

1.2 經(jīng)典離散時間一致性協(xié)議

2 影響力網(wǎng)絡模型

INM可以促進節(jié)點相互之間的通信，增強系統(tǒng)的連通性，進而增強多智能體系統(tǒng)一致性，INM包括DHNI、DHNTR以及基于影響力網(wǎng)絡的一致性協(xié)議三部分。

首先，在傳統(tǒng)的多智能體系統(tǒng)一致性演化過程中，沒有考慮系統(tǒng)中的關鍵節(jié)點。基于社交網(wǎng)絡中的關鍵節(jié)點可以在不同社區(qū)之間起到橋梁的作用，進而促進不同社區(qū)信息交流的思想。因此區(qū)分關鍵節(jié)點和非關鍵節(jié)點是非常重要的，故設計了DHNI。 DHNI考慮當前節(jié)點鄰居集合，根據(jù)鄰居集合中的節(jié)點是否存在多個連通分量去識別當前節(jié)點是否是hub node。

其次，傳統(tǒng)協(xié)議中網(wǎng)絡拓撲的邊都給予相同的權重，沒有考慮更深層次的信息，導致系統(tǒng)在收斂過程中容易出現(xiàn)較多的簇。Yang等人［23］指出公共鄰居數(shù)量是衡量兩個節(jié)點之間連通強度的重要指標，相似性是衡量節(jié)點之間狀態(tài)差異的另一個重要指標。因此，基于所識別出的hub node，并且考慮公共鄰居的數(shù)量以及節(jié)點間的相似性，設計了DHNTR，DHNTR量化了不同節(jié)點對其鄰居的影響力，并將影響力用拓撲權重表示。

最后，在傳統(tǒng)一致性協(xié)議的基礎上，提出了基于影響力網(wǎng)絡的一致性協(xié)議，實驗結果表明，該協(xié)議可以減少多智能體系統(tǒng)演化過程中的收斂簇數(shù)，增強系統(tǒng)一致性。理論分析驗證了該協(xié)議的有效性。

2.1 分布式的hub node識別算法

在社交網(wǎng)絡中，如果一個人在不同的社區(qū)都有朋友，他可以很大程度上比其他人更快地在其社交圈子中接收和傳播信息，在不同的社區(qū)中起到橋梁的作用，這個人可以看做是社交網(wǎng)絡中的關鍵節(jié)點。因此，提出了一個用來區(qū)分多智能體系統(tǒng)中的關鍵節(jié)點和非關鍵節(jié)點的hub nodes識別算法，將同一個連通分量內(nèi)的節(jié)點視為一個社區(qū)，僅考慮當前節(jié)點鄰居集合，若鄰居存在多個連通分量，則當前節(jié)點是hub node。hub node可以促進節(jié)點之間的通信，使當前局部網(wǎng)絡拓撲聯(lián)系更緊密。

hub nodes以及non-hub nodes識別示例如圖1所示。圖1中可以看出，考慮當前節(jié)點的鄰居集合中的節(jié)點存在多個連通分量，則編號5～8的節(jié)點均為hub node。例如8號節(jié)點是hub node，因為存在兩個連通分量，第一個連通分量包含節(jié)點11，第二個連通分量包含節(jié)點7、10。

2.2 基于分布式hub node的拓撲權重設計算法

2.3 基于影響力網(wǎng)絡的一致性協(xié)議

3 系統(tǒng)穩(wěn)定性分析

4 仿真

對提出的基于影響力網(wǎng)絡的多智能體一致性協(xié)議進行仿真，利用系統(tǒng)穩(wěn)定時最終收斂的簇數(shù)作為評價一致性協(xié)議的性能指標，最終簇數(shù)越少說明效果越好。仿真探索八種不同的網(wǎng)絡拓撲對新協(xié)議的最終收斂結果影響。為了驗證新協(xié)議的有效性，實驗數(shù)據(jù)集選用八種不同網(wǎng)絡拓撲。圖3展示的是分別使用200個智能體在5×5的二維平面上構建的八種網(wǎng)絡拓撲［7］。圖3（a）對應拓撲的節(jié)點是隨機分布的，其余拓撲都按照一定的形狀規(guī)則分布。由于圖3（a）對應拓撲的節(jié)點是隨機分布的，具有一般性，所以用圖3（a）舉例說明?？梢钥闯鰣D3（a）拓撲節(jié)點分布較為稀疏，絕大部分互為鄰居的節(jié)點沒有公共鄰居，導致節(jié)點之間的通信是微弱的，系統(tǒng)在收斂過程容易分裂。

圖4展示了圖3（a）在兩個不同時刻使用DHNI所識別出的hub nodes，其中紅色節(jié)點表示hub nodes，可以看出節(jié)點間關聯(lián)性越低，hub nodes節(jié)點在拓撲中出現(xiàn)的越活躍，hub nodes在多智能體系統(tǒng)通信中起到橋梁的作用，促進節(jié)點之間的通信，同時考慮節(jié)點間公共鄰居的數(shù)量以及節(jié)點與其鄰居的相似性，以構建網(wǎng)絡拓撲權重，從而量化節(jié)點對其鄰居的不同影響力，解決系統(tǒng)在演化過程中容易出現(xiàn)分裂的情況。

圖6記錄的是圖3中各個拓撲分別使用傳統(tǒng)協(xié)議與使用新協(xié)議后的收斂簇數(shù)對比情況，其中圖6橫坐標所表示的序號對應圖3中的拓撲序號?？梢钥闯觯褂眯聟f(xié)議后絕大部分拓撲收斂簇數(shù)約為原來的1/3，一小部分拓撲收斂簇數(shù)約為原來的1/4，其中放射線型拓撲使用傳統(tǒng)協(xié)議后的收斂簇數(shù)是21，而使用新協(xié)議后的收斂簇數(shù)為1。圖7記錄的是圖3（a）所對應拓撲分別使用傳統(tǒng)協(xié)議和新協(xié)議后的演化過程，其中圖7（a）表示使用傳統(tǒng)協(xié)議后的演化過程，圖7（b）表示使用新協(xié)議后的演化過程?？梢钥闯鍪褂眯聟f(xié)議后通過識別出的hub nodes，同時施加不同影響力后加強了連接較微弱的節(jié)點間的通信，使得系統(tǒng)連接更加緊密，增強了系統(tǒng)的連通性，最終系統(tǒng)收斂的簇數(shù)更少，更加穩(wěn)定。

5 結束語

本文研究在離散時間網(wǎng)絡拓撲下多智能體系統(tǒng)增強一致性問題，提出了一種影響力網(wǎng)絡模型。首先，基于社交網(wǎng)絡中關鍵人物可以促進不同社區(qū)交流的思想在多智能系統(tǒng)中劃分hub nodes和non-hub nodes；其次，基于hub nodes對拓撲權重進行設計以量化節(jié)點對其鄰居的影響力；最后提出基于影響力網(wǎng)絡的多智能體一致性協(xié)議。通過理論證明分析和仿真實驗結合，驗證了新協(xié)議的有效性。相對傳統(tǒng)協(xié)議而言，使用新協(xié)議后最終多智能體系統(tǒng)收斂簇數(shù)更少，增強了系統(tǒng)一致性。未來的研究工作包括如何進一步節(jié)省控制設計能量，降低系統(tǒng)通信量，同時研究在時延環(huán)境下的增強一致性控制問題。

參考文獻：

［1］Amirkhani A， Amir H B. Consensus in multi-agent systems： a review［J］. Artificial Intelligence Review， 2022，55（5）：3897-3935.

［2］Plappert S， Paul C G， Roland L. Multi-agent systems in mechanical engineering： a review［M］//Jezic G， Chen-Burger J，Kusek M，et al. Agents and Multi-Agent Systems： Technologies and Applications. Singapore：Springer， 2021：193-203.

［3］Lizzio F F， Elisa C， Giorgio G. A review of consensus-based multi-agent UAV implementations［J］. Journal of Intelligent amp; Robotic Systems， 2022，106（2）： 1-10.

［4］Calegari R， Ciatto G， Mascardi V， et al. Logic-based technologies for multi-agent systems： a systematic literature review［J］. Autonomous Agents and Multi-Agent Systems， 2021，35（1）： 1-67.

［5］Olfati-Saber R， Murray R M. Consensus problems in networks of agents with switching topology and time-delays［J］. IEEE Trans on Automatic Control， 2004，49（9）： 1520-1533.

［6］Olfati-Saber R， Fax J A， Murray R M. Consensus and cooperation in networked multi-agent systems［J］. Proceedings of the IEEE， 2007，95（1）： 215-233.

［7］Xie Guangqiang， Xu Haoran， Li Yang， et al. Fast distributed consensus seeking in large-scale and high-density multi-agent systems with connectivity maintenance［J］. Information Sciences，2022， 608： 1010-1028.

［8］Zhang Haixiang， Chen Chong， Huang Jun， et al. Consensus based on output for nonlinear multi-agent systems with switching topologies［J］. Trans of the Institute of Measurement and Control， 2022，44（15）：2953-2966.

［9］Develer ，Akar M. Higher-order cluster consensus of a multi-agent network with continuous-time dynamics［J］. Trans of the Institute of Measurement and Control， 2021，43（8）： 1734-1744.

［10］Cihan O. Topology design for group consensus in directed multi-agent systems［J］. Kybernetika， 2020，56（3）： 578-597.

［11］Hu Xiang， Zhang Zufan， Li Chuadong. Consensus of a new multi-agent system with impulsive control which can heuristically construct the communication network topology［J］. Applied Intelligence，2022，52（4）： 4041-4056.

［12］Liu Huwei， Chen Xin， Guo Liuxiao， et al. Generalized consensus of discrete-time multi-agent systems with directed topology and communication delay［J］. Journal of Systems Science and Complexity，2020，33（6）： 1903-1913.

［13］謝光強， 黃馳， 李楊， 等. 組合控制協(xié)議增強多智能體系統(tǒng)一致性［J］. 計算機應用研究， 2020，37（8）： 2315-2319，2332. （Xie Guangqiang， Huang Chi， Li Yang， et al. Hybrid control for enhancing consensus of multiagent systems［J］. Application Research of Computers， 2020， 37（8）： 2315-2319，2332.）

［14］Yao Lingling，Xie Dongmei. Consensus of general linear multi-agent systems based on second-order neighbours information： directed topology case［J］. International Journal of Control， 2022，95（8）：2083-2097.

［15］Wang Peijun， Wen Guanghui， Huang Tingwen， et al. Consensus of Lur’e multi-agent systems with directed switching topology［J］. IEEE Trans on Circuits and Systems Ⅱ： Express Briefs， 2022，69（2）：474-478.

［16］Jackson M O. Social and economic networks［M］. Princeton： Princeton University Press， 2010.

［17］McPherson M， Smith-Lovin L， Cook J M. Birds of a feather： homophily in social networks［J］. Annual Review of Sociology， 2001，27（1）： 415-444.

［18］Zhang Miaomiao， Yun Hongquan， Ju Wen. The topology optimization rule for multi-agent system fast consensus［C］//Proc of IEEE CSAA Guidance， Navigation and Control Conference. Piscataway，NJ：IEEE Press， 2018： 1-4.

［19］Jia Peng， MirTabatabaei A， Friedkin N E， et al. Opinion dynamics and the evolution of social power in influence networks［J］. SIAM Review， 2015，57（3）： 367-397.

［20］Friedkin N E， Johnsen E C. Social positions in influence networks［J］. Social networks， 1997，19（3）： 209-222.

［21］Vegni A M， Souza C， Loscri V， et al. Data transmissions using hub nodes in vehicular social networks［J］. IEEE Trans on Mobile Computing， 2019，19（7）： 1570-1585.

［22］Blondel V D， Hendrickx J M， Tsitsiklis J N. On Krause’s multi-agent consensus model with state-dependent connectivity［J］. IEEE Trans on Automatic Control， 2009，54（11）： 2586-2597.

［23］Yang Yuecheng， Dimarogonas D V， Hu Xiaoming. Opinion consensus of modified Hegselmann-Krause models［J］. Automatica， 2014，50（2）： 622-627.

［24］Frasca P， Tarbouriech S， Zaccarian L. Hybrid models of opinion dynamics with opinion-dependent connectivity［J］. Automatica， 2019，100： 153-161.

［25］Jabin P E， Motsch S. Clustering and asymptotic behavior in opinion formation［J］. Journal of Differential Equations， 2014，257（11）： 4165-4187.

［26］Motsch S， Tadmor E. Heterophilious dynamics enhances consensus［J］. SIAM Review， 2014，56（4）： 577-621.

［27］Horn R A， Johnson C R. Matrix analysis［M］. Cambridge： Cambridge University Press， 1987.