Colonies of the arboreal turtle ant create networks of trails that link nests and food sources on the graph formed by branches and vines in the canopy of the tropical forest. Ants put down a volatile pheromone on the edges as they traverse them. At each vertex, the next edge to traverse is chosen using a decision rule based on the current pheromone level. There is a bidirectional flow of ants around the network. In a previous field study, it was observed that the trail networks approximately minimize the number of vertices, thus solving a variant of the popular shortest path problem without any central control and with minimal computational resources. We propose a biologically plausible model, based on a variant of the reinforced random walk on a graph, which explains this observation and suggests surprising algorithms for the shortest path problem and its variants. Through simulations and analysis, we show that when the rate of flow of ants does not change, the dynamics converges to the path with the minimum number of vertices, as observed in the field. The dynamics converges to the shortest path when the rate of flow increases with time, so the colony can solve the shortest path problem merely by increasing the flow rate. We also show that to guarantee convergence to the shortest path, bidirectional flow and a decision rule dividing the flow in proportion to the pheromone level are necessary, but convergence to approximately short paths is possible with other decision rules.
more »
« less
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.
more »
« less
- Award ID(s):
- 2026342
- NSF-PAR ID:
- 10319456
- Date Published:
- Journal Name:
- PLoS computational biology
- Volume:
- 17
- Issue:
- (10)
- ISSN:
- 1553-734X
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)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, 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.more » « less
-
more » « less
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 with
Cephalotes varians andCephalotes 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 nest 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. -
more » « less
Abstract In tropical rain forests, the ant community can be divided into ground and arboreal faunas. Here, we report a thorough sampling of the arboreal ant fauna of La Selva Biological Station, a Neotropical rain forest site. Forty‐five canopy fogging samples were centered around large trees. Individual samples harbored an average of 35 ant species, with up to 55 species in a single sample. The fogging samples yielded 163 observed species total, out of a statistically estimated 199 species. We found no relationship between within‐sample ant richness and focal tree species, nor were the ant faunas of nearby trees more similar to each other than the faunas of widely spaced trees. Species density was high, and beta diversity was low: A single column of vegetation typically harbors at least a fifth of the entire arboreal ant fauna. Considering the entire fauna, based on 23,326 species occurrence records using a wide variety of collecting methods, 182 of 539 observed species (196 of 605, estimated statistically) were entirely arboreal. The arboreal ant fauna is thus about a third of the total La Selva ant fauna, a robust result because inventory completeness was similar for ground and arboreal ants. The taxonomic history of discovery of the species that make up the La Selva fauna reveals no disproportionately large pool of undiscovered ant species in the canopy. The last biotic frontier for tropical ants has been the rotten wood, leaf litter, and soil of the forest floor.
Abstract in Spanish is available with online material.
-
Oblivious routing has a long history in both the theory and practice of networking. In this work we initiate the formal study of oblivious routing in the context of reconfigurable networks, a new architecture that has recently come to the fore in datacenter networking. These networks allow a rapidly changing bounded-degree pattern of interconnections between nodes, but the network topology and the selection of routing paths must both be oblivious to the traffic demand matrix. Our focus is on the trade-off between maximizing throughput and minimizing latency in these networks. For every constant throughput rate, we characterize (up to a constant factor) the minimum latency achievable by an oblivious reconfigurable network design that satisfies the given throughput guarantee. The trade-off between these two objectives turns out to be surprisingly subtle: the curve depicting it has an unexpected scalloped shape reflecting the fact that load-balancing becomes more difficult when the average length of routing paths is not an integer because equalizing all the path lengths is not possible. The proof of our lower bound uses LP duality to verify that Valiant load balancing is the most efficient oblivious routing scheme when used in combination with an optimally-designed reconfigurable network topology. The proof of our upper bound uses an algebraic construction in which the network nodes are identified with vectors over a finite field, the network topology is described by either the elementary basis or a sequence of Vandermonde matrices, and routing paths are constructed by selecting columns of these matrices to yield the appropriate mixture of path lengths within the shortest possible time interval.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1371/journal.pcbi.1009523
