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

Orateur:
Cécile MAILLER
Localisation: Université de Bath, Royaume-Uni
Type: Groupe de travail probabilités
Site: UPEC
Salle:
Batiment modulaire 006, UPEC
Date de début:
02/12/2021 - 11:30
Date de fin:
02/12/2021 - 13:00

Résumé : 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 littérature en 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 électriques pour les marches aléatoires, nous cherchons à montrer que, dans ce modèle, les fourmis finissent en effet par trouver le chemin le plus court entre leur nid et la nourriture.