Arboreal Ants Suggest Surprising Algorithms for the Shortest Path Problem and its Variants

The arboreal turtle ant creates trail networks linking nests and food sources on the graph formed by branches and vines in the canopy of the tropical forest. Ants lay a volatile pheromone on 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 field study, Chandrasekhar et al. (2021) observed that trail networks approximately minimize the number of vertices, 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 reinforced random walk on a graph, that 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 of our model converges to the path with the minimum number of vertices, explaining the field observations. The dynamics converges to the shortest path when the rate of flow increases with time, showing that an ant colony can solve the shortest path problem just by varying 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.