logo Journal de l'École Polytechnique
The trace-reinforced ants process does not find shortest paths
[Le processus de fourmis renforçant leur trace ne trouve pas les chemins géodésiques]
Daniel Kious1 ; Cécile Mailler1 ; Bruno Schapira2
1 Department of Mathematical Sciences, University of Bath Claverton Down, BA2 7AY Bath, UK.
2 Aix-Marseille Université, CNRS, Centrale Marseille, I2M, UMR 7373 13453 Marseille, France
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.

Reçu le :
Accepté le :
Publié le :
DOI : 10.5802/jep.188
Classification : 60F15, 60K35
Keywords: Reinforced processes, stochastic approximation, urn processes
Mot clés : Processus renforcés, approximation stochastique, processus d’urnes
Daniel Kious 1 ; Cécile Mailler 1 ; Bruno Schapira 2

1 Department of Mathematical Sciences, University of Bath Claverton Down, BA2 7AY Bath, UK.
2 Aix-Marseille Université, CNRS, Centrale Marseille, I2M, UMR 7373 13453 Marseille, France
Licence : CC-BY 4.0
Droits d'auteur : Les auteurs conservent leurs droits 
@article{JEP_2022__9__505_0,
     author = {Daniel Kious and C\'ecile Mailler and Bruno Schapira},
     title = {The trace-reinforced ants process does~not~find shortest paths},
     journal = {Journal de l{\textquoteright}\'Ecole polytechnique {\textemdash} Math\'ematiques},
     pages = {505--536},
     publisher = {\'Ecole polytechnique},
     volume = {9},
     year = {2022},
     doi = {10.5802/jep.188},
     language = {en},
     url = {https://jep.centre-mersenne.org/articles/10.5802/jep.188/}
}
TY  - JOUR
AU  - Daniel Kious
AU  - Cécile Mailler
AU  - Bruno Schapira
TI  - The trace-reinforced ants process does not find shortest paths
JO  - Journal de l’École polytechnique — Mathématiques
PY  - 2022
SP  - 505
EP  - 536
VL  - 9
PB  - École polytechnique
UR  - https://jep.centre-mersenne.org/articles/10.5802/jep.188/
DO  - 10.5802/jep.188
LA  - en
ID  - JEP_2022__9__505_0
ER  - 
%0 Journal Article
%A Daniel Kious
%A Cécile Mailler
%A Bruno Schapira
%T The trace-reinforced ants process does not find shortest paths
%J Journal de l’École polytechnique — Mathématiques
%D 2022
%P 505-536
%V 9
%I École polytechnique
%U https://jep.centre-mersenne.org/articles/10.5802/jep.188/
%R 10.5802/jep.188
%G en
%F JEP_2022__9__505_0
Daniel Kious; Cécile Mailler; Bruno Schapira. The trace-reinforced ants process does not find shortest paths. Journal de l’École polytechnique — Mathématiques, Tome 9 (2022), pp. 505-536. doi : 10.5802/jep.188. https://jep.centre-mersenne.org/articles/10.5802/jep.188/

[BBCL15] M. Benaïm, I. Benjamini, J. Chen & Y. Lima - “A generalized Pólya’s urn with graph based interactions”, Random Structures Algorithms 46 (2015) no. 4, p. 614-634 | DOI

[Ben99] M. Benaïm - “Dynamics of stochastic approximation algorithms”, in Séminaire de Probabilités, XXXIII, Lect. Notes in Math., vol. 1709, Springer, Berlin, 1999, p. 1-68 | DOI

[CH21] Y. Couzinié & C. Hirsch - “Weakly reinforced Pólya urns on countable networks”, Electron. Comm. Probab. 26 (2021), article ID 35, 10 pages | DOI

[CL14] J. Chen & C. Lucas - “A generalized Pólya’s urn with graph based interactions: convergence at linearity”, Electron. Comm. Probab. 19 (2014), article ID 67, 13 pages | DOI

[DAGP90] J.-L. Deneubourg, S. Aron, S. Goss & J.-M. Pasteels - “The self-organizing exploratory pattern of the argentine ant”, Journal of Insect Behavior 3 (1990) no. 2, p. 159-168 | DOI

[DS04] M. Dorigo & T. Stützle - Ant colony optimization, MIT Press, 2004

[EFR19] D. Erhard, T. Franco & G. Reis - “The directed edge reinforced random walk: The ant mill phenomenon”, 2019 | arXiv

[GADP89] S. Goss, S. Aron, J.-L. Deneubourg & J.-M. Pasteels - “Self-organized shortcuts in the argentine ant”, Naturwissenschaften 76 (1989) no. 12, p. 579-581 | DOI

[Ham20] Y. Hamdi - “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] C. Hirsch, M. Holmes & V. Kleptsyn - “Warm percolation on a regular tree in the strong reinforcement regime”, 2020 | arXiv

[HJ04] B. M. Hambly & J. Jordan - “A random hierarchical lattice: the series-parallel graph and its properties”, Adv. in Appl. Probab. 36 (2004) no. 3, p. 824-838 | DOI

[HK] M. Holmes & V. Kleptsyn - “Infinite WARM graphs II: critical regime”

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

[KMS20] D. Kious, C. Mailler & B. Schapira - “Finding geodesics on graphs using reinforcement learning”, 2020 | arXiv

[LGR18] L. C. Le Goff & O. Raimond - “Vertex reinforced non-backtracking random walks: an example of path formation”, Electron. J. Probab. 23 (2018), article ID 39, 38 pages | DOI

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

[LL10] G. F. Lawler & V. Limic - Random walk: a modern introduction, Cambridge Studies in Advanced Math., vol. 123, Cambridge University Press, Cambridge, 2010 | DOI

[LP16] R. Lyons & Y. Peres - Probability on trees and networks, Cambridge Series in Statistical and Probabilistic Math., vol. 42, Cambridge University Press, New York, 2016 | DOI

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

[MTNS13] Q. Ma, A. Tero, T. Nakagaki & D. J. T. Sumpter - “Current-reinforced random walks for constructing transport networks”, J. R. Soc. Interface (2013), article ID 20120864 | DOI

[Pem07] R. Pemantle - “A survey of random processes with reinforcement”, Probab. Surv. 4 (2007), p. 1-79 | DOI

[vdHHKR16] R. van der Hofstad, M. Holmes, A. Kuznetsov & W. Ruszel - “Strongly reinforced Pólya urns with graph-based competition”, Ann. Appl. Probab. 26 (2016) no. 4, p. 2494-2539 | DOI

Cité par Sources :