« Previous AbstractAir Pollution and Headache Disorders    Next Abstract"NMR solution structure of attractin, a water-borne protein pheromone from the mollusk Aplysia californica" »

Proc Natl Acad Sci U S A

Title:		Distributed algorithms from arboreal ants for the shortest path problem
Author(s):		Garg S; Shiragur K; Gordon DM; Charikar M;
Address:		"Department of Computer Science, Stanford University, Stanford, CA 94305. Department of Management Science and Engineering, Stanford University, Stanford, CA 94305. Department of Biology, Stanford University, Stanford, CA 94305"
Journal Title:		Proc Natl Acad Sci U S A
Year:		2023
Volume:		20230130
Issue:		6
Page Number:		e2207959120 -
DOI:		10.1073/pnas.2207959120
ISSN/ISBN:		1091-6490 (Electronic) 0027-8424 (Print) 0027-8424 (Linking)
Abstract:		"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"
Keywords:		Animals *Ants Trees Algorithms Pheromones Forests ant colonies distributed algorithms graph algorithms natural algorithms shortest path problem;
Notes:		"MedlineGarg, Shivam Shiragur, Kirankumar Gordon, Deborah M Charikar, Moses eng Research Support, Non-U.S. Gov't Research Support, U.S. Gov't, Non-P.H.S. 2023/01/31 Proc Natl Acad Sci U S A. 2023 Feb 7; 120(6):e2207959120. doi: 10.1073/pnas.2207959120. Epub 2023 Jan 30"