 Award ID(s):
 2026342
 Publication Date:
 NSFPAR ID:
 10319456
 Journal Name:
 PLoS computational biology
 Volume:
 17
 Issue:
 (10)
 ISSN:
 1553734X
 Sponsoring Org:
 National Science Foundation
More Like this

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 themore »

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 »

Abstract Biological transportation networks must balance competing functional priorities. The selforganizing mechanisms used to generate such networks have inspired scalable algorithms to construct and maintain lowcost and efficient humandesigned transport networks. The pheromonebased 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 selforganized 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 agentbased model, we demonstrate that this apparently idiosyncratic relationship between nest connectivity and nest choice can emerge without nestmore » 
Animals are often faced with timecritical decisions without prior information about their actions’ outcomes. In such scenarios, individuals budget their investment into the task to cut their losses in case of an adverse outcome. In animal groups, this may be challenging because group members can only access local information, and consensus can only be achieved through distributed interactions among individuals. Here, we combined experimental analyses with theoretical modeling to investigate how groups modulate their investment into tasks in uncertain conditions. Workers of the arboreal weaver ant Oecophylla smaragdina form threedimensional chains using their own bodies to bridge vertical gaps between existing trails and new areas to explore. The cost of a chain increases with its length because ants participating in the structure are prevented from performing other tasks. The payoffs of chain formation, however, remain unknown to the ants until the chain is complete and they can explore the new area. We demonstrate that weaver ants cap their investment into chains, and do not form complete chains when the gap is taller than 90 mm. We show that individual ants budget the time they spend in chains depending on their distance to the ground, and propose a distancebased model ofmore »

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 boundeddegree 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 tradeoff 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 tradeoff between these two objectives turns out to be surprisingly subtle: the curve depicting it has an unexpected scalloped shape reflecting the fact that loadbalancing 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 optimallydesigned reconfigurable network topology. Themore »