Всем привет! Мы — команда из Питерской Вышки, и в этом году мы заняли первое место в RL треке соревнования NeurIPS 2020: Flatland. Цель Flatland — разработать алгоритм, способный как можно лучше управлять трафиком движения поездов по сети железных дорог, при этом система должна принимать решения за ограниченное время.
О том, что это за соревнование и как нам удалось в нем победить (а на контест прислали большее 2000 решений из 51 страны) — читайте под катом.
В команде JBR_HSE было пять участников: Константин Махнев (учится на 4-м курсе бакалаврской программы “Прикладная математика и информатика”) Олег Свидченко и Владимир Егоров (оба учатся в магистратуре “Программирование и анализ данных”), аспирант Дмитрий Иванов и заведующий Центром анализа данных и машинного обучения НИУ ВШЭ — Санкт-Петербург Алексей Шпильман. Все, кроме Константина, также работают в лаборатории Агентных систем и обучения с подкреплением JetBrains Research — отсюда и название команды. Во время участия в соревновании Костя стажировался в этой же лаборатории.
Flatland — это соревнование, которое проходило с 10 июля по 15 ноября на основе платформы AIcrowd и при поддержке известной международной конференции NeurIPS. Цель соревнования — разработать алгоритм, способный как можно лучше управлять железнодорожным трафиком. Важным ограничением было то, что решения нужно принимать за ограниченное время (5 секунд на один шаг симулятора), что не позволяло просто подбирать оптимальные действия.
В NeurIPS 2020: Flatland было два направления: общее и Reinforcement Learning (RL). Первое направление было открыто для любых решений, а второе только для тех, которые используют обучение с подкреплением.
Организаторы предоставили участникам симулятор Flatland, который представляет собой двумерную сетку, где каждая клетка имеет свой тип: дорога, поворот, развилка или непроходимая местность. Каждый поезд занимает ровно одну клетку на сетке и имеет направление, по которому он сейчас перемещается. Симуляция происходит пошагово, на каждом шаге для каждого поезда нужно определить, какое действие ему совершить: остановиться, ехать по самому левому пути или ехать по самому правому пути. Поскольку в текущей реализации полного перекрестка не предусмотрено, т.е. не бывает так, что можно поехать одновременно вперед, направо и налево, то и действие “ехать вперед” тоже не нужно. В случае, когда никаких поворотов нет, второе и третье действие эквивалентны. Поезда могут сталкиваться между собой — получается deadlock. Задача соревнования — заставить все поезда как можно быстрее доехать до их пунктов назначения. Решения оцениваются по сумме времени, которое потратили поезда на достижение цели. В случае, если поезд не доехал, его время равно максимальному времени симуляции.
На Хабре уже было достаточно много постов про обучение с подкреплением, поэтому не будем подробно останавливаться на основных понятиях. Скажем только, что в случае Flatland в качестве среды выступает симуляция железной дороги, а в качестве агентов — поезда. Важно отметить, что поскольку в симуляции участвует множество поездов, то данное окружение является мультиагентным.
При решении задачи мы значительно изменили процесс взаимодействия агента с симулятором, что позволило прилично повысить эффективность нашего алгоритма. Вообще, зачастую подобные модификации очень сильно влияют на результат, однако требуют специфичных для задачи знаний.
Одним из самых значимых изменений было то, что мы решили не давать агенту свободу действий, когда он не находится возле перекрестка. Таким образом, агент может принимать решения только находясь перед развилкой или на развилке, а в остальных случаях всегда движется вперед по единственному возможному пути. Это сильно сокращает длительность эпизода, и, следовательно, делает задачу значительно проще. Также мы решили, что агент будет заканчивать свой эпизод либо когда достиг цели, либо когда попал в дедлок и не может двигаться (в симуляторе в таких случаях эпизод продолжается). Позже мы решили, что и начинаться эпизоды должны не сразу у всех, подробнее об этом расскажем ниже.
Наблюдение для агента состоит из двух частей: признаки, привязанные к конкретной части пути, и признаки, не имеющие привязки к конкретной части пути. Под частью пути здесь понимается участок дороги, соединяющий две развилки.
Первую часть наблюдения можно представить в виде дерева, в вершинах которого находятся развилки, а ребрами являются дороги между ними. Каждому ребру и вершине, в которую оно ведет, мы сопоставляем вектор признаков, посчитанных для данного участка пути (например, длина пути, расстояние от конца ребра до пункта назначения и т.д.). Глубину дерева мы фиксировали, тем самым ограничив количество векторов признаков, получаемых из первой части наблюдения. Ниже приведен пример того, как строится эта часть наблюдения. Цветными линиями обозначены участки дороги, являющиеся ребрами в дереве.
Во вторую часть наблюдения входят такие признаки, как минимальное расстояние до пункта назначения, находится ли агент на перекрестке или перед ним, попал ла агент в дедлок и т.д… Также стоит отметить, что каждому агенту в начале эпизода присваивается идентификатор (случайное число от 0 до 1), которое остается с ним до конца эпизода и позволяет ему лучше договариваться с остальными агентами. Признаки, зависящие от идентификаторов агентов есть в обеих частях наблюдения.
Осталось определить только функцию награды для агента. После некоторого подбора, мы остановились на довольно простой: $0.01 \cdot \Delta d — 5 \cdot \text{is\_deadlocked} + 10 \cdot \text{is\_succeed}$, т.е. награда отражает то, насколько изменилось расстояние $d$ до пункта назначения после принятия решения, с дополнительными наградой в случае успешного завершения эпизода и наказанием в случае попадания в дедлок.
Существует множество алгоритмов обучения с подкреплением, которые разработаны для решения мультиагентных задач. Однако в качестве baseline алгоритма мы решили использовать алгоритм PPO — Proximal Policy Optimization, поскольку его код можно было бы переиспользовать для реализации алгоритмов multiagent RL (например, COMA). Позже, правда, оказалось, что PPO (с некоторыми модификациями) сам по себе решает задачу неплохо, а вот мультиагентные методы обучаются значительно хуже, поэтому PPO остался основной частью нашего финального решения.
Классический алгоритм PPO состоит из двух частей: актора и критика. Критик приближает value-function, а актор учит рандомизированную политику $\pi_\theta(a | s)$, которая максимизирует математическое ожидание суммарной награды.
Одна из важных модификаций, которые мы сделали — добавление в архитектуру актора модуля, который позволяет агенту коммуницировать с ближайшими агентами. Процесс коммуникации построен довольно просто: агенты одновременно генерируют сообщения и рассылают их всем поездам, рядом с которыми находятся, а затем, получив сообщения от соседей, объединяют их в одно сообщение путем взвешенного усреднения. Для определения весов, с которыми будут усредняться сообщения, использовался простой механизм self-attention. При таком построении процесса коммуникации нет необходимости как-то модифицировать процесс обучения, т.к. достаточно просто разрешить градиентам проходить через сообщения во время применения обратного распространения ошибки.
Обучать PPO решили с картой небольшого размера и маленьким количеством агентов, предположив, что поскольку агент наблюдает только то, что находится рядом с ним, после обучения он будет хорошо работать и в окружениях большего размера.
Попробовав просто применить алгоритм PPO, мы довольно быстро пришли к выводу, что большая часть дедлоков происходит именно из-за того, что поезда начинают двигаться одновременно и мешают друг другу. Эту проблему мы решили так: стали одновременно запускать только несколько агентов. Когда один из агентов заканчивал свой эпизод, другому агенту позволялось начать движение. В таком подходе важно понять, в какой последовательности нужно запускать поезда.
Первым подходом, который мы опробовали, стал запуск агентов, которые ближе всего к своей цели. При использовании на окружении небольшого размера — короткие дороги и мало агентов — он показал себя достаточно хорошо, но для больших окружений работал заметно хуже. Поэтому мы решили использовать этот подход только во время обучения агента, а для применения (т.е. сабмита в тестирующую систему) мы использовали другой алгоритм. Идея этого алгоритма заключается в том, чтобы обучить классификатор, который для каждого не начавшего двигаться агента будет определять, доедет ли он до конца или нет. Затем, если вероятность успешно достигнуть пункта назначения достаточно большая, то агент начинает движение, если нет — ждет, пока вероятность не станет достаточной.
В результате наше решение заняло первое место в треке RL и восьмое место в общем зачете. Это значит, что на данный момент не-RL подход пока решает лучше, однако показывает, что у обучения с подкреплением есть потенциал. В нашем подходе довольно много слабых мест и нерешенных вопросов (например, серьезные проблемы с масштабируемостью на окружения большого размера), поэтому нам есть, над чем еще поработать. Сейчас мы вместе с организаторами соревнования готовим статью для отправки ее в competition book NeurIPS 2020.
О том, что это за соревнование и как нам удалось в нем победить (а на контест прислали большее 2000 решений из 51 страны) — читайте под катом.
Наша команда
В команде JBR_HSE было пять участников: Константин Махнев (учится на 4-м курсе бакалаврской программы “Прикладная математика и информатика”) Олег Свидченко и Владимир Егоров (оба учатся в магистратуре “Программирование и анализ данных”), аспирант Дмитрий Иванов и заведующий Центром анализа данных и машинного обучения НИУ ВШЭ — Санкт-Петербург Алексей Шпильман. Все, кроме Константина, также работают в лаборатории Агентных систем и обучения с подкреплением JetBrains Research — отсюда и название команды. Во время участия в соревновании Костя стажировался в этой же лаборатории.
NeurIPS 2020: Flatland — что это?
Flatland — это соревнование, которое проходило с 10 июля по 15 ноября на основе платформы AIcrowd и при поддержке известной международной конференции NeurIPS. Цель соревнования — разработать алгоритм, способный как можно лучше управлять железнодорожным трафиком. Важным ограничением было то, что решения нужно принимать за ограниченное время (5 секунд на один шаг симулятора), что не позволяло просто подбирать оптимальные действия.
В NeurIPS 2020: Flatland было два направления: общее и Reinforcement Learning (RL). Первое направление было открыто для любых решений, а второе только для тех, которые используют обучение с подкреплением.
Организаторы предоставили участникам симулятор Flatland, который представляет собой двумерную сетку, где каждая клетка имеет свой тип: дорога, поворот, развилка или непроходимая местность. Каждый поезд занимает ровно одну клетку на сетке и имеет направление, по которому он сейчас перемещается. Симуляция происходит пошагово, на каждом шаге для каждого поезда нужно определить, какое действие ему совершить: остановиться, ехать по самому левому пути или ехать по самому правому пути. Поскольку в текущей реализации полного перекрестка не предусмотрено, т.е. не бывает так, что можно поехать одновременно вперед, направо и налево, то и действие “ехать вперед” тоже не нужно. В случае, когда никаких поворотов нет, второе и третье действие эквивалентны. Поезда могут сталкиваться между собой — получается deadlock. Задача соревнования — заставить все поезда как можно быстрее доехать до их пунктов назначения. Решения оцениваются по сумме времени, которое потратили поезда на достижение цели. В случае, если поезд не доехал, его время равно максимальному времени симуляции.
Решение: как агент будет взаимодействовать с симулятором
На Хабре уже было достаточно много постов про обучение с подкреплением, поэтому не будем подробно останавливаться на основных понятиях. Скажем только, что в случае Flatland в качестве среды выступает симуляция железной дороги, а в качестве агентов — поезда. Важно отметить, что поскольку в симуляции участвует множество поездов, то данное окружение является мультиагентным.
При решении задачи мы значительно изменили процесс взаимодействия агента с симулятором, что позволило прилично повысить эффективность нашего алгоритма. Вообще, зачастую подобные модификации очень сильно влияют на результат, однако требуют специфичных для задачи знаний.
Одним из самых значимых изменений было то, что мы решили не давать агенту свободу действий, когда он не находится возле перекрестка. Таким образом, агент может принимать решения только находясь перед развилкой или на развилке, а в остальных случаях всегда движется вперед по единственному возможному пути. Это сильно сокращает длительность эпизода, и, следовательно, делает задачу значительно проще. Также мы решили, что агент будет заканчивать свой эпизод либо когда достиг цели, либо когда попал в дедлок и не может двигаться (в симуляторе в таких случаях эпизод продолжается). Позже мы решили, что и начинаться эпизоды должны не сразу у всех, подробнее об этом расскажем ниже.
Наблюдение для агента состоит из двух частей: признаки, привязанные к конкретной части пути, и признаки, не имеющие привязки к конкретной части пути. Под частью пути здесь понимается участок дороги, соединяющий две развилки.
Первую часть наблюдения можно представить в виде дерева, в вершинах которого находятся развилки, а ребрами являются дороги между ними. Каждому ребру и вершине, в которую оно ведет, мы сопоставляем вектор признаков, посчитанных для данного участка пути (например, длина пути, расстояние от конца ребра до пункта назначения и т.д.). Глубину дерева мы фиксировали, тем самым ограничив количество векторов признаков, получаемых из первой части наблюдения. Ниже приведен пример того, как строится эта часть наблюдения. Цветными линиями обозначены участки дороги, являющиеся ребрами в дереве.
Во вторую часть наблюдения входят такие признаки, как минимальное расстояние до пункта назначения, находится ли агент на перекрестке или перед ним, попал ла агент в дедлок и т.д… Также стоит отметить, что каждому агенту в начале эпизода присваивается идентификатор (случайное число от 0 до 1), которое остается с ним до конца эпизода и позволяет ему лучше договариваться с остальными агентами. Признаки, зависящие от идентификаторов агентов есть в обеих частях наблюдения.
Осталось определить только функцию награды для агента. После некоторого подбора, мы остановились на довольно простой: $0.01 \cdot \Delta d — 5 \cdot \text{is\_deadlocked} + 10 \cdot \text{is\_succeed}$, т.е. награда отражает то, насколько изменилось расстояние $d$ до пункта назначения после принятия решения, с дополнительными наградой в случае успешного завершения эпизода и наказанием в случае попадания в дедлок.
Алгоритм PPO
Существует множество алгоритмов обучения с подкреплением, которые разработаны для решения мультиагентных задач. Однако в качестве baseline алгоритма мы решили использовать алгоритм PPO — Proximal Policy Optimization, поскольку его код можно было бы переиспользовать для реализации алгоритмов multiagent RL (например, COMA). Позже, правда, оказалось, что PPO (с некоторыми модификациями) сам по себе решает задачу неплохо, а вот мультиагентные методы обучаются значительно хуже, поэтому PPO остался основной частью нашего финального решения.
Классический алгоритм PPO состоит из двух частей: актора и критика. Критик приближает value-function, а актор учит рандомизированную политику $\pi_\theta(a | s)$, которая максимизирует математическое ожидание суммарной награды.
Одна из важных модификаций, которые мы сделали — добавление в архитектуру актора модуля, который позволяет агенту коммуницировать с ближайшими агентами. Процесс коммуникации построен довольно просто: агенты одновременно генерируют сообщения и рассылают их всем поездам, рядом с которыми находятся, а затем, получив сообщения от соседей, объединяют их в одно сообщение путем взвешенного усреднения. Для определения весов, с которыми будут усредняться сообщения, использовался простой механизм self-attention. При таком построении процесса коммуникации нет необходимости как-то модифицировать процесс обучения, т.к. достаточно просто разрешить градиентам проходить через сообщения во время применения обратного распространения ошибки.
Обучать PPO решили с картой небольшого размера и маленьким количеством агентов, предположив, что поскольку агент наблюдает только то, что находится рядом с ним, после обучения он будет хорошо работать и в окружениях большего размера.
Как решить, каким поездам когда стартовать?
Попробовав просто применить алгоритм PPO, мы довольно быстро пришли к выводу, что большая часть дедлоков происходит именно из-за того, что поезда начинают двигаться одновременно и мешают друг другу. Эту проблему мы решили так: стали одновременно запускать только несколько агентов. Когда один из агентов заканчивал свой эпизод, другому агенту позволялось начать движение. В таком подходе важно понять, в какой последовательности нужно запускать поезда.
Первым подходом, который мы опробовали, стал запуск агентов, которые ближе всего к своей цели. При использовании на окружении небольшого размера — короткие дороги и мало агентов — он показал себя достаточно хорошо, но для больших окружений работал заметно хуже. Поэтому мы решили использовать этот подход только во время обучения агента, а для применения (т.е. сабмита в тестирующую систему) мы использовали другой алгоритм. Идея этого алгоритма заключается в том, чтобы обучить классификатор, который для каждого не начавшего двигаться агента будет определять, доедет ли он до конца или нет. Затем, если вероятность успешно достигнуть пункта назначения достаточно большая, то агент начинает движение, если нет — ждет, пока вероятность не станет достаточной.
Результаты соревнования
В результате наше решение заняло первое место в треке RL и восьмое место в общем зачете. Это значит, что на данный момент не-RL подход пока решает лучше, однако показывает, что у обучения с подкреплением есть потенциал. В нашем подходе довольно много слабых мест и нерешенных вопросов (например, серьезные проблемы с масштабируемостью на окружения большого размера), поэтому нам есть, над чем еще поработать. Сейчас мы вместе с организаторами соревнования готовим статью для отправки ее в competition book NeurIPS 2020.
