Abstract
In this paper, we study how a self-organized mobile robot flock can be steered toward a desired direction through externally guiding some of its members. Specifically, we propose a behavior by extending a previously developed flocking behavior to steer self-organized flocks in both physical and simulated mobile robots. We quantitatively measure the performance of the proposed behavior under different parameter settings using three metrics, namely, (1) the mutual information metric, adopted from Information Theory, to measure the information shared between the individuals during steering, (2) the accuracy metric from directional statistics to measure the angular deviation of the direction of the flock from the desired direction, and (3) the ratio of the largest aggregate to the whole flock and the ratio of informed individuals remaining with the largest aggregate, as a metric of flock cohesion. We conducted a systematic set of experiments using both physical and simulated robots, analyzed the transient and steady-state characteristics of steered flocking, and evaluate the parameter conditions under which a swarm can be successfully steered. We show that the experimental results are qualitatively in accordance with the ones that were predicted in Couzin et al. model (Nature, 433:513–516, 2005) and relate the quantitative differences to the differences between the models.
Similar content being viewed by others
References
Aldana M, Huepe C (2003) Phase transitions in self-driven many-particle systems and related non-equilibrium models: a network approach. J Statis Phys 112(1/2):135–153
Bonabeau E, Dorigo M, Theraulaz G (ed) (1999) Swarm intelligence from natural to artificial systems, vol 4433. Oxford University Press, USA
Buhl J, Sumpter DJT, Couzin I, Hale J, Despland E, Miller E, Simpson SJ (2006) From disorder to order in marching locusts. Science 312(5778):1402–1406
Camazine S, Deneubourg J-L, Franks NR, Sneyd J, Theraulaz G, Bonabeau E (2001) Self-organization in biological systems. Princeton University Press, New Jersey
Çelikkanat H, Turgut AE, Şahin E (2008) Guiding a robot flock via informed robots. In: Asama H, Kurokawa H, Ota J, Sekiyama K (eds) Proceedings of the 9th international symposium on distributed autonomous robotic systems (DARS 2008). Springer, Berlin, pp 215–225
Couzin ID, Krause J, Franks NR, Levin SA (2005) Effective leadership and decision-making in animal groups on the move. Nature 433:513–516
Şahin E, Spears W (eds) (2005) Swarm robotics workshop: state-of-the-art survey, vol 3342. Springer, Berlin
Şahin E, Winfield A (2008) Special issue: swarm robotics. Swarm Intelligence 2(2–4):69–72
Şahin E, Winfield A, Spears W (eds) (2007) Swarm robotics: second SAB 2006 international workshop, vol 4433. Springer, Berlin
Czirók A, Stanley HE, Vicsek T (1997) Spontaneously ordered motion of self-propelled particles. J Phys A Math Gen 30:1375–1385
Dorigo M, Şahin E (2004) Special issue: swarm robotics. Auton Robots 17(2-3):111–113
Feldman D (2002) A brief introduction to: information theory, excess entropy and computational mechanics. Technical report, Department of Physics, University of California
Grassberger P (1988) Finite sample corrections to entropy and dimension estimates. Phys Lett A 128:369–373
Gregoire G, Chate H, Tu Y (2003) Moving and staying together without a leader. Physica D 181:157–170
Halloy J, Sempo G, Caprari G, Rivault C, Asadpour M, Tache F, Said I, Durier V, Canonge S, Ame JM, Detrain C, Correll N, Martinoli A, Mondada F, Siegwart R, Deneubourg JL (2007) Social integration of robots into groups of cockroaches to control self-organized choices. Science 318:1155–1158
Hayes A, Dormiani-Tabatabaei P (2002) Self-organized flocking with agent failure: off-line optimization and demonstration with real robots. In: Proceedings of the IEEE international conference on robotics and automation. pp 3900–3905
Hemelrijk CK, Kunz H (2005) Density distribution and size sorting in sh schools: an individual-based model. Behav Ecol 16:178–187
Huepe C, Aldana M (2008) New tools for characterizing swarming systems: a comparison of minimal models. Physica A 387:2809–2822
Jacob C, von Mammen S (2007) Swarm grammars: growing dynamic structures in 3d agent spaces. Digit Creativ 18(1):54–64
Jadbabaie A, Lin J, Morse A (2003) Coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE Trans Autom Contr 48(6):988–1001
Kazadi S, Chang J (2008) Hijacking swarms. In: Proceedings of the 11th IASTED international conference on intelligent systems and control. pp 228–234
Kelly I, Keating D (1996) Flocking by the fusion of sonar and active infrared sensors on physical autonomous robots. In: Proceedings of the 3rd international conference on mechatronics and machine vision in practice, vol 1. pp 14–17
Kwong H, Jacob C (2003) Evolutionary exploration of dynamic swarm behaviour. In: Proceedings of the congress on evolutionary computation. pp 662–669
Lien JM, Bayazit OB, Sowell RT, Rodríguez S, Amato NM (2004) Shepherding behaviors. In: Proceedings of the IEEE conference on robotics and automation. pp 4159 – 4164
Lien JM, Rodríguez S, Malric J-P, Amato NM (2005) Shepherding behaviors with multiple shepherds. In: Proceedings of the IEEE conference on robotics and automation. pp 3402–3407
Lungarella M, Pegors T, Bulwinkle D, Sporns O (2005) Methods for quantifying the information structure of sensory and motor data. Neuroinformatics 3(3):243–262
von Mammen S, Jacob C (2008) The spatiality of swarmsquantitative analysis of dynamic interaction networks. In: Proceedings of artificial life. pp 662–669
von Mammen S, Jacob C (2009) Swarming for Games: immersion in complex systems. Springer, Berlin, pp 293–302
Mardia KV (1972) Statistics of directional data. Academic Press, London
Matarić MJ (1994) Interaction and intelligent behavior. Ph.D. thesis, MIT
Mermin ND, Wagner H (1966) Absence of ferromagnetism or antiferromagnetism in one- or two-dimensional isotropic Heisenberg models. Phys Rev Lett 17(22):1133–1136
Correll NMS, Rus D (2008) Social control of herd animals by integration of artificially controlled congeners. In: Proceedings of the 10th international conference on simulation of adaptive behavior, LNAI, vol 5040. Springer, pp 437–447
Nagry M, Daruka I, Vicsek T (2007) New aspects of the continuous phase transition in the scalar noise model (snm) of collective motion. Physica A 373:445–454
Nembrini J (2005) Minimalist coherent swarming of wireless networked autonomous mobile robots. Ph.D. thesis, University of the West of England
Nembrini J, Winfield AFT, Melhuish C (2002) Minimalist coherent swarming of wireless networked autonomous mobile robots. In: Proceedings of the 7th international conference on the simulation of adaptive behavior conference, vol 7. pp 273–382
Olfati-Saber R (2006) Flocking for multi-agent dynamic systems: algorithms and theory. IEEE Trans Autom Contr 51(3):401–420
Olfati-Saber R, Murray R (2004) Consensus problems in networks of agents with switching topology and time-delays. IEEE Trans Autom Contr 49(9):1520–1533
Parunak HVD, Brueckner S (2001) Entropy and self-organization in multi-agent systems. In: Proceedings of the 5th international conference on autonomous agents. pp 124–130
Parunak HVD, Brueckner S, Fleischer M, Odell J (2002) Co-x: defining what agents do together. In: Proceedings of the AAMAS’02, workshop on teamwork and coalition formation. pp 62–69
Reebs SG (2000) Can a minority of informed leaders determine the foraging movements of a fish shoal? Anim Behav 59:403–409
Reynolds C (1987) Flocks, herds and schools: a distributed behavioral model. In: Proceedings of SIGGRAPH’87. ACM Press, pp 25–34
Romey WL (1996) Individual differences make a difference in the trajectories of simulated schools of fish. Ecol Model 92:65–77
Shi H, Wang L, Chu T (2006) Virtual leader approach to coordinated control of multiple mobile agents with asymmetric interactions. Physica D 213:51–65
Sperati V, Trianni V, Nolfi S (2008) Evolving coordinated group behaviours through maximization of mean mutual information. Swarm Intell 2(2–4):73–95
Sporns O, Lungarella M (2006) Evolving coordinated behavior by maximizing information structure. In: Rocha L et al (eds) Artificial life X. MIT Press, Cambridge
Steuer RE, Kurths J, Daub CO, Weise J, Selbig J (2002) The mutual information: detecting and evaluating dependencies between variables. In: Proceedings of the European conference on computational biology. pp 231–240
Seeley TDRA, Morse PKV (1979) The natural history of the flight of honey bee swarms. Psyche 86(2–3):103–113
Tanner HG, Jadbabaie A, Pappas GJ (2003) Stable flocking of mobile agents part i: fixed topology. In: Proceedings of the 42nd IEEE conference on decision and control, vol 2. IEEE Press, New Jersey, pp 2010–2015
Tanner HG, Jadbabaie A, Pappas GJ (2003) Stable flocking of mobile agents part ii: dynamic topology. In: Proceedings of 42nd IEEE conference on decision and control, vol 2. IEEE Press, New Jersey, pp 2016–2021
Toner J, Tu Y (1998) Flocks, herds, and schools: a quantitative theory of flocking. Phys Rev E 58(4):4828–4858
Tononi G, Sporns O, Edelman GM (1994) A measure for brain complexity: relating functional segregation and integration in the nervous system. Proc Nat Acad Sci 91:5033–5037
Turgut AE, Çelikkanat H, Gökçe F, Şahin E (2008) Self-organized flocking in mobile robot swarms. Swarm Intell 2(2–4):97–120
Turgut AE, Çelikkanat H, Gökçe F, Şahin, E (2008) Self-organized flocking with a mobile robot swarm. In: Proceedings of the 7th international conference on autonomous agents and multiagent systems. pp 39–46
Turgut AE, Huepe C, Çelikkanat H, Gökçe F, Şahin E (2008) Modeling phase transition in self-organized mobile robot flocks. In: Proceedings of the sixth international conference on ant colony optimization and swarm intelligence, LNCS, vol 5217. Springer, London, pp 108–119
Vaughan R, Sumpter N, Henderson J, Frost A, Cameraon S (2000) Experiments in automatic flock control. Rob Auton Syst 31:109–117
Vicsek T, Czirók A, Ben-Jacob E, Cohen I, Shochet O (1995) Novel type of phase transition in a system of self-driven particles. Phys Rev Lett 75(6):1226–1229
Ward AJW, Sumpter DJT, Couzin ID, Hart PJB, Krause J (2008) Quorum decision-making facilitates information transfer in fish schools. Proc Nat Acad Sci 105(19):6948–6953
Acknowledgments
This work is funded by TÜBİTAK (Turkish Scientific and Technical Council) through the “KARİYER: Kontrol Edilebilir Robot Oğulları” project with number 104E066. Additionally, Hande Çelikkanat acknowledges the partial support of the TÜBİTAK graduate student fellowship. The simulations have been performed on the High Performance Computing Center of the Department of Computer Engineering, Middle East Technical University.
Author information
Authors and Affiliations
Corresponding author
Appendix
Appendix
Mutual Information: Adopting the notation of Feldman [12] and indicating a discrete random variable with the capital letter X, which can take values \(x \in {\mathcal{X}}\), the information entropy is defined as:
where p(x) is the probability that X will take the value of x. H[X] is also called the marginal entropy of X, since it depends on only the marginal probability of one random variable. The marginal entropy of the random variable X is zero if X always assumes the same value with p(X = x′) = 1 and maximum if X assumes all possible states with equal probability. Having defined the marginal entropy of a single random variable, this definition is easily extended to the joint entropy of two random variables:
as well as the conditional entropy of these two random variables:
where p(x, y) is the joint probability that X will take the value of x and Y will take the value of y, and p(x | y) is the conditional probability that X will take the value of x given that Y takes the value of y. Thus, the conditional entropy is the entropy of X, given that Y is known.
Then, the mutual information MI[X, Y] is defined as:
or equivalently,
When p(x|y) becomes 1, the mutual information MI[X, Y] is maximized to be H[X]. Note that, the value of H[X] depends on the discretization of x. For instance, if the value of random variable x is discretized into 8, then p(x) becomes \({\frac{1}{8}}\) leading to \(H[X] = -8 \cdot {\frac{1}{8}} \cdot \log_{2} {\frac{1}{8}} = 3.\)
Angular Deviation: The angular deviation is calculated as follows [29]. Let θ1...θ n denote a set of unit vectors whose angular deviation is to be calculated. Then, their (normalized) mean vector is the vector from (0, 0) to \((\bar{C}, \bar{S})\), where
Let \(\bar{R} = \sqrt{\bar{S}^2 + \bar{C}^2}\) be the length of this normalized mean vector and \(\bar{x}_0\) be its angle with the x-axis such that:
Then, the angular deviation of these vectors around their normalized mean vector is given by:
This intuitively means that the more aligned the vectors are, i.e, the less the angular deviation is, the longer is the mean vector. On the other hand, if they are scattered around the unit circle in a random manner, then their vector sum results in a shorter mean vector, denoting a greater angular deviation from the mean.
The angular deviation around a specific direction can be calculated as an extension of this formulation by letting α denote the angle of the desired direction with the x-axis. Then
give the components of the mean vector in the desired direction, and
gives the angular deviation around this direction. In the accuracy calculations, we utilize this extended formulation which gives the angular deviation around the desired direction of the flock.
Rights and permissions
About this article
Cite this article
Çelikkanat, H., Şahin, E. Steering self-organized robot flocks through externally guided individuals. Neural Comput & Applic 19, 849–865 (2010). https://doi.org/10.1007/s00521-010-0355-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00521-010-0355-y