Projects per year
Abstract
In this paper, we study a probabilistic reinforcementlearning 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 language  English 

Pages (fromto)  505536 
Number of pages  32 
Journal  Journal de l’École polytechnique 
Volume  9 
Early online date  28 Feb 2022 
DOIs  
Publication status  Published  31 Dec 2022 
Bibliographical note
Funding Information:DK is grateful to EPSRC for support through the grant EP/V00929X/1. CM is grateful to EPSRC for support through the fellowship EP/R022186/1.
Keywords
 Reinforced processes
 stochastic approximation
 urn processes
ASJC Scopus subject areas
 General Mathematics
Fingerprint
Dive into the research topics of 'The tracereinforced ants process does not find shortest paths'. Together they form a unique fingerprint.Projects
 2 Finished

Random walks in dynamic random environment
Kious, D. (PI)
Engineering and Physical Sciences Research Council
1/07/21 → 1/02/24
Project: Research council

Fellowship  Random trees: analysis and applications
Mailler, C. (PI)
Engineering and Physical Sciences Research Council
1/06/18 → 31/05/22
Project: Research council