The trace-reinforced ants process does not find shortest paths

Daniel Kious, Cecile Mailler, Bruno Schapira

Research output: Contribution to journalArticlepeer-review

8 Downloads (Pure)

Abstract

In this paper, we study a probabilistic reinforcement-learning model for ants searching for the shortest path(s) from their nest to a food source, represented here by two vertices of a finite graph. In this model, the ants each take a random walk on the graph, starting from the nest vertex, until they reach the food vertex, and then reinforce the weight of the set of crossed edges. We show that if the graph is a finite tree, in which the set of leaves is identified with a single food vertex, and the root with the nest vertex, and if there is an edge between the nest and the food, then almost surely the proportion of ants that end up taking this last edge tends to 1. On the other hand we show on three other examples that in general ants do not always choose the shortest path. Our techniques use stochastic approximation methods, as well as couplings with urn processes.

Original languageEnglish
Pages (from-to)505-536
Number of pages32
JournalJournal de l’École polytechnique
Volume9
Early online date28 Feb 2022
DOIs
Publication statusPublished - 31 Dec 2022

Keywords

  • Reinforced processes
  • stochastic approximation
  • urn processes

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint

Dive into the research topics of 'The trace-reinforced ants process does not find shortest paths'. Together they form a unique fingerprint.

Cite this