[Thèse] Analyse d’algorithmes évolutionnaires pour l’apprentissage d’un essaim robotique

Résumé

Imaginons un ensemble de robots miniatures capable d’évoluer dans un environnement pour réaliser un but précis (exploration, détection de pannes etc.). Supposons que l’environnement soit inconnue et que les robots aient un champ de communication restreint. Concevoir un tel dispositif, est pour le moment un problème ouvert où les approches classiques peinent a fonctionner et où d’autres approches fondées sur la distribution du calcul, l’aléa et l’échange parcimonieux de données, arrivent à trouver des solutions. Cependant, nous restons incapable d’expliquer pourquoi et comment ces derniers y arrivent.

Mots-clés : apprentissage automatique, essaims robotique, analyse d’algorithmes stochastiques.

Contexte

L’équipe LARSEN s’intéresse à l’intelligence artificielle et plus précisément à la conception d’agents robotique dotés de comportements autonomes intelligents. Un agent est une entité informatique ou robotique dotée de capacités sensori-motrices, capable d’évoluer de manière autonome dans un environnement donné. L’objectif de cette thèse est de contribuer à cette thématique en étudiant comment apprendre les comportements d’un ensemble d’agents par apprentissage évolutionnaire (Evolutionary Robotics) [5].
Les essaims de robots sont des systèmes composés d’un grand nombre de robots relativement simples. Du fait du grand nombre d’unités, ces systèmes ont de bonnes propriétés de robustesse et de passage à l’échelle. Néanmoins, concevoir des systèmes de telle nature pour réaliser des tâches intéressante reste un challenge important et les approches classiques (machine learning, deep learning) ne sont pas utilisables. Par conséquent, des approches automatisées et décentralisés comme l’Embodied Evolutionary Robotics (EER) [2] constituent une alternative attirante. Elles ouvrent de nombreuses possibilités, puisque l’apprentissage est mené en parallèle par chaque robot de l’essaim et en ligne pendant l’exécution d’une tâche.

Objectifs

D’un point de vue expérimental, ces algorithmes ont été utilisés avec succès sur un grand nombre de problèmes [2], cependant leurs analyse restent assez peu développées. Il n’existe par exemple aucun résultat garantissant ou quantifiant leur convergence même sur les instances de problèmes les plus simples. Parmi les objectifs de cette thèse, le plus central sera de mieux comprendre ces algorithmes d’un point de vue théorique en proposant les outils et modèles mathématiques et en fixant les cadres permettant l’étude de ces algorithmes. Une piste potentiellement prometteuse que nous proposons de suivre pour atteindre cet objectif est d’utiliser des résultats connus dans le domaine des systèmes distribués ainsi que les modèles stochastiques en biologie computationnelle [3, 4] dont les liens avec les approches EER commencent à être tissés [1]. Ces résultats semblent très prometteurs pour analyser la dynamique interne de ces algorithmes ainsi que pour identifier les conditions nécessaires à leur convergence. Un autre objectif de la thèse sera de définir une classification des problèmes (complexité, nature, etc.) sur lesquels ces algorithmes sont généralement appliqués. Au vu de quelques résultats expérimentaux [2], il semblerait que l’application de ces algorithmes sur différents problèmes produise une dynamique similaire, il serait important de mieux comprendre comment ces instances de problème pourraient être liées. De plus, une telle classification des problèmes permettrait une généralisation des analyses des ses algorithmes.

Informations additionnelles

Le travail de recherche proposé ici alliera l’analyse algorithmique et l’expérimentation en simulation et sur des plates-formes robotiques disponible au laboratoire. Nous recherchons un candidat avec de bonnes connaissances en IA, probabilités et processus stochastiques, et avec un intérêt pour l’apprentissage automatique et la robotique, ainsi que de bonnes compétences en programmation.

Contacts :

  • François Charpillet (DR INRIA, HDR) francois.charpillet@loria.fr
  • Amine Boumaza (MCF, Université de Lorraine) amine.boumaza@loria.fr

Durée  : 3 ans

Date de début :  1er octobre 2020

Références

  1. Amine Boumaza. Phylogeny of embodied evolutionary robotics. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO ’17, pages 1681–1682, New York, NY, USA, 2017. ACM.
  2. Nicolas Bredeche, Evert Haasdijk, and Abraham Prieto. Embodied evolution in collective robotics : A review. Front, in Robo. and AI, 5 :12, 2018.
  3. Benjamin Doerr, Philipp Fischbeck, Clemens Frahnow, Tobias Friedrich, Timo Kötzing, and Martin Schirneck. Island models meet rumor spreading. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO ’17, pages 1359–1366, New York, NY, USA, 2017. ACM.
  4. Jotun Hein, Mikkel H. Schierup, and Carsten Wiuf. Gene Genealogies, Variation and Evolution A Primer in Coalescent Theory. Oxford University Pres, 2005.
  5. Stefano Nolfi and Dario Floreano. Evolutionary Robotics : The Biology, Intelligence, and Technology. MIT Press, Cambridge, MA, USA, 2000.

Logo d'Inria