Во-первых, это соревнование на AIcrowd под названием Flatland, которое, я думаю, к моменту написания этой статьи закончилось. Моя цель создания алгоритма RL для решения этой проблемы заключалась не в том, чтобы выиграть соревнование, на самом деле я даже не представил никаких решений (ну, я все еще пытаюсь заставить его работать). Скорее, у меня давно была идея создать программу для составления расписания поездов с использованием RL. Так что представьте мое счастье, когда я случайно наткнулся на это потрясающее соревнование. Моя цель создания такого программного обеспечения - показать людям, что RL - прекрасный инструмент для решения многих проблем в реальном мире. А также провести исследование и попробовать разные вещи, проявить творческий подход и решить множество проблем, о которых я расскажу вам в этом посте. Этот пост о моем пути решения проблем для этой конкретной задачи (который еще даже не закончился).

Награда и наблюдение

Таким образом, проблема заключается в том, что на карте размером h x w указано n поездов (количество поездов и размер карты может быть разным), каждый из которых должен добраться до пункта назначения за минимально возможное время. Принимая во внимание лимит ресурсов, а также тот факт, что один блокпост может использоваться только одним поездом, действительно создает серьезную проблему. И если этого недостаточно, создатели конкурса дают вам второй раунд, когда поезда не имеют одинаковой скорости, и иногда внезапно (с некоторой вероятностью) некоторые из поездов могут сломаться и застрять посреди железной дороги на некоторое время. в то время как. Для получения дополнительной информации вы можете перейти по ссылке на конкурс, которую я предоставил выше.

Многое из того, что я пробовал

Награда составляет -1 за каждый незавершенный шаг, а также я добавил -2 за каждое незаконное движение (например, незаконный поворот налево, когда железная дорога не дает такой возможности). Наблюдение немного сложно. Прежде всего, каждый поезд получает индивидуальное наблюдение, и окружающая среда может предоставить вам три типа наблюдений - TreeObservation, GlobalObservation, LocalObservation. Я использовал TreeObservation и GlobalObservation, и я кратко расскажу вам об обоих. TreeObservation ... ох, мальчик ... он дает вам 12 различных функций (например, расстояние от ячейки до следующего ветвления или расстояние от ячейки до места назначения и т. Д.) После каждого возможного действия, а также после каждого возможного действия после каждого возможного действия, и это с глубина трех. GlobalObservation, с другой стороны, предоставляет каждому агенту полную карту переходов в виде матрицы h x w x16, а также другие функции, такие как направление и положение этого агента. . И LocalObservation - это то же самое, что GlobalObservation, но вместо полной карты он имеет ограниченный вид для каждого агента по радиусу r, и центр является этим агентом.

Небольшой отказ от ответственности, я не буду объяснять, что такое обучение с подкреплением и многие другие вещи.

Полученные результаты

Я не могу хвастаться своими результатами ЕЩЕ !! Итак, дело в том, что мой код не очень оптимизирован для моего вычислительного бюджета, и я сталкиваюсь с ошибкой памяти до получения каких-либо ценных результатов. Что я могу сказать, так это то, что во время обучения наблюдается очень заметное движение к обучению, поскольку я вижу агентов, которые останавливаются, чтобы пропустить другого агента, и многие подобные мелочи. Я еще далеко не закончил, и я потрачу на это как можно больше свободного времени, потому что у меня есть много идей, как заставить это работать.

Идеи на будущее

Поэтому я хочу сначала оптимизировать код, чтобы хотя бы не столкнуться с ошибкой памяти. Также у меня есть некоторые ошибки, и я бы тоже хотел от них избавиться (я хочу попробовать продолжить обучение для нескольких итераций на одной и той же карте, прежде чем менять ее, но ошибка не позволяет мне). Основное изменение будет заключаться во включении планирования в мой алгоритм, чтобы сократить время обучения, а также кажется интуитивно понятным иметь планирование в таком проекте, так что это необходимо в будущем. Возможно, позже я смогу попробовать иерархическое обучение с подкреплением, так как у меня тоже есть пара идей на этот счет.

В самом начале я даже не начинал читать похожие статьи по решению проблем, потому что у меня была гораздо большая проблема, переменное количество агентов !! Моя позиция заключалась в том, чтобы создавать каждый алгоритм с нуля, поэтому я не использовал RLlib, хотя он предлагает отличные инструменты для настроек обучения с подкреплением как для нескольких, так и для одного агента. Один из возможных способов - создать отдельную сеть для каждого агента, и все будет хорошо, но между агентами не будет никакой связи, а когда им нужно придумать способ совместного использования ресурса, это будет невозможно. Затем я подумал использовать метод, в котором критик централизован и получает все наблюдения агентов и дает каждому значение состояния, а акторы корректируют свои политики в этом направлении, здесь все агенты имеют отдельные сети, поэтому проблема переменного количества агентов выходит за рамки способ. Однако существует проблема децентрализованного исполнения, когда агенты не имеют представления о решениях друг друга во время исполнения. Так что я застрял в размышлениях о способах создания канала связи между агентами, и мне в голову пришла отличная идея, которая, как позже выяснилось, не моя, и некоторые люди уже написали об этом потрясающую статью и назвали ее Multi-agent Bidirectionally. -Скоординированные сети (BiCNet). Идея заключается в следующем: каждый агент в среде представлен как двунаправленная последовательность RNN и передает свое скрытое состояние другим агентам, а поскольку это двунаправленная RNN, каждый агент знает о каждом другом агенте через скрытые состояния. . И самое лучшее в этом то, что вам не нужно проектировать канал связи, они изучат лучший способ общения «язык» в процессе обучения.
Теперь, когда у нас есть архитектура алгоритма, пора выбрать сам алгоритм. В море алгоритмов типа «DQN», «DDQN», «A3C» и т. Д. Я выбрал очень удивительный PPO из семейства алгоритмов типа Actor-Critic. Убыток я рассчитывал для каждого агента индивидуально и суммировал в конце обучения. Среднее значение, а не сумма, тоже работает, поэтому я думаю, что позже мне нужно немного поработать с ним, потому что сумма будет расти по мере увеличения количества агентов, и я не хочу связываться с моей сетью. сюда. Выбор PPO был основан на том факте, что он принадлежит к семейству алгоритмов Actor-Critic, которые работают лучше всего, и к тому же он намного стабильнее, чем A3C, так что вот и мы. Если вы хотите узнать больше о PPO, я бы порекомендовал посмотреть «это потрясающее видео».
Я настроил процесс обучения таким образом, чтобы сложность возрастала с течением времени / итераций, поэтому обучение будет начинаться с 1 агента. на маленькой карте, и карта станет больше, а количество агента увеличится после нескольких приращений размера карты. В будущем я хочу попробовать способ увеличения сложности в зависимости от того, насколько хорошо работает алгоритм, а не просто времени.
Теперь пора поговорить о сетевой архитектуре. Сначала я попытался использовать TreeObservation, и я работал с другой архитектурой, но позже я переключился на GlobalObservation и расскажу о сети, которую я там использовал. Таким образом, наблюдение имеет размер h x w x22x number_of_agents, поэтому я использовал слои CNN поверх слоев RNN. Как я уже сказал, размер карты варьируется, поэтому я использовал Spatial Pyramid Pooling, чтобы позже передать его моему компоненту RNN. Я проделал несколько уловок, чтобы передать CNN все наблюдения агентов в виде пакетов, а затем извлечь настоящие пакеты из наблюдений каждого агента для RNN. Я использовал Pytorch, потому что он потрясающий - с ним легко работать, легко создавать и тестировать новые идеи, а также код выглядит просто потрясающе. Весь код, о котором я говорю, можно найти «здесь».

Мой путь еще не закончен, и я почти уверен, что смогу решить эту проблему, используя современные методы RL. И почему я так сконцентрирован на RL, потому что один алгоритм может быть применен ко многим другим аналогичным задачам, после решения расписания поездов следующим могут быть самолеты, грузовики, корабли, вы называете это. А также, используя алгоритмы обучения, мы гарантируем, что со временем он станет лучше с небольшими изменениями или без них. Кроме того, процесс обучения может дать нам представление о том, как решить проблему, о чем раньше и не думали.
Это все, что нужно для части 1, увидимся в части 2.

Мое путешествие по использованию глубокого обучения с подкреплением для оптимизации расписания поездов: pt. 1