Apprentissage par renforcement contraint et voitures autonomes – le parcours d’un stagiaire

Ce billet a été écrit par un stagiaire d’Ubisoft La Forge, Max Brodeur. Il y décrit son projet estival.

Introduction

Grâce à l’apprentissage par renforcement (AR), on peut apprendre des tâches complexes à des ordinateurs en renforçant positivement ou négativement des comportements, bons ou mauvais. Par exemple, dans le domaine du jeu vidéo, un modèle formé par l’AR pourrait apprendre à s’orienter dans un environnement 3D complexe comme le ferait un joueur ou une joueuse. Cette technologie a le potentiel de transformer le paradigme de la conception des jeux vidéo, que l’on parle de l’amélioration des capacités de test, ou de l’intégration de prodigieux bots à l’expérience vidéoludique.

Toutefois, la mise en place d’un système efficace d’AR peut s’avérer plutôt difficile. C’est le processus de façonnement de récompense qui pose un problème particulier. Le cadre de spécification du comportement développé chez Ubisoft La Forge vise à pallier ce problème par la simplification des mesures de comportement et par l’automatisation du processus de pondération de valeur.

Sur la base de ce travail, nous avons entrepris de généraliser sa mise en œuvre en l’appliquant à un problème connu: la navigation de véhicules dans les jeux vidéo. À la suite d’un projet de stage estival, nous avons démontré que notre mise en œuvre généralisée facilite grandement le processus de façonnement de récompense. L’approche est prometteuse et a le potentiel d’améliorer la productivité des équipes de développement.

Dans ce texte, on propose un bref résumé du problème de la navigation de véhicules, du processus de façonnement de récompense, et de la théorie d’apprentissage par renforcement sous contrainte (pour vous informer davantage sur le sujet, vous pouvez lire cet article ou ce billet de blogue). Enfin, on présente les résultats de la spécification du comportement sur la navigation de véhicules — avec de chouettes vidéos!

La navigation de véhicule

Les emplois d’un modèle AR de pilotage de véhicule sont pluriels: on n’a qu’à penser au test de jeux vidéo, où l’équipe de développement envoie des modèles sur différentes trajectoires pour en vérifier la faisabilité. Pour ce projet, on entraine des véhicules dans un environnement dont la géométrie et la difficulté des terrains varient.

Les véhicules apparaissent sur des points arbitraires de la carte et se font assigner des trajectoires à suivre et des vitesses cibles générées au hasard. Leur tâche est d’atteindre le point final du trajet en conduisant à la bonne vitesse. Le modèle reçoit suffisamment d’informations sur l’environnement pour « comprendre » le problème; par exemple la distance qui le sépare du trajet, les angles d’élévation, la distance des obstacles, etc.

Avant d’entrer dans le vif du sujet, regardons d’abord la façon classique d’aborder ce problème, soit par l’AR avec façonnement de récompense.

Le façonnement de récompense

Le façonnement de récompense est l’élaboration minutieuse d’une fonction mathématique qui évalue le succès d’une action exécutée par notre modèle. Pour évoquer une métaphore, la récompense correspond à la gâterie offerte à un chien qui aurait accompli un tour impressionnant. Elle peut aussi prendre la forme d’une « pénalité », comme quand on crie « mauvais chien! » à l’animal qui a fait une bêtise.

F(x)= Gâterie

F(x)= Mauvais chien!

On peut facilement imaginer la complexité que cette fonction mathématique peut exhiber pour certaines tâches. Pour l’exemple du véhicule autonome dans un jeu vidéo, une fonction de récompense substantielle s’impose. Pour donner une idée, une des fonctions de récompense que j’ai vue à Ubisoft comportait près de 400 lignes de code.

D’abord, qu’entend-on par fonction de récompense? C’est un concept qui permet de spécifier à un modèle donné un comportement désiré en évaluant le succès d’une action. Dans le cas de la navigation du véhicule, on désire que le modèle suive une trajectoire prédéterminée à une vitesse convenue. On programme ces deux comportements avec cette fonction de récompense:

En général, l’objectif d’un entraînement d’AR est de maximiser la valeur attendue de l’ensemble des récompenses futures. Maintenant qu’on a élaboré une fonction, il sera plus facile de définir la notion de façonnement de récompense. En bref, le façonnement de récompense agit comme un modificateur des composantes de la fonction de récompense. Il trouve les mesures optimales de b0 & b1 pour exprimer les comportements désirés, tout en trouvant les poids idéaux pour w0 & w1, lesquels s’imposeront sur ces mesures.

Il y a un scénario qui survient fréquemment et qui exige la pondération des comportements. Considérons que l’on démarre un entraînement non pondéré (c’est-à-dire où w0 = 1 & w1 =1). Lors de l’initialisation, le véhicule se lance d’emblée sur sa trajectoire, mais on constate qu’il ne roule pas à la vitesse convenue. En effet, à cause de la différence dans la fréquence des deux comportements, le modèle aura tendance à prioriser l’un des deux en négligeant l’autre (dépendamment de si la récompense est positive ou négative). Un développeur ou une développeuse d’expérience prendra des précautions pour éviter un tel scénario en établissant une fonction de récompense qui diminue le poids du comportement le plus fréquent. Toutefois, à mesure que s’accroît le nombre d’opérations complexes, une évaluation du rendement du modèle devient souvent nécessaire afin de modifier la pondération. Dans le cas qui nous intéresse, la navigation d’un véhicule peut solliciter plus d’une douzaine d’heures d’entraînement avant de produire des résultats intéressants. Au bout du compte, et à moins d’une chance inouïe, le façonnage de récompense est presque toujours requis pour parvenir aux meilleurs résultats, un processus qui s’étend sur plusieurs jours et, quelquefois, plusieurs semaines!

L’apprentissage par renforcement sous contrainte

Le cadre d’apprentissage par renforcement sous contrainte d’Ubisoft a été développé pour alléger le long processus de façonnement de récompense. On espère ainsi en arriver à une solution qui diminue le nombre de modifications manuelles des paramètres nécessaires. Au lieu d’offrir sous forme de valeur isolée une récompense grâce à une ingénieuse fonction de récompense, notre solution pondère automatiquement les comportements binaires.

Dans le but d’automatiser le processus de pondération, on doit considérer qu’il est difficile de faire une interprétation mathématique des valeurs des comportements lorsqu’elles prennent la forme d’un scalaire continu. Par exemple, comment doit-on interpréter les valeurs que voici?

Ce 0,5: est-il bon ou mauvais? Pour résoudre la question, il nous faudrait savoir ce à quoi correspond le comportement dans son environnement. Or, l’une des avancées clés de la recherche a été de convertir les comportements à des valeurs binaires. Ce faisant, on peut interpréter toute valeur associée à un comportement, nonobstant le contexte de son environnement. La contrainte binaire détermine un comportement qui s’exprime comme suit:

L’intégration d’une négation dans le système binaire est intentionnelle — elle vise à diminuer l’occurrence des contraintes. En effet, lorsque les valeurs de comportement sont exprimées sous la forme d’une contrainte binaire, elles ont toujours le même sens. Il est donc plus facile de les comparer.

Mais comment les comparer?

Voilà où tout se met en place. Si l’on considère les valeurs sous contrainte pour N intervalles, on parvient à évaluer les performances sous contrainte selon la définition suivante:

Ce n’est rien, en réalité, qu’une manière un peu sophistiquée de calculer le pourcentage de temps qu’un comportement se manifeste dans un échantillon. On peut maintenant comparer les contraintes à partir de leurs performances, par exemple ci = 30 % indiquant que le comportement bi s’est manifesté 30 % du temps dans un échantillonnage donné.

Qu’en est-il de l’automatisation de la pondération des contraintes? Elle exige la mise en place de seuils. Pour chaque contrainte ci, on définit un seuil ti qui représente le rendement visé. Comme on le sait, pour chaque contrainte binaire bi, on a un poids wi. À l’aide de superbes outils de descente de gradient en apprentissage machine (l’algorithme d’optimisation Adam, dans ce cas-ci), on réduit au minimum la fonction d’erreur suivante en rapport avec les mesures de poids wi:

Les poids sont passés dans une couche softmax. Un algorithme de descente du gradient qui passe par une couche softmax produit une réactualisation du poids en fonction de l’importance des autres poids. Un tel résultat est salutaire puisqu’il permet d’accorder la priorité aux contraintes qui ont mal performé.

La dernière composante nécessaire au processus d’AR sous contrainte (après les contraintes binaires et les seuils) est la récompense rare. À la différence des contraintes, la phase d’apprentissage va maximiser la valeur projetée de la récompense rare.

Un poids supplémentaire wr est ajouté au vecteur poids de la récompense rare. Toutefois, on garde Err( wr ) = 0 pour l’ensemble des actualisations du poids. De cette façon, la mise à jour du poids de la récompense rare dépendra seulement du gradient de la fonction softmax. Le poids augmentera seulement si les autres poids ont assez diminué. En d’autres mots, une fois que les contraintes sont satisfaites, l’entraînement est focalisé sur la maximisation de la récompense rare.

Au lieu d’une valeur scalaire, la récompense est maintenant un vecteur multidimensionnel fondé sur les valeurs des contraintes binaires et de la récompense rare. Cette récompense est calculée à tous les intervalles du processus. De concert avec le vecteur de seuil, il s’agit de l’unique information nécessaire pour exécuter la phase d’apprentissage.

Résultats

Examinons la configuration suivante à partir des comportements de trajectoire et de vitesse déterminés précédemment:

On observe deux attributs particuliers dans cette configuration: les deux contraintes de vitesse et leurs seuils élevés. Puisque l’on désire que le véhicule maintienne le plus possible la vitesse cible, une approche possible serait de réduire la valeur des seuils. Mais l’existence de ces deux caractéristiques découle d’une impossibilité pour le véhicule d’être exactement sur la vitesse cible.

Le comportement qui modifie la vitesse du véhicule a été séparé en deux contraintes puisqu’il ne peut être exprimé à l’aide d’une seule contrainte. Par exemple, si la contrainte était définie telle que:

Alors on aurait b1 = 1 pour tous les intervalles. Le poids de la contrainte exploserait et le modèle tenterait indéfiniment d’apprendre un comportement qui lui est inaccessible.

On pourrait avancer qu’il est effectivement possible de définir en une seule contrainte le comportement qui modifie la vitesse comme suit:

Mais définir la largeur de cette étendue équivaut à définir un seuil au comportement. Il est plus difficile de répondre à la contrainte d’une petite largeur qu’à celle d’une grande largeur, et les seuils ne fonctionnent pas autrement. Toutefois, nos pourcentages de contrainte sont comparés aux seuils et non pas aux étendues. Ainsi, il est plus difficile d’appréhender la valeur seuil dans le cas de cette définition de contrainte basée sur un intervalle.

Alors, ce qu’on réalise en séparant ce comportement en deux contraintes, c’est de transformer une égalité en deux inégalités. Dans le contexte des contraintes et des seuils, les inégalités sont beaucoup plus faciles à appréhender.

Pour les seuils à haute valeur (t1 & t2), on se fonde sur l’identité ci-dessus.

La première implication découle du fait que le véhicule demeure 100 % du temps soit au-dessus ou au-dessous de la vitesse ciblée. La deuxième découle du fait que l’on veut des seuils réalisables. Si la somme de leur valeur était en deçà de 100 %, le modèle poursuivrait un objectif de rendement impossible!

On démarre l’apprentissage. C’est le temps d’en profiter pour souffler un peu, prendre un café, ou faire une sieste.

Après quelques heures d’entraînement, les véhicules réagissent de manière surprenante…

En fait, on réalise que les véhicules répondent aux contraintes. Mais la contrainte de la trajectoire a été calculée selon la distance latérale entre le véhicule et sa trajectoire. Le véhicule suivait la trajectoire quant à l’axe gauche-droite de la trajectoire, mais la contrainte de trajectoire ne fournissait aucune information sur son axe avant-arrière. En effet, le modèle optimise son comportement pour cette configuration: dès le démarrage, il opère un demi-tour et roule à la vitesse ciblée jusqu’à la fin de l’exercice.

Comment corriger le tir? Par l’ajout d’une contrainte supplémentaire! On introduit une notion de direction au véhicule en intégrant simplement une contrainte binaire qui indique le comportement du d’absorption de la trajectoire.

Observez les résultats après près de 20 heures d’exercices sous cette nouvelle configuration.

Assez impressionnant pour une simple fonction de récompense!

Enfin, le prochain exemple est parfait pour démontrer l’efficacité de l’apprentissage par renforcement. Aucune instruction explicite n’a été soumise au modèle pour lui ordonner d’opérer un demi-tour s’il apparaissait en sens contraire. Et rien n’empêchait le véhicule de rouler en sens contraire jusqu’au point d’arrivée. Les seuls paramètres en jeu étaient les quatre contraintes binaires et la récompense rare. C’est tout ce qu’il fallait pour que le modèle déduise durant la phase d’apprentissage le comportement optimal à suivre.

Quelle est la prochaine étape?

Grâce à ce projet, on peut conclure que le cadre d’AR sous contrainte est une approche simplifiée prometteuse à l’entraînement par AR de modèles de véhicules autonomes. Comme démontré dans un autre billet, on peut aussi l’appliquer à la navigation complexe de PNJ. Mais ce ne sont que deux des possibles emplois de cette technique. Essentiellement, dès qu’on veut assigner un comportement spécifique à un bot, que ce soit dans le domaine de la navigation, du combat, ou autre, nous croyons que l’AR sous contrainte s’avère être un outil formidable!