1 Search Results for "Shiragur, Kirankumar"


Document
Extended Abstract
A Model for Ant Trail Formation and its Convergence Properties (Extended Abstract)

Authors: Moses Charikar, Shivam Garg, Deborah M. Gordon, and Kirankumar Shiragur

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)


Abstract
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.

Cite as

Moses Charikar, Shivam Garg, Deborah M. Gordon, and Kirankumar Shiragur. A Model for Ant Trail Formation and its Convergence Properties (Extended Abstract). In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 85:1-85:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{charikar_et_al:LIPIcs.ITCS.2021.85,
  author =	{Charikar, Moses and Garg, Shivam and Gordon, Deborah M. and Shiragur, Kirankumar},
  title =	{{A Model for Ant Trail Formation and its Convergence Properties}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{85:1--85:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.85},
  URN =		{urn:nbn:de:0030-drops-136247},
  doi =		{10.4230/LIPIcs.ITCS.2021.85},
  annote =	{Keywords: Ant colonies, Reinforced random walks, Natural Algorithms, Graph Algorithms, Shortest Path, Distributed Algorithms}
}
  • Refine by Author
  • 1 Charikar, Moses
  • 1 Garg, Shivam
  • 1 Gordon, Deborah M.
  • 1 Shiragur, Kirankumar

  • Refine by Classification
  • 1 Applied computing → Biological networks
  • 1 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Random walks and Markov chains
  • 1 Theory of computation → Shortest paths

  • Refine by Keyword
  • 1 Ant colonies
  • 1 Distributed Algorithms
  • 1 Graph Algorithms
  • 1 Natural Algorithms
  • 1 Reinforced random walks
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail