無向拓?fù)湎露嘀悄荏w系統(tǒng)目標(biāo)能控的圖論條件

摘要：基于多智能體系統(tǒng)良好的應(yīng)用前景，研究了無向加權(quán)拓?fù)湎乱活愄厥庖话憔€性多智能體系統(tǒng)目標(biāo)能控的圖論條件。利用圖論和矩陣論知識，得到了系統(tǒng)目標(biāo)能控的充分條件。然后，通過實例分析得到了系統(tǒng)目標(biāo)能控的充要條件。結(jié)果顯示在領(lǐng)導(dǎo)者-跟隨者連通拓?fù)湎拢嘀悄荏w系統(tǒng)是目標(biāo)能控的當(dāng)且僅當(dāng)含有跟隨者目標(biāo)節(jié)點的連通分量是目標(biāo)能控的，并且同樣的結(jié)論適用于非領(lǐng)導(dǎo)者-跟隨者連通拓?fù)洹?/p>

關(guān)鍵詞：多智能體系統(tǒng)；目標(biāo)能控性；無向拓?fù)洌活I(lǐng)導(dǎo)者-跟隨者連通拓?fù)?/p>

中圖分類號： TP273⁺.5；O231.1文獻(xiàn)標(biāo)識碼： A

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

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

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

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

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 引言

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

2004年，Tanner^[14]研究了多智能體系統(tǒng)的能控性問題，結(jié)合圖論和矩陣論等知識，提出了領(lǐng)導(dǎo)者-跟隨者框架下系統(tǒng)能控的一些代數(shù)和圖論條件，這個框架的提出在多智能體系統(tǒng)能控性的研究中起了重要作用。Ji等^[13]在2009年研究了領(lǐng)導(dǎo)者-跟隨者框架下多智能體協(xié)調(diào)的互連拓?fù)洌⑻岢隽祟I(lǐng)導(dǎo)者-跟隨者連通拓?fù)涞母拍睿疚睦眠@一概念研究了多智能體系統(tǒng)的目標(biāo)能控性。多智能體系統(tǒng)能控性的研究目的在于使全部智能體達(dá)到我們所期望的狀態(tài)，而目標(biāo)能控性研究僅需要使部分智能體達(dá)到我們所期望的狀態(tài)。

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

本文的主要貢獻(xiàn)是給出了一類特殊一般線性多智能體系統(tǒng)目標(biāo)能控的直觀圖論條件。首先，考慮了領(lǐng)導(dǎo)者-跟隨者連通拓?fù)洌罱K得到：若每一個連通分量是目標(biāo)能控的，則多智能體系統(tǒng)是目標(biāo)能控的。通過進(jìn)一步分析，我們得到在領(lǐng)導(dǎo)者-跟隨者連通拓?fù)湎拢懈S者目標(biāo)節(jié)點的連通分量是目標(biāo)能控的等價于多智能體系統(tǒng)是目標(biāo)能控的。最終，我們發(fā)現(xiàn)這一充要條件同樣適用于非領(lǐng)導(dǎo)者-跟隨者連通拓?fù)洹１疚慕o出的多智能體系統(tǒng)目標(biāo)能控的相關(guān)圖論條件，是通過將拓?fù)鋱D分為一個個子圖（連通分量），考慮每一個子圖的特點和目標(biāo)能控性，來得到該拓?fù)鋱D的目標(biāo)能控性，這對考慮復(fù)雜拓?fù)鋱D的目標(biāo)能控性具有一定的意義。

1 預(yù)備知識

4 結(jié)論

針對無向加權(quán)拓?fù)湎碌囊活愄厥庖话憔€性多智能體系統(tǒng)，本文通過圖論和矩陣論的相關(guān)知識，研究了系統(tǒng)的目標(biāo)能控性，并得到了一些結(jié)論。首先，如果圖的互連拓?fù)湟约邦I(lǐng)導(dǎo)者、跟隨者、目標(biāo)節(jié)點位置是固定的，則改變圖中節(jié)點的標(biāo)號不改變多智能體系統(tǒng)的目標(biāo)能控性。我們還得到在領(lǐng)導(dǎo)者-跟隨者連通拓?fù)湎碌拿恳粋€連通分量是目標(biāo)能控的，那么多智能體系統(tǒng)是目標(biāo)能控的。通過舉例分析，得到同樣在領(lǐng)導(dǎo)者-跟隨者連通拓?fù)湎拢嘀悄荏w系統(tǒng)是目標(biāo)能控的當(dāng)且僅當(dāng)含有跟隨者目標(biāo)節(jié)點的連通分量是目標(biāo)能控的。最后，我們發(fā)現(xiàn)這個充要條件適用于一般拓?fù)浣Y(jié)構(gòu)。今后，我們將進(jìn)一步探索一般線性多智能體系統(tǒng)的目標(biāo)能控性，而不僅僅局限于這一特殊的一般線性多智能體系統(tǒng)，同時，探索多智能體系統(tǒng)目標(biāo)能控的相關(guān)代數(shù)條件也是十分有價值的。

參考文獻(xiàn)：

[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)的城市交通控制與誘導(dǎo)集成化研究[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]張志偉， 紀(jì)志堅. 有向路徑下的一類多智能體系統(tǒng)的能控性分析[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)， 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] 王瀟， 紀(jì)志堅.基于MAS的無人機新型編隊算法[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)， 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] 國俊豪， 紀(jì)志堅. 基于 NE 結(jié)果的多智能體系統(tǒng)模型及其能控性[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)， 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.

（責(zé)任編輯 李 進(jìn)）