Leia sobre que tipo de competição é e como conseguimos vencê-la (e mais de 2.000 soluções de 51 países foram enviadas para a competição) abaixo do corte.
nosso time
A equipe JBR_HSE era composta por cinco membros: Konstantin Makhnev (estudando no 4º ano do programa de bacharelado “ Matemática Aplicada e Ciências da Computação ”) Oleg Svidchenko e Vladimir Egorov (ambos estudando no programa de mestrado “ Programação e Análise de Dados ”), aluno de doutorado Dmitry Ivanov e chefe do Centro de Análise dados e aprendizado de máquina NRU HSE - São Petersburgo Alexey Shpilman. Todos, exceto Konstantin, também trabalham no laboratório de Sistemas de Agentes e Aprendizado por Reforço na JetBrains Research - daí o nome da equipe. Enquanto participava da competição, Kostya treinou no mesmo laboratório.
NeurIPS 2020: Flatland - o que é?
Flatland é uma competição que aconteceu de 10 de julho a 15 de novembro baseada na plataforma AIcrowd e apoiada pela renomada conferência internacional NeurIPS . O objetivo da competição é desenvolver um algoritmo que possa gerenciar o tráfego ferroviário da melhor maneira possível. Uma limitação importante era que as decisões tinham que ser tomadas em um tempo limitado (5 segundos por uma etapa do simulador), o que impossibilitava simplesmente selecionar as ações ideais.
NeurIPS 2020: Flatland tinha duas direções: geral e Reinforcement Learning (RL). A primeira área estava aberta para qualquer decisão, e a segunda apenas para aqueles que utilizavam o aprendizado por reforço.
Os organizadores forneceram aos participantes um simulador Flatland, que é uma grade bidimensional, onde cada célula tem seu próprio tipo: estrada, curva, bifurcação ou terreno intransitável. Cada trem ocupa exatamente uma célula na grade e tem uma direção na qual está se movendo atualmente. A simulação ocorre passo a passo, em cada etapa de cada trem você precisa determinar que ação tomar: parar, ir ao longo do trilho mais à esquerda ou ir ao longo do trilho mais à direita. Uma vez que a implementação atual não fornece uma interseção completa, ou seja, não acontece que você pode ir para frente, para a direita e para a esquerda ao mesmo tempo, então a ação “ir para frente” também não é necessária. No caso em que não há turnos, a segunda e a terceira ações são equivalentes. Os trens podem colidir uns com os outros - acaba sendo um impasse.O objetivo da competição é fazer com que todos os trens cheguem aos seus destinos o mais rápido possível. As decisões são julgadas pela quantidade de tempo que os trens levaram para atingir a meta. Caso o trem não tenha alcançado, seu tempo é igual ao tempo máximo de simulação.
Solução: como o agente irá interagir com o simulador
Já houve alguns posts sobre Habré sobre aprendizagem por reforço, então não vamos nos alongar sobre os conceitos básicos em detalhes. Digamos apenas que, no caso de Flatland, a simulação da ferrovia atua como o ambiente e o trem atua como os agentes. É importante observar que, como muitos trens estão envolvidos na simulação, este ambiente é multiagente.
Na resolução do problema, alteramos significativamente o processo de interação entre o agente e o simulador, o que nos permitiu aumentar significativamente a eficiência do nosso algoritmo. Em geral, essas modificações geralmente afetam muito o resultado, mas exigem conhecimento específico da tarefa.
Uma das mudanças mais significativas foi que decidimos não dar liberdade de ação ao agente quando ele não estiver próximo ao cruzamento. Assim, um agente pode tomar decisões apenas quando está na frente de uma bifurcação ou em uma bifurcação e, em outros casos, ele sempre avança ao longo do único caminho possível. Isso reduz bastante a duração do episódio e, portanto, torna a tarefa muito mais fácil. Decidimos também que o agente encerrará seu episódio quando atingir a meta, ou quando entrar em um impasse e não puder se mover (no simulador, nesses casos, o episódio continua). Posteriormente, decidimos que os episódios não deveriam começar imediatamente para todos, falaremos mais sobre isso a seguir.
A observação de um agente consiste em duas partes: recursos que estão vinculados a uma parte específica do caminho e recursos que não estão vinculados a uma parte específica do caminho. Aqui, uma parte do caminho significa uma seção da estrada que conecta duas bifurcações.
A primeira parte da observação pode ser representada como uma árvore, no topo da qual existem bifurcações, e as bordas são os caminhos entre elas. A cada aresta e vértice que leva, associamos um vetor de recursos calculado para uma determinada seção do caminho (por exemplo, o comprimento do caminho, a distância do final da aresta até o destino, etc.). Fixamos a profundidade da árvore, limitando assim o número de vetores de características obtidos na primeira parte da observação. Abaixo está um exemplo de como esta parte da observação é construída. As linhas coloridas representam as seções da estrada que são arestas da árvore.
A segunda parte da observação inclui sinais como a distância mínima até o destino, se o agente está na interseção ou na frente dela, o agente entrou no impasse, etc. Também é importante notar que cada agente no início do episódio recebe um identificador (um número aleatório de 0 a 1), que fica com ele pelo resto do episódio e permite que ele negocie melhor com o resto dos agentes. Existem sinais dependendo dos identificadores do agente em ambas as partes da observação.
Resta apenas definir a função de recompensa do agente. Após alguma seleção, decidimos por um bastante simples: $ 0,01 \ cdot \ Delta d - 5 \ cdot \ text {is \ _deadlocked} + 10 \ cdot \ text {is \ _succeed} $, ou seja, A recompensa reflete o quanto a distância $ d $ até o destino mudou desde que a decisão foi tomada, com uma recompensa adicional se o episódio for concluído com sucesso e uma penalidade se chegar a um impasse.
Algoritmo PPO
Existem muitos algoritmos de aprendizagem por reforço que são projetados para resolver problemas multiagentes. No entanto, optamos por utilizar o algoritmo PPO - Proximal Policy Optimization como algoritmo de linha de base , pois seu código poderia ser reutilizado para implementar algoritmos RL multiagentes (por exemplo, COMA). Mais tarde, no entanto, descobriu-se que o PPO (com algumas modificações) resolve bem o problema, mas os métodos multiagentes são treinados muito pior, de modo que o PPO permaneceu como a parte principal de nossa solução final.
O algoritmo PPO clássico consiste em duas partes: o ator e o crítico. O crítico aproxima a função de valor e o ator ensina uma política aleatória $ \ pi_ \ theta (a | s) $ que maximiza o valor esperado da recompensa total.
Uma das modificações importantes que fizemos é a adição de um módulo à arquitetura do ator que permite ao agente se comunicar com os agentes próximos. O processo de comunicação é construído de forma bastante simples: os agentes geram mensagens simultaneamente e as enviam para todos os trens próximos aos quais estão e, em seguida, tendo recebido mensagens de vizinhos, combinam-nas em uma mensagem por média ponderada. Um mecanismo simples de autoatenção foi usado para determinar os pesos com os quais as mensagens serão calculadas. Com tal estrutura do processo de comunicação, não há necessidade de modificar de alguma forma o processo de aprendizagem, porque é suficiente simplesmente permitir que os gradientes passem pelas mensagens durante a retropropagação do erro.
Decidimos treinar o PPO com um pequeno mapa e um pequeno número de agentes, supondo que como o agente observa apenas o que está ao seu lado, após o treinamento ele irá trabalhar bem em ambientes maiores.
Como você decide quais trens começarão quando?
Depois de tentar simplesmente aplicar o algoritmo PPO, rapidamente chegamos à conclusão de que a maioria dos deadlocks ocorre precisamente porque os trens começam a se mover ao mesmo tempo e interferem uns nos outros. Resolvemos esse problema da seguinte maneira: começamos a executar apenas alguns agentes ao mesmo tempo. Quando um dos agentes terminou seu episódio, o outro agente foi autorizado a começar a se mover. Nessa abordagem, é importante entender em que sequência os trens devem ser lançados.
A primeira abordagem que tentamos foi lançar os agentes mais próximos de seu objetivo. Quando usado em um ambiente pequeno - estradas curtas e poucos agentes - teve um desempenho bom o suficiente, mas para grandes ambientes teve um desempenho muito pior. Portanto, decidimos usar essa abordagem apenas durante o treinamento do agente e, para a aplicação (ou seja, enviando para o sistema de teste), usamos um algoritmo diferente. A ideia desse algoritmo é treinar um classificador que vai determinar para cada agente que não começou a se mover se vai chegar ao fim ou não. Então, se a probabilidade de alcançar com sucesso o destino for grande o suficiente, então o agente começa a se mover, caso contrário, espera até que a probabilidade se torne suficiente.
Resultados da competição
Como resultado, nossa solução ficou em primeiro lugar na faixa RL e em oitavo no geral. Isso significa que a abordagem não RL ainda é melhor neste ponto, mas mostra que a aprendizagem por reforço tem potencial. Nossa abordagem tem alguns pontos fracos e problemas não resolvidos (por exemplo, sérios problemas com escalabilidade para grandes ambientes), então ainda temos algo em que trabalhar. Agora nós, juntamente com os organizadores da competição, estamos preparando um artigo para enviar para o livro NeurIPS 2020 da competição.