skip to main content
Explore Scholarly Publications and Datasets in the NSF-PAR

Title: A Model for Ant Trail Formation and its Convergence Properties
We introduce a model for ant trail formation, building upon previous work on biologically feasible local algorithms that plausibly describe how ants maintain trail networks. The model is a variant of a reinforced random walk on a directed graph, where ants lay pheromone on edges as they traverse them and the next edge to traverse is chosen based on the level of pheromone; this pheromone decays with time. There is a bidirectional flow of ants in the network: the forward flow proceeds along forward edges from source (e.g. the nest) to sink (e.g. a food source), and the backward flow in the opposite direction. Some fraction of ants are lost as they pass through each node (modeling the loss of ants due to exploration observed in the field). We initiate a theoretical study of this model. We note that ant navigation has inspired the field of ant colony optimization, heuristics that have been applied to several combinatorial optimization problems; however the algorithms developed there are considerably more complex and not constrained to being biologically feasible. We first consider the linear decision rule, where the flow divides itself among the next set of edges in proportion to their pheromone level. Here, more » we show that the process converges to the path with minimum leakage when the forward and backward flows do not change over time. On the other hand, when the forward and backward flows increase over time (caused by positive reinforcement from the discovery of a food source, for example), we show that the process converges to the shortest path. These results are for graphs consisting of two parallel paths (a case that has been investigated before in experiments). Through simulations, we show that these results hold for more general graphs drawn from various random graph models; proving this convergence in the general case is an interesting open problem. Further, to understand the behaviour of other decision rules beyond the linear rule, we consider a general family of decision rules. For this family, we show that there is no advantage of using a non-linear decision rule, if the goal is to find the shortest or the minimum leakage path. We also show that bidirectional flow is necessary for convergence to such paths. Our results provide a plausible explanation for field observations, and open up new avenues for further theoretical and experimental investigation. « less
Authors:
; ; ;
Award ID(s):
1813049 1704417
Publication Date:
NSF-PAR ID:
10275100
Journal Name:
12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; ; ( , PLoS computational biology)
    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.
  2. ( )
    Abstract
    <p>This data set contains 194778 quasireaction subgraphs extracted from CHO transition networks with 2-6 non-hydrogen atoms (CxHyOz, 2 &lt;&#61; x &#43; z &lt;&#61; 6).</p> <p>The complete table of subgraphs (including file locations) is in CHO-6-atoms-subgraphs.csv file. The subgraphs are in GraphML format (http://graphml.graphdrawing.org) and are compressed using bzip2. All subgraphs are undirected and unweighted. The reactant and product nodes (initial and final) are labeled in the &#34;type&#34; node attribute. The nodes are represented as multi-molecule SMILES strings. The edges are labeled by the reaction rules in SMARTS representation. The forward and backward reading of the SMARTS string should be considered equivalent.</p> <p>The generation and analysis of this data set is described in<br /> D. Rappoport, Statistics and Bias-Free Sampling of Reaction Mechanisms from Reaction Network Models, 2023, submitted. Preprint at ChemrXiv, DOI: 10.26434/chemrxiv-2023-wltcr</p> <p>Simulation parameters<br /> - CHO networks constructed using polar bond break/bond formation rule set for CHO.<br /> - High-energy nodes were excluded using the following rules:<br />   (i) more than 3 rings, (ii) triple and allene bonds in rings, (iii) double bonds at<br />   bridge atoms,(iv) double bonds in fused 3-membered rings.<br /> - Neutral nodes were defined as containing only neutral molecules.<br />More>>
  3. ; ; ; ( , Swarm Intelligence)
    Abstract

    Biological transportation networks must balance competing functional priorities. The self-organizing mechanisms used to generate such networks have inspired scalable algorithms to construct and maintain low-cost and efficient human-designed transport networks. The pheromone-based trail networks of ants have been especially valuable in this regard. Here, we use turtle ants as our focal system: In contrast to the ant species usually used as models for self-organized networks, these ants live in a spatially constrained arboreal environment where both nesting options and connecting pathways are limited. Thus, they must solve a distinct set of challenges which resemble those faced by human transport engineers constrained by existing infrastructure. Here, we ask how a turtle ant colony’s choice of which nests to include in a network may be influenced by their potential to create connections to other nests. In laboratory experiments withCephalotes variansandCephalotes texanus, we show that nest choice is influenced by spatial constraints, but in unexpected ways. Under one spatial configuration, colonies preferentially occupied more connected nest sites; however, under another spatial configuration, this preference disappeared. Comparing the results of these experiments to an agent-based model, we demonstrate that this apparently idiosyncratic relationship between nest connectivity and nest choice can emerge without nestmore »preferences via a combination of self-reinforcing random movement along constrained pathways and density-dependent aggregation at nests. While this mechanism does not consistently lead to the de-novo construction of low-cost, efficient transport networks, it may be an effective way to expand a network, when coupled with processes of pruning and restructuring.

    « less
  4. ; ; ; ; ( , Journal of Chemical Ecology)
    Abstract

    Ants communicate via an arsenal of different pheromones produced in a variety of exocrine glands. For example, ants release alarm pheromones in response to danger to alert their nestmates and to trigger behavioral alarm responses. Here we characterize the alarm pheromone and the alarm response of the clonal raider ant Ooceraea biroi, a species that is amenable to laboratory studies but for which no pheromones have been identified. During an alarm response, ants quickly become unsettled, leave their nest pile, and are sometimes initially attracted to the source of alarm, but ultimately move away from it. We find that the alarm pheromone is released from the head of the ant and identify the putative alarm pheromone as a blend of two compounds found in the head, 4-methyl-3-heptanone and 4-methyl-3-heptanol. These compounds are sufficient to induce alarm behavior alone and in combination. They elicit similar, though slightly different behavioral features of the alarm response, with 4-methyl-3-heptanone being immediately repulsive and 4-methyl-3-heptanol being initially attractive before causing ants to move away. The behavioral response to these compounds in combination is dose-dependent, with ants becoming unsettled and attracted to the source of alarm pheromone at low concentrations and repulsed at high concentrations. Whilemore »4-methyl-3-heptanone and 4-methyl-3-heptanol are known alarm pheromones in other more distantly related ant species, this is the first report of the chemical identity of a pheromone inO. biroi,and the first alarm pheromone identified in the genusOoceraea. Identification of a pheromone that triggers a robust, consistent, and conserved behavior, like the alarm pheromone, provides an avenue to dissect the behavioral and neuronal mechanisms underpinning chemical communication.

    « less
  5. ; ; ( , 8th Workshop on Biological Distributed Algorithms (BDA))
    We study the problem of house-hunting in ant colonies, where ants reach consensus on a new nest and relocate their colony to that nest, from a distributed computing perspective. We propose a house-hunting algorithm that is biologically inspired by Temnothorax ants. Each ant is modelled as a probabilistic agent with limited power, and there is no central control governing the ants. We show a (log n) lower bound on the running time of our proposed house-hunting algorithm, where n is the number of ants. Further, we show a matching upper bound of expected O(log n) rounds for environments with only one candidate nest for the ants to move to. Our work provides insights into the house-hunting process, giving a perspective on how environmental factors such as nest qualities or a quorum rule can affect the emigration process. In particular, we find that a quorum threshold that is high enough causes transports to the inferior nest to cease to happen after O(log n) rounds when there are two nests in the environment.
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email