Distributed coordination inmulti-agent systems: a graph Laplacian perspective

Abstract

This paper reviews some main results and progress in distributed multi-agent coordination from a graph Laplacian perspective. Distributed multi-agent coordination has been a very active subject studied extensively by the systems and control community in last decades, including distributed consensus, formation control, sensor localization, distributed optimization, etc. The aim of this paper is to provide both a comprehensive survey of existing literature in distributed multi-agent coordination and a new perspective in terms of graph Laplacian to categorize the fundamental mechanisms for distributed coordination. For different types of graph Laplacians, we summarize their inherent coordination features and specific research issues. This paper also highlights several promising research directions along with some open problems that are deemed important for future study.

Keywords

Multi-agent systems / Distributed coordination / Graph Laplacian

References

[1] Altafini, C., 2013. Consensus problems on networks with antagonistic interactions. IEEE Trans. Automat. Contr., 58(4): 935-946. [

[2] Anderson, B.D.O., Yu, C., Fidan, B., , 2008. Rigid graph control architectures for autonomous formations. IEEE Contr. Syst., 28(6): 48-63. [

[3] Bliman, P., Ferrari-Trecate, G., 2008. Average consensus problems in networks of agents with delayed communications. Automatica, 44(8): 1985-1995. [

[4] Blondel, V.D., Hendrickx, J.M., Olshevsky, A., , 2005. Convergence in multiagent coordination, consensus, and flocking. Proc. 44th IEEE Conf. on Decision and Control and European Control Conf., p.2996-3000. [

[5] Boyd, S., 2006. Convex optimization of graph Laplacian eigenvalues. Proc. Int. Congress of Mathematicians, p.1311-1320.

[6] Boyd, S., Diaconis, P., Parrilo, P., , 2009. Fastest mixing Markov chain on graphs with symmetries. SIAM J. Optim., 20(2): 792-819. [

[7] Bullo, F., Cortes, J., Martinez, S., 2009. Distributed Control of Robotic Networks. Princeton University Press, USA.

[8] Cai, K., Ishii, H., 2012. Average consensus on general strongly connected digraphs. Automatica, 48(11): 2750-2761. [

[9] Cai, K., Ishii, H., 2014. Average consensus on arbitrary strongly connected digraphs with time-varying topologies. IEEE Trans. Automat. Contr., 59(4): 1066-1071. [

[10] Cao, L., Zheng, Y., Zhou, Q., 2011. A necessary and sufficient condition for consensus of continuous-time agents over undirected time-varying networks. IEEE Trans. Automat. Contr., 56(8): 1915-1920. [

[11] Casbeer, D.W., Beard, R., Swindlehurst, A.L., 2008. Discrete double integrator consensus. Proc. 47th IEEE Conf. on Decision and Control, p.2264-2269. [

[12] Chen, J., Wang, C., Sun, Y., , 2011. Semi-supervised Laplacian regularized least squares algorithm for localization in wireless sensor networks. Comput. Netw., 55(10): 2481-2491. [

[13] Cortes, J., 2008. Distributed algorithms for reaching consensus on general functions. Automatica, 44(3): 726-737. [

[14] Cortes, J., 2009. Global and robust formation-shape stabilization of relative sensing networks. Automatica, 45(12): 2754-2762. [

[15] de Abreu, N.M.M., 2007. Old and new results on algebraic connectivity of graphs. Linear Algebra Appl., 423(1): 53-73. [

[16] Degroot, M.H., 1974. Reaching a consensus. J. Am. Statist. Assoc., 69(345): 118-121.

[17] Diao, Y., Lin, Z., Fu, M., , 2013. Localizability and distributed localization of sensor networks using relative position measurements. Proc. 13th IFAC Symp. on Large Scale Complex Systems: Theory and Applications, p.1-6. [

[18] Diao, Y., Lin, Z., Fu, M., 2014. A barycentric coordinate based distributed localization algorithm for sensor networks. IEEE Trans. Signal Process., 62(18): 4760-4771. [

[19] Ding, W., Yan, G., Lin, Z., 2010. Collective motion and formations under pursuit strategies on directed acyclic graphs. Automatica, 46(1): 174-181. [

[20] Ding, W., Yan, G., Lin, Z., 2012. Pursuit formations with dynamic control gains. Int. J. Robust Nonlinear Contr., 22(3): 300-317. [

[21] Dominguez-Garcia, A.D., Cady, S.T., Hadjicostis, C.N., 2012. Decentralized optimal dispatch of distributed energy resources. Proc. IEEE 51st Annual Conf. on Decision and Control, p.3688-3693. [

[22] Dorfler, F., Bullo, F., 2014. Synchronization in complex networks of phase oscillators: a survey. Automatica, 50(6): 1539-1564. [

[23] Easley, D., Kleinberg, J., 2010. Networks, Crowds, and Markets: Reasoning about a Highly Connected World. Cambridge University Press, UK.

[24] Fanti, M.P., Mangini, A.M., Mazzia, F., , 2015. A new class of consensus protocols for agent networks with discrete time dynamics. Automatica, 54: 1-7. [

[25] Ghosh, A., Boyd, S., Saberi, A., 2008. Minimizing effective resistance of a graph. SIAM Rev., 50(1): 37-66. [

[26] Godsil, C., Royle, G., 2001. Algebraic Graph Theory. Springer, New York, USA.

[27] Goldenberg, D.K., Bihler, P., Cao, M., , 2006. Localization in sparse networks using sweeps. Proc. 12th Annual Int. Conf. on Mobile Computing and Networking, p.110-121. [

[28] Gortler, S.J., Healy, A.D., Thurston, D.P., 2010. Characterizing generic global rigidity. Am. J. Math., 132(4): 897-939. [

[29] Han, T., Lin, Z., Fu, M., 2014a. Formation merging control in 3D under directed and switching topologies. Proc. 19th IFAC World Congress, p.10036-10041. [

[30] Han, T., Lin, Z., Xu, W., , 2014b. Three-dimensional formation merging control of second-order agents under directed and switching topologies. Proc. 11th IEEE Int. Conf. on Control and Automation, p.225-230. [

[31] Han, Y., Lu, W., Chen, T., 2013. Cluster consensus in discrete-time networks of multiagents with inter-cluster nonidentical inputs. IEEE Trans. Neur. Netw. Learn. Syst., 24(4): 566-578. [

[32] Han, Z., Wang, L., Lin, Z., , 2012. Double-graph formation control for co-leader vehicle networks. Proc. 24th Chinese Control and Decision Conf., p.158-163. [

[33] Han, Z., Wang, L., Lin, Z., 2013. Local formation control strategies with undetermined and determined formation scales for co-leader vehicle networks. Proc. IEEE 52nd Annual Conf. on Decision and Control, p.7339-7344. [

[34] Han, Z., Lin, Z., Fu, M., 2014. A fully distributed approach to formation maneuvering control of multi-agent systems. Proc. IEEE 53rd Annual Conf. on Decision and Control, p.6185-6190. [

[35] He, C., Feng, Z., Ren, Z., 2012. Flocking of multiagents based on consensus protocol and pinning control. Proc. 10th World Congress on Intelligent Control and Automation, p.1311-1316. [

[36] Hendrickx, J.M., Tsitsiklis, J.N., 2013. Convergence of type-symmetric and cut-balanced consensus seeking systems. IEEE Trans. Automat. Contr., 58(1): 214-218. [

[37] Hong, Y., Hu, J., Gao, L., 2006. Tracking control for multi-agent consensus with an active leader and variable topology. Automatica, 42(7): 1177-1182. [

[38] Huang, H., Wu, Q., 2010. H∞ control of distributed multiagent formation systems with Toeplitz-based consensus algorithms. Proc. American Control Conf., p.6840-6845. [

[39] Hwang, K., Tan, S., Chen, C., 2004. Cooperative strategy based on adaptive Q-learning for robot soccer systems. IEEE Trans. Fuzzy Syst., 12(4): 569-576. [

[40] Jadbabaie, A., Lin, J., Morse, A.S., 2003. Coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE Trans. Automat. Contr., 48(6): 988-1001. [

[41] Jiang, H., Zhang, L., Guo, S., 2014. Cluster anticonsensus in directed networks of multi-agents based on the Q-theory. J. Franklin Inst., 351(10): 4802-4816. [

[42] Kar, S., Hug, G., 2012. Distributed robust economic dispatch in power systems: a consensus+ innovations approach. Proc. IEEE Power and Energy Society General Meeting, p.1-8. [

[43] Khan, U.A., Kar, S., Moura, J.M.F., 2009. Distributed sensor localization in random environments using minimal number of anchor nodes. IEEE Trans. Signal Process., 57(5): 2000-2016. [

[44] Kingston, D.B., Beard, R.W., 2006. Discrete-time averageconsensus under switching network topologies. Proc. American Control Conf., p.3551-3556. [

[45] Kunegis, J., Schmidt, S., Lommatzsch, A., 2010. Spectral analysis of signed graphs for clustering, prediction and visualization. SIAM, 10: 559-570.

[46] Kuriki, Y., Namerikawa, T., 2014. Consensus-based cooperative formation control with collision avoidance for a multi-UAV system. Proc. American Control Conf., p.2077-2082. [

[47] Lakshmanan, H., de Farias, D.P., 2008. Decentralized resource allocation in dynamic networks of agents. SIAM J. Optim., 19(2): 911-940. [

[48] Leonard, N.E., Paley, D.A., Lekien, F., , 2007. Collective motion, sensor networks, and ocean sampling. Proc. IEEE, 95(1): 48-74. [

[49] Li, S., Du, H., Lin, X., 2011. Finite-time consensus algorithm for multi-agent systems with double-integrator dynamics. Automatica, 47(8): 1706-1712. [

[50] Li, Z., Jia, Y., Du, J., , 2008. Flocking for multiagent systems with switching topology in a noisy environment. Proc. American Control Conf., p.111-116. [

[51] Lin, Z., 2008. Distributed Control and Analysis of Coupled Cell Systems. VDM-Verlag, Germany.

[52] Lin, Z., Broucke, M., Francis, B., 2004. Local control strategies for groups of mobile autonomous agents. IEEE Trans. Automat. Contr., 49(4): 622-629. [

[53] Lin, Z., Francis, B., Maggiore, M., 2005. Necessary and sufficient graphical conditions for formation control of unicycles. IEEE Trans. Automat. Contr., 50(1): 121-127. [

[54] Lin, Z., Francis, B., Maggiore, M., 2007. State agreement for continuous-time coupled nonlinear systems. SIAM J. Contr. Optim., 46(1): 288-307. [

[55] Lin, Z., Chen, Z., Fu, M., 2013a. A linear control approach to distributed multi-agent formations in d-dimensional space. Proc. IEEE 52nd Annual Conf. on Decision and Control, p.6049-6054. [

[56] Lin, Z., Ding, W., Yan, G., , 2013b. Leaderfollower formation via complex Laplacian. Automatica, 49(6): 1900-1906. [

[57] Lin, Z., Wang, L., Han, Z., , 2014. Distributed formation control of multi-agent systems using complex Laplacian. IEEE Trans. Automat. Contr., 59(7): 1765-1777. [

[58] Lin, Z., Fu, M., Diao, Y., 2015. Distributed self localization for relative position sensing networks in 2D space. IEEE Trans. Signal Process., in press. [

[59] Liu, X., Chen, T., 2011. Cluster synchronization in directed networks via intermittent pinning control. IEEE Trans. Neur. Netw., 22(7): 1009-1020. [

[60] Lu, W., Liu, B., Chen, T., 2010. Cluster synchronization in networks of coupled nonidentical dynamical systems. Chaos, 20(1), Article 013120. [

[61] Lu, X., Austin, F., Chen, S., 2010a. Cluster consensus of nonlinearly coupled multi-agent systems in directed graphs. Chin. Phys. Lett., 27(5), Article 050503. [

[62] Lu, X., Austin, F., Chen, S., 2010b. Cluster consensus of second-order multi-agent systems via pinning control. Chin. Phys. B, 19(12), Article 120506. [

[63] Martin, S., 2014. Multi-agent flocking under topological interactions. Syst. Contr. Lett., 69: 53-61. [

[64] Mesbahi, M., Egerstedt, M., 2010. Graph Theoretic Methods for Multagent Networks. Princeton University Press, USA.

[65] Morbidi, F., 2013. The deformed consensus protocol. Automatica, 49(10): 3049-3055. [

[66] Moreau, L., 2005. Stability of multiagent systems with timedependent communication links. IEEE Trans. Automat. Contr., 50(2): 169-182. [

[67] Moshtagh, N., Jadbabaie, A., 2007. Distributed geodesic control laws for flocking of nonholonomic agents. IEEE Trans. Automat. Contr., 52(4): 681-686. [

[68] Moshtagh, N., Jadbabaie, A., Daniilidis, K., 2006. Visionbased control laws for distributed flocking of nonholonomic agents. Proc. IEEE Int. Conf. on Robotics and Automation, p.2769-2774. [

[69] Murray, R.M., 2007. Recent research in cooperative control of multivehicle systems. J. Dynam. Syst. Meas. Contr., 129(5): 571-583. [

[70] Nedic, A., Ozdaglar, A., Parrilo, P.A., 2010. Constrained consensus and optimization in multi-agent networks. IEEE Trans. Automat. Contr., 55(4): 922-938. [

[71] Oh, K., Ahn, H.S., 2014. Formation control and network localization via orientation alignment. IEEE Trans. Automat. Contr., 59(2): 540-545. [

[72] Oh, K., Lashhab, F., Moore, K.L., , 2015a. Consensus of positive real systems cascaded with a single integrator. Int. J. Robust Nonlinear Contr., 25(3): 418-429. [

[73] Oh, K., Park, M.C., Ahn, H.S., 2015b. A survey of multi-agent formation control. Automatica, 53: 424-440. [

[74] Okubo, A., 1986. Dynamical aspects of animal grouping: swarms, schools, flocks, and herds. Adv. Biophys., 22: 1-94. [

[75] Olfati-Saber, R., Murray, R.M., 2004. Consensus problems in networks of agents with switching topology and timedelays. IEEE Trans. Automat. Contr., 49(9): 1520-1533. [

[76] Olfati-Saber, R., Fax, J.A., Murray, R.M., 2007. Consensus and cooperation in networked multi-agent systems. Proc. IEEE, 95(1): 215-233. [

[77] Passino, K.M., 2002. Biomimicry of bacterial foraging for distributed optimization and control. IEEE Contr. Syst., 22(3): 52-67. [

[78] Proskurnikov, A., 2013. Consensus in switching symmetric networks of first-order agents with delayed relative measurements. Proc. IEEE 52nd Annual Conf. on Decision and Control, p.917-921. [

[79] Qin, J., Yu, C., 2013. Cluster consensus control of generic linear multi-agent systems under directed topology with acyclic partition. Automatica, 49(9): 2898-2905. [

[80] Qin, J., Zheng, W.X., Gao, H., 2011. Consensus of multiple second-order vehicles with a time-varying reference signal under directed topology. Automatica, 47(9): 1983-1991. [

[81] Qu, Z., 2009. Cooperative Control of Dynamical Systems: Applications to Autonomous Vehicles. Springer-Verlag, London, UK.

[82] Ren, W., 2007. Consensus strategies for cooperative control of vehicle formations. IET Contr. Theory Appl., 1(2): 505-512. [

[83] Ren, W., 2008. On consensus algorithms for doubleintegrator dynamics. IEEE Trans. Automat. Contr., 53(6): 1503-1509. [

[84] Ren, W., Beard, R., 2004. Consensus of information under dynamically changing interaction topologies. Proc. American Control Conf., p.4939-4944.

[85] Ren, W., Beard, R., 2005. Consensus seeking in multiagent systems under dynamically changing interaction topologies. IEEE Trans. Automat. Contr., 50(5): 655-661. [

[86] Ren, W., Beard, R., 2008. Distributed Consensus in Multivehicle Cooperative Control: Theory and Applications. Springer, London, UK.

[87] Ren, W., Cao, Y., 2008. Convergence of sampled-data consensus algorithms for double-integrator dynamics. Proc. 47th IEEE Conf. on Decision and Control, p.3965-3970. [

[88] Ren, W., Cao, Y., 2011. Distributed Coordination of Multiagent Networks: Emergent Problems, Models, and Issues. Springer-Verlag, London, UK.

[89] Ren, W., Beard, R., Atkins, E.M., 2007. Information consensus in multivehicle cooperative control. IEEE Contr. Syst., 27(2): 71-82. [

[90] Reynolds, C.W., 1987. Flocks, herds and schools: a distributed behavioral model. ACM SIGGRAPH Comput. Graph., 21(4): 25-34. [

[91] Semnani, S.H., Basir, O.A., 2015. Semi-flocking algorithm for motion control of mobile sensors in large-scale surveillance systems. IEEE Trans. Cybern., 45(1): 129-137. [

[92] Stanković, S.S., Stankovia, M.S., Stipanović, D.M., 2009. Consensus based overlapping decentralized estimation with missing observations and communication faults. Automatica, 45(6): 1397-1406. [

[93] Sugihara, K., Suzuki, I., 1990. Distributed motion coordination of multiple mobile robots. Proc. 5th IEEE Int. Symp. on Intelligent Control, p.138-143. [

[94] Sun, J., Boyd, S., Xiao, L., , 2006. The fastest mixing Markov process on a graph and a connection to a maximum variance unfolding problem. SIAM Rev., 48(4): 681-699. [

[95] Tahbaz-Salehi, A., Jadbabaie, A., 2008. A necessary and sufficient condition for consensus over random networks. IEEE Trans. Automat. Contr., 53(3): 791-795. [

[96] Tian, Y., Liu, C., 2009. Robust consensus of multi-agent systems with diverse input delays and asymmetric interconnection perturbations. Automatica, 45(5): 1347-1353. [

[97] Tsitsiklis, J.N., 1984. Problems in Decentralized Decision Making and Computation. PhD Thesis, Massachusetts Institute of Technology, USA.

[98] Tsitsiklis, J.N., Bertsekas, D.P., Athans, M., 1986. Distributed asynchronous deterministic and stochastic gradient optimization algorithms. IEEE Trans. Automat. Contr., 31(9): 803-812. [

[99] Wang, C., Chen, J., Sun, Y., , 2009. A graph embedding method for wireless sensor networks localization. Proc. IEEE Global Telecommunications Conf., p.1-6. [

[100] Wang, J., Elia, N., 2010. Consensus over networks with dynamic channels. Int. J. Syst. Contr. Commun., 2(1): 275-297. [

[101] Wang, L., Han, Z., Lin, Z., 2012a. Formation control of directed multi-agent networks based on complex Laplacian. Proc. IEEE 51st Annual Conf. on Decision and Control, p.5292-5297. [

[102] Wang, L., Han, Z., Lin, Z., , 2012b. Complex Laplacian and pattern formation in multi-agent systems. Proc. 24th Chinese Control and Decision Conf., p.628-633. [

[103] Wang, L., Han, Z., Lin, Z., 2013. Realizability of similar formation and local control of directed multi-agent networks in discrete-time. Proc. IEEE 52nd Annual Conf. on Decision and Control, p.6037-6042. [

[104] Wang, L., Han, Z., Lin, Z., , 2014a. A linear approach to formation control under directed and switching topologies. Proc. IEEE Int. Conf. on Robotics and Automation, p.3595-3600. [

[105] Wang, L., Lin, Z., Fu, M., 2014b. Affine formation of multiagent systems over directed graphs. Proc. IEEE 53rd Annual Conf. on Decision and Control, p.3017-3022. [

[106] Wang, W., Peng, H., 2012. Flocking control with communication noise based on second-order distributed consensus algorithm. Proc. IEEE Power Engineering and Automation Conf., p.1-4. [

[107] Wasserman, S., Faust, K., 1994. Social Network Analysis Methods and Applications. Cambridge University Press, UK.

[108] Wei, J., Fang, H., 2014. Multi-agent consensus with timevarying delays and switching topologies. J. Syst. Eng. Electron., 25(3): 489-495. [

[109] Weiss, G., 1999. Multiagent Systems, a Modern Approach to Distributed Artificial Intelligence. MIT Press, USA.

[110] Wu, W., Chen, T., 2009. Partial synchronization in linearly and symmetrically coupled ordinary differential systems. Phys. D, 238(4): 355-364. [

[111] Wu, W., Zhou, W., Chen, T., 2009. Cluster synchronization of linearly coupled complex networks under pinning control. IEEE Trans. Circ. Syst. I, 56(4): 829-839. [

[112] Xia, W., Cao, M., 2011. Clustering in diffusively coupled networks. Automatica, 47(11): 2395-2405. [

[113] Xiao, L., Boyd, S., 2004. Fast linear iterations for distributed averaging. Syst. Contr. Lett., 53(1): 65-78. [

[114] Xiao, L., Boyd, S., 2006. Optimal scaling of a gradient method for distributed resource allocation. J. Optim. Theory Appl., 129(3): 469-488. [

[115] Xiao, L., Boyd, S., Kim, S., 2007. Distributed average consensus with least-mean-square deviation. J. Parall. Distr. Comput., 67(1): 33-46. [

[116] Xing, H., Mou, Y., Fu, M., , 2015. Distributed bisection method for economic power dispatch in smart grid. IEEE Trans. Power Syst., in press. [

[117] Xu, Y., Han, T., Cai, K., , 2015. A fully distributed approach to resource allocation problem under directed and switching topologies. Proc. 10th Asian Control Conf., in press.

[118] Yang, S., Tan, S., Xu, J., 2013. Consensus based approach for economic dispatch problem in a smart grid. IEEE Trans. Power Syst., 28(4): 4416-4426. [

[119] Yu, J., Wang, L., 2010. Group consensus in multi-agent systems with switching topologies and communication delays. Syst. Contr. Lett., 59(6): 340-348. [

[120] Zhang, H., Chen, J., 2014. Bipartite consensus of linear muliagent systems over signed digraphs: an output feedback control approach. Proc. 19th IFAC World Congress, p.4681-4686. [

[121] Zhang, H., Chen, Z., 2014. Consensus acceleration in a class of predictive networks. IEEE Trans. Neur. Netw. Learn. Syst., 25(10): 1921-1927. [

[122] Zhang, H., Zhai, C., Chen, Z., 2011. A general alignment repulsion algorithm for flocking of multi-agent systems. IEEE Trans. Automat. Contr., 56(2): 430-435. [

[123] Zhong, J., Lin, Z., Chen, Z., , 2014. Cooperative localization using angle-of-arrival information. Proc. 11th IEEE Int. Conf. on Control and Automation, p.19-24. [

[124] Zhu, G., Hu, J., 2014. A distributed continuous-time algorithm for network localization using angle-of-arrival information. Automatica, 50(1): 53-63. [

[125] Zhu, W., Cheng, D., 2010. Leader-following consensus of second-order agents with multiple time-varying delays. Automatica, 46(12): 1994-1999. [