Lea sobre qué tipo de competencia es y cómo logramos ganarla (y se enviaron más de 2000 soluciones de 51 países al concurso) bajo el corte.
nuestro equipo
El equipo de JBR_HSE estaba formado por cinco miembros: Konstantin Makhnev (estudiando en el cuarto año del programa de licenciatura " Matemáticas aplicadas e informática ") Oleg Svidchenko y Vladimir Egorov (ambos estudiando en la maestría " Programación y análisis de datos "), el estudiante de doctorado Dmitry Ivanov y director del Centro de Análisis datos y aprendizaje automático NRU HSE - San Petersburgo Alexey Shpilman. Todos, excepto Konstantin, también trabajan en el laboratorio de Sistemas de agentes y Aprendizaje por refuerzo en JetBrains Research, de ahí el nombre del equipo. Mientras participaba en la competencia, Kostya entrenó en el mismo laboratorio.
NeurIPS 2020: Flatland - ¿que es?
Flatland es un concurso que se llevó a cabo del 10 de julio al 15 de noviembre basado en la plataforma AIcrowd y apoyado por la reconocida conferencia internacional NeurIPS . El objetivo del concurso es desarrollar un algoritmo que pueda gestionar el tráfico ferroviario de la mejor manera posible. Una limitación importante era que las decisiones debían tomarse en un tiempo limitado (5 segundos por cada paso del simulador), lo que imposibilitaba simplemente seleccionar las acciones óptimas.
NeurIPS 2020: Flatland tenía dos direcciones: aprendizaje general y por refuerzo (RL). La primera área estaba abierta a cualquier decisión y la segunda solo a aquellos que usaban el aprendizaje por refuerzo.
Los organizadores proporcionaron a los participantes un simulador Flatland, que es una cuadrícula bidimensional, donde cada celda tiene su propio tipo: carretera, giro, bifurcación o terreno intransitable. Cada tren ocupa exactamente una celda en la cuadrícula y tiene una dirección en la que se mueve actualmente. La simulación se lleva a cabo paso a paso, en cada paso de cada tren, debe determinar qué acción tomar: detenerse, seguir por la vía más a la izquierda o seguir por la vía más a la derecha. Dado que la implementación actual no proporciona una intersección completa, es decir no sucede que se pueda ir hacia adelante, derecha e izquierda al mismo tiempo, entonces tampoco es necesaria la acción “seguir adelante”. En el caso de que no haya turnos, la segunda y tercera acciones son equivalentes. Los trenes pueden chocar entre sí; resulta un punto muerto.El objetivo del concurso es hacer que todos los trenes lleguen a sus destinos lo más rápido posible. Las decisiones se juzgan por la cantidad de tiempo que los trenes tardaron en llegar a la meta. En caso de que el tren no haya llegado, su tiempo es igual al tiempo máximo de simulación.
Solución: cómo interactuará el agente con el simulador
Ya ha habido bastantes publicaciones en Habré sobre el aprendizaje por refuerzo, por lo que no nos detendremos en los conceptos básicos en detalle. Digamos que en el caso de Flatland, la simulación del ferrocarril actúa como entorno y el tren actúa como agente. Es importante señalar que, dado que muchos trenes están involucrados en la simulación, este entorno es multiagente.
Al resolver el problema, cambiamos significativamente el proceso de interacción entre el agente y el simulador, lo que nos permitió aumentar significativamente la eficiencia de nuestro algoritmo. En general, estas modificaciones a menudo afectan en gran medida el resultado, pero requieren conocimientos específicos de la tarea.
Uno de los cambios más significativos fue que decidimos no darle libertad de acción al agente cuando no está cerca de la intersección. Así, un agente sólo puede tomar decisiones cuando se encuentra frente a una bifurcación o en una bifurcación, y en otros casos siempre avanza por el único camino posible. Esto acorta enormemente la duración del episodio y, por lo tanto, facilita mucho la tarea. También decidimos que el agente terminará su episodio cuando alcance la meta o cuando entre en un punto muerto y no pueda moverse (en el simulador, en tales casos, el episodio continúa). Más tarde decidimos que los episodios no deberían comenzar de inmediato para todos, le contaremos más sobre esto a continuación.
La observación de un agente consta de dos partes: entidades que están vinculadas a una parte específica de la ruta y entidades que no están vinculadas a una parte específica de la ruta. Aquí, una parte del camino significa un tramo de la carretera que conecta dos bifurcaciones.
La primera parte de la observación se puede representar como un árbol, en la parte superior del cual hay bifurcaciones y los bordes son los caminos entre ellos. A cada borde y vértice al que conduce, asociamos un vector de características calculadas para una sección determinada del camino (por ejemplo, la longitud del camino, la distancia desde el final del borde hasta el destino, etc.). Fijamos la profundidad del árbol, limitando así el número de vectores de características obtenidos en la primera parte de la observación. A continuación se muestra un ejemplo de cómo se construye esta parte de la observación. Las líneas de colores representan las secciones de la carretera que son bordes del árbol.
La segunda parte de la observación incluye señales como la distancia mínima al destino, si el agente está en la intersección o frente a ella, el agente entró en el punto muerto, etc. También vale la pena señalar que a cada agente al comienzo del episodio se le asigna un identificador (un número aleatorio de 0 a 1), que se queda con él durante el resto del episodio y le permite negociar mejor con el resto de agentes. Hay signos que dependen de los identificadores de los agentes en ambas partes de la observación.
Solo queda definir la función de recompensa del agente. Después de algunas selecciones, nos decidimos por una bastante simple: $ 0.01 \ cdot \ Delta d - 5 \ cdot \ text {is \ _deadlocked} + 10 \ cdot \ text {is \ _succeed} $, es decir La recompensa refleja cuánto ha cambiado la distancia $ d $ al destino desde que se tomó la decisión, con una recompensa adicional si el episodio se completa con éxito y una penalización si llega a un punto muerto.
Algoritmo PPO
Hay muchos algoritmos de aprendizaje por refuerzo que están diseñados para resolver problemas de múltiples agentes. Sin embargo, decidimos utilizar el algoritmo PPO - Proximal Policy Optimization como algoritmo de línea de base , ya que su código podría reutilizarse para implementar algoritmos RL multiagente (por ejemplo, COMA). Más tarde, sin embargo, resultó que PPO (con algunas modificaciones) en sí mismo resuelve bien el problema, pero los métodos de múltiples agentes están entrenados mucho peor, por lo que PPO siguió siendo la parte principal de nuestra solución final.
El algoritmo clásico de PPO consta de dos partes: el actor y el crítico. El crítico aproxima la función de valor y el actor enseña una política aleatoria $ \ pi_ \ theta (a | s) $ que maximiza el valor esperado de la recompensa total.
Una de las modificaciones importantes que hicimos fue la adición de un módulo a la arquitectura del actor que le permite al agente comunicarse con los agentes cercanos. El proceso de comunicación se construye de manera bastante simple: los agentes generan mensajes simultáneamente y los envían a todos los trenes próximos a los que se encuentran, y luego, habiendo recibido mensajes de los vecinos, los combinan en un solo mensaje por promediado ponderado. Se utilizó un sencillo mecanismo de auto-atención para determinar los pesos con los que se promediarán los mensajes. Con tal construcción del proceso de comunicación, no hay necesidad de modificar de alguna manera el proceso de aprendizaje, porque es suficiente simplemente permitir que los gradientes pasen por los mensajes durante la propagación hacia atrás del error.
Decidimos entrenar a PPO con un mapa pequeño y una pequeña cantidad de agentes, asumiendo que dado que el agente solo observa lo que está a su lado, después del entrenamiento trabajará bien en entornos más grandes.
¿Cómo decides qué trenes comenzar y cuándo?
Después de haber intentado simplemente aplicar el algoritmo PPO, rápidamente llegamos a la conclusión de que la mayoría de los interbloqueos ocurren precisamente porque los trenes comienzan a moverse al mismo tiempo e interfieren entre sí. Resolvimos este problema de la siguiente manera: comenzamos a ejecutar solo unos pocos agentes al mismo tiempo. Cuando uno de los agentes terminó su episodio, al otro agente se le permitió comenzar a moverse. En este enfoque, es importante comprender en qué secuencia deben lanzarse los trenes.
El primer enfoque que intentamos fue lanzar los agentes más cercanos a su objetivo. Cuando se usó en un entorno pequeño (carreteras cortas y pocos agentes) funcionó lo suficientemente bien, pero para entornos grandes funcionó mucho peor. Por lo tanto, decidimos usar este enfoque solo durante el entrenamiento del agente, y para la aplicación (es decir, el envío al sistema de prueba) usamos un algoritmo diferente. La idea de este algoritmo es entrenar a un clasificador, que por cada agente que no haya comenzado a moverse determinará si llegará al final o no. Entonces, si la probabilidad de llegar con éxito al destino es lo suficientemente grande, entonces el agente comienza a moverse, si no, espera hasta que la probabilidad sea suficiente.
Resultados de la competencia
Como resultado, nuestra solución ocupó el primer lugar en la pista de RL y el octavo en la general. Esto significa que el enfoque sin RL es aún mejor en este punto, pero muestra que el aprendizaje por refuerzo tiene potencial. Nuestro enfoque tiene bastantes debilidades y problemas sin resolver (por ejemplo, problemas serios con la escalabilidad a entornos grandes), por lo que todavía tenemos algo en lo que trabajar. Ahora nosotros, junto con los organizadores del concurso, estamos preparando un artículo para enviarlo al libro del concurso NeurIPS 2020.