The trace-reinforced ants process does not find shortest paths

Kious, Daniel; Mailler, Cécile; Schapira, Bruno

Journal de l’École polytechnique — Mathématiques, Tome 9 (2022), pp. 505-536.

Nous étudions un modèle de renforcement par apprentissage pour les fourmis cherchant le chemin le plus court pour aller de leur nid à une source de nourriture, représentés ici par deux sommets d’un graphe fini. Dans ce modèle les fourmis accomplissent chacune à leur tour une marche aléatoire sur le graphe, partant du sommet nid, jusqu’à atteindre le sommet nourriture, puis renforcent le poids de l’ensemble des arêtes traversées. Nous montrons que si le graphe est un arbre fini, dans lequel l’ensemble des feuilles sont identifiées à un seul sommet nourriture, et la racine au sommet nid, et s’il existe une arête entre le nid et la nourriture, alors presque sûrement la proportion de fourmis qui finit par emprunter cette dernière arête tend vers $1$. D’un autre côté nous montrons sur trois autres exemples qu’en général les fourmis ne choisissent pas toujours le chemin le plus court. Nos techniques utilisent des méthodes d’approximation stochastique, ainsi que des couplages avec des processus d’urnes.

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.

Classification : 60F15, 60K35
Keywords: Reinforced processes, stochastic approximation, urn processes
Mot clés : Processus renforcés, approximation stochastique, processus d’urnes

[BBCL15] Benaïm, Michel; Benjamini, Itai; Chen, Jun; Lima, Yuri A generalized Pólya’s urn with graph based interactions, Random Structures Algorithms, Volume 46 (2015) no. 4, pp. 614-634 | DOI

[Ben99] Benaïm, Michel Dynamics of stochastic approximation algorithms, Séminaire de Probabilités, XXXIII (Lect. Notes in Math.), Volume 1709, Springer, Berlin, 1999, pp. 1-68 | DOI

[CH21] Couzinié, Yannick; Hirsch, Christian Weakly reinforced Pólya urns on countable networks, Electron. Comm. Probab., Volume 26 (2021), 35, 10 pages | DOI

[CL14] Chen, Jun; Lucas, Cyrille A generalized Pólya’s urn with graph based interactions: convergence at linearity, Electron. Comm. Probab., Volume 19 (2014), 67, 13 pages | DOI

[DAGP90] Deneubourg, Jean-Louis; Aron, Serge; Goss, Simon; Pasteels, Jacques-Marie The self-organizing exploratory pattern of the argentine ant, Journal of Insect Behavior, Volume 3 (1990) no. 2, pp. 159-168 | DOI

[DS04] Dorigo, Marco; Stützle, Thomas Ant colony optimization, MIT Press, 2004

[EFR19] Erhard, Dirk; Franco, Tertuliano; Reis, Guilherme The directed edge reinforced random walk: The ant mill phenomenon, 2019 | arXiv

[GADP89] Goss, Simon; Aron, Serge; Deneubourg, Jean-Louis; Pasteels, Jacques-Marie Self-organized shortcuts in the argentine ant, Naturwissenschaften, Volume 76 (1989) no. 12, pp. 579-581 | DOI

[Ham20] Hamdi, Yassine A model of ants’ search for food by reinforced walks on graphs (2020) (UG internship report, https://gitlab.com/yassine_hamdi/a-model-of-ants..., École polytechnique and University of Bath)

[HHK20] Hirsch, Christian; Holmes, Mark; Kleptsyn, Victor Warm percolation on a regular tree in the strong reinforcement regime, 2020 | arXiv

[HJ04] Hambly, Ben M.; Jordan, Jonathan A random hierarchical lattice: the series-parallel graph and its properties, Adv. in Appl. Probab., Volume 36 (2004) no. 3, pp. 824-838 | DOI

[HK] Holmes, Mark; Kleptsyn, Victor Infinite WARM graphs II: critical regime

[Jan04] Janson, Svante Functional limit theorems for multitype branching processes and generalized Pólya urns, Stochastic Process. Appl., Volume 110 (2004) no. 2, pp. 177-245 | DOI

[KMS20] Kious, Daniel; Mailler, Cécile; Schapira, Bruno Finding geodesics on graphs using reinforcement learning, 2020 | arXiv

[LGR18] Le Goff, Line C.; Raimond, Olivier Vertex reinforced non-backtracking random walks: an example of path formation, Electron. J. Probab., Volume 23 (2018), 39, 38 pages | DOI

[Lim16] Lima, Yuri Graph-based Pólya’s urn: completion of the linear case, Stochastic Dyn., Volume 16 (2016) no. 2, 1660007, 13 pages | DOI

[LL10] Lawler, Gregory F.; Limic, Vlada Random walk: a modern introduction, Cambridge Studies in Advanced Math., 123, Cambridge University Press, Cambridge, 2010 | DOI

[LP16] Lyons, Russell; Peres, Yuval Probability on trees and networks, Cambridge Series in Statistical and Probabilistic Math., 42, Cambridge University Press, New York, 2016 | DOI

[Mar17] Markov, Andreï A Sur quelques formules limites du calcul des probabilités, Izv. Ross. Akad. Nauk Ser. Mat., Volume 11 (1917) no. 3, pp. 177-186 (in Russian)

[MTNS13] Ma, Qi; Tero, Atsushi; Nakagaki, Toshiyuki; Sumpter, David J. T. Current-reinforced random walks for constructing transport networks, J. R. Soc. Interface (2013), 20120864 | DOI

[Pem07] Pemantle, Robin A survey of random processes with reinforcement, Probab. Surv., Volume 4 (2007), pp. 1-79 | DOI

[vdHHKR16] van der Hofstad, Remco; Holmes, Mark; Kuznetsov, Alexey; Ruszel, Wioletta Strongly reinforced Pólya urns with graph-based competition, Ann. Appl. Probab., Volume 26 (2016) no. 4, pp. 2494-2539 | DOI