切換偽路圖下的多智能體能控性

中圖分類號：TB3 文獻標識碼：A

Abstract ：This paper introduces a new type of pseudo-path and incorporate switching signals in the study. We apply graph and matrix theories to explore the controllability of multi-agent systems. Firstly，we obtain the system matrix and its exponential function of the multi-agent system，we then derive the necessary and sufficient conditions to achieve controllability. Secondly，we discuss the impact of diferent ways of selecting a single leader on the controllability matrix. Finally，we determine the minimum switching period for the system to reach any specified position in the controllable state space under a given switching sequence.

Keywords：multi-agent system；switched system； pseudo-path； zero-edge node list； controllability

0 引言

作為系統的內在特性之一，能控性反映出外部輸入信號對系統狀態的完全控制能力，是現代控制理論的一個基本概念。能控性的研究為群體智能、基于博弈的控制系統、分布式優化控制等提供了理論依據。Tanner[1]首次將能控性引入多智能體系統，基于拉普拉斯矩陣的特征值和特征向量，建立多智能體系統實現能控性的充要條件。

多智能體系統的應用領域包括人工智能、博弈決策、通信工程、無人機編隊控制、智能交通等[2-11]。Su等[12]用等價劃分和自同構的方法研究多智能體系統的能控性，通過等價劃分和自同構給出多智能體系統能控性的充分條件。Guan等[13]將領導者-跟隨者聯通性概念引入有向圖，利用距離劃分和幾乎等價劃分對能控子空間進行定量研究，討論有向拓撲多智能體系統能控性。根據胞腔間連接數目不同， ΔQu 等[14將非平凡胞腔分為完全連接非平凡胞腔和不完全連接非平凡胞腔，通過分析拉普拉斯矩陣的特征值和特征向量，研究了等價劃分下多智能體系統的能控性。Zhao等[15]考慮了非延遲和延遲條件，用幾何和代數方法研究有向加權符號網絡下一般線性離散時間多智能體系統的能控性。Guo等[15]研究了基于拉普拉斯矩陣的不同模型對領導者-跟隨者多智能體系統能控性的影響，得到了適用于一般模型的能控性結果，同時提出了層次等價劃分（HEP）的概念，并證明了在一般模型下，層次等價劃分的存在使得系統不能控。Ji等[1通過引入下行分支的概念建立起有關樹圖能控性的一些充要條件。Su等[18]利用雙時間尺度特征研究了一階離散時間多智能體系統的能控性。

在信息交互過程中，通信會因障礙物的出現或距離的變化而中斷，這反映出多智能體系統信息交互拓撲結構的變化。因此，研究切換拓撲多智能體系統能控性具有理論價值和實際意義。作為一類重要的混合系統，切換系統由子系統和子系統間的特定切換序列構成[19]，由于其在學術研究和實際應用中都具有重要意義，研究人員對此開展了廣泛的研究，得到許多成果[20-23]。Ji等[24]給出時滯切換拓撲多智能體系統實現能控性的兩個代數充要條件。Liu等[25根據領導者和追隨者之間的耦合關系，獲得了能控性的一些充分條件。Ji等[26]通過研究切換次數和切換序列的設計問題，獲得構造切換序列的新方法并得到線性切換系統實現能控性的最小切換次數的精準估計值。Tian等[27-28]研究了多智能體系統在周期切換拓撲下的能控性以及由連續時間子系統和離散時間子系統組成的切換多智能體系統的能控性。Si等[29]研究具有輸人時滯的多智能體系統在切換拓撲下的相對能控性。Zhang 等[30]討論了系統狀態和控制器都受到隨機擾動的線性切換系統。同時，Li等[31將切換機制引人時序網絡，將其激活為基于時間變化的網絡切換系統并對其開展深人研究，得出一些重要結果。

本文主要貢獻為：1）定義偽路圖及其零邊節點列表，刻畫一類切換偽路圖多智能體系統矩陣指數函數，得到系統實現能控性的充分必要條件;2）依據零邊節點列表，給出不同的領導者選取方式，討論切換拓撲下領導者的不同選取方式對多智能體系統能控性的影響;3）構造切換偽路圖多智能體，給定切換序列，獲得系統狀態到達能控狀態空間任意指定位置的最小切換周期。

1預備知識

1.1 圖論和符號說明

圖論：圖 G=（V，E） 由節點集 V={v₁，v₂，…，v_n} 和邊集 E={（v_j，v_i）|v_j，v_i∈V} 組成。如果 （?v_j°_i）∈ E ，則稱 v_j 是 v_i 的鄰居。 v_i 的鄰居集表示為 N_i={v_j∈V∣（v_j，v_i）∈E} ，集合 N_i 的基數被稱為 v_i 的度。圖 G （204號的鄰接矩陣是 A=[a_ij]_n×n ，如果 v_j∈N_i 那么 a_ij=1 ，否則 a_ij=0 。 L 表示圖 G 的拉普拉斯矩陣，且 L=D-A ，其中對角矩陣 的第 i 個對角元素是 v_i 的度。

符號說明： 和 R⁺ 分別代表實數集和正實數集， Z⁺ 和 N 表示正整數。 I_n 表示 n 階單位矩陣， e_i 表示單位矩陣的第 i 列。 0_n 表示全零元素的 n 階方陣。 R^n×n 表示 n 階實數矩陣。 Rⁿ 表示 n 維實數向量， Rⁿ 表示 n 維實數向量空間。 V_l 和 分別代表領導者和跟隨者集合。 C_Tk^T 表示矩陣 c_?Tk 的轉置矩陣。

1. 2 系統模型

考慮具有 n 個智能體的連續時間多智能體系統，每個智能體的動力學由一階積分器形式描述為

其中 u_i（t），x_i（t）∈R 分別為 v_i 的控制輸入和狀態。

v_i 的控制輸入 u_i（t） 遵循一致性協議（2）：

其中 為作用在 v_i 上的外部輸入。 N_i（t） 為 v_i 在時刻 Ψ_tΨ_Ψ 的鄰居集合。

假設系統有 Σ_P 個領導者，則 p∈{1，2，…，n} ，分別用 表示狀態向量。

在切換拓撲下，具有協議關系（2）的系統（1）表示為

其中， B_σ（t）=[e_i1，e_i2，…，e_ip]∈R^n×p，e_ip 為單位矩陣 I_n 的第 i_p 列，其中 i₁，i₂，…，i_p∈{1，2，…，n} 。函數σ（t）：Z⁺{1，2，…，N} 為系統（3）的切換信號。

1.3 定義和引理

為進一步討論切換偽路圖多智能體系統的能控性，給出本文定義和引理。

定義1（偽路圖）在 n（ngt;3，n∈N ）個節點形成的拓撲圖 P 中，將每個節點依次記為 τ₁，v₂，…，v_n ，假設每兩個相鄰節點之間有且僅有一條連接邊，記為 E_i=（v_i，v_i+1），i=1，2，…，n-1 。則 P 包含 （n-1） 條連接邊，此時 P 為完整路圖。用 ξ_l 代表 P 中連接邊的數量，若 1?l

定義2（切換偽路圖）從 n（n?3，n∈N ）個節點形成的偽路圖中，任取 β（β?2，β∈N ）個偽路圖，給定切換信號σ^（t）：Z⁺{1，2，…，β} ，形成切換偽路圖。

備注1在圖1中，每個拓撲圖都包含4個智能體，因為每個拓撲圖中都含有1條連接邊，所以 ι=1 ，根據定義1，這是兩個偽路圖。根據定義2，給定一個切換信號 σ^（t^）：Z⁺{1，2} ，形成切換偽路圖。

定義3（切換偽路圖多智能體系統）在切換拓撲多智能體系統中，每個子系統都包含 n（n?3，n∈N ）個智能體，記為 τ₁，v₂，…，v_n ，若每個子系統的拓撲結構都是偽路圖，則稱之為切換偽路圖多智能體系統。第 k 個子系統的連接邊記為 ，其中 k∈N，i_k∈{1，2，…，n-1} 。

備注2根據定義3，圖1為切換偽路圖多智能體系統，此時 k∈{1，2} 。 k=1 時， E₁=（v₃，v₄） ， i₁=3;k=2 時，E₂=（v₁，v₂） . i₂=1 。

定義4（零邊節點列表）在切換偽路圖多智能體系統中，每個子系統至少有1個、最多有 （n-1） 個智能體沒有連接邊，將每個子系統中沒有連接邊的智能體依次排列成行，依照切換信號將所有行由上到下排列成一個列表，形成零邊節點列表，記作 T₀ 。

備注3零邊節點列表 T₀ 中的元素僅代表與之對應的智能體而非具體數值。在圖1中，第一個子系統的零邊節點是 v₁，v₂ ，第二個子系統的零邊節點是 v₃，v₄ 。根據定義4，此時

定義5[21] 給定矩陣 R（B） 稱為 B 的列空間，表示為 R （2號η（B）={y∣y=Bx，x∈R^p} 。對于矩陣 A^n×n 和線性子空間 W?Rⁿ ，不變子空間定義為 。為了表示方便，將

定義 6^[25] 給定切換序列 π₁={（i₁，h₁），…，（i_n，h_n）} ，則 π₁∧π₂={（i₁，h₁），…，（i_n，h_n），（i₁，h₁），…，（i_n （204號 h_n）} ，特別地， 。

定義 7^[25] 已知非零初始狀態 x₀∈Rⁿ ，如果存在一個切換序列 π 和控制輸人 u（t）：[0，t_f]R^? ，滿足 x（0）= x₀，x（t_f）=0 ，則稱非零初始狀態 x₀∈Rⁿ 是能控的。

引理 1^[27] 對于任意矩陣 ，存在一組線性無關函數 a_i（t），i=0，1，…，n-1 ，滿足 。引理 2^[27] 給定矩陣 A∈R^n×n 當 00flt;+∞ 時 引理 3^[26] 給定切換序列 π={（i，h_i）}_i=1^N ，切換系統的終端狀態 x（t_N） 表示為

（204 。其中， x₀ 為初始狀態， u_i（t） 為第 i 個子系統的外部輸入， 。

引理4[25] 給定切換序列 π={（i₀，h₀）…（i_s-1，h_s-1）} ，切換系統在該切換序列下的能控狀態集為

給定 ，切換系統在這兩個切換序列下的能控狀態集為

其中， O

引理5[20，25] 系統（3）的嵌套子空間序列為：

2 主要結論

引理6當 l=1 時，切換偽路圖多智能體系統的矩陣指數函數是

證明：取 n?3 且 n∈N 。子系統的系統矩陣由偽路圖的拓撲結構決定，記為 -L_k ， k∈{1，2，…，n-1} 。將第 k 個子系統的特征值記為 λ₁^（k），λ₂^（k），…，λ_n^（k） ，當 l=1 時， -L_k 僅有一個非零特征值 λ_k^（k） ，即：

將 λ_j^（k） j≠k 的幾何重數記作 g₀ ，代數重數記作 a₀ ，由于 -L_k 是實對稱矩陣，所以

g₀=a₀=n-1

因此，－ L_k 的約當標準型矩陣

接下來，求解 -L_k 的特征向量 v_kγ ，其中 k∈{1，2，…，n-1}，γ∈{1，2，…，n} 。因為式（5）成立，所以 v_kγ 之間線性無關，進而可知變換矩陣 T_k=[ν_k1，ν_k2，…，ν_kn] 是非奇異矩陣，必有 T_k^-1=[ν_k1^′，…，ν_kn^′] 。

從而得到

-L_k=T_kJ_kT_k^-1

進而得到

若 l=1 ，則 λ_k^（k）=-2 。為便于討論，將 λ_k^?（k） 視作- L_k 的第一個特征值，相應地， 變為

此時，組成變換矩陣Tk的特征向量具有以下特征：?ngt;3且n∈N，若ik=1，νε=e1-e2，V=e1+e，V=（204號 e₃，…，ν_kn=e_n ；若 若 （20 若 i_k=n-1，ν_k1=e_n-1- 。

特別地，當 n=3 時，若 ；若 （204號 e₃ 。

同時， T_k^-1 具有以下特征：V ngt;3 且 n∈N ，若 v_kn^′=e_n ；若 若 ， 若 i_k=n-1

特別地，當 n=3 時，若 點若

?k，i_k∈{1，…，n-1}，h_k∈R⁺ ，根據式（7）得到：

給定切換序列 π={（r_k，h_k）}_k=1^N ，當 l=1 時，結合引理3和引理6，得到切換偽路圖多智能體的系統狀態表示為

證明：假設存在一個切換序列 π={（r_k，h_k）}_k=1^N 滿足rank （W_c）=n 。基于引理1，將式（8）中的積分項 表示為 ，其中包含 N?n 個標量常數 （20 s）u（s）ds，j∈{1，2，…，N} ！ d∈{0，1，…，n-1} 。取 U_j=[u_j，0，u_j，1，…，u_j，n-1]^T ，得到

令 U=[U₁^T，U₂^T，…，U_N^T]^T ，根據（8）和（9），得到

由于 W_c 行滿秩，所以總是存在解 U 使得（10）成立，因此切換偽路圖多智能體系統是能控的。

假設切換偽路圖多智能體系統能控，給定任意切換序列 π={（r_k，h_k）}_k=1^N 使得 rank（W_c）lt;_n ，那么一定存在非零向量 x_α∈Rⁿ 滿足 x_α^TW_c=0 ，也就是說， x_α^TW_c，j=0，j∈{1，2，…，N} 。因此得到

由于切換偽路圖多智能體系統能控，當 x（t₀）=0 時，一定存在切換序列 π={（r_k，h_k）}_k=1^N 和一個控制輸入u（t） ，其中 t∈[t₀，t_N] ，滿足 x_α=x（t_N） 。結合（8），得到

根據（12）、（13），得到

x_α^Tx_α=0

與最初假設 x_α≠0 矛盾。所以，當切換偽路圖多智能體系統能控時， rank（W_c）=n 。

定理2當 時，任取 ξ₁ 個互不相同的子系統，從 T₀ 中任選每個子系統的單領導者，若 ξ₁ 個單領導者兩兩相同，則 rank（W_c）=1 。任取 ξ₂ 個互不相同的子系統且 ξ₂ 個單領導者互不相同，則r ank（W_c）=ξ₂ 。其中 ξ₁∈ {2，3，…，n-2}，ξ₂∈{2，3，…，n-1} 。

證明：當 l=1 時，第 k 個子系統的度矩陣 D_k 和鄰接矩陣 A_k 分別是

其中， 進而得到第 k 個子系統的系統矩陣

其中，

?μ∈N ，得到

特別地， （-L_k）⁰=I_n 。

選取 （n-2） 個子系統的共同零邊節點 v_o 作為領導者，其中 o∈{1，n} ，則 的第 σ_o （20列元素相同， B₁=B₂=…=B_n-2=e_o ，因此 W_c，1=W_c，2=…=W_c，n-2 ，此時 rank（W_c）=1 。

從 T₀ 中選取 v_n 作為第一個子系統的領導者，選取 V_k-1 作為第 k 個子系統的領導者，其中， k=2，3，…，n- 1。此時 B₁?B₂≠…≠B_n-1 ，經過運算發現 W_c，1，W_c，2，…，W_c，n-1 之間線性無關，此時 rank（W_c）=n-1 。例2取 n=4，N=2 ，令 E₁=（v₁，v₂） ?i₁=1，E₂=（v₂，v₃），i₂=2 。給定切換序列 π={（1，1），（2，1）} ，則 δT₀= ，顯然，此時的共同零邊節點只有 v₄ 。首先，選取 v₄ 作為兩個子系統的領導者，則 B₁=B₂= [0001]。根據引理6，得到e?2?2 = 根據定理1及（16），得到 W_c，1=

0 0 07 -e-2+1 07 0 0 0 2 0 B1= 。所以 。 e?2+1 0 0 0 0 2 1 L0 0 0 1

2?rank（W_c）?n-1

證明：從子系統的零邊節點中任選一個節點等價于從 T₀ 中任選一個元素，于是，可以將全部子系統的單領導者看作集合元素，并將全部子系統的單領導者集合記作 F 。由于集合元素具有互異性，因此得到

∣F∣_min=2，∣F∣_max=n-1

由定理2，得到

2?rank（W_c）?n-1

定理3當 l=1 時，給定切換序列 π={（r_k，h_k）}_k=1^n-1 ，依據 T₀ 選取互不相同的子系統單領導者，在此切換序列下完成兩次切換，切換偽路圖多智能體系統實現能控性。

證明：將該切換序列下完成兩次切換的嵌套子空間記作 W₂ ，能控狀態空間記作 c ，此時 W₂=C 。根據引理5，得到

任取 i∈{1，…，n-1} ，根據引理4得到

任取 i₀，i₁∈{1，…，n-1} ，記

則

依據引理1，得到

其中， k=1，…，n-1 。將上式代入 中，得到構成 Δ_i0，i1 的一個加和項為

任取 k∈{1，…，n-1} ，α₀（h_k），α₁（h_k）…，α_n-1（h_k） 為標量，因此

其中， i₀，i₁∈{1，…，n-1} ， j∈{0，1，…，n-1} 。結合式 （18）～（20） ，得到：

由于 且 W₂=C ，所以 C（π^∧2）=W₂=C 。因此，在該切換序列下經過兩次切換，切換偽路圖多智能體的系統狀態可以到達能控狀態空間的任意指定位置。

4結論

本文討論切換偽路圖多智能體系統的能控性。文章利用幾何特征刻畫一類切換偽路圖多智能體的矩陣指數函數，給出系統實現能控性的充分必要條件。隨后，依據零邊節點列表研究了單領導者選取方式與系統能控性矩陣的關系。最后，構造切換偽路圖多智能體，獲得系統在給定切換序列下實現能控性的最小切換周期。結果表明，即使偽路圖的結構簡單，但是引入切換機制后，這類圖理論的復雜性也是直觀的。本文為進一步研究切換拓撲一般線性多智能體系統的能控性問題提供了理論基礎。

參考文獻：

[1]TANNER H. On the controllability of nearest neighbor interconnections[C]//Proceedings of the 43^rd IEEE Conference on Decision and Control.Atlantis.ParadiseIsland，Bahamas，2004：2467-2472.

[2]武海鷹，王緒安.分布式人工智能與多智能體系統研究[J]．微機發展，2004，14（3）：80－82.WUHY，WANGXA.Researchonmult-agent systemanddistributedAIJ].MicrocomputerDevelopment，2004，14（3）：80-82.

[3]李瑞敏，史其信.基于多智能體系統的城市交通控制與誘導集成化研究[J]．公路交通科技，2004，21（5）：109－112.LIRM，HQXReseachotgratioofubanraficotrolndoutegancebsedogentJJoualofhda2009，45（12）：2857-2863.

[5]LIUXZ，JZJControllbilitofultiagetsystsaseonpathdcclegrasJIterationalJoualofRobustandNrCotrol，2018，28（1），296－309.

[6]紀志堅．網絡系統的控制與優化[J]．系統科學與數學，2015，35（3）：257.JI ZJ.Optimizationandcontrolof network systemsJ].JournalofSystems ScienceandMathematicalSciences，2015，35（3）：257.

[7］王瀟，紀志堅．基于MAS的無人機新型編隊算法[J]．復雜系統與復雜性科學，2019，16（2）：60－68.WANG X，JIZJ.AnewUAV formationalgorithm basedon MAS[J]. Complex Systems and Complexity Science，2019，16（2）：60-68.

[8]ZHAOB，GUAQDatasampligotrolablitfultagntsstesIMAJualofathematicalCtrolandIfoatio37（3）： 794-813.

[9]國俊豪，紀志堅．基于NE結果的多智能體系統模型及其能控性[J]．復雜系統與復雜性科學，2021，18（4）：50－57.GUOJH，JIZJ.AmultiagentsyemmodelbasedonNesultsanditsontrolbility].CmplexSystesadCmplexitySi1，18（4）： 50-57.

[10]張志偉，紀志堅．有向路徑下的一類多智能體系統的能控性分析[J]．復雜系統與復雜性科學，2022，19（2）：63－70，95.ZHANG ZW，JZJControllbilityofultiagentsystemasedondrctedpathsJ]ComplexSystemsandComplexitSciee2，19（2）：63-70，95.

[11]紀志堅．等價劃分下多智能體系統能控性的一種判定方法[J/OL]．聊城大學學報（自然科學版），2023，36（6）：1－8.JIZJ.AetdfotengthotrollbiltyfultigentstesundereqitblepartitoOLJoualofiocngUiy（Nat Sci），2023，36（6）：1-8.

[12]SU，Gtapugeoloeiebe2023，138：301-310.

[13]GUANYQ，ZJZHALtalControlbiltfuliagesstesudedretedtolgnteatalualfutdNonlinear Control，2017，27（18）：4333-4347.

[14]QUJJ，JZJYegaalodiftrolablifultiagentsyssdereqiablearto]EETsacCybernetics，2021，51（9）：4661-4672.

[15]ZHOLHUalontrollltfaldseeulagtssiedegho[J].Journalof SystemsScienceand Complexity，2022，35（6）：2107-2130.

[16]GUOJH，etalUiderstangdulsftrobiloelofltigenttstenal of Robust and Nonlinear Control，2022，32（11）：6330－6345.

[17]JIZJ，ULesuligetroideosesgitdtrogSed2012，61（9），918-925.

[18]SUHS，ONMK，ZENGZGCotrobilitftotesalediseeeutiagessts]EETasactsonCbei，2020，50（4）：1440-1449.

[19]JZJ，WAUXXOrolltfidiearstsEEsactsai）：.

[20]SUNZD，HENGDH.OneachabilityandstabilizationofswitchedlinearsystemsJ]IEEETransactiosoAutomaticControl00，46（2）：291-295.

[21]SUZD，GESS，LEETHControlblityndeachabilityiteiaforswicedearsysts]Automatia8（5）：786.

[22]XIEGMLontrolbildtabilzblifswicdearsytsSytandtroLe8）：55.

[23]CHENGDZControlabilityofswitched bilinearsystems[J]IEEETransactionsonAutomaticControl，2005，50（4）：51-515.

[24]JZJ，Dltolifiaeional of Control，2010，83（2）：371-386.

[25]LIUB，CALtal.otrolbitfwicgetwoksofultiagentststeatlualfosdolinear Control，2012，22（6）：630－644.

[26]JZJ，WAUOXX.esiofsicngsquetrolbltalzaoofsiedliearsstotic，43（4）：662-668.

[27]TIANLL，ZHAOBWALControbilityfultiagestes withperiodicallywitcopologiesandswingleadstenational Journal of Control，2018，91（5）：1023-1033.

[28]TIANLLUANYQWANGLControbilitndbservabilitofswicdultiagentsystesInteratioalualoftol，2019，92（8）：1742-1752.

[29］司元超．時滯多智能體系統的能控性研究[D]．貴州：貴州大學，2022.SI YC.Research on controllability of multi-agent systems with delay[D]. Guizhou： Guizhou University，2022.

[30］張婷瑞．隨機切換系統的納什均衡精確能控性及線性二次最優控制[D]．北京：北京交通大學，2018.ZHANGTR.NashulibimprecisioncotrolabiltndlinearadaticptialtrolforstocasticswitchdsystmsDeing：Bejing Jiaotong University，2018.

[31]LIAM，OUSUYtalefundamentaldntageoftepoalnetwoksJSienc，58366）：0446.

（責任編輯 耿金花）