基于影響力網絡模型的多智能體一致性協議

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

關鍵詞：多智能體系統； 一致性； 影響力網絡； 關鍵節點

中圖分類號：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 引言

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

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

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

智能體間的公共鄰居數量和智能體間的相似性是多智能體系統增強一致性研究的重點領域，受到眾多學者的關注。智能體和鄰居之間的連接在切換拓撲網絡中一旦斷開，就很難恢復［22］。Yang等人［23］發現在一致性演化過程中加入公共鄰居的概念后，提出的新協議中智能體通過對公共鄰居數量較少的鄰居給予更大的權重以減少和鄰居發生斷開的情況，增強了系統一致性［24，25］。基于“相似性滋生聯系”的概念，Motsch等人［26］提出了“heterophily”的思想，認為和不同的人聯系更密切，而不是和相似的人聯系更緊密。

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

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

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

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

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

1 預備知識和問題描述

1.1 圖論與矩陣論

1.2 經典離散時間一致性協議

2 影響力網絡模型

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

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

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

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

2.1 分布式的hub node識別算法

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

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

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

2.3 基于影響力網絡的一致性協議

3 系統穩定性分析

4 仿真

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

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

圖6記錄的是圖3中各個拓撲分別使用傳統協議與使用新協議后的收斂簇數對比情況，其中圖6橫坐標所表示的序號對應圖3中的拓撲序號。可以看出，使用新協議后絕大部分拓撲收斂簇數約為原來的1/3，一小部分拓撲收斂簇數約為原來的1/4，其中放射線型拓撲使用傳統協議后的收斂簇數是21，而使用新協議后的收斂簇數為1。圖7記錄的是圖3（a）所對應拓撲分別使用傳統協議和新協議后的演化過程，其中圖7（a）表示使用傳統協議后的演化過程，圖7（b）表示使用新協議后的演化過程。可以看出使用新協議后通過識別出的hub nodes，同時施加不同影響力后加強了連接較微弱的節點間的通信，使得系統連接更加緊密，增強了系統的連通性，最終系統收斂的簇數更少，更加穩定。

5 結束語

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

參考文獻：

［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］謝光強， 黃馳， 李楊， 等. 組合控制協議增強多智能體系統一致性［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.