Controllable multi-agent systems modeled by graphs with exactly one repeated degree

Bader Alshamary; Milica Anđelić; Edin Dolićanin; Zoran Stanić; Bader Alshamary; Milica Anđelić; Edin Dolićanin; Zoran Stanić

doi:10.3934/math.20241255

AIMS Mathematics

2024, Volume 9, Issue 9: 25689-25704. doi: 10.3934/math.20241255

Previous Article Next Article

Research article

Controllable multi-agent systems modeled by graphs with exactly one repeated degree

1.
Department of Mathematics, Kuwait University, Al-Shadadiyah, Kuwait
2.
Department of Technical Sciences, State University of Novi Pazar, 36300 Novi Pazar, Serbia
3.
Faculty of Mathematics, University of Belgrade, Studentski trg 16, 11000 Belgrade, Serbia

Received: 15 May 2024 Revised: 07 August 2024 Accepted: 12 August 2024 Published: 04 September 2024
MSC : 15A18, 05C50, 93A16

We consider the controllability of multi-agent dynamical systems modeled by a particular class of bipartite graphs, called chain graphs. Our main focus is related to chain graphs with exactly one repeated degree. We determine all chain graphs with this structural property and derive some properties of their Laplacian eigenvalues and associated eigenvectors. On the basis of the obtained theoretical results, we compute the minimum number of leading agents that make the system in question controllable and locate the leaders in the corresponding graph. Additionaly, we prove that a chain graph with exactly one repeated degree, that is not a star or a regular complete bipartite graph, has the second smallest Laplacian eigenvalue (also known as the algebraic connectivity) in $ (0.8299, 1) $ and we show that the second smallest eigenvalue increases when the number of vertices increases. This result is of a particular interest in control theory, since families of controllable graphs whose algebraic connectivity is bounded from below model the systems with a small risk of power or communication failures.
- controllable graph,
- chain graph,
- algebraic connectivity,
- multi-agent system
Citation: Bader Alshamary, Milica Anđelić, Edin Dolićanin, Zoran Stanić. Controllable multi-agent systems modeled by graphs with exactly one repeated degree[J]. AIMS Mathematics, 2024, 9(9): 25689-25704. doi: 10.3934/math.20241255

Related Papers:

Abstract

We consider the controllability of multi-agent dynamical systems modeled by a particular class of bipartite graphs, called chain graphs. Our main focus is related to chain graphs with exactly one repeated degree. We determine all chain graphs with this structural property and derive some properties of their Laplacian eigenvalues and associated eigenvectors. On the basis of the obtained theoretical results, we compute the minimum number of leading agents that make the system in question controllable and locate the leaders in the corresponding graph. Additionaly, we prove that a chain graph with exactly one repeated degree, that is not a star or a regular complete bipartite graph, has the second smallest Laplacian eigenvalue (also known as the algebraic connectivity) in $ (0.8299, 1) $ and we show that the second smallest eigenvalue increases when the number of vertices increases. This result is of a particular interest in control theory, since families of controllable graphs whose algebraic connectivity is bounded from below model the systems with a small risk of power or communication failures.

References

[1]	C. E. Garcia, D. M. Prett, M. Morari, Model predictive control: Theory and practice-A survey, Automatica, 25 (1989), 335–348. https://doi.org/10.1016/0005-1098(89)90002-2 doi: 10.1016/0005-1098(89)90002-2
[2]	N. Kishor, R. P. Saini, S. P. Singh, A review on hydropower plant models and control, Renew. Sust. Energ. Rev., 11 (2007), 776–796. https://doi.org/10.1016/j.rser.2005.06.003 doi: 10.1016/j.rser.2005.06.003
[3]	J. Klamka, Controllability of dynamical systems, Dordreht: Academic Publishers, 1991.
[4]	H. Mirinejad, S. H. Sadati, M. Ghasemian, H. Torab, Control techniques in heating, ventilating and air conditioning (HVAC) systems, J. Comput. Sci., 4 (2008), 777–783.
[5]	A. J. Sorensen, A survey of dynamic positioning control systems, Annu. Rev. Control, 35 (2011), 123–136. https://doi.org/10.1016/j.arcontrol.2011.03.008 doi: 10.1016/j.arcontrol.2011.03.008
[6]	B. Ding, Z. N. Li, Z. M. Li, Y. X. Xue, X. Y. Chang, J. Su, et al., A CCP-based distributed cooperative operation strategy for multi-agent energy systems integrated with wind, solar, and buildings, Appl. Energ., 365 (2024), 123275. https://doi.org/10.1016/j.apenergy.2024.123275 doi: 10.1016/j.apenergy.2024.123275
[7]	Z. N. Li, S. Su, X. L. Jin, M. Xia, Q. F. Chen, K. Yamashita, Stochastic and distributed optimal energy management of active distribution networks within integrated office buildings, CSEE J. Power Energy, 10 (2024), 504–517. http://dx.doi.org/10.17775/CSEEJPES.2021.04510 doi: 10.17775/CSEEJPES.2021.04510
[8]	H. G. Tanner, On the controllability of nearest neighbor interconnections, 2004 43rd IEEE Conference on Decision and Control, 3 (2004), 2467–2472. https://doi.org/10.1109/CDC.2004.1428782 doi: 10.1109/CDC.2004.1428782
[9]	M. Ji, M. Egerstedt, A graph-theoretic characterization of controllability for multi-agent systems, 2007 American Control Conference, 2007, 4588–4593. https://doi.org/10.1109/ACC.2007.4283010
[10]	C. Altafini, Consensus problems on networks with antagonistic interactions, IEEE T. Automat. Contr., 58 (2013), 935–946. https://doi.org/10.1109/TAC.2012.2224251 doi: 10.1109/TAC.2012.2224251
[11]	C. Sun, G. Q. Hu, L. Xie, Controllability of multiagent networks with antagonistic interactions, IEEE T. Automat. Contr., 62 (2017), 5457–5462. https://doi.org/10.1109/TAC.2017.2697202 doi: 10.1109/TAC.2017.2697202
[12]	X. Z. Liu, Z. J. Ji, T. Hou, Graph partitions and the controllability of directed signed networks, Sci. China Inf. Sci., 62 (2019), 42202. https://doi.org/10.1007/s11432-018-9450-8 doi: 10.1007/s11432-018-9450-8
[13]	Y. Q. Guan, L. Wang, Controllability of multi-agent systems with directed and weighted signed networks, Syst. Control Lett., 116 (2018), 47–55. https://doi.org/10.1016/j.sysconle.2018.04.010 doi: 10.1016/j.sysconle.2018.04.010
[14]	Y. Y. Liu, J. J. Slotine, A. L. Barabási, Controllability of complex networks, Nature, 473 (2011), 167–173. https://doi.org/10.1038/nature10011 doi: 10.1038/nature10011
[15]	H. Gao, Z. J. Ji, T. Hou, Equitable partitions in the controllability of undirected signed graphs, 2018 IEEE 14th International Conference on Control and Automation, 2018,532–537. https://doi.org/10.1109/ICCA.2018.8444164
[16]	Y. Q. Guan, L. L. Tian, L. Wang, Controllability of switching signed networks, IEEE T. Circuits-Ⅱ, 67 (2020), 1059–1063. https://doi.org/10.1109/TCSII.2019.2926090 doi: 10.1109/TCSII.2019.2926090
[17]	C. T. Lin, Structural controllability, IEEE T. Automat. Contr., 19 (1974), 201–208. https://doi.org/10.1109/TAC.1974.1100557 doi: 10.1109/TAC.1974.1100557
[18]	M. Zamani, H. Lin, Structural controllability of multi-agent systems, 2009 American Control Conference, 2009, 5743–5748. https://doi.org/10.1109/ACC.2009.5160170
[19]	M. K. Mehrabadi, M. Zamani, Z. Y. Chen, Structural controllability of a consensus network with multiple leaders, IEEE T. Automat. Contr., 64 (2019), 5101–5107. https://doi.org/10.1109/TAC.2019.2909809 doi: 10.1109/TAC.2019.2909809
[20]	Y. Q. Guan, A. Li, L. Wang, Structural controllability of directed signed networks, IEEE T. Contr. Netw. Syst., 8 (2021), 1189–1200. https://doi.org/10.1109/TCNS.2021.3059836 doi: 10.1109/TCNS.2021.3059836
[21]	H. Mayeda, T. Yamada, Strong structural controllability, SIAM J. Control Optim., 17 (1979), 123–138. https://doi.org/10.1137/0317010 doi: 10.1137/0317010
[22]	N. Monshizadeh, S. Zhang, M. K. Camlibel, Zero forcing sets and controllability of dynamical systems defined on graphs, IEEE T. Automat. Contr., 59 (2014), 2562–2567. https://doi.org/10.1109/TAC.2014.2308619 doi: 10.1109/TAC.2014.2308619
[23]	S. S. Mousavi, M. Haeri, M. Mesbahi, On the structural and strong structural controllability of undirected networks, IEEE T. Automat. Contr., 63 (2018), 2234–2241. https://doi.org/10.1109/TAC.2017.2762620 doi: 10.1109/TAC.2017.2762620
[24]	Y. S. Sun, Z. J. Ji, Y. G. Liu, C. Lin, On stabilizability of multi-agent systems, Automatica, 144 (2022), 110491. https://doi.org/10.1016/j.automatica.2022.110491 doi: 10.1016/j.automatica.2022.110491
[25]	G. Corso, A. I. L. de Araujo, A. M. de Almeida, Connectivity and nestedness in bipartite networks from community ecology, J. Phys: Conf. Ser., 285 (2011), 012009. https://doi.org/10.1088/1742-6596/285/1/012009 doi: 10.1088/1742-6596/285/1/012009
[26]	J. C. Nacher, T. Akutsu, Structural controllability of unidirectional bipartite graphs, Sci. Rep., 3 (2013), 1647. https://doi.org/10.1038/srep01647 doi: 10.1038/srep01647
[27]	M. S. Mariani, Z. M. Ren, J. Bascompte, C. J. Tessone, Nestedness in complex networks: Observation, emergence, and implications, Phys. Rep., 813 (2019), 1–90. https://doi.org/10.1016/j.physrep.2019.04.001 doi: 10.1016/j.physrep.2019.04.001
[28]	G. A. Pavlopoulos, P. I. Kontou, A. Pavlopoulou, C. Bouyioukos, E. Markou, P. G. Bagos, Bipartite graphs in systems biology and medicine: A survey of methods and applications, GigaScience, 7 (2018), giy014. https://doi.org/10.1093/gigascience/giy014 doi: 10.1093/gigascience/giy014
[29]	A. Alazemi, M. Anđelić, T. Koledin, Z. Stanić, Chain graphs with simple Laplacian eigenvalues and their Laplacian dynamics, Comput. Appl. Math., 42 (2023), 6. https://doi.org/10.1007/s40314-022-02141-5 doi: 10.1007/s40314-022-02141-5
[30]	M. Anđelić, C. M. da Fonseca, E. Kılıć, Z. Stanić, A Sylvester-Kac matrix type and the Laplacian controllability of half graphs, Electron. J. Linear Al., 38 (2022), 559–571. https://doi.org/10.13001/ela.2022.6947 doi: 10.13001/ela.2022.6947
[31]	S. P. Hsu, Controllability of the multi-agent system modelled by the threshold graph with one repeated degree, Syst. Control Lett., 97 (2016), 149–156. https://doi.org/10.1016/j.sysconle.2016.09.010 doi: 10.1016/j.sysconle.2016.09.010
[32]	D. Cvetković, P. Rowlinson, S. Simić, An introduction to the theory of graph spectra, Cambridge: Cambridge University Press, 2011. https://doi.org/10.1017/CBO9780511801518
[33]	M. Fiedler, Algebraic connectivity of graphs, Czechoslovak Math. J., 23 (1973), 298–305. https://doi.org/10.21136/CMJ.1973.101168 doi: 10.21136/CMJ.1973.101168
[34]	A. Simonetto, T. Keviczky, R. Babuška, Constrained distributed algebraic connectivity maximization in robotic networks, Automatica, 49 (2013), 1348–1357. https://doi.org/10.1016/j.automatica.2013.02.031 doi: 10.1016/j.automatica.2013.02.031
[35]	A. Rahmani, M. Ji, M. Mesbahi, M. Egerstedt, Controllability of multi-agent systems from a graph theoretic perspective, SIAM J. Control Optim., 48 (2009), 162–186. https://doi.org/10.1137/060674909 doi: 10.1137/060674909
[36]	T. Kailath, Linear systems, Englewood Cliffs: Prentice-Hall, 1980.
[37]	Z. J. Ji, Z. D. Wang, H. Lin, Z. Wang, Interconnection topologies for multi-agent coordination under leader-follower framework, Automatica, 45 (2009), 2857–2863. https://doi.org/10.1016/j.automatica.2009.09.002 doi: 10.1016/j.automatica.2009.09.002
[38]	X. Z. Liu, Z. J. Ji, Controllability of multiagent systems based on path and cycle graphs, Int. J. Robust Nonlin., 28 (2018), 296–309. https://doi.org/10.1002/rnc.3870 doi: 10.1002/rnc.3870
[39]	S. S. Mousavi, M. Haeri, M. Mesbahi, Laplacian dynamics on cographs: Controllability analysis through joins and unions, IEEE T. Automat. Contr., 66 (2021), 1383–1390. https://doi.org/10.1109/TAC.2020.2992444 doi: 10.1109/TAC.2020.2992444
[40]	M. Anđelić, C. M. da Fonseca, T. Koledin, Z. Stanić, Sharp spectral inequalities for connected bipartite graphs with maximal $Q$-index, Ars Math. Contemp., 6 (2013), 171–185. http://dx.doi.org/10.26493/1855-3974.271.85e doi: 10.26493/1855-3974.271.85e
[41]	A. Alazemi, M. Anđelić, K. C. Das, C. M. da Fonseca, Chain graph sequences and Laplacian spectra of chain graphs, Linear Multilinear Algebra, 71 (2023), 569–585. https://doi.org/10.1080/03081087.2022.2036672 doi: 10.1080/03081087.2022.2036672
[42]	R. A. Horn, C. R. Johnson, Matrix analysis, second edition, New York: Cambridge University Press, 2013. https://doi.org/10.1017/CBO9781139020411
[43]	Z. Stanić, Inequalities for graph eigenvalues, Cambridge: Cambridge University Press, 2015. https://doi.org/10.1017/CBO9781316341308
[44]	M. Anđelić, E. Dolićanin, Z. Stanić, Controllability of the multi-agent system modelled by the chain graphs with repeated degree, IX International Conference IcETRAN and LXVI ETRAN Conference, 2022,539–542.

Reader Comments

Your name:*

Email:*
© 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)