logo

SCIENCE CHINA Information Sciences, Volume 61, Issue 5: 052202(2018) https://doi.org/10.1007/s11432-017-9129-y

Non-fragility of multi-agent controllability

More info
  • ReceivedMar 4, 2017
  • AcceptedMay 16, 2017
  • PublishedDec 7, 2017

Abstract

Controllability of multi-agent systems is determined by the interconnection topologies. In practice, losing agents can change the topologies of multi-agent systems, which may affect the controllability. In order to preserve controllability, this paper first introduces the concept of non-fragility of controllability. In virtue of the notion of cutsets, necessary and sufficient conditions are established from a graphic perspective, for almost surely strongly/weakly preserving controllability, respectively. Then, the problem of leader selection to preserve controllability is proposed. The tight bounds of the fewest leaders to achieve strongly preserving controllability are estimated in terms of the diameter of the interconnection topology, and the cardinality of the node set. Correspondingly, the tight bounds of the fewest leaders to achieve weakly preserving controllability are estimated in terms of the cutsets of the interconnection topology. Furthermore, two algorithms are established for selecting the fewest leaders to strongly/weakly preserve the controllability. In addition, the algorithm for leaders' locations to maximize non-fragility is also designed. Simulation examples are provided to illuminate the theoretical results and exhibits how the algorithms proceed.


Acknowledgment

This work was supported by National Natural Science Foundation of China (Grant Nos. 61375120, 61603288).


References

[1] Xiao F, Wang L, Chen J. Partial state consensus for networks of second-order dynamic agents. Syst Control Lett, 2010, 59: 775-781 CrossRef Google Scholar

[2] Long Wang , Feng Xiao . Finite-Time Consensus Problems for Networks of Dynamic Agents. IEEE Trans Automat Contr, 2010, 55: 950-955 CrossRef Google Scholar

[3] Zhang Z, Zhang L, Hao F, et al. Leader-following consensus for linear and lipschitz nonlinear multiagent systems with quantized communication. IEEE Trans Cyber, 2016, 47: 1970--1982. Google Scholar

[4] Jing G, Zheng Y, Wang L. Consensus of Multiagent Systems With Distance-Dependent Communication Networks.. IEEE Trans Neural Netw Learning Syst, 2017, 28: 2712-2726 CrossRef PubMed Google Scholar

[5] Xiao F, Wang L, Chen J. Finite-time formation control for multi-agent systems. Automatica, 2009, 45: 2605-2611 CrossRef Google Scholar

[6] Olfati-Saber R. Flocking for Multi-Agent Dynamic Systems: Algorithms and Theory. IEEE Trans Automat Contr, 2006, 51: 401-420 CrossRef Google Scholar

[7] Jing G, Zheng Y, Wang L. Flocking of multi-agent systems with multiple groups. Int J Control, 2014, 87: 2573-2582 CrossRef Google Scholar

[8] Guan Y, Ji Z, Zhang L. Decentralized stabilizability of multi-agent systems under fixed and switching topologies. Syst Control Lett, 2013, 62: 438-446 CrossRef Google Scholar

[9] Guan Y, Ji Z, Zhang L. Controllability of heterogeneous multi-agent systems under directed and weighted topology. Int J Control, 2016, 89: 1009-1024 CrossRef Google Scholar

[10] Guan Y, Wang L. Structural controllability of multi-agent systems with absolute protocol under fixed and switching topologies. Sci China Inf Sci, 2017, 60: 092203 CrossRef Google Scholar

[11] Guan Y, Ji Z, Zhang L. Controllability of multi-agent systems under directed topology. Int J Robust NOnlinear Control, 2017, 27: 4333-4347 CrossRef Google Scholar

[12] Lu Z, Zhang L, Ji Z. Controllability of discrete-time multi-agent systems with directed topology and input delay. Int J Control, 2016, 89: 179-192 CrossRef Google Scholar

[13] Ma J, Zheng Y, Wu B. Equilibrium topology of multi-agent systems with two leaders: A zero-sum game perspective. Automatica, 2016, 73: 200-206 CrossRef Google Scholar

[14] Tanner H. On the controllability of nearest neighbor interconnections. In: Proceedings of the 43rd IEEE Conference on Decision and Control, Nassau, 2004. 2467--2472. Google Scholar

[15] Wang L, Jiang F C, Xie G M. Controllability of multi-agent systems based on agreement protocols. Sci China Ser F-Inf Sci, 2009, 52: 2074-2088 CrossRef Google Scholar

[16] Zhao B, Guan Y, Wang L. Controllability improvement for multi-agent systems: leader selection and weight adjustment. Int J Control, 2016, 89: 2008-2018 CrossRef Google Scholar

[17] Ji Z, Lin H, Yu H. Protocols Design and Uncontrollable Topologies Construction for Multi-Agent Networks. IEEE Trans Automat Contr, 2015, 60: 781-786 CrossRef Google Scholar

[18] Rahmani A, Ji M, Mesbahi M. Controllability of Multi-Agent Systems from a Graph-Theoretic Perspective. SIAM J Control Optim, 2009, 48: 162-186 CrossRef Google Scholar

[19] Ji Z, Lin H, Yu H. Leaders in multi-agent controllability under consensus algorithm and tree topology. Syst Control Lett, 2012, 61: 918-925 CrossRef Google Scholar

[20] Parlangeli G, Notarstefano G. On the Reachability and Observability of Path and Cycle Graphs. IEEE Trans Automat Contr, 2012, 57: 743-748 CrossRef Google Scholar

[21] Notarstefano G, Parlangeli G. Controllability and Observability of Grid Graphs via Reduction and Symmetries. IEEE Trans Automat Contr, 2013, 58: 1719-1731 CrossRef Google Scholar

[22] Partovi A, Lin H, Ji Z. Structural controllability of high order dynamic multi-agent systems. In: Proceedings of IEEE Conference on Robotics Automation and Mechatronics, Singapore, 2010. 327--332. Google Scholar

[23] Zamani M, Lin H. Structural controllability of multi-agent systems. In: Proceedings of the 2009 American Control Conference, St. Louis, 2009. 5743--5748. Google Scholar

[24] Lou Y, Hong Y. Controllability analysis of multi-agent systems with directed and weighted interconnection. Int J Control, 2012, 85: 1486-1496 CrossRef Google Scholar

[25] Goldin D, Raisch J. On the weight controllability of consensus algorithms. In: Proceedings of European Control Conference, Zurich, 2013. 233--238. Google Scholar

[26] Jafari S, Ajorlou A, Aghdam A G. Leader selection in multi-agent systems subject to partial failure. In: Proceedings of the 2011 American Control Conference, San Francisco, 2011. 5330--5335. Google Scholar

[27] Rahimian M A, Aghdam A G. Structural controllability of multi-agent networks: Robustness against simultaneous failures. Automatica, 2013, 49: 3149-3157 CrossRef Google Scholar

[28] Wilson R J. Introduction to Graph Theory. 4th ed. Upper Saddle River: Prentice Hall, 1996. Google Scholar

[29] Mayeda H, Yamada T. Strong Structural Controllability. SIAM J Control Optim, 1979, 17: 123-138 CrossRef Google Scholar

  • Figure 3

    A weighted graph with 5 nodes.

  • Figure 4

    A weighted graph with 4 nodes.

  • Figure 7

    A path with 5 nodes.

  • Figure 8

    A graph with 8 nodes.

  • Figure 9

    A graph with 9 nodes.

  • Figure 12

    A graph consists of 7 nodes.

  • Figure 13

    A graph consists of 8 nodes.

  •   

    Algorithm 1 Searching for the fewest leaders making the topology ASSPC

    Get the diameter of ${G}$, and denote it as $l$;

    for $i=\lfloor\frac{l-1}{3}\rfloor+1:\lfloor\frac{n}{2}\rfloor$

    Get all combinations of $i$ nodes from ${V}$, and denote them as ${V}_1,\ldots,{V}_{C_n^i}$;

    for $j=1:C_n^i$

    if $\langle{V}_j,{V}/{V}_j\rangle$ constitutes a bipartite graph then

    Output “The topology is ASSPC with the minimal leader set ${V}_j$” and exit.

    end if

    end for

    end for

  •   

    Algorithm 2 Searching for the fewest leaders making the topology at least AS$k$WPC

    Let $k'=k$;

    if no cutset of ${G}$ contains $k$ or less nodes then

    Output “The topology is at least AS$k'$WPC for any selection of leaders” and exit;

    end if

    while $k\neq1$ do

    if there exists a $k$-node cutset of ${G}$ then

    Find all the $k$-node cutsets, and denote them as $\mathcal{C}_1,\mathcal{C}_2,\ldots,\mathcal{C}_{s_k}$;

    Break;

    else

    $k=k-1$;

    end if

    end while

    for $l_m=2:n-1$

    Denote the selections of $l_m$ nodes from ${G}$ as $V_1,\ldots,V_{C_n^{l_m}}$;

    for $j=1:C_n^{l_m}$

    if no leader-follower cutset of ${G}$ contains $k$ or less nodes then

    Output “The topology is AS$k'$WPC with the leader set ${V}_j$” and exit.

    end if

    end for

    end for

  •   

    Algorithm 3 Leaders' distribution to maximize non-fragility

    Get the maximum number of leaders $M$, find all the $M$-node subsets of ${V}$, and denote them as ${V}_1,\ldots,{V}_{C_n^M}$, $\tilde{{V}}=\emptyset$, $\tilde{k}=0$;

    for $i=1:C_n^M$

    Select ${V}_i$ as the leader set;

    if the topology is AS$k$WPC and $k>\tilde{k}$ then

    $\tilde{{V}}={V}_i,~\tilde{k}=k$;

    end if

    end for

    if $k==n-M$ then

    Run algorithm 1 to search for the fewest leaders making the topology ASSPC, denote the number of the fewest leaders as $m$, $k=n-m$, and update the leader set $\tilde{{V}}$;

    end if

    Output “The topology is at most AS$k$WPC with no more than $M$ leaders, and achieves AS$k$WPC with the fewest leaders $\tilde{{V}}$”.

Copyright 2019 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1