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

Jijun Qu; Zhijian Ji; Jirong Wang; Yungang Liu

doi:10.1109/JAS.2024.124866

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

Article Navigation > IEEE/CAA Journal of Automatica Sinica > 2025 > In Press, Accepted Manuscript

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, 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, 2025. doi: 10.1109/JAS.2024.124866

Citation:

PDF( 1112 KB)

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

Author Bio:
Jijun Qu was born in 1992. He received the M.S. degree in control science and engineering from Qingdao University, Qingdao, China, in 2019, where he is currently pursuing the Ph.D. degree in system science at Qingdao University.His research interests include consensus and controllability problems in multiagent systems and complex networks

Zhijian Ji (Senior Member, IEEE) was born in 1973. He received the M.S. degree in applied mathematics from the Ocean University of China, Qingdao, China, in 1998, and the Ph.D. degree in control theory and control engineering from Peking University, Beijing, China, in 2005.He is currently a full-time Professor of Institute of Complexity Science with Qingdao University, Qingdao. In 2015 and in 2013, he was, respectively, a Visiting Professor with the University of Notre Dame, Notre Dame, IN, USA, and the University of Alberta, Edmonton, AB, Canada. From 2009 to 2010 and from 2008 to 2009, he was, respectively, a Research Fellow with the National University of Singapore, Singapore, and Brunel University London, Uxbridge, U.K. From 2006 to 2007, he was a Senior Research Associate with the City University of Hong Kong, Hong Kong. He has published more than 170 refereed papers in journals and international conference proceedings. His research interests include multiagent systems, switched control systems, networked control systems, intelligent control, and robot systems. Prof. Ji is a member of the Technical Committee on Control Theory in China

Jirong Wang (Doctor of Engineering) is a full-time Professor of Qingdao University, postdoctoral supervisor in Textile Discipline, and head of Master’s program in Mechanical Design and Theory. She received Ph.D. degree in mechanical engineering from the Ocean University of China, Qingdao, China, in 2009. She is currently a Shandong Province Teaching Master, Member of Shandong Province Mechanics Teaching Guidance Committee, Executive Director of Shandong Robotics Research Association, Top Talent in Laoshan District, Chairman of Qingdao Mechanics Society, Vice President of Qingdao Ultrasound Medical Engineering Society, and Director of Qingdao Robotics Society. Her research focuses on robots and non-standard automated production lines

Yungang Liu received the Ph.D. degree in control theory and control engineering from Shanghai JiaoTong University, Shanghai, China, in 2000.He is currently a Changjiang Scholar Chair Professor with the School of Control Science and Engineering, Shandong University, Jinan, China. His current research interests include stochastic control, nonlinear control design and system analysis, adaptive control and applications in power systems. Dr. Liu was a recipient of the Guan Zhaozhi Award in 2004, the National Outstanding Youth Science Foundation of China in 2013, and the Second Prize of the National Natural Science Award of China in 2015. He currently serves as an Associate Editor for seven famous scientific journals
Corresponding author: Zhijian Ji, e-mail: jizhijian@pku.org.cn
Received Date: 2024-04-04
Revised Date: 2024-07-09
Accepted Date: 2024-08-14

Available Online: 2025-01-02

Abstract

Abstract

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.
- Circle graphs,
- controllability,
- controllable subspace,
- essential controllability,
- tree graphs

FullText(HTML)

References(38)

References

[1]	R. Olfati-Saber, and R. M. Murray, “Consensus problems in networks of agents with switching topology and time-delays,” IEEE Trans. Automatic Control, vol. 49, no. 9, pp. 1520–1533, 2004. doi: 10.1109/TAC.2004.834113
[2]	C. Altafini, “Consensus problems on networks with antagonistic interactions,” IEEE Trans. Automatic Control, vol. 58, no. 4, pp. 935–946, 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. Cybernetics, vol. 49, no. 9, pp. 3532–3546, 2019. doi: 10.1109/TCYB.2018.2850760
[4]	O. Skeik, A. Lanzo, “Distributed robust stabilization of networked multiagent systems with strict negative imaginary uncertainties,” Int. Journal of Robust and Nonlinear Control, vol. 29, no. 14, pp. 4845–4858, 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 crowdsensingin intelligent transportation systems,” IEEE System Journal 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. Industrial Electronics, 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. Industrial Informatics, vol. 9, no. 4, pp. 2360–2372, 2013. doi: 10.1109/TII.2012.2222034
[8]	H. G. Tanner, “On the controllability of nearest neighbor interconnections,” In Proceeding of the 43rd IEEE Conf. on Decision and Control, Atlantis, Paradise Island, Bahamas, December 14–17, 2004, 2464–2472.
[9]	A. Rahmani, M. Ji, M. Mesbahi and M. Egerstedt, “Controllability of multi-agent systems from a graph-theoretic perspective,” SIAM Journal on Control and Optimization, vol. 48, no. 1, pp. 162–186, 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, pp. 2857–2863, 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. Automatic Control, vol. 62, no. 10, pp. 5457–5462, 2017. doi: 10.1109/TAC.2017.2697202
[12]	G. Notarstefano, G. Parlangeli, “Controllability and observability of grid graphs via reduction and symmetries,” IEEE Trans. Automatic Control, vol. 58, no. 7, pp. 1719–1731, 2013. doi: 10.1109/TAC.2013.2241493
[13]	X. Liu and Z. Ji, “Controllability of multi-agent systems based on path and cycle graphs,” Int. Journal of Robust and Nonlinear Control, vol. 28, no. 1, pp. 296–309, 2017.
[14]	G. Parlangeli and G. Notarstefano, “On the reachability and observability of path and cycle graphs,” IEEE Trans. Automatic Control, vol. 57, no. 3, pp. 743–748, 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. Cybernetics, vol. 50, no. 1, pp. 222–232, 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. Automatic Control, vol. 66, no. 3, pp. 1383–1390, 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. Automatic Control, vol. 53, no. 4, pp. 1009–1013, 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 Journal of Automatica Sinica, p. , 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. Automatic Control, vol. 66, no. 12, pp. 6187–6193, 2021. doi: 10.1109/TAC.2021.3063948
[20]	S. Hsu, “Constructing a controllable graph under edge constraints,” System & Control Letter, vol. 107, pp. 110–116, 2017.
[21]	S. Hsu, “Laplacian controllability of interconnected graphs,” IEEE Trans. Control of Network System, vol. 7, no. 2, pp. 797–806, 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. Automatic Control, vol. 60, no. 6, pp. 1611–1623, 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. Cybernetics, vol. 51, no. 1, pp. 64–76, 2021. doi: 10.1109/TCYB.2020.2972403
[24]	M. Cao, S. Zhang, and M. Kanat Camlibel, “A class of uncontrollable diffusively coupled multiagent systems with multichain topologies,” IEEE Trans. Automatic Control, vol. 58, no. 2, pp. 465–469, 2013. doi: 10.1109/TAC.2012.2208314
[25]	C. O. Aguilar, “Strongly uncontrollable network topologies,” IEEE Trans. Control of Network Systems, vol. 7, no. 2, pp. 878–886, 2020. doi: 10.1109/TCNS.2019.2951665
[26]	C. O. Aguilar, B. Gharesifard, “Almost equitable partitions and new necessary conditions for network controllability,” Automatica, vol. 80, pp. 25–31, 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,” SCIENCE CHINA Information Sciences, vol. 62, pp. 042202:1–042202:11, 2018.
[28]	Y. Guan, and L. Wang, “Controllability of multi-agent systems with directed and weighted signed networks,” System & Control Letter, vol. 116, pp. 47–55, 2017.
[29]	A. Y. Yazicioğlu, W. Abbas, and M. Egerstedt, “Graph distances and controllability of networks,” IEEE Trans. Automatic Control, vol. 61, no. 12, pp. 4125–4130, 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. Automatic Control, vol. 59, no. 3, pp. 745–750, 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. Automatic Control, p. , 2022. doi: 10.1109/TAC.2022.3160682
[32]	Y. Guan, S. Chao, A. Li, “Edge controllability of signed networks,” Automatica, vol. 147, pp. 1–10, 2023.
[33]	J. Jia, H. L. Trentelman, W. Baar, and M. K. Camlibel, “Strong structural controllability of systems on colored graphs,” IEEE Trans. Automatic Control, vol. 65, no. 10, pp. 3977–3990, 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. Automatic Control, vol. 63, no. 7, pp. 2234–2241, 2018. doi: 10.1109/TAC.2017.2762620
[35]	C. Lin, “Structural controllability,” IEEE Trans. Automatic Control, vol. 19, no. 3, pp. 201–208, 1974. doi: 10.1109/TAC.1974.1100557
[36]	G. Frobenius, “Uber matrizen aus nicht negativen elementen,” Sitzungsber Press, Berlin Wiss, pp. 456-477, 1912.
[37]	N. Monshizadeh, S. Zhang, and M. Kanat Camlibel, “Zero forcing sets and controllability of dynamical systems defined on graphs,” IEEE Trans. Automatic Control, vol. 59, no. 9, pp. 2562–2567, 2014. doi: 10.1109/TAC.2014.2308619
[38]	W. Yueh, “Eigenvalues of several tridiagonal matrices,” Applied Mathmatics E-notes, vol. 5, pp. 66–74, 2005.

Supplements(0)

Cited By

Proportional views

Proportional views

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

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

Figures(4)

Get Citation

PDF

XML

Article Metrics

Article views (32) PDF downloads(8)

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

doi: 10.1109/JAS.2024.124866

Abstract

References

Proportional views

Catalog

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

Article Metrics

Export File

Citation

Format

Content