More Like this

1. Distributed algorithms from arboreal ants for the shortest path problem

   https://doi.org/10.1073/pnas.2207959120  

   Garg, Shivam; Shiragur, Kirankumar; Gordon, Deborah M.; Charikar, Moses (February 2023, Proceedings of the National Academy of Sciences)

   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
2. A Model for Ant Trail Formation and its Convergence Properties

   https://doi.org/10.4230/LIPIcs.ITCS.2021.85  

   Charikar, Moses; Garg, Shivam; Gordon, Deborah M.; Shiragur, Kirankumar (January 2021, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021))

   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
3. Nest choice in arboreal ants is an emergent consequence of network creation under spatial constraints

   https://doi.org/10.1007/s11721-021-00187-5  

   Chang, Joanna; Powell, Scott; Robinson, Elva J.; Donaldson-Matasci, Matina C. (April 2021, Swarm Intelligence)

   null (Ed.)

   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 and Cephalotes 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
4. Adhesion and Running Speed of a Tropical Arboreal Ant (Cephalotes atratus) on Rough, Narrow, and Inclined Substrates

   https://doi.org/10.1093/icb/icaa078  

   Stark, Alyssa Y; Yanoviak, Stephen P (June 2020, Integrative and Comparative Biology)

   null (Ed.)

   Synopsis Arboreal ants must navigate variably sized and inclined linear structures across a range of substrate roughness when foraging tens of meters above the ground. To achieve this, arboreal ants use specialized adhesive pads and claws to maintain effective attachment to canopy substrates. Here, we explored the effect of substrate structure, including small and large-scale substrate roughness, substrate diameter, and substrate orientation (inclination), on adhesion and running speed of workers of one common, intermediately-sized, arboreal ant species. Normal (orthogonal) and shear (parallel) adhesive performance varied on sandpaper and natural leaf substrates, particularly at small size scales, but running speed on these substrates remained relatively constant. Running speed also varied minimally when running up and down inclined substrates, except when the substrate was positioned completely vertical. On vertical surfaces, ants ran significantly faster down than up. Ant running speed was slower on relatively narrow substrates. The results of this study show that variation in the physical properties of tree surfaces differentially affects arboreal ant adhesive and locomotor performance. Specifically, locomotor performance was much more robust to surface roughness than was adhesive performance. The results provide a basis for understanding how performance correlates of functional morphology contribute to determining local ant distributions and foraging decisions in the tropical rainforest canopy. 

   more » « less
5. From foraging trails to transport networks: how the quality-distance trade-off shapes network structure

   https://doi.org/10.1098/rspb.2021.0430  

   Lecheval, Valentin; Larson, Hannah; Burns, Dominic D.; Ellis, Samuel; Powell, Scott; Donaldson-Matasci, Matina C.; Robinson, Elva J. (April 2021, Proceedings of the Royal Society B: Biological Sciences)

   null (Ed.)

   Biological systems are typically dependent on transportation networks for the efficient distribution of resources and information. Revealing the decentralized mechanisms underlying the generative process of these networks is key in our global understanding of their functions and is of interest to design, manage and improve human transport systems. Ants are a particularly interesting taxon to address these issues because some species build multi-sink multi-source transport networks analogous to human ones. Here, by combining empirical field data and modelling at several scales of description, we show that pre-existing mechanisms of recruitment with positive feedback involved in foraging can account for the structure of complex ant transport networks. Specifically, we find that emergent group-level properties of these empirical networks, such as robustness, efficiency and cost, can arise from models built on simple individual-level behaviour addressing a quality-distance trade-off by the means of pheromone trails. Our work represents a first step in developing a theory for the generation of effective multi-source multi-sink transport networks based on combining exploration and positive reinforcement of best sources. 

   more » « less