Description and composition of bio-inspired design patterns: a complete overview <s> Flocking pattern <s> This paper presents an investigation of flocking by teams of autonomous mobile robots using principles of Swarm Intelligence. First, we present a simple flocking task, and we describe a leaderless distributed flocking algorithm (LD) that is more conducive to implementation on embodied agents than the established algorithms used in computer animation. Next, we use an embodied simulator and reinforcement learning techniques to optimize LD performance under different conditions, showing that this method can be used not only to improve performance but also to gain insight into which algorithm components contribute most to system behavior. Finally, we demonstrate that a group of real robots executing LD with emulated sensors can successfully flock (even in the presence of individual agent failure) and that systematic characterization (and therefore optimization) of real robot flocking performance is achievable. <s> BIB001 </s> Description and composition of bio-inspired design patterns: a complete overview <s> Flocking pattern <s> Vicsek et al. proposed (1995) a simple but compelling discrete-time model of n autonomous agents {i.e., points or particles} all moving in the plane with the same speed but with different headings. Each agent's heading is updated using a local rule based on the average of its own heading plus the headings of its "neighbors". In their paper, Vicsek et al. provide simulation results which demonstrate that the nearest neighbor rule they are studying can cause all agents to eventually move in the same direction despite the absence of centralized coordination and despite the fact that each agent's set of nearest neighbors change with time as the system evolves. This paper provides a theoretical explanation for this observed behavior. In addition, convergence results are derived for several other similarly inspired models. The Vicsek model proves to be a graphic example of a switched linear system which is stable, but for which there does not exist a common quadratic Lyapunov function. <s> BIB002 </s> Description and composition of bio-inspired design patterns: a complete overview <s> Flocking pattern <s> There is little or no guidance to systematically design a self-organising emergent solution that achieves the desired macroscopic behaviour. This paper describes decentralised coordination mechanisms such as gradient fields as design patterns, similar to patterns used in mainstream software engineering. As a consequence, a structured consolidation of best practice in using each coordination mechanism becomes available to guide engineers in applying them, and to directly decide which mechanisms are promising to solve a certain problem. As such, self-organising emergent solutions can be engineered more systematically, which is illustrated in a packet delivery service application. <s> BIB003 </s> Description and composition of bio-inspired design patterns: a complete overview <s> Flocking pattern <s> As the MAV (Micro or Miniature Aerial Vehicles) field matures, we expect to see that the platform's degree of autonomy, the information exchange, and the coordination with other manned and unmanned actors, will become at least as crucial as its aerodynamic design. The project described in this paper explores some aspects of a particularly exciting possible avenue of development: an autonomous swarm of MAVs which exploits its inherent reliability (through redundancy), and its ability to exchange information among the members, in order to cope with a dynamically changing environment and achieve its mission. We describe the successful realization of a prototype experimental platform weighing only 75g, and outline a strategy for the automatic design of a suitable controller. <s> BIB004
Flocking is a kind of self-organising motion coordination behaviour of a herd of animals of similar size and body orientation, often moving en masse or migrating in the same direction and with a common group objective. The Flocking Pattern is able to control dynamic pattern formations and move the agents over the environment while keeping the formation pattern, interconnections between them and avoiding collisions. Different disciplines have been interested in the emergent behaviour of flocking, swarming, schooling and herding. Several examples can be found in (Olfati-Sabe 2006) . The forces that drive the flocking behaviour were proposed in 1986 by Craig W. Reynolds (Reynold 1987) . They are known as Reynolds rules: (1) cohesion (flock centering), (2) separation (obstacle avoidance and crowd avoidance) and (3) alignment (velocity and direction matching). Cohesion captures the intuition that individuals try to keep close to nearby flockmates because they always try to move towards the flocking center. Separation pursues collision avoidance with nearby flockmates and other obstacles. Alignment is related to the ability to move the flock with all the individuals at the same speed. Flocking is typically used for motion coordination of large scale MAS, mainly 2D or 3D simulations. Problem: dynamic motion coordination and pattern formation of swarms. Solution: the Flocking Pattern provides a set of rules for moving groups of agents over the environment while keeping the formation and interconnections between them. Inspiration: this pattern is inspired by the behaviour of a group of birds when they are foraging or flying and by schools of fish when they are avoiding a predator attack or foraging. For example, when a school of fish is under a predator attack, the movement of the first fish sensing the predator presence, produces a fast movement alerting the other fishes by waves of pressure sent through the water. The schools of fish then changes its formation for avoiding the predator attack, recovering the initial formation after the attack. It is similar for obstacle avoidance. Forces: parameters such as, avoidance distance, maximum velocity and maximum acceleration must be tuned to achieve the desired motion coordination. Entities-dynamic-environment: the entities participating in the Flocking Pattern are only Agents using direct communication. Basically, agents sense the position of their neighbours and keep a constant desired distance. When the distance changes due to external perturbations, each agent responds in a decentralised way to control the distance and to recover the original formation pattern. The transition rule for the Flocking Pattern is formalised in Transition Rule (4), where the specific instance of q for computing the new position is described in the following. Implementation: details about the algorithm and theory can be found in (Olfati-Sabe 2006) . Here we present some basic concepts about the algorithm and the implementation. Analogously to the free-flocking algorithm presented in (OlfatiSabe 2006), each agent's motion is controlled by Eq. (14). Figures 18 represents two agents that coordinate their behaviour according to the first term (cohesion and separation): (a) agents are attracted to each other, because they are situated in an attracting zone; (b) agents repel each other because they are too close; finally, in (c) agents are in the neutral zone where the term becomes zero. When all the agents of the flocks are situated in the neutral area, they form a stress-free structure. Analogously to the Repulsion The only difference is that the Flocking Pattern applies more rules, not only repulsion. Known uses: the first application of the Flocking Pattern was modelling animal behaviour for movies. Specifically, it was used to generate realistic crowds moves. Flocking has also been used to control the behaviour of Unmanned Air Vehicles (UAVs) BIB003 , Autonomous mobile robots BIB001 BIB002 , Micro or Miniature Aerial Vehicles (MAV) BIB004 and Mobile Sensor Networks . Consequences: flocking tries to generalise the behaviour of flocking, independently of individuals (birds, penguins, fish, etc.). Its behaviour does not depend on the methods used for the generation of agents' trajectories. The Flocking Pattern provides robustness and self-healing properties when faced with agents' failures and communication problems. Related Patterns: the Flocking Pattern extends the Repulsion Pattern (Sect. 5.1.4). In fact, repulsion can be seen as a simplification of the Flocking Pattern where only the repulsion vector is taken into account for calculating the next position.