無向拓撲下多智能體系統(tǒng)目標能控的圖論條件

摘要：基于多智能體系統(tǒng)良好的應用前景，研究了無向加權拓撲下一類特殊一般線性多智能體系統(tǒng)目標能控的圖論條件。利用圖論和矩陣論知識，得到了系統(tǒng)目標能控的充分條件。然后，通過實例分析得到了系統(tǒng)目標能控的充要條件。結果顯示在領導者-跟隨者連通拓撲下，多智能體系統(tǒng)是目標能控的當且僅當含有跟隨者目標節(jié)點的連通分量是目標能控的，并且同樣的結論適用于非領導者-跟隨者連通拓撲。

關鍵詞：多智能體系統(tǒng)；目標能控性；無向拓撲；領導者-跟隨者連通拓撲

中圖分類號： TP273⁺.5；O231.1文獻標識碼： A

收稿日期：2022-12-06；修回日期：2023-01-28

基金項目：國家自然科學基金（62373205，62033007）；山東省泰山學者特聘教授人才支持計劃（tstp20230624，ts20190930）；山東省泰山學者攀登計劃和青島大學系統(tǒng)科學+聯(lián)合攻關項目（XT2024101）

第一作者：紀亞楠（1998-），女，山東青島人，碩士研究生，主要研究方向為群體智能的分析與控制。

通信作者：紀志堅（1973-），男，山東青島人，博士，教授，主要研究方向為多智能體網絡系統(tǒng)，復雜網絡的分析與控制等。

Graph-theoretic Conditions for Target Controllability of Multi-agent System in Undirected Topology

JI Ya′nan，JI Zhijian

（Qingdao University a. School of Automation; b. Shandong Key Laboratory of Industrial

Control Technology， Qingdao 266071， China）

Abstract：Based on the good application prospects of multi-agent systems， we study the graph-theoretic conditions of target controllability for a class of special general linear multi-agent systems under undirected weighted topology. By using the knowledge of graph and matrix theory， a sufficient condition for the target controllability of the system is obtained. Then， through the analyses on actual examples， we obtain a necessary and sufficient condition of target controllability for the system. The results show that under the leader-follower connected topology， the multi-agent system is target controllable if and only if the connected component containing the follower target nodes is target controllable， and the same conclusion applies to the non leader-follower connected topology.

Keywords： multi-agent system; target controllability; undirected topology; leader-follower connected topology

0 引言

近年來，大量學者對分布式人工智能產生了濃厚的興趣，多智能體系統(tǒng)作為分布式人工智能的一個分類^[1]，逐漸成為一個研究熱點，并在很多領域問題的研究和解決上起了重要作用^[2-4]。隨著時間的推移，人們對多智能體系統(tǒng)進行了越來越深入的研究^[1-20]，提出了許多十分有價值的結論?，F(xiàn)實生活中，我們總是期望能通過控制少部分個體使群體中的每一個個體達到我們所期望的狀態(tài)，而多智能體系統(tǒng)的能控性研究能幫助我們完成這一設想。

2004年，Tanner^[14]研究了多智能體系統(tǒng)的能控性問題，結合圖論和矩陣論等知識，提出了領導者-跟隨者框架下系統(tǒng)能控的一些代數(shù)和圖論條件，這個框架的提出在多智能體系統(tǒng)能控性的研究中起了重要作用。Ji等^[13]在2009年研究了領導者-跟隨者框架下多智能體協(xié)調的互連拓撲，并提出了領導者-跟隨者連通拓撲的概念，本文利用這一概念研究了多智能體系統(tǒng)的目標能控性。多智能體系統(tǒng)能控性的研究目的在于使全部智能體達到我們所期望的狀態(tài)，而目標能控性研究僅需要使部分智能體達到我們所期望的狀態(tài)。

多智能體系統(tǒng)的目標能控性是指在有限時間內，存在控制輸入，從系統(tǒng)任意初始狀態(tài)，能得到任意目標終端狀態(tài)^[15]。2010年，Mesbahi等^[21]研究了多智能體網絡，主要分析了網絡化動態(tài)系統(tǒng)，提出了綜合的圖論方法。研究多智能體系統(tǒng)的目標能控性可采用圖論或代數(shù)方法等，其中圖論方法較代數(shù)方法更為直觀。近期，許多學者對系統(tǒng)的目標能控性研究進行了深入的探討^[15-17]。2020年，Guan等^[15]研究了固定和切換拓撲下多智能體系統(tǒng)的目標能控性。2021年，Lu等^[16]針對切換有符號網絡的強目標能控性進行了討論，2022年，Lu等^[17]考慮了有限域上時變拓撲多智能體系統(tǒng)的強目標能控性。Guan等^[15]和Lu等^[17]的研究均考慮的一階多智能體系統(tǒng)，而在現(xiàn)實生活中，一個智能體可能含有多種狀態(tài)，因此，研究一般線性多智能體系統(tǒng)是必要且有價值的。

本文的主要貢獻是給出了一類特殊一般線性多智能體系統(tǒng)目標能控的直觀圖論條件。首先，考慮了領導者-跟隨者連通拓撲，最終得到：若每一個連通分量是目標能控的，則多智能體系統(tǒng)是目標能控的。通過進一步分析，我們得到在領導者-跟隨者連通拓撲下，含有跟隨者目標節(jié)點的連通分量是目標能控的等價于多智能體系統(tǒng)是目標能控的。最終，我們發(fā)現(xiàn)這一充要條件同樣適用于非領導者-跟隨者連通拓撲。本文給出的多智能體系統(tǒng)目標能控的相關圖論條件，是通過將拓撲圖分為一個個子圖（連通分量），考慮每一個子圖的特點和目標能控性，來得到該拓撲圖的目標能控性，這對考慮復雜拓撲圖的目標能控性具有一定的意義。

1 預備知識

4 結論

針對無向加權拓撲下的一類特殊一般線性多智能體系統(tǒng)，本文通過圖論和矩陣論的相關知識，研究了系統(tǒng)的目標能控性，并得到了一些結論。首先，如果圖的互連拓撲以及領導者、跟隨者、目標節(jié)點位置是固定的，則改變圖中節(jié)點的標號不改變多智能體系統(tǒng)的目標能控性。我們還得到在領導者-跟隨者連通拓撲下的每一個連通分量是目標能控的，那么多智能體系統(tǒng)是目標能控的。通過舉例分析，得到同樣在領導者-跟隨者連通拓撲下，多智能體系統(tǒng)是目標能控的當且僅當含有跟隨者目標節(jié)點的連通分量是目標能控的。最后，我們發(fā)現(xiàn)這個充要條件適用于一般拓撲結構。今后，我們將進一步探索一般線性多智能體系統(tǒng)的目標能控性，而不僅僅局限于這一特殊的一般線性多智能體系統(tǒng)，同時，探索多智能體系統(tǒng)目標能控的相關代數(shù)條件也是十分有價值的。

參考文獻：

[1]武海鷹， 王緒安. 分布式人工智能與多智能體系統(tǒng)研究[J]. 微機發(fā)展， 2004， 14（3）：80-82.

WU H Y， WANG X A. Research on multi-agent system and distributed AI[J]. Microcomputer Development， 2004， 14（3）：80-82.

[2]DAI X K， TANG W J， WANG Y F， et al. A study of an intelligent battlefield damage assessment system based on a multi-agent system[J]. International Journal of Plant Engineering and Management， 2008， 13（1）：41-46.

[3]COSTANTINI S， DE GASPERIS G， MIGLIARINI P. Multi-agent system engineering for emphatic human-robot interaction[C]//2019 IEEE Second International Conference on Artificial Intelligence and Knowledge Engineering （AIKE）. Sardinia， Italy： IEEE， 2019：36-42.

[4]李瑞敏， 史其信. 基于多智能體系統(tǒng)的城市交通控制與誘導集成化研究[J]. 公路交通科技， 2004， 21（5）：109-112.

LI R M， SHI Q X. Research on integration of urban traffic control and route guidance based on mult-agent[J]. Journal of Highway and Transportation Research and Development， 2004， 21（5）：109-112.

[5]LIN K， JI Z. Dynamic event-triggered consensus of general linear multi-agent systems with adaptive strategy[J]. IEEE Transactions on Circuits and Systems II： Express Briefs， 2022， 69（8）：3440-3444.

[6]TIAN C， LIU K， JI Z. Adaptive event-triggered consensus of multi-agent systems with general linear dynamics[J]. International Journal of Systems Science， 2022， 53（8）：1744-1755.

[7]張志偉， 紀志堅. 有向路徑下的一類多智能體系統(tǒng)的能控性分析[J]. 復雜系統(tǒng)與復雜性科學， 2022， 19（2）：63-70.

ZHANG Z W， JI Z J. Controllability of multi-agent system based on directed paths[J]. Complex Systems and Complexity Scienc， 2022， 19（2）：63-70.

[8]SUN Y， JI Z， LIU Y， et al. On stabilizability of multi-agent systems[J]. Automatica， 2022， 144：1-13.

[9]GUAN Y， JI Z， ZHANG L， et al. Controllability of multi-agent systems under directed topology[J]. International Journal of Robust and Nonlinear Control， 2017， 27（18）：4333-4347.

[10] JI Z， LIN H， YU H. Leaders in multi-agent controllability under consensus algorithm and tree topology[J]. Systems amp; Control Letters， 2012， 61（9）：918-925.

[11] CHAO Y， JI Z. Necessary and sufficient conditions for multi-agent controllability of path and star topologies by exploring the information of second-order neighbors[J]. IMA Journal of Mathematical Control and Information， 2021， 38（1）：1-14.

[12] GUO J， JI Z， LIU Y. Sufficient conditions and limitations of equivalent partition in multiagent controllability[J]. Science China Information Sciences， 2022， 65（3）：1-15.

[13] JI Z， WANG Z， LIN H， et al. Interconnection topologies for multi-agent coordination under leader-follower framework[J]. Automatica， 2009， 45（12）：2857-2863.

[14] TANNER H G. On the controllability of nearest neighbor interconnections[C]//The 43rd IEEE Conference on Decision and Control （CDC）. Nassau， Bahamas： IEEE， 2004：2467-2472.

[15] GUAN Y， WANG L. Target controllability of multiagent systems under fixed and switching topologies[J]. International Journal of Robust and Nonlinear Control， 2019， 29（9）：2725-2741.

[16] LU Z， GUAN Y. Strong targeted controllability of switching signed networks[J]. IEEE Transactions on Circuits and Systems II： Express Briefs， 2021， 69（3）：1109-1113.

[17] LU Z， ZHANG Z， JI Z. Strong targeted controllability of multi-agent systems with time-varying topologies over finite fields[J]. Automatica， 2022， 142：1-5.

[18] 王瀟， 紀志堅.基于MAS的無人機新型編隊算法[J].復雜系統(tǒng)與復雜性科學， 2019， 16（2）： 60-68.

WANG X， JI Z J.A new UAV formation algorithm based on MAS[J].Complex Systems and Complexity Science， 2019， 16（2）： 60-68.

[19] 國俊豪， 紀志堅. 基于 NE 結果的多智能體系統(tǒng)模型及其能控性[J]. 復雜系統(tǒng)與復雜性科學， 2021， 18（4）： 50-57.

GUO J H， JI Z J. A multi-agent system model based on NE results and its controllability[J]. Complex Systems and Complexity Science， 2021， 18（4）： 50-57.

[20] LI Z， REN W， LIU X， et al. Distributed containment control of multi-agent systems with general linear dynamics in the presence of multiple leaders[J]. International Journal of Robust and Nonlinear Control， 2013， 23（5）： 534-547.

[21] MESBAHI M， EGERSTEDT M. Graph Theoretic Methods in Multiagent Networks[M]. Princeton and Oxford： Princeton University Press， 2010.

（責任編輯 李 進）