Do Ants Need to Estimate the Geometrical Properties of Trail Bifurcations to Find an Efficient Route? A Swarm Robotics Test Bed

Interactions between individuals and the structure of their environment play a crucial role in shaping self-organized collective behaviors. Recent studies have shown that ants crossing asymmetrical bifurcations in a network of galleries tend to follow the branch that deviates the least from their incoming direction. At the collective level, the combination of this tendency and the pheromone-based recruitment results in a greater likelihood of selecting the shortest path between the colony''s nest and a food source in a network containing asymmetrical bifurcations. It was not clear however what the origin of this behavioral bias is. Here we propose that it results from a simple interaction between the behavior of the ants and the geometry of the network, and that it does not require the ability to measure the angle of the bifurcation. We tested this hypothesis using groups of ant-like robots whose perceptual and cognitive abilities can be fully specified. We programmed them only to lay down and follow light trails, avoid obstacles and move according to a correlated random walk, but not to use more sophisticated orientation methods. We recorded the behavior of the robots in networks of galleries presenting either only symmetrical bifurcations or a combination of symmetrical and asymmetrical bifurcations. Individual robots displayed the same pattern of branch choice as individual ants when crossing a bifurcation, suggesting that ants do not actually measure the geometry of the bifurcations when travelling along a pheromone trail. Finally at the collective level, the group of robots was more likely to select one of the possible shorter paths between two designated areas when moving in an asymmetrical network, as observed in ants. This study reveals the importance of the shape of trail networks for foraging in ants and emphasizes the underestimated role of the geometrical properties of transportation networks in general.     

Trail formation in ants. A generalized Polya urn process

Faced with a choice of paths, an ant chooses a path with a higher concentration of pheromone. Subsequently, it drops pheromone on the path chosen. The reinforcement of the pheromone-following behavior favors the selection of an initially discovered path as the preferred path. This may cause a long path to emerge as the preferred path, were it discovered earlier than a shorter path. However, the shortness of the shorter path offsets some of the pheromone accumulated on the initially discovered longer path. In this paper, we model the trail formation behavior as a generalized Polya urn process. For k equal length paths, we give the distribution of pheromone at any time and highlight its sole dependence on the initial pheromone concentrations on paths. Additionally, we propose a method to incorporate the lengths of paths in the urn process and derive how the pheromone distribution alters on its inclusion. Analytically, we show that it is possible, under certain conditions, to reverse the initial bias that may be present in favor of paths that were discovered prior to the discovery of more efficient (shorter) paths. This addresses the Plasticity–Stability dilemma for ants, by laying out the conditions under which the system will remain stable or become plastic and change the path. Finally, we validate our analysis and results using simulations.     

Individual rules for trail pattern formation in Argentine ants (Linepithema humile)

We studied the formation of trail patterns by Argentine ants exploring an empty arena. Using a novel imaging and analysis technique we estimated pheromone concentrations at all spatial positions in the experimental arena and at different times. Then we derived the response function of individual ants to pheromone concentrations by looking at correlations between concentrations and changes in speed or direction of the ants. Ants were found to turn in response to local pheromone concentrations, while their speed was largely unaffected by these concentrations. Ants did not integrate pheromone concentrations over time, with the concentration of pheromone in a 1 cm radius in front of the ant determining the turning angle. The response to pheromone was found to follow a Weber's Law, such that the difference between quantities of pheromone on the two sides of the ant divided by their sum determines the magnitude of the turning angle. This proportional response is in apparent contradiction with the well-established non-linear choice function used in the literature to model the results of binary bridge experiments in ant colonies (Deneubourg et al. 1990). However, agent based simulations implementing the Weber's Law response function led to the formation of trails and reproduced results reported in the literature. We show analytically that a sigmoidal response, analogous to that in the classical Deneubourg model for collective decision making, can be derived from the individual Weber-type response to pheromone concentrations that we have established in our experiments when directional noise around the preferred direction of movement of the ants is assumed.     

Modeling,analysis and simulation of ant-based network routing protocols

Using the metaphor of swarm intelligence, ant-based routing protocols deploy control packets that behave like ants to discover and optimize routes between pairs of nodes. These ant-based routing protocols provide an elegant, scalable solution to the routing problem for both wired and mobile ad hoc networks. The routing problem is highly nonlinear because the control packets alter the local routing tables as they are routed through the network. We mathematically map the local rules by which the routing tables are altered to the dynamics of the entire networks. Using dynamical systems theory, we map local protocol rules to full network performance, which helps us understand the impact of protocol parameters on network performance. In this paper, we systematically derive and analyze global models for simple ant-based routing protocols using both pheromone deposition and evaporation. In particular, we develop a stochastic model by modeling the probability density of ants over the network. The model is validated by comparing equilibrium pheromone levels produced by the global analysis to results obtained from simulation studies. We use both a Matlab simulation with ideal communications and a QualNet simulation with realistic communication models. Using these analytic and computational methods, we map out a complete phase diagram of network behavior over a small multipath network. We show the existence of both stable and unstable (inaccessible) routing solutions having varying properties of efficiency and redundancy depending upon the routing parameters. Finally, we apply these techniques to a larger 50-node network and show that the design principles acquired from studying the small model network extend to larger networks.     

Decay rates of attractive and repellent pheromones in an ant foraging trail network

Pharaoh’s ants (Monomorium pharaonis) use at least three types of foraging trail pheromone: a long-lasting attractive pheromone and two short-lived pheromones, one attractive and one repellent. We measured the decay rates of the behavioural response of ant workers at a trail bifurcation to trail substrate marked with either repellent or attractive short-lived pheromones. Our results show that the repellent pheromone effect lasts more than twice as long as the attractive pheromone effect (78 min versus 33 min). Although the effects of these two pheromones decay at approximately the same rate, the initial effect of the repellent pheromone on branch choice is almost twice that of the attractive pheromone (48% versus 25% above control). We hypothesise that the two pheromones have complementary but distinct roles, with the repellent pheromone specifically directing ants at bifurcations, while the attractive pheromone guides ants along the entire trail. Received 15 November 2007; revised 7 March 2008; accepted 18 March 2008.     

From nonlinearity to optimality: pheromone trail foraging by ants

Pheromone trails laid by foraging ants serve as a positive feedback mechanism for the sharing of information about food sources. This feedback is nonlinear, in that ants do not react in a proportionate manner to the amount of pheromone deposited. Instead, strong trails elicit disproportionately stronger responses than weak trails. Such nonlinearity has important implications for how a colony distributes its workforce, when confronted with a choice of food sources. We investigated how colonies of the Pharaoh's ant, Monomorium pharaonis, distribute their workforce when offered a choice of two food sources of differing energetic value. By developing a nonlinear differential equation model of trail foraging, and comparing model with experiments, we examined how the ants allocate their workforce between the two food sources. In this allocation, the most profitable feeder (i.e. the feeder with the highest concentration of sugar syrup) was usually exploited by the majority of ants. The particular form of the nonlinear feedback in trail foraging means that when we offered the ants a choice between two feeders of equal profitability, foraging was biased to the feeder with the highest initial number of visitors. Taken together, our experiments illuminate how pheromones provide a mechanism whereby ants can efficiently allocate their workforce among the available food sources without centralized control.     

Symmetry Breaking on Density in Escaping Ants: Experiment and Alarm Pheromone Model

The symmetry breaking observed in nature is fascinating. This symmetry breaking is observed in both human crowds and ant colonies. In such cases, when escaping from a closed space with two symmetrically located exits, one exit is used more often than the other. Group size and density have been reported as having no significant impact on symmetry breaking, and the alignment rule has been used to model symmetry breaking. Density usually plays important roles in collective behavior. However, density is not well-studied in symmetry breaking, which forms the major basis of this paper. The experiment described in this paper on an ant colony displays an increase then decrease of symmetry breaking versus ant density. This result suggests that a Vicsek-like model with an alignment rule may not be the correct model for escaping ants. Based on biological facts that ants use pheromones to communicate, rather than seeing how other individuals move, we propose a simple yet effective alarm pheromone model. The model results agree well with the experimental outcomes. As a measure, this paper redefines symmetry breaking as the collective asymmetry by deducing the random fluctuations. This research indicates that ants deposit and respond to the alarm pheromone, and the accumulation of this biased information sharing leads to symmetry breaking, which suggests true fundamental rules of collective escape behavior in ants.     

The Effect of Trail Pheromone and Path Confinement on Learning of Complex Routes in the Ant Lasius niger

Route learning is key to the survival of many central place foragers, such as bees and many ants. For ants which lay pheromone trails, the presence of a trail may act as an important source of information about whether an error has been made. The presence of trail pheromone has been demonstrated to support route learning, and the effect of pheromones on route choice have been reported to persist even after the pheromones have been removed. This could be explained in two ways: the pheromone may constrain the ants onto the correct route, thus preventing errors and aiding learning. Alternatively, the pheromones may act as a ‘reassurance’, signalling that the learner is on the right path and that learning the path is worthwhile. Here, we disentangle pheromone presence from route confinement in order to test these hypotheses, using the ant Lasius niger as a model. Unexpectedly, we did not find any evidence that pheromones support route learning. Indeed, there was no evidence that ants confined to the correct route learned at all. Thus, while we cannot support the ‘reassurance’ hypothesis, we can rule out the ‘confinement’ hypothesis. Other findings, such as a reduction in pheromone deposition in the presence of trail pheromones, are remarkably consistent with previous experiments. As previously reported, ants which make errors on their outward journey upregulate pheromone deposition on their return. Surprisingly, ants which would go on to make an error down-regulate pheromone deposition on their outward journey, hinting at a capacity for ants to gauge the quality of their own memories.     

The Regulation of Ant Colony Foraging Activity without Spatial Information

Many dynamical networks, such as the ones that produce the collective behavior of social insects, operate without any central control, instead arising from local interactions among individuals. A well-studied example is the formation of recruitment trails in ant colonies, but many ant species do not use pheromone trails. We present a model of the regulation of foraging by harvester ant (Pogonomyrmex barbatus) colonies. This species forages for scattered seeds that one ant can retrieve on its own, so there is no need for spatial information such as pheromone trails that lead ants to specific locations. Previous work shows that colony foraging activity, the rate at which ants go out to search individually for seeds, is regulated in response to current food availability throughout the colony's foraging area. Ants use the rate of brief antennal contacts inside the nest between foragers returning with food and outgoing foragers available to leave the nest on the next foraging trip. Here we present a feedback-based algorithm that captures the main features of data from field experiments in which the rate of returning foragers was manipulated. The algorithm draws on our finding that the distribution of intervals between successive ants returning to the nest is a Poisson process. We fitted the parameter that estimates the effect of each returning forager on the rate at which outgoing foragers leave the nest. We found that correlations between observed rates of returning foragers and simulated rates of outgoing foragers, using our model, were similar to those in the data. Our simple stochastic model shows how the regulation of ant colony foraging can operate without spatial information, describing a process at the level of individual ants that predicts the overall foraging activity of the colony.     

Artificial pheromone for path selection by a foraging swarm of robots

Foraging robots involved in a search and retrieval task may create paths to navigate faster in their environment. In this context, a swarm of robots that has found several resources and created different paths may benefit strongly from path selection. Path selection enhances the foraging behavior by allowing the swarm to focus on the most profitable resource with the possibility for unused robots to stop participating in the path maintenance and to switch to another task. In order to achieve path selection, we implement virtual ants that lay artificial pheromone inside a network of robots. Virtual ants are local messages transmitted by robots; they travel along chains of robots and deposit artificial pheromone on the robots that are literally forming the chain and indicating the path. The concentration of artificial pheromone on the robots allows them to decide whether they are part of a selected path. We parameterize the mechanism with a mathematical model and provide an experimental validation using a swarm of 20 real robots. We show that our mechanism favors the selection of the closest resource is able to select a new path if a selected resource becomes unavailable and selects a newly detected and better resource when possible. As robots use very simple messages and behaviors, the system would be particularly well suited for swarms of microrobots with minimal abilities.     

An agent-based model to investigate the roles of attractive and repellent pheromones in ant decision making during foraging

Pharaoh's ants organise their foraging system using three types of trail pheromone. All previous foraging models based on specific ant foraging systems have assumed that only a single attractive pheromone is used. Here we present an agent-based model based on trail choice at a trail bifurcation within the foraging trail network of a Pharaoh's ant colony which includes both attractive (positive) and repellent (negative) trail pheromones. Experiments have previously shown that Pharaoh's ants use both types of pheromone. We investigate how the repellent pheromone affects trail choice and foraging success in our simulated foraging system. We find that both the repellent and attractive pheromones have a role in trail choice, and that the repellent pheromone prevents random fluctuations which could otherwise lead to a positive feedback loop causing the colony to concentrate its foraging on the unrewarding trail. An emergent feature of the model is a high level of variability in the level of repellent pheromone on the unrewarding branch. This is caused by the repellent pheromone exerting negative feedback on its own deposition. We also investigate the dynamic situation where the location of the food is changed after foraging trails are established. We find that the repellent pheromone has a key role in enabling the colony to refocus the foraging effort to the new location. Our results show that having a repellent pheromone is adaptive, as it increases the robustness and flexibility of the colony's overall foraging response.     

Modelling foraging ants in a dynamic and confined environment

In social insects, the superposition of simple individual behavioral rules leads to the emergence of complex collective patterns and helps solve difficult problems inherent to surviving in hostile habitats. Modelling ant colony foraging reveals strategies arising from the insects’ self-organization and helps develop of new computational strategies in order to solve complex problems. This paper presents advances in modelling ants’ behavior when foraging in a confined and dynamic environment, based on experiments with the Argentine ant Linepithema humile in a relatively complex artificial network. We propose a model which overcomes the problem of stagnation observed in earlier models by taking into account additional biological aspects, by using non-linear functions for the deposit, perception and evaporation of pheromone, and by introducing new mechanisms to represent randomness and the exploratory behavior of the ants.     

The effect of a non-uniform turning kernel on ant trail morphology

An ordinary differential equation model is constructed for the formation of pheromone trails by ants on a pre-determined network. At each junction of the trails the probability that an ant will turn through any particular angle is given by a turning kernel. We prove analytically using analogies with thermodynamics that turning behaviour determines trail morphology when the turning kernel is steep. We conjecture that this is also true in general for non-uniform turning kernels and present numerical simulations as evidence. Using this conjecture we show the existence of three types of collective foraging: individuals exploring without the use of a trail network, and two distinct types of trail networks; one that consists of low pheromone concentration trails that bend, branch and dissipate and one that consists of high pheromone concentration, straight, unbranched trails. We show that the form of the pheromone response function is crucial in determining the existence and stability of the steady states corresponding to these three foraging strategies, and examine the bifurcations between different trail morphologies as a function of turning kernel steepness for a particular response function.Revised version: 25 December 2002     

Ants find the shortest path: a mathematical proof

In the most basic application of Ant Colony Optimization (ACO), a set of artificial ants find the shortest path between a source and a destination. Ants deposit pheromone on paths they take, preferring paths that have more pheromone on them. Since shorter paths are traversed faster, more pheromone accumulates on them in a given time, attracting more ants and leading to reinforcement of the pheromone trail on shorter paths. This is a positive feedback process that can also cause trails to persist on longer paths, even when a shorter path becomes available. To counteract this persistence on a longer path, ACO algorithms employ remedial measures, such as using negative feedback in the form of uniform evaporation on all paths. Obtaining high performance in ACO algorithms typically requires fine tuning several parameters that govern pheromone deposition and removal. This paper proposes a new ACO algorithm, called EigenAnt, for finding the shortest path between a source and a destination, based on selective pheromone removal that occurs only on the path that is actually chosen for each trip. We prove that the shortest path is the only stable equilibrium for EigenAnt, which means that it is maintained for arbitrary initial pheromone concentrations on paths, and even when path lengths change with time. The EigenAnt algorithm uses only two parameters and does not require them to be finely tuned. Simulations that illustrate these properties are provided.     

Two-category model of task allocation with application to ant societies

In many network models of interacting units such as cells or insects, the coupling coefficients between units are independent of the state of the units. Here we analyze the temporal behavior of units that can switch between two 'category' states according to rules that involve category-dependent coupling coefficients. The behaviors of the category populations resulting from the asynchronous random updating of units are first classified according to the signs of the coupling coefficients using numerical simulations. They range from isolated fixed points to lines of fixed points and stochastic attractors. These behaviors are then explained analytically using iterated function systems and birth-death jump processes. The main inspiration for our work comes from studies of non-hierarchical task allocation in, e.g., harvester ant colonies where temporal fluctuations in the numbers of ants engaged in various tasks occur as circumstances require and depend on interactions between ants. We identify interaction types that produce quick recovery from perturbations to an asymptotic behavior whose characteristics are function of the coupling coefficients between ants as well as between ants and their environment. We also compute analytically the probability density of the population numbers, and show that perturbations in our model decay twice as fast as in a model with random switching dynamics. A subset of the interaction types between ants yields intrinsic stochastic asymptotic behaviors which could account for some of the experimentally observed fluctuations. Such noisy trajectories are shown to be random walks with state-dependent biases in the 'category population' phase space. With an external stimulus, the parameters of the category-switching rules become time-dependent. Depending on the growth rate of the stimulus in comparison to its population-dependent decay rate, the dynamics may qualitatively differ from the case without stimulus. Our simple two-category model provides a framework for understanding the rich variety of behaviors in network dynamics with state-dependent coupling coefficients, and especially in task allocation processes with many tasks.     

The Behavior of <Emphasis Type="Italic">Acromyrmex crassispinus</Emphasis> (Hymenoptera: Formicidae) on Trail Bifurcations and the Influence of Ant Flow on Error Rates of Nestbound Laden Workers

Ants are ordinarily faced with a succession of bifurcations along their foraging networks. Given that there is no directionality in pheromone trails, each bifurcation is potentially an opportunity for error in the trajectory of laden workers to the nest, which could entail considerable inefficiencies in the transportation of food to the colony. Leaf-cutting ants (Atta and Acromyrmex) commonly show intense traffic and complex foraging trail systems, which make them ideal organisms to study worker behavior in trail bifurcations. The behavior of leaf-cutting ants of the genus Acromyrmex in trail bifurcations is still largely unexplored. Thus, this study aimed to assess the behavior of Acromyrmex crassispinus workers on trail bifurcations and to investigate whether differences in ant flow on foraging trails influence the error rate of nestbound laden workers at trail bifurcation. There was a negative relationship between ant flow and error rate of nestbound laden workers. Most workers walked in the central part of the foraging trails but occupied a broader area of the foraging trail when the ant flow was high. The results of this study provide valuable insight into the organization of traffic flow in A. crassispinus and its impacts on the foraging strategy of the species.     

Self-organized lane formation and optimized traffic flow in army ants

We show how the movement rules of individual ants on trails can lead to a collective choice of direction and the formation of distinct traffic lanes that minimize congestion. We develop and evaluate the results of a new model with a quantitative study of the behaviour of the army ant Eciton burchelli. Colonies of this species have up to 200 000 foragers and transport more than 3000 prey items per hour over raiding columns that exceed 100 m. It is an ideal species in which to test the predictions of our model because it forms pheromone trails that are densely populated with very swift ants. The model explores the influences of turning rates and local perception on traffic flow. The behaviour of real army ants is such that they occupy the specific region of parameter space in which lanes form and traffic flow is maximized.     

Traffic dynamics of the leaf-cutting ant, Atta cephalotes

Colonies of Atta cephalotes (Myrmicinae: Formicidae) construct cleared paths between their nest and the vegetation sources at which they harvest leaf tissue. Here, we employ ideas from traffic engineering to study streams of laden and unladen ants on these paths. The relationship between average traffic speed and the concentration of workers on the road surface follows a relationship similar to what is expected by analogy to fluid dynamics. Although the traffic is composed of eusocial organisms with a common interest in group success, the coarse-grained behavior of Atta traffic displays little more coordination than a moving fluid. The relationship between speed and concentration implies that maximum flow rates (which are likely to be closely tied to colony-level rates of resource acquisition) occur at a relatively high concentration that keeps individual speeds well below their "free flow" maximum. We predict that this optimal concentration will characterize peak traffic throughout a trail network, and we propose a simple behavioral mechanism that would allow trails to be cleared to the correct width to provide the optimal concentration. Collisions (including encounters for antennation) are common in leaf-cutting ant traffic because traffic is not segregated into unidirectional streams. Nonetheless, we find a counterintuitive suggestion that flow rates (with concentration differences statistically removed) are higher when traffic is near a 50:50 mix of outbound and returning ants than when it contains majority flows in a single direction. Mixed-direction traffic may help disperse laden ants with reduced agility, thereby preventing inhomogeneities in the traffic stream that could clog the trail.     

Effect of Trail Bifurcation Asymmetry and Pheromone Presence or Absence on Trail Choice by Lasius niger Ants

During foraging, ant workers are known to make use of multiple information sources, such as private information (personal memory) and social information (trail pheromones). Environmental effects on foraging, and how these interact with other information sources, have, however, been little studied. One environmental effect is trail bifurcation asymmetry. Ants forage on branching trail networks and must often decide which branch to take at a junction (bifurcation). This is an important decision, as finding food sources relies on making the correct choices at bifurcations. Bifurcation angle may provide important information when making this choice. We used a Y‐maze with a pivoting 90° bifurcation to study trail choice of Lasius niger foragers at varying branch asymmetries (0°, [both branches 45° from straight ahead], 30° [branches at 30° and 60° from straight ahead], 45°, 60° and 90° [one branch straight ahead, the other at 90°]). The experiment was carried out either with equal amounts of trail pheromone on both branches of the bifurcation or with pheromone present on only one branch. Our results show that with equal pheromone, trail asymmetry has a significant effect on trail choice. Ants preferentially follow the branch deviating least from straight, and this effect increases as asymmetry increases (47% at 0°, 54% at 30°, 57% at 45°, 66% at 60° and 73% at 90°). However, when pheromone is only present on one branch, the graded effect of asymmetry disappears. Overall, however, there is an effect of asymmetry as the preference of ants for the pheromone‐marked branch over the unmarked branch is reduced from 65%, when it is the less deviating branch, to 53%, when it is the more deviating branch. These results demonstrate that trail asymmetry influences ant decision‐making at bifurcations and that this information interacts with trail pheromone presence in a non‐hierarchical manner.     

Multi-Objective Ant Colony Optimization Based on the Physarum-Inspired Mathematical Model for Bi-Objective Traveling Salesman Problems

Bi-objective Traveling Salesman Problem (bTSP) is an important field in the operations research, its solutions can be widely applied in the real world. Many researches of Multi-objective Ant Colony Optimization (MOACOs) have been proposed to solve bTSPs. However, most of MOACOs suffer premature convergence. This paper proposes an optimization strategy for MOACOs by optimizing the initialization of pheromone matrix with the prior knowledge of Physarum-inspired Mathematical Model (PMM). PMM can find the shortest route between two nodes based on the positive feedback mechanism. The optimized algorithms, named as iPM-MOACOs, can enhance the pheromone in the short paths and promote the search ability of ants. A series of experiments are conducted and experimental results show that the proposed strategy can achieve a better compromise solution than the original MOACOs for solving bTSPs.