Monday 23 April 2012

A CLASSIFICATION SCHEME FOR SWARMING

...... birds do it, bees do it. Even educated fleas do it ..... oh yes ! ... they all form swarms. The sense of collectivism runs deep into insects, fishes, animals and human beings. The collective exhibits traits which are not present in the individual. 

Anthropomorphism of such collective intelligence into the mobile robots domain has been  the motivator for swam robotics. The central idea is forming distinguishable flocks of mobile robots. As Çelikkanat etal. puts it, "... aims to develop self-organization in large groups of robots with no centralized control while putting emphasis on flexibility, robustness and scalability ..."

The earliest work on swarm robotics was by Mataric. Later research into animal robot interaction by Vaughan, Henderson, Halloy, Bonabeau etc; into particle swarms by Vicsek and philosophical insights and arguments by Reynolds, Dorigo and Şahin structured the discipline to its current form. 

Fig.1. Mobile robot flocks, experiments by Mataric
Fig.2. Sheepdog project by Cameron and Vaughan
Fig.3. Experiments by Halloy etal.
In mobile robot context, the terms flocking and swarming are often used synonymously. Swarm may be structured by various control paradigms, some well known scenarios are; 
  1. Same pose - similar angular orientations will clearly distinguish a swarm
  2. Goal driven - similar destination/intentions will implicitly form swarm. Such can also be seen in, foraging for food and escaping from the same predator/adversary - 'follow the leader' or 'follow landmarks' can be seen to be an extension of this idea wherein the goal is dynamic.
Like these there are very many ways to form flocks, it is worth a note that agents with similar velocity or similar position do not reflect a control paradigm and do not necessarily form flocks.
The above calls for a classification of swarms, which would be based on a behaviour based approach and would aid in developing a pedagogy for studying swarms. Such an ontology is provided by Turgut etal., swarming is attributed as an vector like addition of behaviours much in the spirit of Brooks and Arkin. Turgut defines f as the flocking control vector;


where p is the proximal control vector, that encodes attraction/repulsion roles, a is the alignment control vector and g is the goal direction vector. While α, β and γ are arbitrary constants.

Proximal control (p) is manifestation of the idea that the agents should come close enough to form a swarm but not too close to crash into each other, this level of control is chosen as the lowest level in order to form the swarm and maintain it. Couzin etal. illustrates this notion with a zone model.
Fig.4. Zones model as suggested by Couzin etal.
Angular alignment (a) is a popular tool for flock formation, aligning the agents with a common heading angle ensures a common trait across the group. However a swarm structured on angular alignment without proximal control, the agents may exhibit a collision prone Brownian motion like behaviour. 

Goal directedness (g) is not a behaviour exhibited by swarms, however for researches as those by Couzin, Turgut and Ferrante this serves to incorporate informed agents, which whence would implicitly guide the swarm to its goal.  

This superposition of 3 control vectors to yield a flocking control vector can be seen an extension of layered control as suggested by Brooks in subsumption architecture. 

Fig.5. Layered control for swarming
Thus, with Turgut's flocking control vector; 
  1. Same angular alignment : f = a but probably there will be oodles of collisions !!!! thus a better option may be, f = p + a 
  2. Goal driven : f = g which is not very realistic, thus f = p + g 
Scenarios of  f = p + a + g, will be seen in effect in a swarm formed by angular alignment, which also has informed agents equipped a sense of goal directedness.

Fig.6. The Nerd Herd by Mataric
REFERENCES
  1. Maja J Matarić, "Interaction and Intelligent Behavior", MIT EECS PhD Thesis, May 1994, MIT AI Lab Tech Report AITR-1495,Aug 1994.
  2. Richard T. Vaughan, "Experiments in Automatic Flock Control", PhD thesis, University of Oxford, 1999.
  3. Ali Emre Turgut, "Self-organized Flocking with a Mobile Robot Swarm", PhD thesis, Middle Eastern Technical University, 2008
  4. Halloy, J., Sempo, G., Caprari, G., Rivault, C., Asadpour, M., Tache, F., Said, I., Durier, V., Canonge, S., Ame, J.M., Detrain, C., Correll, N., Martinoli, A., Mondada, F., Siegwart, R. & Deneubourg, J.L. 2007.  Social integration of robots into groups of cockroaches to control self-organized choices. Science 318: 1155-1158.
  5. Turgut, A. E., Çelikkanat, H., Gökçe, F., & Şahin, E. (2008). Self-organized flocking in mobile robot swarms. Swarm Intelligence, 2(2-4), 97-120. International Foundation for Autonomous Agents and Multiagent Systems.
  6. Çelikkanat, H., Turgut, A. E., & Sahin, E. (2008). Guiding a robot flock via informed robots. Distributed Autonomous Robotic Systems DARS 2008 (p. 215–225). Springer-Verlag.