Seminar Interacting Random Systems
- Mittwoch, 03.03.2021, 11:30 Uhr (Online Event)
Cecile Mailler, The University of Bath, GB:
The ants walk: finding geodesics in graphs using reinforcement learning
mehr ... Veranstaltungsort
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 ths 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.
Seminar Interacting Random Systems (Online Event)
Organisers: Luisa Andreis and Willem van Zuijlen