Découvrez de quel type de concours il s'agit et comment nous avons réussi à le gagner (et plus de 2000 solutions de 51 pays ont été envoyées au concours) sous la coupe.
notre équipe
L'équipe JBR_HSE était composée de cinq membres: Konstantin Makhnev (étudiant en 4e année du programme de licence " Mathématiques appliquées et informatique ") Oleg Svidchenko et Vladimir Egorov (tous deux étudiant au master " Programmation et analyse de données "), doctorant Dmitry Ivanov et responsable du Centre d'analyse données et apprentissage automatique NRU HSE - Saint-Pétersbourg Alexey Shpilman. Tout le monde, à l'exception de Konstantin, travaille également dans le laboratoire d'apprentissage des systèmes d'agent et du renforcement de JetBrains Research - d'où le nom de l'équipe. En participant au concours, Kostya s'est entraîné dans le même laboratoire.
NeurIPS 2020: Flatland - qu'est-ce que c'est?
Flatland est un concours qui s'est déroulé du 10 juillet au 15 novembre basé sur la plateforme AIcrowd et soutenu par la célèbre conférence internationale NeurIPS . L'objectif du concours est de développer un algorithme capable de gérer au mieux le trafic ferroviaire. Une limitation importante était que les décisions devaient être prises dans un temps limité (5 secondes par étape du simulateur), ce qui rendait impossible de sélectionner simplement les actions optimales.
NeurIPS 2020: Flatland avait deux directions: l'apprentissage général et l'apprentissage par renforcement (RL). Le premier domaine était ouvert à toutes les décisions et le second uniquement à ceux qui utilisent l'apprentissage par renforcement.
Les organisateurs ont fourni aux participants un simulateur Flatland, qui est une grille bidimensionnelle, où chaque cellule a son propre type: route, virage, fourche ou terrain impraticable. Chaque train occupe exactement une cellule sur la grille et a une direction dans laquelle il se déplace actuellement. La simulation se déroule étape par étape, à chaque étape de chaque train, vous devez déterminer l'action à entreprendre: arrêter, suivre la voie la plus à gauche ou suivre la voie la plus à droite. Puisque l'implémentation actuelle ne fournit pas une intersection complète, c'est-à-dire il n'arrive pas que vous puissiez avancer, à droite et à gauche en même temps, alors l'action «avancer» n'est pas non plus nécessaire. Dans le cas où il n'y a pas de virage, les deuxième et troisième actions sont équivalentes. Les trains peuvent entrer en collision les uns avec les autres - cela s'avère une impasse.Le but du concours est de permettre à tous les trains d'atteindre leur destination le plus rapidement possible. Les décisions sont jugées en fonction du temps que les trains ont mis pour atteindre l'objectif. Dans le cas où le train n'est pas arrivé, son temps est égal au temps maximum de simulation.
Solution: comment l'agent interagira avec le simulateur
Il y a déjà eu pas mal d' articles sur Habré sur l'apprentissage par renforcement, nous ne nous attarderons donc pas sur les concepts de base en détail. Disons simplement que dans le cas de Flatland, la simulation du chemin de fer joue le rôle d'environnement et le train joue le rôle d'agents. Il est important de noter que puisque de nombreux trains sont impliqués dans la simulation, cet environnement est multi-agents.
Lors de la résolution du problème, nous avons considérablement modifié le processus d'interaction entre l'agent et le simulateur, ce qui nous a permis d'augmenter considérablement l'efficacité de notre algorithme. En général, ces modifications affectent souvent considérablement le résultat, mais elles nécessitent des connaissances spécifiques à la tâche.
L'un des changements les plus significatifs a été que nous avons décidé de ne pas donner à l'agent la liberté d'action lorsqu'il n'est pas près de l'intersection. Ainsi, un agent ne peut prendre des décisions que devant une fourche ou à une fourche, et dans d'autres cas, il avance toujours le long du seul chemin possible. Cela raccourcit considérablement la durée de l'épisode et rend donc la tâche beaucoup plus facile. Nous avons également décidé que l'agent mettrait fin à son épisode soit lorsqu'il atteindra l'objectif, soit lorsqu'il se trouvera dans une impasse et ne pourra pas bouger (dans le simulateur, dans de tels cas, l'épisode continue). Plus tard, nous avons décidé que les épisodes ne devraient pas commencer immédiatement pour tout le monde, nous vous en dirons plus à ce sujet ci-dessous.
L'observation pour un agent se compose de deux parties: les entités liées à une partie spécifique du chemin et les entités qui ne sont pas liées à une partie spécifique du chemin. Ici, une partie du chemin signifie une section de la route qui relie deux fourches.
La première partie de l'observation peut être représentée comme un arbre, au sommet duquel se trouvent des fourches, et les bords sont les routes entre eux. A chaque arête et sommet auquel il mène, on associe un vecteur d'entités calculées pour une section donnée du chemin (par exemple, la longueur du chemin, la distance de l'extrémité de l'arête à la destination, etc.). Nous avons fixé la profondeur de l'arbre, limitant ainsi le nombre de vecteurs de caractéristiques obtenus à partir de la première partie de l'observation. Voici un exemple de la façon dont cette partie de l'observation est construite. Les lignes colorées représentent des tronçons de route qui sont des arêtes dans l'arbre.
La deuxième partie de l'observation comprend des signes tels que la distance minimale jusqu'à la destination, si l'agent est à l'intersection ou en face, l'agent est entré dans l'impasse, etc. Il convient également de noter que chaque agent au début de l'épisode se voit attribuer un identifiant (un nombre aléatoire de 0 à 1), qui l'accompagne pour le reste de l'épisode et lui permet de mieux négocier avec le reste des agents. Il y a des signes dépendant des identifiants d'agent dans les deux parties de l'observation.
Il ne reste plus qu'à définir la fonction de récompense de l'agent. Après quelques sélections, nous avons opté pour une solution assez simple: 0,01 $ \ cdot \ Delta d - 5 \ cdot \ text {is \ _deadlocked} + 10 \ cdot \ text {is \ _succeed} $, c'est-à-dire La récompense reflète à quel point la distance $ d $ à la destination a changé depuis que la décision a été prise, avec une récompense supplémentaire si l'épisode est terminé avec succès et une pénalité s'il rencontre une impasse.
Algorithme PPO
Il existe de nombreux algorithmes d'apprentissage par renforcement conçus pour résoudre des problèmes multi-agents. Cependant, nous avons décidé d'utiliser l'algorithme PPO - Proximal Policy Optimization comme algorithme de base , car son code pourrait être réutilisé pour implémenter des algorithmes RL multi-agents (par exemple, COMA). Plus tard, cependant, il s'est avéré que PPO (avec quelques modifications) résout bien le problème à lui seul, mais les méthodes multi-agents apprennent bien pire, donc PPO est resté la partie principale de notre solution finale.
L'algorithme PPO classique se compose de deux parties: l'acteur et le critique. Le critique se rapproche de la valeur-fonction, et l'acteur enseigne une politique aléatoire $ \ pi_ \ theta (a | s) $ qui maximise la valeur attendue de la récompense totale.
L'une des modifications importantes que nous avons apportées est l'ajout d'un module à l'architecture d'acteur qui permet à l'agent de communiquer avec les agents proches. Le processus de communication est construit assez simplement: les agents génèrent simultanément des messages et les envoient à tous les trains à côté desquels ils se trouvent, puis, ayant reçu des messages de voisins, les combinent en un seul message par moyenne pondérée. Un simple mécanisme d'auto-attention a été utilisé pour déterminer les poids avec lesquels les messages seront moyennés. Avec une telle construction du processus de communication, il n'est pas nécessaire de modifier en quelque sorte le processus d'apprentissage, car il suffit de laisser passer les dégradés à travers les messages tout en rétropropageant l'erreur.
Nous avons décidé de former PPO avec une petite carte et un petit nombre d'agents, en supposant que puisque l'agent n'observe que ce qui se trouve à côté de lui, après la formation, il fonctionnera bien dans des environnements plus grands.
Comment décidez-vous quels trains commencer quand?
Après avoir essayé d'appliquer simplement l'algorithme PPO, nous sommes rapidement arrivés à la conclusion que la plupart des blocages se produisent précisément parce que les trains commencent à se déplacer en même temps et interfèrent les uns avec les autres. Nous avons résolu ce problème de la manière suivante: nous n'avons commencé à exécuter que quelques agents en même temps. Quand l'un des agents a terminé son épisode, l'autre agent a été autorisé à commencer à bouger. Dans cette approche, il est important de comprendre dans quel ordre les trains doivent être lancés.
La première approche que nous avons essayée était de lancer les agents les plus proches de leur objectif. Lorsqu'il est utilisé dans un petit environnement - routes courtes et peu d'agents - il fonctionne assez bien, mais pour les grands environnements, il est bien pire. Par conséquent, nous avons décidé d'utiliser cette approche uniquement pendant la formation des agents et pour l'application (c'est-à-dire la soumission au système de test), nous avons utilisé un algorithme différent. L'idée de cet algorithme est de former un classifieur qui déterminera pour chaque agent qui n'a pas commencé à bouger s'il atteindra la fin ou non. Ensuite, si la probabilité d'atteindre avec succès la destination est suffisamment grande, alors l'agent commence à se déplacer, sinon, attend que la probabilité devienne suffisante.
Résultats du concours
En conséquence, notre solution a pris la première place de la piste RL et la huitième au général. Cela signifie que l'approche non-RL est encore meilleure à ce stade, mais cela montre que l'apprentissage par renforcement a du potentiel. Notre approche comporte de nombreuses faiblesses et problèmes non résolus (par exemple, de graves problèmes d'évolutivité vers de grands environnements), nous avons donc encore quelque chose à travailler. Nous préparons maintenant, avec les organisateurs du concours, un article pour l'envoyer au livre du concours NeurIPS 2020.