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.     

A novel ACO algorithm for optimization via reinforcement and initial bias

In this paper, we introduce the MAF-ACO algorithm, which emulates the foraging behavior of ants found in nature. In addition to the usual pheromone model present in ACO algorithms, we introduce an incremental learning component. We view the components of the MAF-ACO algorithm as stochastic approximation algorithms and use the ordinary differential equation (o.d.e.) method to analyze their convergence. We examine how the local stigmergic interaction of the individual ants results in an emergent dynamic programming framework. The MAF-ACO algorithm is also applied to the multi-stage shortest path problem and the traveling salesman problem. Research of Prof. V.S. Borkar was supported in part by grant no. III.5(157)/99-ET and a J.C. Bose Fellowship from the Department of Science and Technology, Government of India.     

Path efficiency of ant foraging trails in an artificial network

In this paper we present an individual-based model describing the foraging behavior of ants moving in an artificial network of tunnels in which several interconnected paths can be used to reach a single food source. Ants lay a trail pheromone while moving in the network and this pheromone acts as a system of mass recruitment that attracts other ants in the network. The rules implemented in the model are based on measures of the decisions taken by ants at tunnel bifurcations during real experiments. The collective choice of the ants is estimated by measuring their probability to take a given path in the network. Overall, we found a good agreement between the results of the simulations and those of the experiments, showing that simple behavioral rules can lead ants to find the shortest paths in the network. The match between the experiments and the model, however, was better for nestbound than for outbound ants. A sensitivity study of the model suggests that the bias observed in the choice of the ants at asymmetrical bifurcations is a key behavior to reproduce the collective choice observed in the experiments.     

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.     

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.     

Local-based semantic navigation on a networked representation of information

The size and complexity of actual networked systems hinders the access to a global knowledge of their structure. This fact pushes the problem of navigation to suboptimal solutions, one of them being the extraction of a coherent map of the topology on which navigation takes place. In this paper, we present a Markov chain based algorithm to tag networked terms according only to their topological features. The resulting tagging is used to compute similarity between terms, providing a map of the networked information. This map supports local-based navigation techniques driven by similarity. We compare the efficiency of the resulting paths according to their length compared to that of the shortest path. Additionally we claim that the path steps towards the destination are semantically coherent. To illustrate the algorithm performance we provide some results from the Simple English Wikipedia, which amounts to several thousand of pages. The simplest greedy strategy yields over an 80% of average success rate. Furthermore, the resulting content-coherent paths most often have a cost between one- and threefold compared to shortest-path lengths.     

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.     

Community Evolution in International Migration Top1 Networks

Focusing on each country’s topmost destination/origin migration relation with other countries, this study builds top1 destination networks and top1 origin networks in order to understand their skeletal construction and community dynamics. Each top1 network covers approximately 50% of the complete migrant network stock for each decade between 1960 and 2000. We investigate the community structure by implementing the Girvan-Newman algorithm and compare the number of components and communities to illustrate their differences. We find that (i) both top1 networks (origin and destination) exhibited communities with a clear structure and a surprising evolution, although 80% edges persist between each decade; (ii) top1 destination networks focused on developed countries exhibiting shorter paths and preferring more advance countries, while top1 origin networks focused both on developed as well as more substantial developing nations that presented a longer path and more stable groups; (iii) only few countries have a decisive influence on community evolution of both top1 networks. USA took the leading position as a destination country in top1 destination networks, while China and India were the main Asian emigration countries in top1 origin networks; European countries and the Russian Federation played an important role in both.     

Mathematical and kinetic modeling of biofilm reactor based on ant colony optimization

Inverse estimation of model parameters via mathematical modeling route, known as inverse modeling (IM), is an attractive alternative approach to the experimental methods. This approach makes use of efficient optimization techniques in the course of solution of an inverse problem with the aid of measured data. In this study, a novel optimization method based on ant colony optimization (ACO), denoted by ACO-IM, is presented for inverse estimation of kinetic and film thickness parameters of biofilm models that describe an experimental fixed bed anaerobic reactor. The proposed optimization method for parameter estimation emulates the fact that ants are capable of finding the shortest path from a food source to their nest by depositing a trial of pheromone during their walk. The efficacy of the ACO-IM for numerical estimation of bio-kinetic parameters is demonstrated through its application for the anaerobic treatment of industry wastewater in a fixed bed biofilm process. The results explain the rigorousness of mathematical models, the form of kinetic and film thickness models and the type of packing to be used with the biofilm process for accurate determination of kinetic and film thickness parameters so as to ensure reliable predictive performance of the biofilm reactor models.     

Reactive Searching and Infotaxis in Odor Source Localization

Male moths aiming to locate pheromone-releasing females rely on stimulus-adapted search maneuvers complicated by a discontinuous distribution of pheromone patches. They alternate sequences of upwind surge when perceiving the pheromone and cross- or downwind casting when the odor is lost. We compare four search strategies: three reactive versus one cognitive. The former consist of pre-programmed movement sequences triggered by pheromone detections while the latter uses Bayesian inference to build spatial probability maps. Based on the analysis of triphasic responses of antennal lobe neurons (On, inhibition, Off), we propose three reactive strategies. One combines upwind surge (representing the On response to a pheromone detection) and spiral casting, only. The other two additionally include crosswind (zigzag) casting representing the Off phase. As cognitive strategy we use the infotaxis algorithm which was developed for searching in a turbulent medium. Detection events in the electroantennogram of a moth attached to a robot indirectly control this cyborg, depending on the strategy in use. The recorded trajectories are analyzed with regard to success rates, efficiency, and other features. In addition, we qualitatively compare our robotic trajectories to behavioral search paths. Reactive searching is more efficient (yielding shorter trajectories) for higher pheromone doses whereas cognitive searching works better for lower doses. With respect to our experimental conditions (2 m from starting position to pheromone source), reactive searching with crosswind zigzag yields the shortest trajectories (for comparable success rates). Assuming that the neuronal Off response represents a short-term memory, zigzagging is an efficient movement to relocate a recently lost pheromone plume. Accordingly, such reactive strategies offer an interesting alternative to complex cognitive searching.     

An experimental analysis of design choices of multi-objective ant colony optimization algorithms

There have been several proposals on how to apply the ant colony optimization (ACO) metaheuristic to multi-objective combinatorial optimization problems (MOCOPs). This paper proposes a new formulation of these multi-objective ant colony optimization (MOACO) algorithms. This formulation is based on adding specific algorithm components for tackling multiple objectives to the basic ACO metaheuristic. Examples of these components are how to represent multiple objectives using pheromone and heuristic information, how to select the best solutions for updating the pheromone information, and how to define and use weights to aggregate the different objectives. This formulation reveals more similarities than previously thought in the design choices made in existing MOACO algorithms. The main contribution of this paper is an experimental analysis of how particular design choices affect the quality and the shape of the Pareto front approximations generated by each MOACO algorithm. This study provides general guidelines to understand how MOACO algorithms work, and how to improve their design.     

Internal Node and Shortcut Based Routing with Guaranteed Delivery in Wireless Networks

Several localized position based routing algorithms for wireless networks were described recently. In greedy routing algorithm (that has close performance to the shortest path algorithm, if successful), sender or node S currently holding the message m forwards m to one of its neighbors that is the closest to destination. The algorithm fails if S does not have any neighbor that is closer to destination than S. FACE algorithm guarantees the delivery of m if the network, modeled by unit graph, is connected. GFG algorithm combines greedy and FACE algorithms. Greedy algorithm is applied as long as possible, until delivery or a failure. In case of failure, the algorithm switches to FACE algorithm until a node closer to destination than last failure node is found, at which point greedy algorithm is applied again. Past traffic does not need to be memorized at nodes. In this paper we further improve the performance of GFG algorithm, by reducing its average hop count. First we improve the FACE algorithm by adding a sooner-back procedure for earlier escape from FACE mode. Then we perform a shortcut procedure at each forwarding node S. Node S uses the local information available to calculate as many hops as possible and forwards the packet to the last known hop directly instead of forwarding it to the next hop. The second improvement is based on the concept of dominating sets. Each node in the network is classified as internal or not, based on geographic position of its neighboring nodes. The network of internal nodes defines a connected dominating set, i.e., and each node must be either internal or directly connected to an internal node. In addition, internal nodes are connected. We apply several existing definitions of internal nodes, namely the concepts of intermediate, inter-gateway and gateway nodes. We propose to run GFG routing, enhanced by shortcut procedure, on the dominating set, except possibly the first and last hops. The performance of proposed algorithms is measured by comparing its average hop count with hop count of the basic GFG algorithm and the benchmark shortest path algorithm, and very significant improvements were obtained for low degree graphs. More precisely, we obtained localized routing algorithm that guarantees delivery and has very low excess in terms of hop count compared to the shortest path algorithm. The experimental data show that the length of additional path (in excess of shortest path length) can be reduced to about half of that of existing GFG algorithm.     

A fast algorithm for computing geodesic distances in tree space

Comparing and computing distances between phylogenetic trees are important biological problems, especially for models where edge lengths play an important role. The geodesic distance measure between two phylogenetic trees with edge lengths is the length of the shortest path between them in the continuous tree space introduced by Billera, Holmes, and Vogtmann. This tree space provides a powerful tool for studying and comparing phylogenetic trees, both in exhibiting a natural distance measure and in providing a euclidean-like structure for solving optimization problems on trees. An important open problem is to find a polynomial time algorithm for finding geodesics in tree space. This paper gives such an algorithm, which starts with a simple initial path and moves through a series of successively shorter paths until the geodesic is attained.     

Better tired than lost: Turtle ant trail networks favor coherence over short edges

Creating a routing backbone is a fundamental problem in both biology and engineering. The routing backbone of the trail networks of arboreal turtle ants (Cephalotes goniodontus) connects many nests and food sources using trail pheromone deposited by ants as they walk. Unlike species that forage on the ground, the trail networks of arboreal ants are constrained by the vegetation. We examined what objectives the trail networks meet by comparing the observed ant trail networks with networks of random, hypothetical trail networks in the same surrounding vegetation and with trails optimized for four objectives: minimizing path length, minimizing average edge length, minimizing number of nodes, and minimizing opportunities to get lost. The ants’ trails minimized path length by minimizing the number of nodes traversed rather than choosing short edges. In addition, the ants’ trails reduced the opportunity for ants to get lost at each node, favoring nodes with 3D configurations most likely to be reinforced by pheromone. Thus, rather than finding the shortest edges, turtle ant trail networks take advantage of natural variation in the environment to favor coherence, keeping the ants together on the trails.     

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.     

Food collection and response to pheromones in an ant species exposed to electromagnetic radiation

We used the ant species Myrmica sabuleti as a model to study the impact of electromagnetic waves on social insects' response to their pheromones and their food collection. We quantified M. sabuleti workers' response to their trail, area marking and alarm pheromone under normal conditions. Then, we quantified the same responses while under the influence of electromagnetic waves. Under such an influence, ants followed trails for only short distances, no longer arrived at marked areas and no longer orientated themselves to a source of alarm pheromone. Also when exposed to electromagnetic waves, ants became unable to return to their nest and recruit congeners; therefore, the number of ants collecting food increases only slightly and slowly. After 180 h of exposure, their colonies deteriorated. Electromagnetic radiation obviously affects social insects' behavior and physiology.     

Cornicle length in Macrosiphini aphids: a comparison of ecological traits

Abstract 1. Aphids often emit cornicle droplets when attacked by predators. While the function of cornicle droplets has long been debated (i.e. mechanical protection vs. chemical signalling), it is not understood why aphid species have cornicles of different lengths.
2. It was hypothesised that aphids living in more scattered colonies have longer cornicles to scent-mark predators with cornicle droplets containing alarm pheromone, so that clone-mates are provided with advanced warning of a threat, even if not at the predation site. To test this hypothesis, multiple regression analyses were used, due to a lack of phylogenetic information on these taxa, to address which ecological traits (amount of wax on an aphid, degree of colony aggregation, feeding shelter, ant attendance) are correlated with cornicle length.
3. Aphids living in dense colonies tended to have shorter cornicles than aphids living in more scattered colonies. Also, aphids with more protection (i.e. wax) on their bodies had shorter cornicles. Aphids also tended to have shorter cornicles when tended by ants. The presence of a feeding shelter was not a good predictor of cornicle length.
4. It is suggested that longer cornicles function to scent-mark predators with alarm pheromone to increase the inclusive fitness of a clone; however the negative correlation between the amount of individual protection, and also ant attendance, and cornicle length argues for a trade-off between different forms of defence.     

Self-organized cooperation between robotic swarms

We study self-organized cooperation between heterogeneous robotic swarms. The robots of each swarm play distinct roles based on their different characteristics. We investigate how the use of simple local interactions between the robots of the different swarms can let the swarms cooperate in order to solve complex tasks. We focus on an indoor navigation task, in which we use a swarm of wheeled robots, called foot-bots, and a swarm of flying robots that can attach to the ceiling, called eye-bots. The task of the foot-bots is to move back and forth between a source and a target location. The role of the eye-bots is to guide foot-bots: they choose positions at the ceiling and from there give local directional instructions to foot-bots passing by. To obtain efficient paths for foot-bot navigation, eye-bots need on the one hand to choose good positions and on the other hand learn the right instructions to give. We investigate each of these aspects. Our solution is based on a process of mutual adaptation, in which foot-bots execute instructions given by eye-bots, and eye-bots observe the behavior of foot-bots to adapt their position and the instructions they give. Our approach is inspired by pheromone mediated navigation of ants, as eye-bots serve as stigmergic markers for foot-bot navigation. Through simulation, we show how this system is able to find efficient paths in complex environments, and to display different kinds of complex and scalable self-organized behaviors, such as shortest path finding and automatic traffic spreading.     

Pheromone puff trajectory and upwind flight of male gypsy moths in a forest

ABSTRACT. Pheromone released from a point source beneath a forest canopy usually follows a non-linear trajectory as demonstrated by the paths of small, neutrally-buoyant, helium-filled balloons or puffs of smoke. Mark-recapture experiments show that few male gypsy moths ( Lymantria dispar L.) follow a pheromone plume over distances greater than 80 m even though they can easily detect pheromone at that distance as indicated by wingfanning assay. The directional consistency of successive puffs of pheromone appears more important than the linearity of their trajectories in enabling males to locate a pheromone source.     

A new distance measure for comparing sequence profiles based on path lengths along an entropy surface

We describe a new distance measure for comparing DNA sequence profiles. For this measure, columns in a multiple alignment are treated as character frequency vectors (sum of the frequencies equal to one). The distance between two vectors is based on minimum path length along an entropy surface. Path length is estimated using a random graph generated on the entropy surface and Dijkstra's algorithm for all shortest paths to a source. We use the new distance measure to analyze similarities within familes of tandem repeats in the C. elegans genome and show that this new measure gives more accurate refinement of family relationships than a method based on comparing consensus sequences.