Apprentissage par renforcement appliqué à la conduite autonome dans un simulateur 1/2

le 24/04/2020 par Paul DALOUS, Yannick Schini
Tags: Data & AI, Deep Learning

Afin d’explorer de nouvelles possibilités concernant la conduite autonome, de nombreuses compétitions de mini-voitures autonomes existent telles que la compétition de l’Iron Car ou encore la compétition Donkey ® Car  aux États-Unis. Lors de ces compétitions, des mini voitures (type voitures radiocommandées) doivent parcourir quelques tours d’un circuit faisant approximativement la taille d’un hangar. Dans cet article, nous allons étudier l’utilisation d’une solution d’apprentissage par renforcement (RL - Reinforcement Learning - pour les intimes) pour la conduite autonome selon le contexte schématisé en figure 1.

*Fig 1 : L’objectif est d’entraîner un agent à prédire les modifications à apporter sur l’accélération et la direction à partir d’une image issue de la caméra frontale de la voiture [Crédit image: Le simulateur Donkey]*Afin d’entraîner un agent de RL dans un simulateur de conduite nous allons :

  1. Expliciter les concepts généraux du RL évoqués dans l’article précédent [Blog Octo : L'apprentissage par renforcement démystifié] dans notre cas d’usage particulier de la conduite autonome ;
  2. Expliquer en détail le fonctionnement de l’algorithme de RL que nous avons choisi ;
  3. Décrire brièvement l’architecture de notre projet et notamment comment l’algorithme s’interface avec le simulateur ;

Cependant nous n’irons pas jusqu’au déploiement en réel qui comporte son lot de complications (si vous voulez savoir quel(s) type(s) de complication(s) nous vous invitons à consulter l’article suivant : [Blog Octo : L'IA embarquée : entraîner, déployer et utiliser du Deep Learning sur un Raspberry (Partie 1)]).

Enfin, dans un deuxième article, nous entraînerons cet algorithme et nous analyserons les résultats en terme de conduite autonome.

L’apprentissage par renforcement appliqué à la conduite autonome

1. Principes généraux du RL dans le cas de la conduite autonome

Un précédent article sur le blog d’Octo [Blog Octo : L'apprentissage par renforcement démystifié] a déjà éclairci le sujet du RL dans les grandes lignes. Nous vous conseillons, si vous êtes novice dans le domaine du RL, de vous y référer pour vous familiariser avec les concepts les plus fondamentaux (principe général, notions d’état, d’action, de récompense et version basique du Q-learning) sur lesquels nous ne reviendrons pas ici. Dans le cas particulier de la conduite autonome :

  • L’agent est le pilote de la voiture autonome, ou plus exactement l’algorithme de RL utilisé par la voiture pour gérer son pilotage. C’est lui que l’on cherche à entraîner.
  • Les actions que peut entreprendre l’agent dans l’environnement sont la modification de la direction de la voiture et son accélération.
  • Les états dans lesquels peut se retrouver notre agent à tout instant t (notés st) sont décrits par une image issue de la caméra frontale de la voiture.
  • L’environnement est la route sur laquelle évolue notre voiture. Dans notre cas d’usage il s’agit d’un simulateur de conduite. Cet environnement prend l’état à un instant donné st  et calcule à partir de l’action entreprise par l’agent (notée at) le nouvel état st+1 , le fournit à l’agent et ainsi de suite… Cette succession d'événements est une étape.
  • L’épisode est la suite d’étapes se finissant par une sortie de route de la voiture.

L’apprentissage de l’agent dans l’environnement est résumé sur la figure 2.

Fig 2 : Principe général de l’apprentissage par renforcement appliqué à notre cas d’usage. Crédit image: [Donkey Car]

2. Le Deep Q-Learning

2.1. Principe théorique

Nous avons choisi d’utiliser comme algorithme une “version améliorée” du Q-Learning décrit dans l’article précédent : le Deep Q-Learning. Pour rappel le but du Q-Learning [Watkins, 1989] est d’optimiser au fur et à mesure la fonction de valeur Q décrite en figure 3. Si on connaît cette fonction, alors on sait estimer correctement la valeur de chaque action pour un état donné et il suffit d’entreprendre à chaque fois la meilleure.

Fig 3 : La fonction de valeur est ce que l’on espère gagner sur le long terme si l’on entreprend une certaine action dans un certain état en suivant une certaine politique

La notation pi (st)= at n’est pas totalement exacte. En réalité, la politique renvoie une distribution de probabilité des actions : pi(st) = p (at = a), pour tous les a dans A (l'espace des actions possibles), c’est à dire à quelle fréquence il faudrait effectuer chaque action dans telle ou telle situation. Cette dernière notation permet de décrire des cas plus complexes, par exemple au poker on peut imaginer qu’il est une bonne stratégie de bluffer parfois et on aurait donc une politique qui ressemblerait à p (at= "bluff") = 0.10 ; p (at = "se coucher") = 0.90 . On revient au cas décrit ici si la probabilité est de 1 pour une certaine action et de 0 pour toutes les autres.

Le Deep Q-Learning (DQL) [Mnih et al., 2013] propose comme approximateur de la fonction Q un réseau de neurones (généralement profond, d’où le terme Deep Q-Learning) plutôt qu’une Q-table comme décrit précédemment. Cela répond à la problématique de la taille de l’espace des états évoqué dans l’article précédent [Blog Octo : L'apprentissage par renforcement démystifié]. Dans notre cas, on choisit de décrire chaque état par une image de la route et après un prétraitement, cette image est en noir et blanc de taille 84 par 84. La taille de l’espace des états (noté S) dans ce cas est donc |S| = 256^(84x84) ≈ 1O^(16 992) , ce qui est bien trop grand pour autoriser une représentation de la fonction de valeur Q sous forme de tableau (qui aurait donc 1O^(16 992 lignes)).

Fig 4 : Le Deep Q-Learning utilise un réseau de neurones comme approximateur de la fonction Q. Nous avons choisi ici 5 actions possibles correspondant à 5 angles de braquage différents, l’accélération étant fixée constante. Dans cet exemple, le réseau de neurones est déjà entraîné puisqu’il prédit avec raison une meilleure récompense pour l’action d’aller tout droit dans une ligne droite.

Il s’agit ici de comprendre que l’on veut utiliser un réseau de neurones comme un “oracle” que l’on consulte. On lui présente une image de la route et il nous indique pour chaque action possible la récompense totale que l’on est censé obtenir avant de sortir de la route (i.e. avant la fin de l’épisode) comme le montre la figure 4. Bien entendu cet oracle n’est pas pertinent au début de l’entraînement car on choisit en général des poids aléatoires quand on initialise un réseau de neurones mais on va l’entraîner et ce quasiment de la même façon que l’on mettait à jour notre Q-table.

Si l’on change la représentation de notre fonction de valeur Q, on doit également changer notre méthode de mise-à-jour lors de l’entraînement. Souvenez-vous de l’équation de Bellman décrite dans l’article précédent et rappelée en figure 5, elle permet de remplacer une valeur par une autre en fonction de la récompense obtenue pour affiner l’estimation.

*Fig 5 : L’équation de Bellman qui décrit la méthode de mise-à-jour de notre Q-table. Écriture adaptée de [Sutton and Barto, 1998]*Or si l’on choisit de représenter notre fonction non plus par un tableau mais par un réseau de neurones, cette mise-à-jour doit concerner les paramètres du réseau de neurones. La mise-à-jour de notre approximation va fonctionner selon le même principe : minimiser l’écart entre une valeur actuelle Q-predict et une valeur cible Q-target. Sans rentrer dans le détail, à chaque mise-à-jour des paramètres de notre réseau de neurones, on effectue une descente de gradient ayant la fonction de coût décrite en figure 6.

Fig 6 : La fonction de coût du réseau de neurones se base sur la différence Q-target / Q-predict de façon analogue à l’équation de Bellman

Si les termes de descente de gradient et de fonction de coût ne vous sont pas familiers, vous pouvez vous référer à l’article suivant [Blog Octo : Classification d’images : les réseaux de neurones convolutifs en toute simplicité], notamment le paragraphe “Entraînement des CNN, quelques principes”. Il n’est cependant pas nécessaire ici de connaître en détail le fonctionnement, seulement de comprendre qu’un réseau de neurones possède des valeurs numériques qui lui sont propres (appelées poids) et qui lui servent à prédire ses valeurs de sorties à partir de ses entrées. Ce sont ces valeurs qui sont modifiées lors de l’apprentissage. Pour les modifier, on utilise une métrique : la fonction de coût. Cette fonction de coût est un indicateur basé sur la différence entre les valeurs actuellement prédites par notre réseau de neurones et celles que l’on voudrait qu’il prédise. En Deep Q-Learning on utilise la fonction de récompense pour calculer les valeurs que l’on souhaite que notre réseau de neurones prédise. Le gradient est un vecteur qui contient la modification des poids à effectuer pour tendre vers cet objectif et affiner notre prédiction. Effectuer une “descente de gradient” c’est donc répéter ce mode de fonctionnement autant de fois que nécessaire afin que les paramètres du réseau de neurones s’affinent progressivement pour prédire pertinemment les valeurs cibles.

Le principe reste donc le même que précédemment, à chaque mise-à-jour des paramètres de notre réseau de neurones, le réseau “tend un peu plus vers” une estimation correcte de la fonction de valeur Q. On peut donc supposer que si on s’entraîne suffisamment longtemps le réseau de neurones va converger et l’estimateur va devenir bon.

En réalité la convergence de tels algorithmes n’est pas mathématiquement prouvée. Celle-ci a été démontrée dans le cas d’utilisation d’approximateurs linéaires de la fonction de valeur Q (telles que les Q-tables) [Watkins and Dayan, 1992] mais pas en utilisant des approximateurs non-linéaires tels que les réseaux de neurones. N’ayez crainte, le succès de l’utilisation de ces méthodes laisse à penser qu’ils convergent, sans que l’on sache encore exactement pourquoi...

En prenant en compte tout ce qui vient d’être dit l’algorithme du DQL est :

Fig 7 : Pseudo-algorithme du Deep Q-Learning adapté de [Mnih et al., 2013] .

2.2. Limites du DQL

Cependant, le DQL ainsi implémenté est considéré comme instable lorsqu’il utilise des approximateurs non-linéaires tels que les réseaux de neurones profonds [Tsitsiklis and Van Roy, 1997]. Cela est principalement dû à deux choses :

  1. La forte corrélation qui lie les séquences d’observation : les états sont observés les uns à la suite des autres et présentés dans cet ordre au réseau de neurones pour l’entraînement. En effet, un état st+1 ressemble fortement à un état St, puisqu’ils correspondent à deux images successives de la route.
  2. La forte influence de la fonction Q sur la politique menée et donc sur la distribution des états rencontrés dans l’environnement. L’état St+1 est issu de l’état St après avoir entrepris l’action at (qui peut être aléatoire ou issue de la prédiction de notre réseau de neurones si on suit une politique epsilon-greedy) qui elle même dépend de notre politique.

Afin de traiter le premier problème #1, une méthode appelée experience replay peut être utilisée.

2.3. Experience replay

Le principe de l'experience replay [Lin, 1992] est d’utiliser une mémoire de reprise (replay memory) pour stocker les transitions observées lors de l’exploration de l’environnement de la part de l’agent puis les sélectionner aléatoirement à chaque étape de l’apprentissage. Ces tuples de transitions sont des quintuplets de la forme (st, at, rt, st+1, terminalt) (terminal étant un booléen indiquant si l’état est terminal ou non) correspondant à une seule étape de l’exploration de l’environnement. Lors de l’étape de mise à jour des paramètres du réseau de neurones, on sélectionne aléatoirement les expériences à l'intérieur de cette mémoire de reprise plutôt que de s’entraîner sur la dernière expérience observée ce qui évite d’introduire un biais lors de l’apprentissage. Ce principe est résumé en figure 8.

Fig 8: Principe de l’experience replay

Un deuxième avantage de cette technique est qu’elle donne la possibilité de s’entraîner par “lots” (mini-batches) et de pouvoir faire une descente de gradient stochastique. Sans rentrer dans le détail, plutôt que de mettre à jour les paramètres de notre réseau de neurones en n’utilisant qu’une seule étape de transition à chaque fois, on calcule un gradient “agrégé” qui moyenne plusieurs gradients issus de plusieurs étapes de transition différentes. Cette technique permet d’augmenter les chances de trouver “une bonne direction” pour la descente de gradient et d’augmenter la vitesse de convergence de l’algorithme  [StackExchange : "Shuffling data in the mini-batch training of neural network"].

Reste un deuxième problème à résoudre : la forte influence de la fonction Q sur la politique menée et donc sur la distribution des états rencontrés dans l’environnement #2.

2.4. Le double Deep Q-Learning ou DDQL

Le Double Deep Q-Learning (DDQL) est une version améliorée du DQL permettant de palier à l’une de ses faiblesses : la surestimation de l’importance de certaines actions dans certaines conditions [van Hasselt et al., 2015].

L’idée derrière le DDQL est de séparer la sélection de l’action qui maximise la valeur Q de son évaluation. L’expression de mise-à-jour de la valeur Q donnée dans l’expression de la fonction de coût utilisée pour la descente de gradient sur le réseau de neurones suppose l’utilisation du même réseau de neurones pour sélectionner l’action at+1 et pour calculer la valeur Q (st+1, at+1, theta(actuel)). Le DDQL propose donc l’utilisation de deux réseaux de neurones distincts :

  • l’un pour la sélection de l’action : le réseau "Q"
  • l’autre pour l’évaluation de l’action : le réseau “Q-cible".

Lors de l’entraînement, les paramètres du réseau de neurones "Q-cible" sont régulièrement mis-à-jour en clonant les paramètres du réseau de neurones "Q" ce qui permet de profiter de l’amélioration de l’estimation dû à l’apprentissage progressif de l’agent pendant l’entraînement.

Fig 9: Principe du dédoublement du réseau de neurones pour le DDQL

Le pseudo code de notre algorithme de DDQL avec expérience-replay s’écrit comme suit :

Fig 10 : Pseudo-algorithme du Double Deep Q-Learning adapté de [van Hasselt et al., 2015]. Les modifications apportées par rapport à l’algorithme précédent (figure 7) sont en mises en valeur.

3. Comment l’algorithme interagit avec le simulateur

Nous avons décrit le type d’algorithme utilisé et son fonctionnement. Mais concrètement comment cet algorithme interagit avec le simulateur ?

Un simulateur de conduite est a priori un jeu vidéo conçu pour interagir avec un utilisateur humain via une interface physique. Pour pouvoir être manipulé par un agent de RL, le simulateur doit posséder une API [Application Programming Interface] permettant un appel automatisé aux commandes du simulateur. Si cette API n’est pas directement incluse dans le code du simulateur, il faut concevoir une couche supplémentaire de code, un wrapper, permettant de remplir cette fonction.

Nous avons introduit dans l’article précédent une API standard souvent retrouvée dans le domaine du RL : l’interface [Gym]. Pour répondre à notre problème nous allons devoir créer un environnement personnalisé qui ressemble à ceci :

Fig 11 : Structure globale d’un environnement de type Gym

Pour notre cas d’usage, nous allons utiliser le simulateur Donkey Car dans sa version proposée par Tawn Kramer [Code source du simulateur Donkey de Tawn Kramer]. Ce simulateur est un code source écrit en C#  qui, compilé à l’aide du logiciel d’édition de jeux vidéos 3D Unity, permet de générer un fichier binaire. Pour interagir avec le processus correspondant à l’exécution de ce fichier binaire, nous utilisons une interface Gym customisée selon le modèle décrit précédemment (reconstruite à partir de celle de Tawn Kramer [Interface Gym customisée de Tawn Kramer]). C’est dans l’implémentation des classes et méthodes de cette interface qu’on gère la communication avec le simulateur via le réseau local. Par la suite, nous utiliserons le terme de simulateur pour désigner l’ensemble formé par le fichier binaire compilé à l’aide d’Unity ainsi que le wrapper Python (implémentation de l’interface Gym customisée) comme résumé en figure 12.

Fig 12 : Fonctionnement du simulateur, ensemble formé par le fichier binaire et le wrapper python

Mettre en place cet environnement n’est en réalité pas une mince affaire. Il faut apporter des modifications aux codes sources cités desquels nous sommes repartis, mais de telles considérations nous emmeneraient en dehors du sujet de cet article. Ici, il s’agit simplement de comprendre que nous nous sommes outillés d’une librairie Python customisée nous fournissant toutes les méthodes utiles à l’interaction de notre algorithme avec notre simulateur.

Conclusion

Nous avons décrit l’algorithme de Double Deep Q-Learning utilisé, ainsi que les modalités de son interaction avec le simulateur. Ce qu’il est important de retenir :

  • On cherche à entraîner un oracle (le réseau de neurones) qui pour un état donné nous dit : si j’entreprend telle action, je suis censé accumuler telle récompense avant de sortir de la route.
  • Pour entraîner cet oracle, on se promène dans l’environnement et on stocke toutes nos observations dans une mémoire de reprise. L’oracle va ensuite piocher aléatoirement dans cette mémoire pour s’entraîner.
  • On utilise la récompense pour calculer une valeur cible. La différence entre la valeur cible et la valeur prédite par l’oracle est la mesure que celui-ci utilise pour affiner sa prédiction. La valeur cible étant calculée à partir de la récompense l’oracle va affiner sa prédiction au fur et à mesure de l’entraînement.
  • Comme le calcul de la valeur cible utilise la prédiction de l’oracle, on choisit de le dédoubler en utilisant un oracle pour le calcul de cet valeur, et un autre oracle qui s’entraîne. Régulièrement, on met-à-jour l’oracle du calcul qui sert à calculer la valeur cible avec les informations de l’oracle qui s’entraîne.

Le pseudo code de notre algorithme est donné en annexe 1.

Il est important de remarquer que la seule chose qu’est capable de faire un algorithme de RL est de converger vers la politique maximisant la récompense. Si l’entraînement fonctionne bien, l’algorithme va trouver une manière (si ce n’est la meilleure) d’évoluer dans l’environnement pour maximiser la récompense. Cependant si la maximisation de cette récompense n’a aucun rapport avec la tâche que nous souhaitons accomplir… l’algorithme convergera vers un état où il est incapable de remplir sa tâche. N’ayez crainte, nous aborderons la question du choix de la fonction de récompense dans l’article suivant.

Notre environnement d’apprentissage et notre algorithme étant prêt, on peut commencer l’entraînement … ce que nous verrons dans un deuxième article !

Références

Annexes

Annexe 1 : Structure globale de notre algorithme de double Deep Q-learning avec experience replay implémenté en python