×

Leaders in multi-agent controllability under consensus algorithm and tree topology. (English) Zbl 1270.93017

Summary: By controllability of multi-agent systems, we mean the property that all agents can be driven to arbitrary configurations only through regulating a few leaders externally, while the rest of the agents are subject to the nearest-neighbor-law. It is known that the controllability of multi-agent systems depends not only on the communication topologies among agents but also on the selection of leaders. The main objective of this paper aims to characterize the virtue that leaders should have from the perspective of algebraic and graphical conditions. We begin with a heuristic observation for tree graph. To gain more insights, necessary and sufficient conditions are then proposed in terms of downer branch and subgraphs, respectively. In particular, it is shown for path topologies that controllability completely depends on the leaders’ location. The obtained results may help us to pave the way towards a new method of formation and reconfiguration control in swarming robots.

MSC:

93B05 Controllability
93A14 Decentralized systems
68T42 Agent technology and artificial intelligence
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Hong, Y.; Chen, G.; Bushnell, L., Distributed observers design for leader-following control of multiagent networks, Automatica, 44, 3, 846-850 (2008) · Zbl 1283.93019
[2] Lafferriere, G.; Williams, A.; Caughman, J.; Veerman, J. J.P., Decentralized control of vehicle formations, Systems and Control Letters, 54, 9, 899-910 (2005) · Zbl 1129.93303
[3] Ren, W.; Beard, R. W., Consensus seeking in multiagent systems under dynamically changing interaction topologies, IEEE Transactions on Automatic Control, 50, 5, 655-661 (2005) · Zbl 1365.93302
[4] H.G. Tanner, On the controllability of nearest neighbor interconnections, in: Proceedings of the 43rd IEEE Conference on Decision and Control, Atlantis, Paradise Island, Bahamas, Dec. 14-17, 2004, pp. 2467-2472.; H.G. Tanner, On the controllability of nearest neighbor interconnections, in: Proceedings of the 43rd IEEE Conference on Decision and Control, Atlantis, Paradise Island, Bahamas, Dec. 14-17, 2004, pp. 2467-2472.
[5] M. Ji, M. Egerstedt, A graph-theoretic characterization of controllability for multi-agent systems, in: Proceedings of the 2007 American Control Conference, Marriott Marquis Hotel at Times Square, New York City, USA, July 11-13, 2007, pp 4588-4593.; M. Ji, M. Egerstedt, A graph-theoretic characterization of controllability for multi-agent systems, in: Proceedings of the 2007 American Control Conference, Marriott Marquis Hotel at Times Square, New York City, USA, July 11-13, 2007, pp 4588-4593.
[6] Liu, B.; Chu, T. G.; Wang, L.; Xie, G., Controllability of a leader-follower dynamic network with switching topology, IEEE Transactions on Automatic Control, 53, 4, 1009-1013 (2008) · Zbl 1367.93074
[7] Ji, Z.; Wang, Z. D.; Lin, H.; Wang, Z., Controllability of multi-agent systems with time-delay in state and switching topology, International Journal of Control, 83, 2, 371-386 (2010) · Zbl 1184.93017
[8] R. Lozano, M.W. Spong, J.A. Guerrero, N. Chopra, Controllability and observability of leader-based multi-agent systems, in: Proceedings of the 47th IEEE Conference on Decision and Control, Cancun, Mexico, Dec. 9-11, 2008, pp. 3713-3718.; R. Lozano, M.W. Spong, J.A. Guerrero, N. Chopra, Controllability and observability of leader-based multi-agent systems, in: Proceedings of the 47th IEEE Conference on Decision and Control, Cancun, Mexico, Dec. 9-11, 2008, pp. 3713-3718.
[9] A. Rahmani, M. Mesbahi, On the controlled agreement problem, in: Proceedings of the 2006 American Control Conference, Minneapolis, Minnesota, USA, Jun. 14-16, 2006, pp. 1376-1381.; A. Rahmani, M. Mesbahi, On the controlled agreement problem, in: Proceedings of the 2006 American Control Conference, Minneapolis, Minnesota, USA, Jun. 14-16, 2006, pp. 1376-1381.
[10] S. Martini, M. Egerstedt, A. Bicchi, Controllability decompositions of networked systems through quotient graphs, in: 47th IEEE Conference on Decision and Control, Fiesta Americana Grand Coral Beach, Cancun, Mexico, December 9-11, 2008.; S. Martini, M. Egerstedt, A. Bicchi, Controllability decompositions of networked systems through quotient graphs, in: 47th IEEE Conference on Decision and Control, Fiesta Americana Grand Coral Beach, Cancun, Mexico, December 9-11, 2008.
[11] Rahmani, A.; Ji, M.; Mesbahi, M.; Egerstedt, M., Controllability of multi-agent systems from a graph-theoretic perspective, SIAM Journal on Control and Optimization, 48, 1, 162-186 (2009) · Zbl 1182.93025
[12] Z. Ji, H. Lin, T. Lee, A graph theory based characterization of controllability for multi-agent systems with fixed topology, in: Proceedings of the 47th IEEE Conference on Decision and Control, Fiesta Americana Grand Coral Beach, Cancun, Mexico, December 9-11, 2008, pp. 5262-5267.; Z. Ji, H. Lin, T. Lee, A graph theory based characterization of controllability for multi-agent systems with fixed topology, in: Proceedings of the 47th IEEE Conference on Decision and Control, Fiesta Americana Grand Coral Beach, Cancun, Mexico, December 9-11, 2008, pp. 5262-5267.
[13] Ji, Z.; Wang, Z. D.; Lin, H.; Wang, Z., Interconnection topologies for multi-agent coordination under leader-follower framework, Automatica, 45, 12, 2857-2863 (2009) · Zbl 1192.93013
[14] Z. Ji, H. Lin, T. Lee, Nodes with the same number of neighbors and multi-agent controllability, in: Proceedings of the 30th Chinese Control Conference, Yantai, China, July 22-24, 2011, pp. 4792-4796.; Z. Ji, H. Lin, T. Lee, Nodes with the same number of neighbors and multi-agent controllability, in: Proceedings of the 30th Chinese Control Conference, Yantai, China, July 22-24, 2011, pp. 4792-4796.
[15] Liu, Y.-Y.; Slotine, J.-J.; Barabási, A.-L., Controllability of complex networks, Nature, 473, 167-173 (2011)
[16] I. Shames, A.M.H. Teixeira, H. Sandberg, K.H. Johansson, Distributed leader selection without direct inter-agent communication, in: 2nd IFAC Workshop on Estimation and Control of Networked Systems, Annecy, France, 2010, pp. 221-226.; I. Shames, A.M.H. Teixeira, H. Sandberg, K.H. Johansson, Distributed leader selection without direct inter-agent communication, in: 2nd IFAC Workshop on Estimation and Control of Networked Systems, Annecy, France, 2010, pp. 221-226.
[17] Wang, W.; Slotine, J. E., A theoretical study of different leader roles in networks, IEEE Transactions on Automatic Control, 51, 7, 1156-1161 (2006) · Zbl 1366.93416
[18] Faria, I., Permanental roots and the star degree of a graph, Linear Algebra and its Applications, 64, 255-265 (1985) · Zbl 0559.05041
[19] Merris, R., Laplacian graph eigenvectors, Linear Algebra and its Applications, 278, 221-236 (1998) · Zbl 0932.05057
[20] Bıyıkoğlu, T.; Leydold, J.; Stadler, P. F., (Laplacian Eigenvectors of Graphs: Perron-Frobenius and Faber-Krahn Type Theorems. Laplacian Eigenvectors of Graphs: Perron-Frobenius and Faber-Krahn Type Theorems, Lecture Notes in Mathematics (2007), Springer) · Zbl 1129.05001
[21] Bıyıkoğlu, T., A discrete nodal domain theorem for trees, Linear Algebra and its Applications, 360, 197-205 (2003) · Zbl 1012.05114
[22] Kim, I.-J.; Shader, B. L., On Fiedler- and Parter-vertices of acyclic matrices, Linear Algebra and its Applications, 428, 2601-2613 (2008) · Zbl 1145.15011
[23] Johnson, C. R.; Duarte, A. L.; Saiago, C. M., The Parter-Wiener theorem: Refinement and generalization, SIAM Journal on Matrix Analysis and Applications, 25, 2, 352-361 (2003) · Zbl 1067.15003
[24] Wilkinson, J., The calculation of eigenvectors of codiagonal mat, The Computer Journal, 1, 2, 90-96 (1958) · Zbl 0117.11001
[25] Parlett, B. N., The Symmetric Eigenvalue Problem (1997), SIAM: SIAM Philadelphia, PA
[26] Jiang, E. X., An extension of the roots separation theorem, Annals of Operations Research, 103, 315-327 (2001) · Zbl 0997.65063
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.