A journal of IEEE and CAA , publishes high-quality papers in English on original theoretical/experimental research and development in all areas of automation

IEEE/CAA Journal of Automatica Sinica

  • JCR Impact Factor: 15.3, Top 1 (SCI Q1)
    CiteScore: 23.5, Top 2% (Q1)
    Google Scholar h5-index: 77, TOP 5
Turn off MathJax
Article Contents
J. Qu, Z. Ji, J. Wang, and Y. Liu, “Necessary and sufficient conditions for controllability and essential controllability of directed circle and tree graphs,” IEEE/CAA J. Autom. Sinica, vol. 12, no. 4, pp. 694–704, Apr. 2025. doi: 10.1109/JAS.2024.124866
Citation: J. Qu, Z. Ji, J. Wang, and Y. Liu, “Necessary and sufficient conditions for controllability and essential controllability of directed circle and tree graphs,” IEEE/CAA J. Autom. Sinica, vol. 12, no. 4, pp. 694–704, Apr. 2025. doi: 10.1109/JAS.2024.124866

Necessary and Sufficient Conditions for Controllability and Essential Controllability of Directed Circle and Tree Graphs

doi: 10.1109/JAS.2024.124866
Funds:  This work was supported by the National Natural Science Foundation of China (62373205, 62033007), Taishan Scholars Climbing Program of Shandong Province of China, and Taishan Scholars Project of Shandong Province of China (tstp20230624, ts20190930)
More Information
  • The multi-agent controllability is intrinsically affected by the network topology and the selection of leaders. A focus of exploring this problem is to uncover the relationship between the eigenspace of Laplacian matrix and network topology. For strongly connected directed circle graphs, we elaborate how the zero entries in the left eigenvectors of Laplacian matrix L arise. The topologies arising from left eigenvectors with zero entries are filtered to construct essentially controllable directed circle graphs regardless of the choice of leaders. We propose two methods for constructing a substantial quantity of essentially controllable graphs, with a focus on utilizing essentially controllable circle graphs as the foundation. For a special directed graph-OT tree, the controllability is shown to be related with its substructure-paths. This promotes the establishment of a sufficient and necessary condition for controllability. Finally, a method is presented to check the controllable subspace by identifying the left eigenvectors and generalized left eigenvectors.

     

  • loading
  • [1]
    R. Olfati-Saber and R. M. Murray, “Consensus problems in networks of agents with switching topology and time-delays,” IEEE Trans. Autom. Control, vol. 49, no. 9, pp. 1520–1533, Sept. 2004. doi: 10.1109/TAC.2004.834113
    [2]
    C. Altafini, “Consensus problems on networks with antagonistic interactions,” IEEE Trans. Autom. Control, vol. 58, no. 4, pp. 935–946, Apr. 2013. doi: 10.1109/TAC.2012.2224251
    [3]
    H. Sun, Y. Liu, F. Li, and X. Niu, “Distributed LQR optimal protocol for leader-following consensus,” IEEE Trans. Cybern., vol. 49, no. 9, pp. 3532–3546, 2019. doi: 10.1109/TCYB.2018.2850760
    [4]
    O. Skeik and A. Lanzon, “Distributed robust stabilization of networked multiagent systems with strict negative imaginary uncertainties,” Int. J. Robust Nonlinear Control, vol. 29, no. 14, pp. 4845–4858, Sept. 2019. doi: 10.1002/rnc.4652
    [5]
    M. Li, M. Ma, L. Wang, Z. Pei, J. Ren, and B. Yang, “Multiagent deep reinforcement learning based incentive mechanism for mobile crowdsensing in intelligent transportation systems,” IEEE Syst. J., vol. 18, no. 1, pp. 527–538, Mar. 2024. doi: 10.1109/JSYST.2024.3351310
    [6]
    G. Zhabelova and V. Vyatkin, “Multiagent smart grid automation architecture based on IEC 61850/61499 intelligent logical nodes,” IEEE Trans. Ind. Electron., vol. 59, no. 5, pp. 2351–2362, 2012. doi: 10.1109/TIE.2011.2167891
    [7]
    P. Leitão, V. Mařík, and P. Vrba, “Past, present, and future of industrial agent applications,” IEEE Trans. Ind. Inf., vol. 9, no. 4, pp. 2360–2372, Nov. 2013. doi: 10.1109/TII.2012.2222034
    [8]
    H. G. Tanner, “On the controllability of nearest neighbor interconnections,” in Proc. 43rd IEEE Conf. Decision and Control, Nassau, Bahamas, 2004, pp. 2467–2472.
    [9]
    A. Rahmani, M. Ji, M. Mesbahi, and M. Egerstedt, “Controllability of multi-agent systems from a graph-theoretic perspective,” SIAM J. Control Optim., vol. 48, no. 1, pp. 162–186, Jan. 2009. doi: 10.1137/060674909
    [10]
    Z. Ji, Z. Wang, H. Lin, and Z. Wang, “Interconnection topologies for multi-agent coordination under leader-follower framework,” Automatica, vol. 45, no. 12, pp. 2857–2863, Dec. 2009. doi: 10.1016/j.automatica.2009.09.002
    [11]
    C. Sun, G. Hu, and L. Xie, “Controllability of multiagent networks with antagonistic interactions,” IEEE Trans. Autom. Control, vol. 62, no. 10, pp. 5457–5462, Oct. 2017. doi: 10.1109/TAC.2017.2697202
    [12]
    G. Notarstefano and G. Parlangeli, “Controllability and observability of grid graphs via reduction and symmetries,” IEEE Trans. Autom. Control, vol. 58, no. 7, pp. 1719–1731, Jul. 2013. doi: 10.1109/TAC.2013.2241493
    [13]
    X. Liu and Z. Ji, “Controllability of multiagent systems based on path and cycle graphs,” Int. J. Robust Nonlinear Control, vol. 28, no. 1, pp. 296–309, 2018. doi: 10.1002/rnc.3870
    [14]
    G. Parlangeli and G. Notarstefano, “On the reachability and observability of path and cycle graphs,” IEEE Trans. Autom. Control, vol. 57, no. 3, pp. 743–748, Mar. 2012. doi: 10.1109/TAC.2011.2168912
    [15]
    B. She, S. Mehta, C. Ton, and Z. Kan, “Controllability ensured leader group selection on signed multiagent networks,” IEEE Trans. Cybern., vol. 50, no. 1, pp. 222–232, Jan. 2020. doi: 10.1109/TCYB.2018.2868470
    [16]
    S. S. Mousavi, M. Haeri, and M. Mesbahi, “Laplacian dynamics on cographs: Controllability analysis through joins and unions,” IEEE Trans. Autom. Control, vol. 66, no. 3, pp. 1383–1390, Mar. 2021. doi: 10.1109/TAC.2020.2992444
    [17]
    B. Liu, T. Chu, L. Wang, and G. Xie, “Controllability of a leader-follower dynamic network with switching topology,” IEEE Trans. Autom. Control, vol. 53, no. 4, pp. 1009–1013, May 2008. doi: 10.1109/TAC.2008.919548
    [18]
    J. Yan, B. Hu, Z. Guan, Y. Hou, and L. Shi, “New controllability criteria for linear switched and impulsive systems,” IEEE/CAA J. Autom. Sin., 2024, DOI: 10.1109/JAS.2024.124272.
    [19]
    M. Xue and S. Roy, “Modal barriers to controllability in networks with linearly coupled homogeneous subsystems,” IEEE Trans. Autom. Control, vol. 66, no. 12, pp. 6187–6193, Dec. 2021. doi: 10.1109/TAC.2021.3063948
    [20]
    S. P. Hsu, “Constructing a controllable graph under edge constraints,” Syst. Control Lett., vol. 107, pp. 110–116, Sept. 2017. doi: 10.1016/j.sysconle.2017.07.015
    [21]
    S. P. Hsu, “Laplacian controllability of interconnected graphs,” IEEE Trans. Control Network Syst., vol. 7, no. 2, pp. 797–806, Jun. 2020. doi: 10.1109/TCNS.2019.2947589
    [22]
    C. O. Aguilar and B. Gharesifard, “Graph controllability classes for the Laplacian leader-follower dynamics,” IEEE Trans. Autom. Control, vol. 60, no. 6, pp. 1611–1623, Jun. 2015. doi: 10.1109/TAC.2014.2381435
    [23]
    Z. Ji, H. Lin, S. Cao, Q. Qi, and H. Ma, “The complexity in complete graphic characterizations of multiagent controllability,” IEEE Trans. Cybern., vol. 51, no. 1, pp. 64–76, Jan. 2021. doi: 10.1109/TCYB.2020.2972403
    [24]
    M. Cao, S. Zhang, and M. K. Camlibel, “A class of uncontrollable diffusively coupled multiagent systems with multichain topologies,” IEEE Trans. Autom. Control, vol. 58, no. 2, pp. 465–469, Feb. 2013. doi: 10.1109/TAC.2012.2208314
    [25]
    C. O. Aguilar, “Strongly uncontrollable network topologies,” IEEE Trans. Control Network Syst., vol. 7, no. 2, pp. 878–886, Jun. 2020. doi: 10.1109/TCNS.2019.2951665
    [26]
    C. O. Aguilar and B. Gharesifard, “Almost equitable partitions and new necessary conditions for network controllability,” Automatica, vol. 80, pp. 25–31, Jun. 2017. doi: 10.1016/j.automatica.2017.01.018
    [27]
    X. Liu, Z. Ji, and T. Hou, “Graph partitions and the controllability of directed signed networks,” Sci. China Inf. Sci., vol. 62, no. 4, p. 42202, Mar. 2019. doi: 10.1007/s11432-018-9450-8
    [28]
    Y. Guan and L. Wang, “Controllability of multi-agent systems with directed and weighted signed networks,” Syst. Control Lett., vol. 116, pp. 47–55, Jun. 2018. doi: 10.1016/j.sysconle.2018.04.010
    [29]
    A. Y. Yazicioğlu, W. Abbas, and M. Egerstedt, “Graph distances and controllability of networks,” IEEE Trans. Autom. Control, vol. 61, no. 12, pp. 4125–4130, Dec. 2016. doi: 10.1109/TAC.2016.2546180
    [30]
    S. Zhang, M. Cao, and M. K. Camlibel, “Upper and lower bounds for controllable subspaces of networks of diffusively coupled agents,” IEEE Trans. Autom. Control, vol. 59, no. 3, pp. 745–750, Mar. 2014. doi: 10.1109/TAC.2013.2275666
    [31]
    M. Shabbir, W. Abbas, A. Y. Yazicioğlu, and X. Koutsoukos, “Computation of the distance-based bound on strong structural controllability in networks,” IEEE Trans. Autom. Control, vol. 68, no. 3, pp. 1768–1775, Mar. 2023. doi: 10.1109/TAC.2022.3160682
    [32]
    Y. Guan, S. Chao, and A. Li, “Edge controllability of signed networks,” Automatica, vol. 147, p. 110694, Jan. 2023. doi: 10.1016/j.automatica.2022.110694
    [33]
    J. Jia, H. L. Trentelman, W. Baar, and M. K. Camlibel, “Strong structural controllability of systems on colored graphs,” IEEE Trans. Autom. Control, vol. 65, no. 10, pp. 3977–3990, Oct. 2020. doi: 10.1109/TAC.2019.2948425
    [34]
    S. S. Mousavi, M. Haeri, and M. Mesbahi, “On the structural and strong structural controllability of undirected networks,” IEEE Trans. Autom. Control, vol. 63, no. 7, pp. 2234–2241, Jul. 2018. doi: 10.1109/TAC.2017.2762620
    [35]
    N. Monshizadeh, S. Zhang, and M. K. Camlibel, “Zero forcing sets and controllability of dynamical systems defined on graphs,” IEEE Trans. Autom. Control, vol. 59, no. 9, pp. 2562–2567, Sept. 2014. doi: 10.1109/TAC.2014.2308619
    [36]
    C. T. Lin, “Structural controllability,” IEEE Trans. Autom. Control, vol. 19, no. 3, pp. 201–208, Jun. 1974. doi: 10.1109/TAC.1974.1100557
    [37]
    G. Frobenius, Uber Matrizen Aus Nicht Negativen Elementen. Berlin, Germany: Sitzungsber Press, 1912, pp. 456-477.
    [38]
    W. C. Yueh, “Eigenvalues of several tridiagonal matrices,” Appl. Math. E-Notes, vol. 5, pp. 66–74, Jan. 2005.

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Figures(4)

    Article Metrics

    Article views (80) PDF downloads(24) Cited by()

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return