Choisir la langue :

Trouver les chemins les plus courts dans un graphe en utilisant l'apprentissage par renforcement.

Thematic tag(s): 

Comment une colonie de fourmis trouve-t-elle le chemin le plus court entre son nid et une source de nourriture sans autre forme de communication que les traces de phéromones que chaque fourmi dépose derrière elle ? Une réponse proposée dans la litérature de biologie est que les fourmis suivent un algorithme d’apprentissage par renforcement. 

Dans ce travail en commun avec Daniel Kious (Bath) et Bruno Schapira (Marseille), nous proposons un nouveau modèle probabiliste pour ce phénomène dans lequel le nid et la nourriture sont deux noeuds marqués dans un graphe fini. Les fourmis effectuent des marches aléatoires successives du noeud ``nid’’ au noeud ``nourriture’’, et la distribution de la n-ième marche dépend des trajectoires des (n-1) marches précédentes par un procédé de renforcement linéaire. 

En utilisant des méthodes d’approximation stochastique, des couplage avec des processus d’urnes, et la méthode des circuits éléctriques pour les marches aléatoires, nous montrons que dans ce modèle, les fourmis finissent en effet par trouver le chemin le plus court entre leur nid et la nourriture.

Dates: 
Wednesday, September 23, 2020 - 10:30
Location: 
Salle de Séminaire Online et Salle de réunion du M2
Speaker(s): 
Cécile Mailler
Affiliation(s): 
University of Bath
Other: 
https://people.bath.ac.uk/cdm37/index.html