Description and composition of bio-inspired design patterns: a complete overview <s> Repulsion pattern <s> We describe a decentralized algorithm for coordinating a swarm of identically-programmed mobile agents to spatially self-aggregate into arbitrary shapes using only local interactions. Our approach, called SHAPEBUGS, generates a consensus coordinate system by agents continually performing local trilaterations, and achieves shape formation by simultaneously allowing agents to disperse within the defined 2D shape using a Contained Gas Model. This approach has several novel features (1) agents can easily aggregate into arbitrary user-specified shapes, using a formation process that is independent of the number of agents (2) the system automatically adapts to influx and death of agents, as well as accidental displacement. We show that the consensus coordinate system is robust and provides reasonable accuracy in the face of significant sensor and movement error. <s> BIB001 </s> Description and composition of bio-inspired design patterns: a complete overview <s> Repulsion pattern <s> Dealing with imprecise information is a common characteristic in real-world problems. Specifically, when the source of the information are physical sensors, a level of noise in the evaluation has to be assumed. Particle Swarm Optimization is a technique that presented a good behavior when dealing with noisy fitness functions. Nevertheless, the problem is still open. In this paper we propose the use of the evaporation mechanism for managing with dynamic multi-modal optimization problems that are subject to noisy fitness functions. We will show how the evaporation mechanism does not require the detection of environment changes and how can be used for improving the performance of PSO algorithms working in noisy environments. <s> BIB002
The Repulsion Pattern is a basic pattern for motion coordination in large scale MAS. The Repulsion Pattern enables the agents to get a uniform distribution in a specific area or to avoid collision among them. Moreover, using repulsion, agents can adapt their position when the desired area changes or when some nodes disappear. Alias: none to our knowledge. Problem: agents' movements have to be coordinated in a decentralised manner in order to achieve a uniform distribution and to avoid collisions among them. Solution: the Repulsion Pattern creates a repulsion vector that guides agents to move from regions with high concentrations of agents to regions with lower concentrations. Thus, after few iterations agents reach a more uniform distribution in the environment. Inspiration: the repulsion mechanism appears in a wide range of biological self-organising processes, such as the diffusion process in physical science, the flocking of birds or schools of fish. For instance, the diffusion process describes the spread of particles through random motion from regions of higher concentration to regions of lower concentration. Figure 8 illustrates the different steps of the diffusion process. First, a concentration of ink is deposited in the glass of water, step (a). We observe the initial state where the particles concentrate in one corner of the glass. The corner with the particles, therefore, contains a higher concentration of ink's particles. Second, the particles begin to move in the diffusion process, from regions of higher concentration to regions of lower concentration, step (b). The closer the particles are to the corner, the higher the concentration, thus creating a so called concentration gradient. This gradient is provided by the difference in concentration between neighbouring particles. Finally, we observe how the diffusion process has randomly moved around all the particles inside the water, producing a uniform random distribution of the particles. At this point the different ink's concentrations disappear. Inside a container, the particles reach a uniform distribution after the diffusion process. However, in an open space, the diffusion process spreads the particles until the concentration is so low that it is considered negligible. As Fig. 8 shows, the diffusion process finishes when the particles reach a uniform distribution, i.e. when the concentration gradient becomes zero. The repulsion mechanism is also alternatively presented as inspired by the gas theory BIB001 ). In the case of gas theory, the time to reach a uniform concentration is shorter than in the case of the diffusion process. Forces: the main parameters involved in the Repulsion Pattern are the repulsion frequency (i.e. how frequent the repulsion is applied) and the repulsion radius (i.e. how strong the repulsion is). A high repulsion frequency involves a faster spreading of the agents and a faster adaptation when the desired formation (or area) changes. However, it increases the number of messages, because the Repulsion Pattern requires information about the position of neighbours. The repulsion radius should be limited to the communication range of the agents, because it makes not sense to move to one location where the concentration of agents is unknown and also because the agent can not jump to a host that is not in the communication radius. Thus, the movement of one agent in each repulsion step must be restricted to its communication range. Entities-Dynamic-Environment: repulsion can be applied in systems where the agents are residing in mobile hosts (e.g. robotic swarms) or in software agents that are moving freely in a network composed of (stationary or not) hosts. In both cases the dynamics between them is the same. When repulsion is applied, the agent that executes the repulsion sends a position request to all its neighbouring agents. After the agent receives the positions of neighbouring hosts, it calculates the desired position and moves to that position. When the environment is not continuous, as in the mobile agents case, the agent moves to the host closest to the desired position. In this case the position request must be sent also to the hosts. To apply the Repulsion Pattern, each agent should know its position and its neighbourhood. The Repulsion Pattern may apply also to information that might need to be spatially distributed. Transition Rule (4) precises the repulsion behaviour: repulsion :: hL; Ci; hL 1 ; C 1 i; . . .; hL n ; C n iÀ! r ev hL 0 ; Ci; hL 1 ; C 1 i; . . .; hL n ; C n i where L 0 ¼ qðfhL; Ci; hL 1 ; C 1 i; . . .; hL n ; C n igÞ ð4Þ A function qðfhL; Ci; hL 1 ; C 1 i; . . .; hL n ; C n igÞ is given for computing the new location of the information or of the agent according to the spatial distribution of the neighbours and to its actual position. An example of such a function follows. Function q depends also on the values of attributes contained in C, for instance the concentration of particles in each location. Implementation: one possible implementation to reach a uniform distribution, involves a transition rule that calculates a repulsion vector between the particles that is inversely proportional to the distance between them. The transition rule is then implemented as follows: Let R be the repulsive radius; d i the distance between a given node and neighbouring node i; p the position of the given node and p i the position of the neighbouring node i. Then, the position p t?1 of the agent at time t ? 1 and the movement vector m are given by: Figure 9 shows how agent 1 is repelled by agents 2 and 3 when it applies the repulsion mechanism. In Fig. 9a agent 1 executes Eq. (6) to create the repulsion vector. In Fig. 9b agent 1 moves by following the repulsion vector. Figure 10a shows the behaviour of an agent that is executing the Repulsion Pattern. At the beginning the agents send a position request to all the agents in the communication range. When positions are received, the repulsion vector is calculated following Eq. (6) and then, the new desired position by using Eq. (5). At this step if the system is composed of a swarm of robots, the robot that is executing the Repulsion Pattern would move to the desired position. If the Repulsion Pattern is executing using a mobile agents technology, the agent would move to the closest node to the desired position. Figure 10b shows the interaction between the agent that is executing the Repulsion Pattern, the host where the agent is running and their neighbouring hosts. Known uses: repulsion has not been proposed as a pattern so far. Several applications have used the repulsion mechanism, such as swarm robotics for pattern formation BIB001 , where the system achieves shape formation by simultaneously allowing agents to disperse within a defined 2D shape. In Particle Swarm Optimisation (PSO), Repulsion coordinates the position of explorer particles in a multi-swarm approach BIB002 . In ), the repulsion is used to coordinate the position of pieces of information, ensuring the accessibility to this information in a specific area of interest using the minimum possible memory. Consequences: repulsion does not involve replication, i.e. during the repulsion process no new agents are created, contrarily to spreading. Repulsion is a continuous process that produces a uniform distribution of the agents in the system. Even when the agents are uniformly distributed in the environment, the repulsion mechanism continues working, producing a self-adaptation process when the number of agents changes (i.e. self-repairing formation in swarms of robots) or environmental changes occur. Related Patterns: the Repulsion Pattern is used in the Flocking Pattern (Sect. 5.3.5). 