Collective motions and formations under pursuit strategies on directed acyclic graphs. (English) Zbl 1213.93073

Summary: A novel pursuit-based approach is presented to investigate collective motions and formations of a large number of agents with both single-integrator kinematics and double-integrator dynamics on Directed Acyclic Graphs (DAGs). Each agent pursues its neighbors according to a directed acyclic graph, in which the agents without neighbors are leaders. Based on signal flow graph analysis and Mason’s rule, necessary and sufficient conditions are derived for BIBO stability of resulting pursuit systems. Moreover, achievable collective motions and formations are analyzed by adjusting a set of control parameters when leaders keep stationary, perform uniform rectilinear motions, and perform uniform circular motions. Finally, simulations are provided for achieving a static formation and mimicking several complex collective behaviors observed in nature, such as V-formation, vortex motions, and tornado motions.


93C05 Linear systems in control theory
93A14 Decentralized systems
49N75 Pursuit and evasion games
94C15 Applications of graph theory to circuits and networks
Full Text: DOI


[1] Bai, H.; Arcak, M.; Wen, J., Adaptive design for reference velocity recovery in motion coordination, Systems & control letters, 57, 8, 602-610, (2008) · Zbl 1140.93397
[2] Bruckstein, A., Cohen, N., & Efrat, A. (1991). Ants, crickets and frogs in cyclic pursuit. Technion, Haifa, Israel, Center Intell. Syst., Israel Inst. Technol., Tech. Rep 9105
[3] Chen, C., Linear system theory and design, (1984), Saunders College Publishing Philadelphia, PA, USA
[4] Chen, H.; Leung, K., Rotating states of self-propelling particles in two dimensions, Physical review E, 73, 056107, (2006)
[5] Chen, S.; Tsai, J., A new tabular form for determining root distribution of a complexpolynomial with respect to the imaginary axis, IEEE transactions on automatic control, 38, 10, 1536-1541, (1993) · Zbl 0790.93053
[6] Chu, T.; Wang, L.; Chen, T.; Mu, S., Complex emergent dynamics of anisotropic swarms: convergence vs oscillation, Chaos, solitons and fractals, 30, 4, 875-885, (2006) · Zbl 1142.34346
[7] Couzin, I.; Krause, J., Self-organization and collective behavior in vertebrates, Advances in the study of behavior, 32, 1-75, (2003)
[8] Couzin, I.; Krause, J.; Franks, N.; Levin, S., Effective leadership and decision-making in animal groups on the move, Nature, 433, 7025, 513-516, (2005)
[9] Das, A.; Fierro, R.; Kumar, V.; Ostrowski, J.; Spletzer, J.; Taylor, C., A vision-based formation control framework, IEEE transactions on robotics and automation, 18, 5, 813-825, (2002)
[10] Ding, W., Yan, G., & Lin, Z. (2009). Formations on two-layer pursuit systems. In Proceedings of IEEE international conference on robotics and automation (pp. 3496-3501)
[11] Dorato, P.; Lepschy, A.; Viaro, U., Some comments on steady-state and asymptotic responses, IEEE transactions on education, 37, 3, 264-268, (1994)
[12] Gönci, B.; Nagy, M.; Vicsek, T., Phase transition in the scalar noise model of collective motion in three dimensions, The European physical journal-special topics, 157, 1, 53-59, (2008)
[13] Jadbabaie, A.; Lin, J.; Morse, A., Coordination of groups of mobile autonomous agents using nearest neighbor rules, IEEE transactions on automatic control, 48, 6, 988-1001, (2003) · Zbl 1364.93514
[14] Krause, J.; Ruxton, G., Living in groups, (2002), Oxford University Press
[15] Lawton, J.; Beard, R.; Young, B.; Syst, R.; Tucson, A., A decentralized approach to formation maneuvers, IEEE transactions on robotics and automation, 19, 6, 933-941, (2003)
[16] Lin, Z., Distributed control and analysis of coupled cell systems, (2008), VDM-Verlag
[17] Lin, Z.; Broucke, M.; Francis, B., Local control strategies for groups of mobile autonomous agents, IEEE transactions on automatic control, 49, 4, 622-629, (2004) · Zbl 1365.93208
[18] Marshall, J.; Broucke, M.; Francis, B., Formations of vehicles in cyclic pursuit, IEEE transactions on automatic control, 49, 11, 1963-1974, (2004) · Zbl 1366.91027
[19] Mason, S.J., Feedback theory: further properties of signal flow graphs, Proceedings of the IRE, 44, 7, 920-926, (1956)
[20] Olfati-Saber, R., Flocking for multi-agent dynamic systems: algorithms and theory, IEEE transactions on automatic control, 51, 3, 401-420, (2006) · Zbl 1366.93391
[21] Paley, D.; Leonard, N.; Sepulchre, R.; Grünbaum, D.; Parrish, J., Oscillator models and collective motion, IEEE control systems magazine, 27, 4, 89-105, (2007)
[22] Parrish, J.; Viscido, S.; Grunbaum, D., Self-organized fish schools: an examination of emergent properties, Biological bulletin, 202, 3, 296-305, (2002)
[23] Pavone, M.; Frazzoli, E., Decentralized policies for geometric pattern formation and path coverage, Journal of dynamic systems, measurement, and control, 129, 5, 633-643, (2007)
[24] Ren, W., Consensus strategies for cooperative control of vehicle formations, IET control theory & applications, 1, 2, 505-512, (2007)
[25] Ren, W., Multi-vehicle consensus with a time-varying reference state, Systems & control letters, 56, 7-8, 474-483, (2007) · Zbl 1157.90459
[26] Ren, W. (2008a). Collective motion from consensus with cartesian coordinate coupling-part I: Single-integrator kinematics. In Proceedings of the 47th IEEE conference on decision and control (pp. 1006-1011)
[27] Ren, W. (2008b). Collective motion from consensus with cartesian coordinate coupling-part II: Double-integrator dynamics. In Proceedings of the 47th IEEE conference on decision and control (pp. 1012-1017)
[28] Sepulchre, R.; Paley, D.; Leonard, N., Stabilization of planar collective motion with limited communication, IEEE transactions on automatic control, 53, 3, 706-719, (2008) · Zbl 1367.93145
[29] Shi, H.; Wang, L.; Chu, T., Virtual leader approach to coordinated control of multiple mobile agents with asymmetric interactions, Physica D: nonlinear phenomena, 213, 1, 51-65, (2006) · Zbl 1131.93354
[30] Shi, H., Wang, L., Chu, T., & Xu, M. (2007). Tracking control for groups of mobile agents. In Proceedings of American Control Conference (pp. 3265-3270)
[31] Sinha, A.; Ghose, D., Generalization of nonlinear cyclic pursuit, Automatica, 43, 11, 1954-1960, (2007) · Zbl 1293.91023
[32] Sumpter, D., The principles of collective animal behaviour, Philosophical transactions of the royal society B: biological sciences, 361, 1465, 5-22, (2006)
[33] Sumpter, D.; Buhl, J.; Biro, D.; Couzin, I., Information transfer in moving animal groups, Theory in biosciences, 127, 2, 177-186, (2008)
[34] Tanner, H.; Jadbabaie, A.; Pappas, G., Flocking in fixed and switching networks, IEEE transactions on automatic control, 52, 5, 863-868, (2007) · Zbl 1366.93414
[35] Tanner, H.; Pappas, G.; Kumar, V., Leader-to-formation stability, IEEE transactions on robotics and automation, 20, 3, 443-455, (2004)
[36] Vicsek, T.; Czirók, A.; Ben-Jacob, E.; Cohen, I.; Shochet, O., Novel type of phase transition in a system of self-driven particles, Physical review letters, 75, 6, 1226-1229, (1995)
[37] Wang, P. (1989). Navigation strategies for multiple autonomous mobile robots moving in formation. In Proceedings of IEEE/RSJ International Workshop on Intelligent Robots and Systems (pp. 486-493)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.