Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

An important goal of collective robotics (Dudek et al. 1996; Cao et al. 1997; Dorigo and Sahin 2004; Dorigo et al. 2004) is the development of multi-robot systems capable of accomplishing collective tasks without centralized coordination (Kube and Zhang 1993; Holland and Melhuish 1999; Ijspeert et al. 2001; Quinn et al. 2003). From an engineering point of view, decentralized multi-robot systems have several advantages vs. centralized ones in some tasks. For example, they are more robust with respect to the failure of some of their composing robots, do not require a control system or robot with sophisticated computational capabilities to manage the centralized control (Kube and Bonabeau 2000), have a high scalability with respect to the whole system’s size (Baldassarre et al. 2006, 2007a), and tend to require simpler robots due to the low requirements of communication as they often can rely upon implicit coordination (Beckers et al. 1994; Trianni et al. 2006).

Decentralized coordination is usually based on self-organizing principles. Very often research on decentralized multi-robot systems makes a general claim on the presence of these principles underlying the success of the studied systems, but it does not conduct a detailed analysis of which specific principles are at work, nor it attempts to measure their effects in terms of the evolution of the system’s organization in time or to analyze the robustness of its operation versus noise (e.g. see Holland and Melhuish 1999; Krieger et al. 2000; Kube and Bonabeau 2000; Quinn et al. 2003). This paper studies some of these issues in a multi-robot system presented in detail elsewhere (Baldassarre et al. 2003, 2006, 2007a, 2007b). This system is formed by robots that are physically connected and have to coordinate their direction of motion to explore an open arena without relying on a centralized coordination. The robots are controlled by an identical neural network whose weights are evolved through a genetic algorithm. Through this algorithm the system develops the capacity to solve the task on the basis of self-organizing principles. The goal of this paper is to present some preliminary results that show how such principles lead the organization of the system, measured through a suitable index based on Boltzmann entropy, to arise in a quite abrupt way if the noise/signal ratio related to the signal that allows the robots to coordinate is slowly decreased. With this respect, the paper argues, on the basis of theoretical arguments and experimental evidence, that such sudden emergence of organization shares some properties with the phase transitions exhibited by some physical system studied in physics (Anderson 1997).

The rest of the paper is organized as follows. Section 7.2 presents a qualitative description of the mechanisms that are usually behind self-organization and introduces an index, based on Boltzmann entropy, that can be used to measure the synchronic level of order of a system composed of many dynamical parts. Section 7.3 illustrates the robots forming the multi-robot system considered here, the collective task tackled with it, the neural controller of the robots, and the genetic algorithm used to evolve it. Section 7.4 analyzes the behavior of the single robots developed by the genetic algorithm, and the effects it has at the collective level. Section 7.5 uses the entropy index to show that, when the noise/signal ratio related to the signal used by the robots to coordinate is slowly decreased, the level of order of the robotic system behaves as some global organization parameters observed in phase transitions of some physical systems. Finally, Sect. 7.6 draws the conclusions.

2 Mechanisms of Self-Organization, Phase Transitions, and Indexes to Measure the Organization Level of Collective Systems

Prokopenko et al. (2009) (see also Chap. 1 Prokopenko 2008) suggest that self-organization is characterized by three features: (a) it causes the parts forming a collective system to acquire global coordination; (b) this coordination is caused by the local interactions and information exchange between the parts composing the system and not by a centralized ordering mechanism; (c) the system passes from less organized states to more organized states. This section first tackles points (a) and (b) from a qualitative perspective, by presenting three basic mechanisms that usually underlie self-organization. Then it presents an index based on Boltzmann entropy that can be used to measure the level of order of a collective system at a given instant of time. This index can be used, as illustrated in the succeeding sections, to measure the level of organization of a multi-robot system under the action of self-organizing processes and hence to study point (c). Finally the section presents some theoretical arguments in favor of the hypothesis for which in some cases the dynamics of order exhibited by self-organizing multi-robot systems, as the one considered here, might have the features of phase transitions studied in physics. These arguments are supported by the experimental results presented in Sect. 7.5.

2.1 Qualitative Mechanisms of Self-Organization

Self-organizing processes regard systems composed of several and usually similar components. Self-organizing processes usually (always?) rely upon three basic principles (Camazine et al. 2001): (a) random fluctuations; (b) positive feedback; (c) negative feedback. These principles are now illustrated in detail.

The elements composing self-organizing systems are usually dynamic in the sense that they can assume one state among a certain number of possible states at each time step, and pass from state to state in time. Fully disorganized systems are those where each component passes from state to state in a random fashion. A typical feature of such systems is that the distribution of the components over the possible states tends to be uniform, that is symmetric (e.g., a school of fish randomly swimming in an aquarium tend to have a uniform distribution in the aquarium’s water).

The symmetry of a collective system formed by components driven by random dynamics tends to be imperfect in the sense that it tends to have random fluctuations in time due to noise (e.g., there are some areas of the aquarium with a slightly higher density of fish). Now consider the possibility that each component of the system does not move (only) randomly, but tends to assume the states assumed by some other components of the system, that is it individually follows a conformist rule of the kind “I do what you do” (e.g., fish move to portions of space where other fish are located, so as to minimize the chance of being found alone by predators). In this condition, it might happen that some random fluctuations are amplified: indeed, the larger the number of components that assume a certain state vs. other states, the more intensely the remaining components will tend to imitate their state, so causing an exponential avalanche effect with a consequent symmetry break of the initial uniform distribution (e.g., the fish tend to cluster and form a whole school). The process that leads to this amplification is called positive feedback. In all real systems, the action of positive feedback tends to be counterbalanced by negative feedback. The latter might assume the form of an active process (e.g., the fish tend to cluster to avoid predators, but they also tend to keep at a certain minimal distance to avoid collisions) or a passive process (e.g., all fish have converged to the same zone in space) so the process of convergence stops. Starting from an initial uniform distribution, and after a first exponential convergence of the elements of the system to similar states due to positive feedback, negative feedback will start to slow down the process of convergence. With this respect, negative feedback tends to operate with a strength positively related to the number of elements that have already converged to the same states (e.g., to avoid collisions the fish “repulsion” behavior might be implemented with more vigor in space areas with higher densities of conspecifics as such densities correspond to smaller distances and higher chances of collision). For this reason negative feedback usually increases to levels that fully counterbalance the effect of positive feedback. At this point usually the system’s overall state tends to reach equilibrium (e.g., the density of the fish school remains within a certain range; for examples of simulations of flocks, herds and schools of animals, see the seminal paper of Reynolds (1987), and the literature that followed it linked in the web page http://www.red3d.com/cwr/boids/).

2.2 An Index to Measure the Synchronous Level of Organization of Collective Systems Based on Boltzmann Entropy

The index used to measure the level of order of the group of robots studied here is based on Boltzmann entropy. Note that the index can be used to measure the level of organization of a collective system independently of the fact that such organization is the result of the action of self-organizing or of centralized coordination mechanisms. Boltzmann entropy has been proposed in mechanical statistics to measure the level of disorder that characterizes a system formed by a set of N gas molecules that occupy a given portion of space. This portion of space is divided into an arbitrary number C of cells each having a constant volume (in general the number of cells will influence the outcome of the application of the index, but, as we will see, the index can be suitably normalized to avoid this problem). The index is based on the assumption that the elements composing the system move randomly. This implies that at any time step an element can occupy any cell with a constant probability 1/C (the cell occupied by the element will constitute the element state). To give an example of this, consider the case of the robotic system studied here. This system is composed of N=40 robots. Each robot can assume a given direction of motion ranging over a 1D closed space that ranges over [0∘,360∘] degrees. If this space is divided into C=8 cells of constant size, at each time step the probability that an element occupies a given cell is equal to 1/8.

The computation of the index is based on the so called microstates and macrostates of the system. A microstate of the system corresponds to all individual states of the elements in a given time step. For example, in a system with N=2 and C=2, the microstate is the vector (c 1,c 2) where c n is the cell occupied by the element n. Note that the microstate is a vector and not a simple set, that is the order of the c n states of the elements is relevant: this is a consequence of the fact that the identity of the elements is assumed to be distinguishable. So, for example, given a system with N=2 and C=2, the microstate where the first element occupies the first cell and the second element occupies the second cell is different from the microstate where the first element occupies the second cell and the second element occupies the first cell, even if in both cases the system has one element in the first cell and one element in the second cell. As each element can be in one of C possible different states, the number of different possible microstates is C N.

Indicating with N i the number of elements in cell i, a macrostate of the system is defined as the distribution (N 1,N 2,…,N i ,…,N C ) of the elements over the cells, without considering the identity of the elements. An example of distribution for the system with N=2 and C=2 is (0,2), this meaning that there are zero elements in the first cell and two elements in the second cell. Each macrostate is (usually) composed of several possible microstates as the distribution of elements over the cells that correspond to it can be obtained in different ways. For example, in the N=2,C=2 system, the macrostate (1,1) with one element in each cell is composed of two microstates, that is (1,2) and (2,1). The other two macrostates (2,0) and (0,2), respectively with both elements in the first and the second cell, are each composed of only one microstate each, respectively (1,1) and (2,2).

Boltzmann entropy E m refers to the macrostate m of the system at a given time step and is defined as follows:

$$ E_{m} = k \ln[w_{m}] $$
(7.1)

where w m is the number of microstates of m, ln[⋅] is the natural logarithm and k is a scaling constant.

As at any time-step the probability of having any microstate is constant and equal to 1/C N. The probability that the system is in a given macrostate is proportional to the number of microstates that compose it: this probability is equal to w m /C N. Now consider the possibility that an ordering mechanism (e.g., a flow of energy that goes trough the system) starts to operate on the elements of the system previously subject only to noise. This mechanism is “ordering” in the sense that it drives the system towards macrostates composed of fewer microstates, so it operates against the noise, that is against the evolution that the system would undergo if only driven by randomness. The important point for Boltzmann entropy is that as the elements of the system wander across the different states due to noise, and hence the system wanders across the different corresponding microstates, at a given time step the system has a high probability of being in macrostates that are formed by many microstates vs. macrostates that are formed by few microstates. As Boltzmann entropy is positively related to the number of microstates that compose the macrostate of the system, it can be considered a measure of the disorder of the system caused by the random forces acting on its composing elements and operating against the ordering mechanisms eventually existing within it. This also implies that Boltzmann entropy can be used as an index to detect the presence and level of effectiveness of ordering mechanisms operating in the system: the lower the value of the index, the stronger the effectiveness of such mechanisms.

Notice that highly disordered macrostates correspond to situations where the elements of the system tend to be more equally distributed over the cells (these are macrostates composed by many microstates), hence to situations where the system is highly symmetric, whereas ordered macrostates correspond to situations where the system is asymmetric, for example macrostates where the system’s elements gather in few cells (these are macrostates composed by relatively few microstates). With this respect, ordering mechanisms operating on the system tend to lead it from symmetric to asymmetric global states.

The reader should note an important feature of the index of disorder used here: it allows computing the level of disorder of a dynamical system at a given time step, whereas many other indexes applied to dynamical systems, such as the entropy rate and the excess entropy, are used to capture the regularities of the states visited by the systems in time (Feldman 1998; Prokopenko et al. 2006). This property allows the use of the index to study how the level of order of systems evolves in time, as done here and in Baldassarre et al. (2007a). Intuitively, the reason why the index can compute the level of disorder of a system at an instant of time, i.e., on the basis of a “synchronic picture” of it, is that unlike other indexes it does not need to compare the states that system assumes in time in order to estimate the probabilities of such states. But it rather computes such probabilities on the basis of the potential microstates that the system might have assumed if driven by sheer random forces.

Calculating the specific value of the index for a particular macrostate m assumed by a system requires computing the number w m of microstates that compose it. This number can be obtained as follows:

$$ {w}_{m} = \frac{N!}{N_1! N_2! \cdots N_C!} \quad \sum _{i=1}^C N_i = N $$
(7.2)

where N i is the number of elements in the cell c, and “!” is the factorial operator. The formula relies upon the fact that there are ((N)(N−1)⋯(N−N 1+1))/N 1! different possible sets of elements that can occupy the first cell, there are ((N−N 1)(N−N 1−1)⋯(N−N 1−N 2+1))/N 2! different sets of elements that can occupy the second cell for each set of elements occupying the first cell, and so on. The expression for w m is given by the multiplication of these elements referring to all the C cells. Substituting Eq. (7.2) into Eq. (7.1) of the index one has:

$$ {E}_{m} = k \ln[w_{m}] = k \ln \biggl[{ \frac{{N!}}{{N}_{1}! { N}_{2}! \cdots N_{C}! }} \biggr] = k \Biggl({\ln[N!] - \sum _{i=1}^{C} \ln[N_{i}!] } \Biggr) $$
(7.3)

Once N and C are given, the maximum entropy is equal to the entropy of the macrostate where the N elements are equally distributed over the cells. This allows setting k to one divided by the maximum entropy, obtaining, from Eq. (7.3), a normalized entropy index ranging in [0,1]:

(7.4)

Last, the calculation of the index can avoid the computation of the factorials, which becomes unfeasible for increasing integers, by using the Stirling’s approximation:

$$ {\ln[n!]} \approx \biggl( n + \frac{1}{2} \biggr) {\ln[n]} - n + \ln \bigl[ \sqrt{2 {\pi}} \bigr] $$
(7.5)

Stirling’s approximation gives increasingly good approximations for integers n of increasing size (e.g., the error of approximation goes below 0.5 % for n>20).

2.3 An Hypothesis: Self-Organization of Multi-Robot Systems as a Phase Transition

One of the main contributions of this paper is to present some results that suggest that the self-organization of robotic systems as those considered here might have the features of phase transitions as those studied in physics. According to Wikipedia (2008) (http://en.wikipedia.org/wiki/Phase_transition), a phase transition can be defined as follows: “In physics, a phase transition, or phase change, is the transformation of a thermodynamic system from one phase to another. The distinguishing characteristic of a phase transition is an abrupt sudden change in one or more physical properties, in particular the heat capacity, with a small change in a thermodynamic variable such as the temperature” (Italics added). The distinguishing feature of a phase transition is hence the fast change of a variable related to the collective level of a system (e.g., the heat capacity of a gas, that is the capacity of a whole gaseous system to absorb energy when temperature changes of a certain amount) when a variable related to the behavior of the composing elements (e.g., the average noisy movement of the molecules of a gas, captured by the temperature) is slowly changed and passes a critical value that characterizes the phase transition.

The diagram of Fig. 7.1 shows an example of phase transition in a physical system, illustrated through a result obtained in physics with a spin-1 Ising model related to finite spin systems (Tsai and Salinas 1998). This example shows how the magnetization properties of the spin system undergoes an abrupt change when the temperature of the system is slowly decreased below a critical value.

Fig. 7.1
figure 1

Example of phase transition studied in physics. Y-axis: a measure of magnetization (fourth-order cumulant) in a spin-1 Ising model. X-axis: temperature. Reported from Tsai and Salinas (1998: copyright of the Brazilian Journal of Physics)

Full size image

Here we suggest that the dynamics of organization generated by self-organizing principles in multi-robot systems might share some features with that of the global organization exhibited by some physical systems undergoing a phase transition. The suggestion stems from the following considerations. The behavior of individual robots is affected by noise that influences their sensors’ reading and actuators’ performance. This noise causes the robots to act in a random disorganized fashion. On the other side, the controller of the robots might implement an “ordering mechanism” of the kind “I do what you do” that tends to generate self-organization within the system. However, in order to lead the whole system to successfully self-organize (i.e., all robots converge on the same behavior), the ordering mechanism has to overcome the effects of noise. This requires three conditions: (a) the signal that is perceived by the robots through the sensors, that informs them on the behavior of the other robots (i.e., that allows the robots to know “what you do”), is sufficiently high with respect to noise; (b) the commands issued to the motors (i.e., the “I do” part) are sufficiently effective and succeed to overcome the noise affecting actuator’s response; (c) the controller is capable of implementing a “conformist principle” that self-organization needs to function (i.e., to implement the causation “what you do → I do”).

These considerations suggest the following prediction: in the case the actuators are sufficiently reliable, the controllers are sufficiently effective, and the controller produces a conformist behaviour, if the noise/signal ratio related to the robots sensors is slowly decreased starting from high values, then the organization of the system generated by self-organizing principles should abruptly emerge, as in phase transitions studied in physics. The fact that such order should emerge “abruptly” is due to the fact that once self-organization succeeds to amplify some random fluctuations vs. noise, that is to overcome the “noise barrier” that initially prevents the emergence of the system’s organization by continuously disrupting the asymmetries generated by the random fluctuations, then the positive feedback mechanism generates a self-reinforcing process that further strengthens the signal that enforces the robots to adopt the same behavior. Consequently, such signal definitely overcomes noise and the system “remains locked” in the organized phase and resists external perturbations due to noise. Section 7.5 will present some preliminary results that support this prediction and the related explanation.

3 Robots and Task

The scenario used for the experiments consists of a group of simulated robots (from 4 to 36, see Figs. 7.2 and 7.6, the latter explained later) set in an open arena. The robots are physically linked (they are manually assembled before the experiment) and their controller is evolved with a genetic algorithm. The task of the robots is to harmonize their direction of motion in order to move together as far as possible from the initial position in a given amount of time.

Fig. 7.2
figure 2

Top: The hardware robots. Bottom: The simulated robots. Each simulated robot is made up by a chassis having two motorized cylindrical wheels and two smaller caster wheels (the visible dark-gray caster wheel marks the front of the chassis). The chassis supports a cylindrical turret (the arrow on the turret indicates its orientation)

Full size image

The simulation of the robots was carried out with a C++ program based on Vortex™ SDK, a set of commercial libraries that allow programming realistic simulations of dynamics and collisions of rigid bodies in three dimensions. The simulation of each robot was based on the prototype of a hardware robot that was built within the project SWARM-BOTS funded by the European Union (Mondada et al. 2004; see Fig. 7.2). Each robot was composed of a cylindrical turret with a diameter of 5.8 cm and a chassis with two motorized wheels at the two sides and two caster wheels at the front and at the rear for stability. The simulated robot was half the size of the hardware robot: this decreased the weights of the simulated bodies and so allowed decreasing the simulation time step of Vortex and decreasing the computational burden of the simulations (see below).

The chassis was capable of freely rotating with respect to the turret through a further motor. This motor was activated on the basis of the difference of the activation of the motors of the two side wheels to ease the robots’ turning while being physically linked to other robots (see Baldassarre et al. 2006, for details). The turret was provided with a gripper through which the robot could grasp other robots: this gripper was simulated through a rigid joint connecting the robots since our work focused on the behavior of groups of robots that were physically linked between them during the whole duration of the experiments. The gravitational acceleration coefficient was set at 9.8 cm/s2 and the maximum torque of the wheels’ motors was set at 70 dynes/cm. These low parameter settings, together with the small size of the robots, allowed the use of a relatively fast integration time step in Vortex lasting 100 ms. This was desirable since simulations based on Vortex are computationally very heavy. The speed of the wheels was updated by the robots’ controllers every 100 ms and could vary within ±5 rad/s.

Each robot had only a sensor, a special sensor called traction sensor (introduced for the first time in Baldassarre et al. 2003). This sensor was placed between the turret and the chassis. The sensor indicated to the robot the angle (with respect to the chassis orientation) and the intensity of the force that the turret exerted on the chassis. During the tests this force was caused by the physical interactions between the robots, in particular by the mismatch of the direction of movement of the chassis of the robot with respect to the movement of its turret and hence of the robots attached to it. Notice that if one assumes a perfect rigidity of the physical links, the turrets and the links of the robots of the group formed a whole solid body, so the traction measured the mismatch of movement between the robot’s chassis and the rest of the group. Traction, seen as a vector, was affected by a 2D noise of ±5 % of its maximum length (computed based on a simulation where one robot tries to move at maximum speed and the group is still).

The controller of each robot was a two-layer feed-forward neural network. The input layer was composed of four sensory units that encoded the traction force from four different preferential orientations with respect to the chassis orientation (rear, left, front and right). When the angle was within ±90∘, each of these units had an activation proportional to the cosine of the angle between the unit’s preferential orientation and the traction direction. With angles different from ±90∘, the units had a zero activation. The units’ activation was also multiplied by the intensity of traction normalized in [0,1] based on its maximum value. The last unit of the input layer was a bias unit that was constantly activated with 1. The output of the neural network was formed by two sigmoid output units. These units were used to activate the wheels’ motors by mapping their activation onto the range of the desired speed motor commands that varied in ±5 rad/s.

The connection weights of the neural controllers were evolved through an evolutionary algorithm (Nolfi and Floreano 2001). Initially the algorithm created a population of 100 random genotypes. Each genotype contained a binary encoding of the ten connection weights of the neural controller (the weights ranged over ±10). The neural controller encoded by a genotype was duplicated for a number of times equal to the number of robots forming a group, and these identical controllers were used to control the robots themselves (so the robots were “clones”).

Groups of four robots connected to form a line were used to evolve the controllers. Each group was tested in five epochs each lasting 150 cycles (15 s). At the beginning of each epoch the robots were assigned random chassis’ orientations. The 20 genotypes corresponding to the groups with the best performance of each generation were used to generate five copies each. Each bit of these copies was mutated (flipped) with a probability of 0.015. The whole cycle composed of these testing, selecting, and reproducing phases was repeated 100 times (generations). The whole evolutionary process was replicated 30 times by starting with different populations of randomly generated genotypes. Notice that in this evolutionary algorithm one genotype corresponds to one robots’ group (so the group is the unit of selection of the genetic algorithm), and the robots’ groups compete and are selected as wholes. This allows obtaining groups composed of highly cooperating individuals so avoiding the risk of the emergence of “free rider” individuals within them.

The genetic algorithm selected the best 20 genotypes (groups) of the population of each generation on the basis of a fitness criterion capturing the ability of the groups to move as straight and as fast as possible. In particular, the Euclidean distance covered by each group from the starting point to the point reached at the end of the epoch was measured and averaged over the five epochs. To normalize the value of the fitness within [0,1] the distance averaged over the five epochs was divided by the maximum distance covered by a single robot moving straight at maximum speed in 15 s (one epoch).

4 Analysis of the Emerged Self-Organizing Behavior at the Individual and Collective Level

The graph of Fig. 7.3 shows how the fitness of the best group and the average fitness of the whole population of 100 groups increase throughout the generations in one evolutionary run. Testing the best groups of the last generation of each of the 30 evolution replications for 100 epochs showed that the best and worst group have a performance of respectively 0.91 and 0.81. This means that all the evolutionary runs produce groups that are very good in coordinating and moving together.

Fig. 7.3
figure 3

The fitness (y-axis) of the best robots’ group (thin curve), and average of the whole population (bold curve), across the 100 generations of one of the best evolutionary processes (x-axis)

Full size image

Now the functioning of the evolved behavior will be described at the individual level and then at the collective level, focussing on the controller emerged in the 30th run of evolution (one with top fitness). Overall, the behavior of single robots can be described as a “conformist behavior”: the robots tend to follow the movement of the group as signaled by their traction sensors. Figure 7.4 shows more in detail the commands that the controller issues to the motors of the wheels in correspondence to different combinations of intensities and angles of traction. If a robot is moving towards the same direction of motion of the group, the robot perceives a zero or low traction from the front (around 180∘): in this case the robot keeps moving straight. If the robot is moving in one direction and the group moves towards its left hand side, it tends to perceive a traction from the left (around 90∘) and as a consequence turns left. Similarly, if the robot is moving in one direction and the group moves towards its right hand side, it tends to perceive a traction from the right (around 270∘) and as a consequence turns right. Finally, if the robot moves in the opposite direction with respect to the group’s movement, it perceives a traction from the rear (around 0∘): in this case the robot tends to move straight, but since this is an unstable equilibrium state situated between the behaviors of turning left and right, the robot soon escapes it due to noise.

Fig. 7.4
figure 4

The graph shows how a robot’s left motor (bold curves) and right motor (thin curves) react to a traction force with eleven different levels of intensity (different bold and thin lines) and angles measured clockwise from the rear of the chassis of the robot (x-axis). The speed of the wheels (y-axis) is scaled between −1 (that corresponds to a wheel’s maximum backward speed) and +1 (wheel’s maximum forward speed)

Full size image

When the evolved robots are tested together, one can observe that they start to pull and push in different directions selected at random. In fact initially there is symmetry in the distribution of the motion directions over 360∘. Noise causes some robots to move toward similar directions. If one of these random fluctuations eventually gains enough intensity, so that the other robots feels a traction in that direction, it breaks the initial symmetry: other robots start to follow such bearing, and in so doing they further increase the traction felt by the non-aligned robots toward the same direction. The whole group will hence rapidly converge toward the same direction of motion: the positive feedback mechanism succeeds in amplifying one of the initial random fluctuations so causing an avalanche effect that rapidly leads the whole group to coordinate.

It is important to note that the common direction of motion that emerges in one coordinated motion test is the result of a collective decision based on the amplification of some fluctuations that depend on the robots’ initial random orientations. As a consequence, as shown in Fig. 7.5, if the test is repeated more times the group’s direction of motion that emerges is always different.

Fig. 7.5
figure 5

The absolute angles (with respect to the environment) of the chassis’ orientations of the four robots forming a group (y-axis) measured in two tests (respectively bold and thin curves) where the initial orientations are randomly selected

Full size image

Similarly important, in some tests where the robots’ chassis have particular initial orientations, the group starts to rotate around its geometrical center. This collective behavior is a stable equilibrium for the group since the robots perceive a slight traction towards the center of the group itself, which makes them to keep moving in circle around it. The experiments show that the stronger the symmetry of the group with respect to its center, the more likely that it falls into this stable state.

The illustrated robots’ behavior indicates that the distributed coordination performed by the evolved robots’ controller relies upon the self-organizing mechanism of positive feedback. Indeed, the behavior that the robots exhibit at the individual level is of the type “conform to the behavior of the group”, as requested by the positive feedback mechanism (see Sect. 7.2.1). Moreover at the collective level, as illustrated in Fig. 7.5, this behavior leads the robots to amplify some random fluctuations that eventually move the system away from the initial symmetric state. As a consequence the system achieves a complete asymmetric ordered state corresponding to a very good alignment and coordination of the robots.

5 The Emergence of Organization vs. Noise: A Phase Transition?

This section presents some results that suggest that the organization generated by the self-organizing mechanisms presented in the previous sections might have some features in common with the organization observed in phase transitions of physical systems. Notice that to gain stability of the data, the tests reported in this section were carried out with a group of robots formed by far more individuals than those that composed the group with which the controller was evolved, precisely 36 (Fig. 7.6). This was possible because, as shown in detail elsewhere (Baldassarre et al. 2006, 2007b), the evolved controller has very good scaling properties due to the self-organizing mechanisms it relies upon.

Fig. 7.6
figure 6

A group of 36 robots engaged in the coordinated motion task. The black segments between the turrets of robots’ couples represent the physical connection between them

Full size image

First of all, let us see how the entropy index was applied to the robotic system. The possible orientation angle of each robot, within the range [0∘,360∘] (this was considered as the state space of the elements of the system), was divided into eight “cells” of 45∘ each. The 0∘ angle was set to correspond to 22.5∘ clockwise with respect to the absolute angle of one particular robot chosen as “pivot” (the angles of the other robots were then computed anticlockwise with respect to this origin angle). Notice that while the origin angle on the basis of which the cells are computed is arbitrary, the selection done here assured that when the group achieved high coordination, the chassis’ orientations of the robots were located close to the center of the first cell and inside it (minimum entropy). Moreover, as the pivot robot was always in the first cell, the number of microstates used to compute the entropy was computed with respect to N−1=35 and not N robots.

In order to normalize E m within [0,1], the scaling constant k of the index was set to one divided by the maximum value that ln[w m ] (see Eq. (7.1)) could assume for the studied system, corresponding to a uniform distribution of the chassis’ orientations over the eight cells. In particular, given the low number of robots, for greater accuracy instead of considering (7.4) the maximum value was directly computed on the basis of Eq. (7.2) by considering the most uniform distribution that could be obtained with the 35 robots composing the system:

$$ k = 1 / \ln\bigl[35! / (5! \ 5! \ 5! \ 4! \ 4! \ 4! \ 4! \ 4!)\bigr] \approx 1 / \ln\bigl[7.509 * 10^{26}\bigr] \approx 1 / 61.8843 \approx 0.01615 $$
(7.6)

The graph in Fig. 7.7 illustrates the functioning of the index by reporting the level of entropy measured during 20 coordinated motion tests run with the system formed by 36 robots shown in Fig. 7.6. The figure shows how the disorganization of the group initially decreases exponentially and then stabilizes at a null value when all the robots have converged to the same direction of motion (see Baldassarre et al. 2007a for a statistical analysis and further considerations on these results).

Fig. 7.7
figure 7

Entropy of a group formed by 36 robots engaged in a coordinated motion task. The thin lines refers to the entropy measured in 20 tests that lasted 200 cycles each and were run with different initial random orientations of the robots’ chassis; the bold line is the average of the 20 tests

Full size image

The tests directed to evaluate if the self-organization of the robotic system has the properties of a phase transition relied upon a slow progressive decrease of the ratio between noise and the signal returned by the traction sensor (recall from Sect. 7.3 that such signal is used by the robots to “know” the direction of movement of the other robots so as to conform to it). In particular, the noise/signal ratio was built through the following procedure (see Fig. 7.8): (a) At each time step, a 2D vector similar to the signal’s vector was randomly generated (this vector had a random direction and a length ranging in [0,1]). (b) The controller of the robot received as input a vector equal to a weighted average of the random vector and the signal vector (this average vector was obtained by multiplying the length of the two vectors by the respective “weights” of the average, and then by computing the sum of the resulting vectors with the parallelogram rule). (c) The weights of this weighted average were respectively equal to ε∈[0,1] and to (1−ε) for the noise and the signal: the “noise/signal ratio” manipulated in the experiments presented below was ε.

Fig. 7.8
figure 8

Scheme of how the signal perceived by each robot was corrupted by noise at each time step of the tests depending on the noise/signal ratio: (a) an example of traction signal (continuous arrow) and noise (dashed arrow) represented as vectors; (b) if the ratio is equal to zero, the signal is not corrupted by noise (the signal perceived by the robot is represented by the bold arrow); (c) if the ratio has an intermediate value, for example 0.5 as in this case, the signal is partially corrupted by noise; (d) if the ratio is equal to one, the signal is completely substituted by noise

Full size image

This computation of the ratio allowed running 20 tests with the 36-robots system where the noise/signal ratio ε was linearly lowered from one to zero during 20,000 time steps. During these tests the entropy of the group was measured. Figure 7.9 reports the results of these measurements in terms of the relationship between the noise/signal ratio and the level of order of the group (i.e. the complement to one of the normalized entropy index).

Fig. 7.9
figure 9

Relationship between the noise/signal ratio and the level of organization of the group (equal to the complement to one of the normalized entropy) measured while slowly lowering the noise/signal ratio from one to zero. Average (bold line) ± standard deviation (thin lines) of the results obtained in 20 replications of the experiment

Full size image

A first relevant fact highlighted by the figure is that the system starts to organize at a very high level of noise/signal ratio, about 0.8, indicating a surprising robustness vs. noise of the self-organizing mechanisms employed by the system. Previous work (Baldassarre et al. 2006) already gave some indications in such direction but this result overcomes prior expectations and furnishes a quantitative measure of the level of such robustness.

The second relevant fact is that when the noise/signal ratio is progressively lowered, organization does not increase linearly but rather reaches its maximum level quite abruptly in correspondence to levels of noise/signal ratio ranging approximately between 0.6 and 0.8. This suggests that there is a critical noise/signal level in correspondence to which the system exhibits a transition from a disorganized to an organized state.

To further investigate the possible existence of such critical value, groups of 20 tests where carried out by setting the noise/signal level to fixed values chosen in the range between 0.9 and 0.6, at intervals of 0.05, and by measuring the level of entropy of the system in 10,000 cycles of simulation. The goal of these tests was to verify if there was a critical level of noise/signal ratio above and below which the system exhibited a discontinuous behavior in terms of overall organization. The outcome of these tests suggested that this might be the case. In particular Fig. 7.10, that shows the outcome of these tests for three levels of noise/signal ratio, indicates that this critical level might be within (0.75,0.80). In fact, if the noise/signal value is set at 0.80 the entropy of the system fluctuates in the range of (0.80,1.00), that is around its maximum values (in evaluating the level of order corresponding to such noise/signal values, consider that a level of entropy of 0.9 corresponds to quite uniform distributions of the robots on the cells, for example: 5,6,6,6,6,5,1,0). On the contrary, for noise/signal values set at 0.75 in 18 out of 20 experiments the entropy level of the system initially decreases from about 0.95 to about 0.55, indicating that the system self-organizes, and then stabilizes at values ranging in (0.45,0.65) (in evaluating the level of order corresponding to such noise/signal values, consider that a level of entropy of 0.55 corresponds to quite concentrated distributions of the robots on the cells, for example: 0,1,6,20,7,1,0,0). Once the system “gets locked” in the ordered state, it tends to resist noise perturbations, as predicted by the considerations presented in Sect. 7.2.1. Indeed, entropy raised again to high values only in 2 out of 20 cases after the system reached the ordered state (see bold lines in the bottom graph of Fig. 7.10).

Fig. 7.10
figure 10

Level of entropy (100-step moving average) of the 36-robot system in 20 tests lasting 10,000 steps each, when the noise/signal ratio is set at two different fixed levels, namely 0.80 and 0.75 for the top and bottom graph respectively (the level of the noise/signal ratio is indicated on the y-axis of each graph by the bold arrow). The two bold lines of the bottom graph refer to two tests where the system first reached an ordered state and then lost it

Full size image

6 Conclusions

This paper presented a multi-robot system guided by a decentralized control system evolved with a genetic algorithm. The control system is capable of coordinating the robots so as to accomplish a collective task relying upon a minimal implicit communication between them and self-organizing mechanisms. These self-organizing mechanisms were first described at the level of individual and collective behavior, and then the effects they produced on the level of organization of the whole system were quantitatively analyzed on the basis of an index based on Boltzmann entropy. This analysis showed that, when one slowly decreases the noise/signal ratio related to the signal that the robots use to coordinate, the dynamics of the self-organization exhibited by the system resembles the self-organization characterizing physical systems undergoing phase-transitions. In particular, the order of the system tends to emerge quite abruptly when the ratio is lowered below a critical value.

The hypothesis that the dynamics of the level of order of self-organized multi-robot systems might have the features of a phase transition would have important implications if confirmed. In fact it would imply that self-organization of collective systems tends to manifest in an all-or-nothing fashion depending on the quality of the signals exchanged by the elements forming the system. Moreover, when such quality overcomes a critical value, even of a small amount, the organization produced by the self-organizing mechanisms becomes fully effective and robust vs. noise (as the system “locks in” in its state of order). These implications are relevant for engineering purposes. For example identifying the critical noise-signal level that characterizes a distributed multi-robot system might allow adjusting the physical set-up of the latter so as to achieve a reliable level of robustness of its self-organization. The implications are also important for scientific purposes, for example for investigating self-organization in collective biological systems (Bonabeau et al. 1999; Camazine et al. 2001; Anderson et al. 2002). In fact in some of such systems self-organization emerges quite abruptly if some parameters of the system change beyond certain thresholds. For example, trail formation in ants requires that the number of ants that compose the group, and hence the amount of pheromone released on the ground, reaches a certain level for the organization of the group to emerge. Indeed, given that the laid pheromone trace slowly vanishes in time, if the number of ants, and hence the level of the released pheromone, is not enough, the signal that it furnishes to the ants is too weak to allow them to self-organize.

The added value of the paper resides also in the techniques it presented. In particular such techniques might not only be used to measure the level of organization of decentralized (and also centralized) systems, as done here, but it might also be directly used as fitness function to evolve systems that exhibit useful behaviors (for some examples of this, that use entropy indexes different from those used here, see Prokopenko et al. 2006), or to explore the self-organization potential of systems. Moreover, the identification of the critical noise/signal ratio that characterizes a decentralized robotic system might be a way to furnish a quantitative measure of the robustness of the self-organizing principles that govern it.

Notwithstanding the relevance of all these implications, we recognize that the results presented in the paper, in particular those related to the hypothesis according to which in some conditions self-organization of some multi-robot systems might behave as a phase transition, are preliminary under many respects. For example, further research is needed to corroborate or falsify the hypothesis itself, to better understand the behavior of the system in correspondence to the critical level of the noise/signal ratio, and to better understand the relationship existing between the level of order of the system and the role that it plays in its functioning (e.g., in its capacity to displace in space). Moreover, it might be useful to build a mathematical abstract model of the system to carry out an analytical study directed to ascertain at a more formal level if it posses the properties that characterize phase transitions. For example, this analysis might identify some quantities associated with the self-organization of the robotic system that behave similarly to “free energy” or “latent heat” in phase transitions of physical systems (for an introduction on these topics, see http://en.wikipedia.org/wiki/Phase_transition).

A last observation is that experiments similar to those conducted here by slowly lowering the noise/signal ratio might be also conducted on the actuator’s noise and on the controller’s effectiveness. With this respect it might be possible to envisage a way to regulate the “noise/effectiveness level” of actuators, or the “level of effectiveness” of the controller in ways similar to the one used here to regulate the noise/signal ratio of sensors. These experiments might show that also these two manipulations lead to phase-transitions at the level of the system’s overall organization.

7 Epilogue

The multi-robot system presented in the first edition (Baldassarre 2008) has been further developed in two follow-up works. The first work (Baldassarre and Nolfi 2009) further investigated the robotic system used here to show how the controller evolved with the genetic algorithm can be captured with a simple mathematical function linking the direction and strength of the traction sensor to the motor commands. The parameters of the mathematical function can be found based on a non-linear regression of the input-output points of the original controller and the whole technique has a general applicability to simple controllers. The paper shows that, in general, this transformation allows “bridging” the controllers develop with evolutionary techniques with more standard robotic controllers, such as behaviour based (e.g., schema-based) controllers, so allowing the exploitation of the strengths of both. Once this transformation is done, thanks to the robustness of the original controller capable of exploiting self-organisation, the resulting function offers a number of advantages. These go from a higher transparency with respect to the original neural network, to the possibility of changing its parameters by hand, and to the possibility of using the function to build more-complex compound controllers capable of solving a number of different tasks. With respect to the issues discussed here, the function-based description of the controller might also facilitate the application of formal and principled tools to investigate the self-organising principles underlying evolved controllers.

The second work (Ferrauto et al. 2013) studies again a multi-robot decentralised system of robots engaged in navigation tasks (here groups are formed only by two robots). However, in this case the work focusses on different possible genetic algorithms that might be used to evolve the robots so to lead them to solve two different tasks requiring either specialisation or dynamic role-taking. Based on these tasks, the work analyses the most important genetic algorithms proposed so far to evolve collective systems showing their strengths and weaknesses for the two types of tasks. The different genetic algorithms vary with respect to the unit of selection, the number of populations used, and the test of each robot within a fixed or variable group. The relevance of this work for the issues faced here resides in the fact that the controllers evolved with the different genetic algorithms tend to exploit different self-organisation principles such as symmetry breaking in role allocation and self-organised behaviour generated by robots with different controllers.

Although promising, no further work has been carried out on the specific issue tackled here and related to self-organisation principles of multi-robot systems analysed in quantitative and formal ways (the author research has diverged to the study of behaviour and brain of single organisms). However, the author is still convinced that the research presented in this chapter contributed to open a very important new research thread within the study of self-organising multi-robot systems. The reason is that the “methodological message” of this paper is still very important. Such message can be summarised in three points as follows:

  • Multi-robot systems exploiting self-organisation principles are very robust, effective, and simple. This makes them very interesting from a scientific point of view, and potentially very useful from an engineering point of view.

  • To fully understand and exploit self-organising principles in multi-robot systems, and to be cumulative in doing so, we need to study such self-organising principles in a quantitative/formal fashion where theory and empirical tests go hand in hand.

  • The theoretical and formal apparatus needed for doing this can be borrowed from physics and information theory: these can furnish the needed ideas, principles, formalisms, and metrics to investigate self-organising principles in a quantitative and principled fashion.