Encadrants: Nicolas Bredeche (ISIR), Stephane Doncieux (ISIR)
Encadrement technique: Leo Cazenille (LIED)
Les algorithmes d'illumination (ou Quality-Diversity) permettent d'explorer de grands espaces de recherche. Ces algorithmes sont typiquement très utiles en robotique, où il existe souvent des solutions très différentes présentant toutes un intérêt très fort pour le concepteur. L'algorithme MAP-elite [1] a par exemple été utilisée pour la découverte de stratégie de marche robuste pour un robot hexapode [2].
Cependant, il arrive fréquemment que l'évaluation d'une solution candidate soit difficile à réaliser, la performance mesurée pouvant varier grandement entre deux évaluations. Il est alors nécessaire d'estimer la fidélité d'une évaluation, voire d'évaluer plusieurs fois une même solution pour estimer correctement sa valeur. On fait donc face à un compromis entre (1) une évaluation peu coûteuse mais potentiellement imprécise et (2) une évaluation précise mais coûteuse. De plus, le compromis "idéal" n'est pas forcément le même selon la solution à évaluer (p.ex.: deux configurations de robots peuvent être très différentes en terme de stabilité).
Dans le cadre de ce stage, on souhaite étendre l'algorithme MAP-elite pour prendre en compte la confiance accordées aux performances mesurées, et d'opérer un compromis entre la réévaluation d'une solution déjà connue et l'exploration d'une nouvelle solution. On combinera un algorithme de type epsilon-greedy pour trancher entre réévaluation et exploration, et un algorithme de type bandit manchot pour choisir quel individu réévaluer.
On étudiera aussi l'opportunité d'appliquer cette méthode à l'algorithme SAIL [3], qui suit approche dîte surrogate applicable à l'algorithme MAP-elite [3]. Le modèle surrogate tend à construire un prédicteur de performances en fonction des évaluations précédentes, ce qui permet d'obtenir une approximation très peu couteuse de la qualité d'une solution. Cette approximation (et plus généralement le modèle surrogate) nécessite bien sûr une excellente confiance dans les évaluations réelles utilisée pour construire le modèle surrogate (ie. la qualité d'une solution donnée peut être interpolée à partir d'évaluations réelles, pour peu qu'elles soient fiables).
On utilisera dans un premier temps une fonction artificielle f(x)=(y,z), tel que x soit la description d'une solution candidate, y la performance mesurée et z le bruit applicable à la performance. La performance mesurée sera donc une fonction g(y,z) (ie. application d'un bruit sur la mesure de f(x)). Dans un second temps, on utilisera un simulateur de micro-robotique en essaim et programmation moléculaire, qui présente un problème typique avec une fonction d'évaluation coûteuse pouvant bénéficier d'une approche surrogate et d'une exploration type MAP-elite.
Le code sera fait en Python en utilisant la librairie QDpy [4].
[1] Mouret, Clune (2015) Illuminating search spaces by mapping elites. https://arxiv.org/abs/1504.04909
[2] Cully, Clune, Tarapore, Mouret (2015) Robots that can adapt like natural animals. http://www.isir.upmc.fr/files/2015ACLI3468.pdf
[3] Gaier, Asteroth, Mouret (2018) Data-Efficient Design Exploration through Surrogate-Assisted Illumination. https://hal.inria.fr/hal-01817505/document
[4] https://gitlab.com/leo.cazenille/qdpy