plosPLoS Comput BiolploscompPLoS Computational Biology1553-734X1553-7358Public Library of ScienceSan Francisco, USAPCOMPBIOL-D-11-0034210.1371/journal.pcbi.1002177Research ArticleBiologyTheoretical biologyComputer scienceComputer modelingComputerized simulationsComputer ScienceSmart Swarms of Bacteria-Inspired Agents with Performance Adaptable InteractionsBacteria-Inspired Smart SwarmsShklarshAdi123ArielGil4SchneidmanElad5Ben-JacobEshel26*School of Computer Science, Tel Aviv University, Tel Aviv, IsraelSchool of Physics and Astronomy, Tel Aviv University, Tel Aviv, IsraelDepartment of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot, IsraelDepartment of Mathematics, Bar Ilan University, Ramat Gan, IsraelDepartment of Neurobiology, Weizmann Institute of Science, Rehovot, IsraelThe Center for Theoretical and Biological Physics, University of California San Diego, La Jolla, California, United States of AmericaCouzinIain D.EditorPrinceton University, United States of America* E-mail: eshel@tamar.tau.ac.il
Wrote the paper: AS GA ES EBJ. Conceived and designed the model: AS GA ES EBJ. Conceived and designed the algorithm: AS GA ES EBJ.
The authors have declared that no competing interests exist.
92011299201179e1002177143201127620112011Shklarsh et alThis is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
Collective navigation and swarming have been studied in animal groups, such as fish schools, bird flocks, bacteria, and slime molds. Computer modeling has shown that collective behavior of simple agents can result from simple interactions between the agents, which include short range repulsion, intermediate range alignment, and long range attraction. Here we study collective navigation of bacteria-inspired smart agents in complex terrains, with adaptive interactions that depend on performance. More specifically, each agent adjusts its interactions with the other agents according to its local environment – by decreasing the peers' influence while navigating in a beneficial direction, and increasing it otherwise. We show that inclusion of such performance dependent adaptable interactions significantly improves the collective swarming performance, leading to highly efficient navigation, especially in complex terrains. Notably, to afford such adaptable interactions, each modeled agent requires only simple computational capabilities with short-term memory, which can easily be implemented in simple swarming robots.
Author Summary
Many groups of organisms, from colonies of bacteria and social insects through schools of fish and flocks of birds to herds of mammals exhibit advanced collective navigation. Identifying the minimal features of biologically-inspired interacting agents that can lead to emergence of “intelligent” like collective navigation and decision making is fundamental to our understanding of collective behavior, and is of great interest in artificial intelligence and robotics. Previous models of collective behavior of agents, which relied on static interactions of repulsion, orientation (alignment), and attraction, have shown the emergence of collective swarming. Here we show the advantage of performance adaptable interactions for navigation of groups in complex terrains. Each agent senses the local environment and is then allowed to adjust its interactions with the other agents according to its local environment – by decreasing the peers' influence while navigating in a beneficial direction and vice versa. We found that inclusion of such adaptable interactions dramatically improves the collective swarming performance leading to highly efficient navigation especially in very complex terrains.
This research has been supported in part by the Tauber Family Foundation, the Maguy-Glass Chair in Physics of Complex Systems in Tel Aviv University, the Marie Curie IRG grant, and the Google Anita Borg memorial Scholarship, as well as the Clore center of biological physics at the Weizmann Institute of Science, a fellowship from the Center for complexity science and the Peter and Patricia Gruber foundation. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.Introduction
Many organisms exhibit complex group behavior [1]–[10], including collective navigation observed in the flight of birds [11], trail organization in ants [12], and swarming of locust [13], fish [14] and bacteria [15], among others. The aggregation results in highly complex collective behavior, with new functionality and computational ability. Simple interaction models, which describe how each agent acts according to the result of a ‘computation’ it performs on the locations of the other agents, have been used to demonstrate and study the fundamental building blocks of complex group behavior [16]–[24].
In computational models, swarming behavior can arise from simple rules, and in particular demonstrate qualitive (and sometimes quantitative) features of collective behavior observed in nature: Vicsek et al. [16] introduced the ‘self-propelling particles’ (SPP) model, in which the motion of each individual is determined by the mean orientation of its local neighborhood with some noise induced perturbation. The SPP model can exhibit random or coherent motion of group clusters depending on the particle density and on the noise of each individual; high density and low noise results in a coherent group motion. Later derivatives of the SPP model included individual preferential movement directions, collision avoidance, and attraction [17]–[23]. Couzin et al. [17], [18] studied a model in which the direction of motion of each individual is determined by a set of rules: repulsion (from neighbors who are too close), attraction (to prevent fragmentation), alignment (of velocity directions and speed), and reaction to the environment. A swarm using these interaction rules can come to a collective ‘decision’ about its direction of movement without leadership and a small fraction of individuals ‘in agreement’ are needed for such a cohesive decision to be made. Recently, Torney et al. [25] presented a model in which the individual agents adapt their interactions according to local conditions. A special feature of this model is that it leads to the emergence of collective navigation although each agent does not possess individual navigation capabilities.
Even bacteria show remarkably sophisticated collective behaviors. Some bacteria strains can form large colonies with intricate complex architectures, which allows them to expand efficiently by taking advantage of the available resources [26]–[29]. They construct intricate multicellular structures utilized for protection and cooperation of cells [30]–[33]. In addition, bacteria display complicated movement dynamics, in which cells organize into vortices, form traffic lanes, or move collectively in a common direction [34]–[36]. Bacteria swarming behavior in colonies was explained by considering attractive and repulsive forces between colony parts [10], [28], [37], [38], communication capabilites [39]–[43], physical interactions between cells, and forces from the environment [44].
Bacteria navigate using chemotaxis, i.e., moving according to gradients in the chemical concentration [45]–[49]. Bacteria are too small to detect the chemical gradients across their body receptors, and thus detect the concentration as they swim, and delay their tumble if the concentration increases. As a result, they make longer excursions towards areas of higher concentration. Each bacterium may only acquire local and partial cues from the environment, but as a group bacteria can navigate through challenging environments. In such cases, the optimal local direction may be completely independent of the global environment. In addition, microorganisms are especially sensitive to noise, due to stochastic variations in their internal mechanisms, sensory system, and the external environment. Information pooling was shown to improve decision making in animal groups [1], [50]–[52], such as the accuracy of navigating birds. In addition, it has been shown that schooling can improve the collective ability of groups of chemotactic organisms, such as bacteria, to climb gradients [53].
Interaction between individuals such as repulsion, alignment, and attraction, may exist in bacteria due to the associations between single cells by mechanical and chemical means. Mechanical interactions can result in collision or adhesion of cells. Chemical interactions, by secretion and detection of various diffusible chemicals, can result in repulsion or attraction. In high densities, interactions between elongated cells cause alignment of cell bodies and velocities.
Here, motivated by bacteria swarming, we study the collective behavior of agents with self-navigation capabilities (particularly, a tractable variant of chemotaxis) and performance dependent adaptable interactions. Specifically, when the change of chemical concentration is positive, an agent is more likely to continue in its previous direction, thus, decreasing the influence of the other agents, and vice versa. This implies that the interaction network among agents is plastic – similar in spirit to the approach in machine learning and neuroscience [54]–[56] and the recent work by Torney et al. [25].
The current approach enables quanitative comparison between the efficiency of collective navigation in the case of static and adaptable interactions. We found that the adaptable interactions become more important for more complex terrains. We also found that collective navigation of agents with adaptable interactions is more robust to the initial conditions, to the internal noise in the system, and to the values of the interactions.
MethodsModeling the terrain
We studied the navigation efficiency of swarms in a complex two-dimensional terrain with obstacles. The structure of the terrain was given by a static concentration map (Figure 1A) of the form:where , are constants defining the periodic variations of the terrain, and are constants relating to the underlying chemical diffusion gradient. is the modified Bessel function of the second kind (which is the solution to the differential equations related to diffusion in two dimensions) and is the location of the target. The ‘topography’ was one of mountains and valleys, representing locally changing chemical concentration that is ‘overlaid’ on a global concentration valley. In particular, the modeled terrain had local minima and bottlenecks. The mountains represent low chemical concentration whereas the valleys represent high concentration. The target was the lowest point on the map – which was the maximum concentration point (Figure 1B,C). The concentration map was chosen as a simplified model of a problem with local variations and local minima (see Text S1, Figure S1), motivated by real navigational problems in bacteria swarms. Agents that are only capable of local measurements are thus faced with an extremely challenging navigation task.
10.1371/journal.pcbi.1002177.g001
Illustration of the terrain representing the chemical concentration map.
A. Overview of the terrain given by . B. Illustration of a single agent and the global direction (in black) to the target compared to the local gradient (in purple) of the concentration map. C. Illustration of the terrain height along a straight trajectory from the swarm's starting position to the target.
Movement of individual agents
Three main factors influence the movement of the agents. The first is internal noise of each agent, the second is its environment, and the third is interaction with other agents.
On each time step, the location and the direction of the velocity of agent were updated according to the following rules:where represents internal noise taken from a Gaussian distribution with variance , , and is an agent's new angle (see below).
The movement of an individual agent devised here was inspired by chemotaxis in swimming bacteria. A bacterium follows chemical gradients by decreasing its tumbling frequency in high gradients, whereas the tumbling angle is random (Figure 2A). In the model we implemented this mechanism by maintaining an equal tumbling frequency whereas the tumbling angle depended on the chemical gradient (Figure 2B). We note that both approaches produce the same effect statistically. An agent moves forward and after a time step , it changes direction by an angle, , which is randomly chosen from a Gaussian distribution, . The distribution variance was given bywhere is the chemical gradient and . We note that when the speed is constant, the agent will move forward by ; since in the model , the forward motion length equals . The variance decreases with an increase in the chemical gradient, biasing the direction of motion up chemical gradients.
10.1371/journal.pcbi.1002177.g002
Illustration of the motion of an individual bacterium and an individual agent.
A. A bacterium's motion in chemical gradients is a biased random walk towards areas of higher chemical concentration. A bacterium makes longer excursions when it moves in areas of higher chemical gradients after which it performs a random switch of direction, known as a tumble. B. The motion of an individual agent is composed of equal sized excursions after which the agent tumbles. The tumble is a change in direction taken from a Gaussian distribution whose variance is a function of the chemical concentration. When the chemical gradient is small, the variance is large, and vice versa.
During a forward motion, an agent's new angle was the angle of its previous velocity direction, , and during a tumble, the new angle was given by
Interactions between the agentsTwo-agents interaction
An individual agent will repel from another agent when it is in the range ; it will align its velocity with the direction of the other agent when it is in the range , and it will go towards it if it is in the range (Figure 3).
10.1371/journal.pcbi.1002177.g003
Illustration of agent-agent interactions in the swarm model.
Agents repel from close agents, align with intermediate agents, and move towards far agents.
Many-agents interaction
We denote to be the direction resulting from the group interactions of agent , if there is more than one agent in any of the interaction ranges. If there are any agents within distance , it will try to avoid collision, and will thus set its velocity to be:where , and the sum is over all such that . If there are no agents in the range of repulsion, agent will align with agents within distance and move towards agents within distance according to: where for the left term, the sum is over all such that , for the right term, the sum is over all such that , and .
Combination of chemotactic motion with group interactions
During a forward motion, an agent's new angle , was selected by:where the direction was a combination of an agent's previous velocity direction and the group interactions and was defined aswhere . During a tumble, the new angle was selected as in equation (5).
Adaptable interaction model
In the model presented above, the weight , which determines the balance between group interactions and individual direction, was fixed (see equation (9)). We now consider the case of an adaptable that is adjusted according to local conditions. Specifically, we decreased the weight of agent , , when the agent moved in the direction of decreasing gradient and vice versa. Among many possible ways to control the weight that would accomplish this goal we used a simple update scheme where
The new direction was then given by: . Note that for , the new direction depends only on group interactions. In contrast, corresponds to equal balance between group interactions and individual direction.
Group movement characteristics
The path length, which is equal to the navigation time multiplied by , was computed as the median path length, and corresponds to the time it took half of the agents in the group to reach the target. The group alignment was given by
The group alignment is the average alignment between individuals over the trajectory. Notice that the group alignment is in the range . The group's cohesion was assessed by the number of clusters at the end of the simulation where clusters were separated according to the region of interactions between agents bounded by .
Selection of the model parameters
In nature, an organism's motion mechanism or interaction range should fit the common characteristics of its environment. The challenge in choosing the model parameters is to select them to fit the terrain, since for each terrain there is a different set of parameters that is most efficient. We fixed the terrain and chose the model parameters, including the time step in which an agent moves forward before it tumbles, , and the group interaction radii, . The terrain characteristic sizes include the terrain characteristic length, which corresponds to the typical distance between two adjacent peaks or valleys, and the characteristic slope of the mountains or valleys. We found to have a strong effect on the behavior of individual agents. When the length of an agent's forward motion was small compared to the terrain's characteristic gradient, the agents were unable to detect changes in the concentration, causing their motion to become more random. When the forward motion ‘runs’ were large compared to the terrain's characteristic length, then agents could not follow the smooth terrain's gradient since their motion was made of large independent leaps in an irregular terrain. Moreover, small radii of repulsion compared to the terrain's characteristic gradient, resulted in groups aggregating together and thus measuring more similar concentrations, which caused the groups to get stuck in local minima. In general, increasing the characteristic gradient of the terrain (corresponding to a ‘heightening’ of the mountains and a ‘deepening’ of the valleys) makes the task harder since agents are more likely to settle in local minima.
Results
We simulated different groups of moving agents navigating on a complex terrain, given by equation (1), with . The initial conditions were set such that the agents' locations, , were uniformly distributed around the starting position inside a circle with radius , which meant that the group was not fragmented and all the agents were interacting with other agents. The agents' velocities were , and their directions were uniformly distributed over all directions, .
Comparison of typical realizations of the models
Figure 4 shows the typical results for the movement patterns of a group of independent agents on a complex terrain. An example of a similar group of interacting agents, with static interactions is shown in Figure 5. Examples of the paths of a single agent under the independent model, the static interactions model, and the adaptable interactions model are shown in Figure 6. These snapshots are reproduced from full simulation runs (see full movies in Supplementary Information Video S1-3). The height along the navigation path of the group center for interacting agents and agents with adaptable interactions are shown in Figure 7. The groups demonstrated extremely diverse movement patterns: groups split and collide, they bump into the mountains, single agents break away from the main group, groups move away from the target, or circle around in one place (See Video S4–6).
10.1371/journal.pcbi.1002177.g004
Frames from the simulation show independent agents moving towards the target.
A. Simulation step 100. B. Simulation step 2000. .
10.1371/journal.pcbi.1002177.g005
Frames from a simulation of interacting agents moving collectively towards the target.
A. Simulation step 200 from starting position. B. Zoom in on the group in the left frame. Simulation parameters are as in Figure 4, .
10.1371/journal.pcbi.1002177.g006
Examples of individual paths of agents using the different interaction mechanisms.
A. The path of a single independent agent shows a biased random walk towards the target. B. The path of a single interacting agent shows directed movement towards the target with global errors. C. The path of a single agent with adaptable interactions shows directed movement towards the target with smaller global errors. Simulation parameters are as in Figure 5.
10.1371/journal.pcbi.1002177.g007
Height along the path of the group center.
A. For interacting agents. B. For agents with adaptable interactions. Simulation parameters are as in Figure 5.
Navigation of independent agents and interacting agents
A single agent performing an independent search on the concentration map would move in a biased random walk fashion towards the target with a profuse amount of local ‘errors’ with respect to the global target. A group of agents navigating independently would converge as a group towards the target, with each agent performing its own biased Brownian motion. We quantify the error fraction by:where is the median path length (the time it took half of the elements in the group to reach the target multiplied by ) and is the distance between the starting position and the target, and found that the error fraction was approximately . We chose to measure the median path length and not the average, to prevent the bias of rare instances of extremely long path lengths.
In complex terrains, interacting agents were less sensitive to local noise due to the group's influence, and the group as a whole was cohesive and aligned; this is in agreement to what has been suggested by Grunbaum [53]. The average error fraction (equation (12)) in this case was approximately 0.65, considerably less than the independent agents. Although the interacting agents were more robust to local noise than the independent agents, they still had a large error fraction.
The effect of the balance between the group's influence and individual direction on interacting agents
The value of the weight , which balances the effect of the individual direction of motion (based on local information) and the group's influence (equation (9)), had an immense effect on the group's behavior and organization (Figure 8). Large weights imply that the agents were mostly influenced by their own direction of motion and that the interactions between them were weak, which means that the group would behave more like independent agents. Small imply that agents were strongly influenced by their neighbors, which results in excessive conformity. This could also mean that agents would be led off the track by small errors and perturbations that would be amplified by the positive feedback in the group. There is an intermediate range of weight values that lead to optimal median path lengths, shown in Figure 8.
10.1371/journal.pcbi.1002177.g008
The path length of interacting agents is optimal in an intermediate range of weights.
The median path length is shown as a function of the constant fixed weight of interacting agents. The average median path length of independent agents and agents with adaptable interactions is shown for comparison. Simulation parameters are as in Figure 5, 100 rounds. Error bars represent standard error.
The effect of adaptable interactions
The adaptable interaction rules (equation (10)) kept the group cohesive and aligned as in the case of static interactions, but, we found that such groups were not sensitive to local noise, and also less sensitive to global noise. The error fraction (equation (12)) in this case was approximately 0.5 – considerably less than both the independent and the fixed interaction agents. The adaptable interactions affect the error in the global group movement by modulating the positive feedback in the group's self-influence with feedback from the environment.
The median length of the path of agents with adaptable interactions was smaller than that of the fixed interacting agents – even for optimal weight values (shown in Figure 8) – which was smaller than that of the independent agents (Figure 9). Interestingly, the variance of the distribution of the path length of the interacting agents was higher than in the other mechanisms. We suggest that this is due to the positive feedback, which may sometimes lead groups off track in the presence of a global noise source. As illustrated in Figure 9, the variance of the distribution of agents with adaptable interactions was smaller than the variance of interacting agents, giving the adaptable mechanism yet another advantage – having the group find the target quickly with certainty.
10.1371/journal.pcbi.1002177.g009
Distribution of navigation path lengths for the different interaction mechanisms.
The mean median path length of agents with adaptable interactions is lower than that of both interacting and independent agents. The mean path length of independent agents is significantly larger. The variance of the path lengths of interacting agents is larger than that of the other mechanisms due to positive feedback. Simulation parameters are as in Figure 5, 500 rounds.
We compared the group's movement characteristics as a function of group size for the three interaction mechanisms. Figure 10A shows that agents with adaptable interactions found the source faster than the groups using the other mechanisms. The navigation time increased as a function of the group size for independent agents, due to convergence to the true average navigation time, since there is a larger probability for rare occurrences with an increase in the number of agents. However, the path length decreased as a function of group size for interacting agents and agents with adaptable interactions, due to collection of information from more agents. Alignment decreased with group size and, as expected, independent agents had very low alignment (Figure 10B). For agents with adaptable interactions, we found that the alignment and the average weight (which equals the proportion of agents with ), are lower than that of fixed interactions agents (Figure 10C). This may seem contradictory since lower weights are expected to increase the coordination in the group, which leads to higher alignment. We note however that for each agent in our case, or , whereas for the fixed interaction agents, for all agents at all times. This amounts to a non-linear effect of the weights on the alignment. The average number of clusters was the highest for independent agents, having no interactions. The number of clusters of agents with adaptable interactions was slightly higher than that of the interacting agents due to the nonconformity (Figure 10D).
10.1371/journal.pcbi.1002177.g010
Comparison of the interaction mechanisms as a function of group size.
A. Agents with adaptable interactions find the target faster than interacting agents. Both are much faster than independent agents. The median path length increases as a function of group size for independent agents due to an increase in the sample size. It decreases for interacting agents and for agents with adaptable interactions due to the collection of information from more agents. B. Alignment decreases as a function of group size. Independent agents are not aligned while agents with adaptable interactions are less aligned than interacting agents. C. For agents with adaptable interactions, group average weight is not strongly dependent on group size. The average weight of agents with adaptable interactions is lower than the constant predetermined weight of interacting agents. Nonlinearity cause lower average weights, which correspond to higher conformism and implies higher group alignment, to couple with lower alignment. D. The average number of clusters increases with the group size. Independent agents are highly clustered while agents with adaptable interactions are more clustered than interacting agents. Simulation parameters are as in Figure 8, apart from. Error bars represent standard error.
The effect of noise on group behavior
Our model has three sources of stochasticity: The first one is external, imposed by the surface variations (equation (1)). The second is the Gaussian noise related to the measured concentration gradient, applied by switching direction (equation (4)). The third is the internal noise related to the selection of the direction (equation (3)).
To assess the effect of individual agent stochasticity on the group collective navigation, we deflected each agent's movement direction by Gaussian noise with a constant variance, . We found that the path length of the group increased with , while the manner by which it increased was dependent on the interaction mechanism (Figure 11A). Independent agents were most vulnerable to this noise and for high values they failed to complete the task. Agents with fixed interactions and agents with adaptable interactions were affected similarly by the noise, although interacting agents were affected more strongly. We found that alignment decreased as a function of (Figure 11B). The alignment of independent agents also decreased since the noise disrupted the independent biased random walk to the target. In addition, we found that the average weight of agents with adaptable interactions decreased as a function of (Figure 11C). Similar to the effect of adaptable interactions on the average weight and alignment, we found that lower average weights implied low alignment. Unlike the performance of agents with adaptable interactions, here the noise causing this led to longer navigation paths.
10.1371/journal.pcbi.1002177.g011
The effect of internal noise on group behavior.
A. Diversity in the agents' movements resulting from internal noise causes an increase of median path lengths among all the mechanisms. The effect on the independent agents is the most devastating and groups did not complete the task by the end of the simulation. The effect on the interacting agents is larger than the effect on agents with adaptable interactions. B. Group alignment decreases with . For independent agents, alignment decreases due to the individual loss of biased motion towards the target because of the noise. C. The average weight of agents with adaptable interactions, which is lower than the constant predefined weight of the interacting agents, reduces further with , implying groups become more conformist. D. Clustering is weakly affected by . Independent agents are more clustered due to loss of biased motion. Interacting agents become slightly more clustered with . Agents with adaptable interactions are generally slightly more clustered than interacting agents but their clustering is not affected by . Simulation parameters are as in Figure 8, apart from . Error bars represent standard error.
Next, we let each agent pick a forward run time, , taken from a uniform distribution in the range of values that fit the terrain. We then asked how this diversity affected the path lengths of the groups under the three interaction mechanisms. The distributions of the median path lengths reflect that adaptable interactions resulted in considerably shorter paths than that of independent and interacting agents, for which the path lengths were longer than the simulation length (Figure 12).
10.1371/journal.pcbi.1002177.g012
Distribution of median path lengths with diverse forward motion runs.
When the sizes of the agents' forward motion runs, denoted by , are diverse, the mean median path length of agents with adaptable interactions is much lower than the other mechanisms, which are not clearly visible in the graph since they exceed the simulation length. Simulation parameters are as in Figure 9, apart from the previously constant forward motion run; here .
The effect of the radii of interactions
The interactions between the agents – repulsion, alignment, or attraction – depend on the distance between them as defined by the radii of interactions, , , and, respectively; these radii of interactions determine the collective behavior, in particular, alignment and task performance [18]. We found performance dependent adaptable interactions to be more robust to the values of the radii of interactions than the other mechanisms (Figure S2, Figure S3). See more details in the Text S1.
Discussion
We introduced a collective behavior model of a group of interacting agents, in which each group member senses the environment and adaptively weighs its own evidence and the behavior of its neighbors to navigate in a complex environment.
We expanded a model that originated from the self propelling particles model and has been used to describe swarming in many complex systems [17]–[23], [25], [53], [57]. We investigated the navigation capabilities of the swarm in a complex terrain and showed that independent agents create fragmented groups while each agent performs an independent biased random walk towards the target. Interacting agents were far better in finding the target than independent agents, and also demonstrated emergent collective swarming, but were affected strongly by global noise due to positive feedback. Previously, Torney et al. [25] showed that adaptable interactions can lead to the emergence of collective navigation in swarms composed of agents that do not posses navigation capabilities as individuals. Here, we studied collective navigation of agents which do possess navigation capabilities as individuals while focusing on the advantage of performance dependent interactions.
When we added a learning mechanism to the network of agent-agent interactions, these swarms had a higher probability of finding the source, and significantly faster. Moreover, performance-dependent adaptive interactions improved the efficiency of the collective navigation beyond that of agents with static interactions, even for an optimal set of static interaction parameters. The adaptable interactions enabled agents to adjust the weight they gave to their neighbors according to local conditions. We used a hard limit weighting, in which agents either followed their neighbors or balanced equally between them and their individual direction, and this was enough to significantly improve the navigation efficiency of swarms in a complex terrain. We note that we did not add memory beyond the measurement of the change in concentration, which already exists in the navigation of an independent agent, or additional computational capabilities to the agents. Using the immediate environment as a teacher the weights of each agent in the network changes dynamically. This gave a form of noise reduction, where the influence of erroneous agents on the system was reduced, and the power of sub-groups changed and resulted in a dynamically shifting leading cluster of agents that comprises of only the most successful performers.
We found that the adaptable interactions model is more robust to internal noise and to diversity in the agents' control mechanism parameters. In particular, the model was robust to the radii of interactions. The system of agents with adaptable interactions changed dynamically according to each agent's success and as a result, the system as a whole transforms into a robust yet “plastic” network.
Models of swarm intelligence and their analysis have the potential to export ideas and algorithms from nature into novel computational tools, including distributed algorithms for optimization and other complex problems in addition to mechanisms for robotic systems [58]-[61]. The model we studied here can be viewed as a distributed network of sensors, with the capability of having local effects on each other. The problem at hand is a function optimization task, where the function samples contain local and global errors. Each sensor can only sample the function at one position and the next sampling position is in the local proximity of the previous one. We investigated how the local effects or interactions between the sensors affect the function optimization time of the network under different conditions. We found that adaptable interactions benefit the system as a whole in a complex navigation task making it faster to find the target under more diverse conditions than before.
In the current study, our swarms constituted of identical individuals with equal measurement capabilities. Natural extension would be investigating the effect of variability, for example in the interaction ranges and noise distributions of agents, on the swarm's collective navigation performance. It is known that many biological mechanisms benefit from variability in the system in the presence of noise [62]-[64]. We expect agent variability to be advantageous for navigation in the case of both spatial and temporal noise. The combination of sensor diversity and adaptable interactions can constitute a solution to navigation in the presence of spatial and temporal noise such as in the case of a time-changing terrain.
Bacteria have developed various communication capabilities such as direct and indirect cell-cell physical and chemical interactions, chemical signaling, such as quorum sensing, and chemotaxis signaling [30], [32], [36], [40], [43], [65]–[67]. Thus, the communication mechanisms necessary to sustain adaptable interactions already exist in bacteria; in fact, the interaction capabilities found in some strains of social bacteria are far more sophisticated and have yet to be understood [68]. Adaptable interactions, similar to what we have suggested, may be found in other groups of simple organisms such as fish. Moreover, we suggest that performance dependent adaptable interactions exist in more complex networks, such as social networks.
Supporting Information
Local minima, maxima, and saddle points in the terrain. The black circle with the letter S marks the starting position of the swarm. Local maxima are marked with a black triangle, local minima are marked with a black x, and saddle points are marked with a blue circle. A linear approximation of the separatrix, connecting the maxima and saddle points along the gradient of the terrain, is illustrated with a dotted line. A. Contour of the terrain. Recall that mountains (in red) correspond with low concentration and that valleys (in blue) correspond with high concentration. B. colored image of the terrain.
(TIF)
The effect of the radii of interaction on interacting agents. The radii of interaction control all characteristics of the group's behavior, pattern and performance. A. Median path length as a function of the radius of alignment and attraction. Strong attraction and weak alignment cause groups to attract to their centers of mass and stay in place, harming their task performance. Strong alignment and weak attraction cause excessively high conformity in the group which again, harms performance. Intermediate values around a fixed quotient of reach optimal performance. B. Alignment decreases for values lower than the fixed quotient of . C. A weak attraction term results in high clustering by the end of the simulation almost independent of the alignment term. D. The 90th percentile path length is affected in the same manner but to a higher degree by the radii of interaction as the median path length. Simulation parameters are as in Figure 8, apart from .
(TIF)
The effect of the radii of interaction on agents with adaptable interactions. The group movement characteristics of agents with adaptable interactions remain similar for a larger range of radii of interactions than that of interacting agents. Performance drops for values in which performance of interacting agents also drops. A. Median path length as a function of the radius of alignment and attraction. Strong attraction and weak alignment cause groups to attract to their centers of mass harming their task performance, similarly to interacting agents. As opposed to interacting agents, strong alignment and weak attraction do not harm performance. B. Alignment decreases for values lower than the fixed quotient of , similarly to interacting agents. C. A weak attraction term results in high clustering almost independent of the alignment term, similarly to interacting agents. D. The 90th percentile path length is affected in the same manner but to a slightly higher degree by the radii of interaction as the median path length. Simulation parameters are as in Figure S2.
(TIF)
Supporting information. The chemical concentration map and the effect of the radii of interactions.
(DOC)
Movie of the simulation show independent agents moving towards the target. Simulation parameters are as in Figure 4.
(MP4)
Movie of the simulation show interacting agents moving collectively towards the target. Simulation parameters are as in Figure 4, .
(MP4)
Movie of the simulation show agents with adaptable interactions moving collectively towards the target. Simulation parameters are as in Figure 4.
(MP4)
Movie of the simulation shows interacting agents split and collide at the target. Simulation parameters are as in Figure 4.
(MP4)
Movie of the simulation shows agents with adaptable interactions fracture. Simulation parameters are as in Figure 4 except .
(MP4)
Movie of the simulation shows agents with adaptable interactions split and collide. Simulation parameters are as in Figure 4 except .
(MP4)
We have greatly benefited from discussions with Herbert Levine, Inbal Hecht, Eytan Ruppin, and Arnon Avron.
ReferencesConradtLRoperTJ2005Consensus decision making in animals.20449456doi:10.1016/j.tree.2005.05.008MirolloREStrogatzSH1990Synchronization of pulse-coupled biological oscillators.5016451662BuckJB1988Synchronous rhythmic flashing of fireflies. II.63265doi:10.1086/415929HalloyJSempoGCaprariGRivaultCAsadpourM2007Social integration of robots into groups of cockroaches to control self-organized choices.31811551158doi:10.1126/science.1144259LecaJBGunstNThierryBPetitO2003Distributed leadership in semifree-ranging white-faced capuchin monkeys.6610451052doi:10.1006/anbe.2003.2276SimpsonSJDesplandEHägeleBFDodgsonT2001Gregarious behavior in desert locusts is evoked by touching their back legs.9838957doi:PMC31149JaffeKDeneubourgJL1992On foraging, recruitment systems and optimum number of scouts in eusocial colonies.39201213doi:10.1007/BF01249295BeckersRDeneubourgJGossSPasteelsJ1990Collective decision making through food recruitment.37258267doi:10.1007/BF02224053CamazineSDeneubourgJ-LFranksNRSneydJTheraulazG2003Self-organization in biological systems.New JerseyPrinceton University Press558Ben-JacobESchochetOTenenbaumACohenICzirókA1994Generic modelling of cooperative growth patterns in bacterial colonies.3684649doi:10.1038/368046a0NagyMAkosZBiroDVicsekT2010Hierarchical group dynamics in pigeon flocks.464890893doi:10.1038/nature08891BeckersRDeneubourgJLGossS1992Trails and U-turns in the selection of a path by the ant Lasius niger.159397415doi:10.1016/S0022-5193(05)80686-1UvarovB1966Grasshoppers and locusts.Cambridge, , U.K.Cambridge University Press613AokiI1982A simulation study on the schooling mechanism in fish.4810811088Ben-JacobEAharonovYShapiraY2004Bacteria harnessing complexity.1239263doi:10.1017/S1479050505001596VicsekTCzirokABen-JacobECohenIShochetO1995Novel type of phase transition in a system of self-driven particles.751226doi:10.1103/PhysRevLett.75.1226CouzinIDKrauseJFranksNRLevinSA2005Effective leadership and decision-making in animal groups on the move.433513516doi:10.1038/nature03236CouzinIDKrauseJJamesRRuxtonGDFranksNR2002Collective memory and spatial sorting in animal groups.218111doi:10.1006/jtbi.2002.3065TopazCMBernoffAJLoganSToolsonW2008A model for rolling swarms of locusts.15793109doi:10.1140/epjst/e2008-00633-yBuhlJSumpterDJTCouzinIDHaleJJDesplandE2006From disorder to order in marching locusts.31214021406doi:10.1126/science.1125142GaziVPassinoKM2003Stability analysis of swarms. IEEE Trans. Automat.48692697ViscidoSVParrishJKGrunbaumD2005The effect of population size and number of influential neighbors on the emergent properties of fish schools.183347363doi:10.1016/j.ecolmodel.2004.08.019CuckerFSmaleS2007On the mathematics of emergence.2197227doi:10.1007/s11537-007-0647-xBalleriniMCabibboNCandelierRCavagnaACisbaniE2008Interaction ruling animal collective behavior depends on topological rather than metric distance: evidence from a field study.10512327doi:PMC2234121TorneyCNeufeldZCouzinID2009Context-dependent interaction leads to emergent search behavior in social aggregates.1062205522060doi:10.1073/pnas.0907929106Ben-JacobECohenIGoldingIGutnickDLTcherpakovM2000Bacterial cooperative organization under antibiotic stress.282247282doi:10.1016/S0378-4371(00)00093-5ShapiroJA1995The significances of bacterial colony patterns.17597607doi:10.1002/bies.950170706Ben-JacobECohenILevineH2000Cooperative self-organization of microorganisms.49395554Ben-JacobELevineH2006Self-engineering capabilities of bacteria.3197214doi:10.1098/rsif.2005.0089ShapiroJADworkinM1997Bacteria as multicellular organisms.New YorkOxford University Press466KaiserD2003Coupling cell movement to multicellular development in myxobacteria.14554doi:10.1038/nrmicro733DunnyGMBrickmanTJDworkinM2008Multicellular behavior in bacteria: communication, cooperation, competition and cheating.30296298doi:10.1002/bies.20740AguilarCVlamakisHLosickRKolterR2007Thinking about Bacillus subtilis as a multicellular organism.10638643doi:10.1016/j.mib.2007.09.006Ben-JacobECohenIGutnickDL1998Cooperative organization of bacterial colonies: From Genotype to Morphotype.52779806doi:10.1146/annurev.micro.52.1.779InghamCJBen-JacobE2008Swarming and complex pattern formation in Paenibacillus vortex studied by imaging and tracking cells. BMC Microbiol.83636doi:10.1186/1471-2180-8-36Ben-JacobECohenICzirókAVicsekTGutnickDL1997Chemomodulation of cellular movement, collective formation of vortices by swarming bacteria, and colonial development.238181197doi:10.1016/S0378-4371(96)00457-8KozlovskyYCohenIGoldingIBen-JacobE1999Lubricating bacteria model for branching growth of bacterial colonies.5970257035doi:10.1103/PhysRevE.59.7025CohenIGoldingIKozlovskyYBen-JacobE1998Continuous and discrete models of cooperation in complex bacterial colonies.7235247Ben-JacobEBeckerIShapiraYLevineH2004Bacterial linguistic communication and social intelligence. Trends Microbiol.12366372doi:10.1016/j.tim.2004.06.006BasslerBLLosickR2006Bacterially speaking.125237246doi:10.1016/j.cell.2006.04.001BischofsIBHugJALiuAWWolfDMArkinAP2009Complexity in bacterial cell–cell communication: Quorum signal integration and subpopulation signaling in the Bacillus subtilis phosphorelay.10664596464doi:10.1073/pnas.0810878106Ben-JacobESochetOTenebaumACohenICzirokA1994Communication regulation and control during growth of bacterial colonies.211544MillerMBBasslerBL2001Quorum sensing in bacteria.55165199doi:11544353MatsushitaMFujikawaH1990Diffusion-limited growth in bacterial colony formation.168498506doi:10.1016/0378-4371(90)90402-EBergHC1993Random walks in biology.New JerseyPrinceton University Press164BergH1990Chemotaxis of bacteria in glass capillary arrays. Escherichia coli, motility, microchannel plate, and light scattering.58919930doi:10.1016/S0006-3495(90)82436-XAdlerJ1966Chemotaxis in bacteria.153708716doi:10.1126/science.153.3737.708BergHCPurcellEM1977Physics of chemoreception.20193219doi:10.1016/S0006-3495(77)85544-6KellerEFSegelLA1971Model for chemotaxis.30225234doi:10.1016/0022-5193(71)90050-6SimonsAM2004Many wrongs: the advantage of group navigation.19453455doi:10.1016/j.tree.2004.07.001ConradtLRoperTJ2003Group decision-making in animals.421155158doi:10.1038/nature01294ListC2004Democracy in animal groups: a political science perspective.19168169doi:10.1016/j.tree.2004.02.004GrunbaumD1998Schooling as a strategy for taxis in a noisy environment.12503522doi:10.1023/A:1006574607845RosenblattF1958The perceptron: A probabilistic model for information storage and organization in the brain.65386408HopfieldJJ1982Neural networks and physical systems with emergent collective computational abilities.7925542558HollandJ1992Adaptation in natural and artificial systems.Cambridge, , MAMIT Press228HelbingDKeltschJMolnarP1997Modelling the evolution of human trail systems.3884750PoliRKennedyJBlackwellT2007Particle swarm optimization.13357doi:10.1007/s11721-007-0002-0ChazelleB2009Natural algorithms.SODA422431BanksAVincentJAnyakohaC2007A review of particle swarm optimization. Part I: background and development.6467484doi:10.1007/s11047-007-9049-5DorigoMStutzleT2004Ant colony optimization.Cambridge, , MAMIT Press305Ben-JacobESchultzD2010Bacteria determine fate by playing dice with controlled odds.1071319713198doi:10.1073/pnas.1008254107KussellELeiblerS2005Phenotypic diversity, population growth, and information in fluctuating environments.30920752078doi:10.1126/science.1114383SumpterDJT2006The principles of collective animal behaviour.361522doi:10.1098/rstb.2005.1733KellerLSuretteMG2006Communication in bacteria: an ecological and evolutionary perspective.4249258doi:10.1038/nrmicro1383DworkinM1999Fibrils as extracellular appendages of bacteria: Their role in contact-mediated cell-cell interactions in Myxococcus xanthus.21590595doi:10.1002/(SICI)1521-1878(199907)21:7<590::AID-BIES7>3.0.CO;2-EDworkinM1996Recent advances in the social and developmental biology of the myxobacteria.6070102Ben-JacobE2003Bacterial self–organization: co–enhancement of complexification and adaptability in a dynamic environment.36112831312doi:10.1098/rsta.2003.1199