The ants walk: finding geodesics in graphs using reinforcement learning.
19th February 2021, 3:15 pm – 4:15 pm
How does a colony of ants find the shortest path between its nest and a source of food without any means of communication other than the pheromones each ant leave behind itself?
In this joint work with Daniel Kious (Bath) and Bruno Schapira (Marseille), we introduce a new probabilistic model for this phenomenon. In this model, the nest and the source of food are two marked nodes in a finite graph. Ants perform successive random walks from the nest to the food, and the distribution of the n-th walk depends on the trajectories of the (n-1) previous walks through some linear reinforcement mechanism.
Using stochastic approximation methods, couplings with Pólya urns, and the electric conductances method for random walks on graphs, we prove that, in this model, the ants indeed eventually find the shortest path(s) between their nest and the source food.