[Введение

В современных городах пробки повсюду, и эти пробки, в отличие от апельсиновых пробок, которые вы едите на завтрак, часто чертовски раздражают людей, если они случайно попадают в одну из них. Существует огромный интерес к попытке понять, почему возникают пробки и как их уменьшить, потому что они представляют собой большую проблему как в социальном, так и в экономическом плане. Рабочие, застрявшие в бесконечных пробках, тратят драгоценное время впустую, что снижает продуктивность рабочей силы, в то время как граждане, застрявшие в своих машинах в пути по городу, создают разочарованных и несчастных жителей. Существует множество факторов, способствующих возникновению пробок, но общее мнение состоит в том, что главными виновниками являются мелкие, незаметные ошибки, совершаемые водителями, которые со временем будут распространяться и усиливаться. Представьте себе ровный транспортный поток на шоссе, когда вдруг один из водителей немного сбавил скорость, чтобы включить радио. Внезапное снижение скорости заставляет следующего водителя быть осторожным, как и должно быть, и также замедлять свою машину. Эти шаблоны распространяются по трафику и усиливаются из-за неравномерного замедления и ускорения поведения разных водителей, что в конечном итоге создает пробку. Эта линия гипотез была продолжена Нагелем и Шрекенбергом (1992), где они смоделировали транспортный поток, используя простые правила клеточного автомата со случайным уменьшением скорости водителей, создав модель, очень похожую на пробку в реальном мире.

Теперь мы определили хотя бы одну возможную причину пробок, как мы пытаемся решить эту проблему? В многоагентной среде, где каждый агент ведет себя индивидуально, а вся система отвечает таким же образом, мы получили сложную систему. Очень сложно эффективно и результативно взаимодействовать и модифицировать сложные системы, поскольку они могут отреагировать и изменить свою динамику, что делает наши вмешательства бесполезными. К счастью, есть способ решить эту проблему: обучение с подкреплением. Обучение с подкреплением — это парадигма машинного обучения, в которой агентов можно научить адаптироваться к конкретным условиям, учась на своих ошибках. Цель любого обучения с подкреплением проста: взаимодействовать с окружающей средой, наблюдать за ее состоянием и предпринимать определенные действия, а затем максимизировать потенциальное вознаграждение. Любая проблема, которую можно сформулировать в терминах вознаграждения за действие, можно решить с помощью обучения с подкреплением. Недавние разработки в области алгоритмов обучения с подкреплением привели к многочисленным интересным прорывам в ранее почти неразрешимых задачах: AlphaGo, обыгрывающая опытных игроков в шахматы с использованием сети политик для управления поиском по дереву Монте-Карло; задачи многомерного управления роботами плавно подходят с помощью моделирования и нейронных сетей, или эмерджентного поведения при выработке стратегии игровых агентов, использующих самостоятельную игру.

[II] Метод

Есть три основных компонента любой проблемы обучения с подкреплением:

  1. Состояние:чтобы наш агент обучения с подкреплением мог взаимодействовать с окружающей средой, ему сначала нужно увидетьсреду. Нам нужно предоставить агенту состояние: своего рода представление среды в текущий момент времени, чтобы агент мог решить, что делать. Обратите внимание, что эта информация, которую мы предоставляем, не обязательно должна быть идеальной. Фактически, тот факт, что мы можем предоставлять несовершенную, зашумленную информацию, а агент может научиться адаптироваться к ней, является наиболее мощным аспектом алгоритмов обучения с подкреплением. В реальном мире датчики работают шумно, а восприятие несовершенно, и разумному человеку необходимо переварить всю эту информацию, чтобы выделить для себя наиболее важные аспекты. Например, вы, вероятно, не чувствуете своего тела, сидящего на стуле прямо сейчас (хотя после того, как я обратил ваше внимание на этот вопрос, используя предыдущее предложение, вы, вероятно, заметили, что сидите на стуле с яркими ощущениями), потому что ваш мозг предпочитает сосредоточиться на этих предложениях, которые вы читаете, а не на ощущениях в вашем теле. В этом суть обучения с подкреплением: среда подает неверные сигналы, алгоритм выдает правильные действия.
  2. Действие:агенту нужен способ взаимодействия и изменения среды. Каждая проблема обучения с подкреплением требует спецификации пространства действий: допустимых действий, которые агент может предпринять в текущий момент времени. Например, агент, пытающийся контролировать трафик, должен каким-то образом воздействовать на трафик, например, изменять скорость автомобилей или временно блокировать дороги (например, с помощью светофоров). . Обучение с подкреплением — это серия взаимодействий между агентом и средой, как показано на рисунке выше, поэтому агенту должен быть доступен список допустимых взаимодействий.
  3. Награда: так же, как собаке нужны лакомства, чтобы понять, что она хороший мальчик (хотя я утверждаю, что все собаки с хорошими владельцами — хорошие мальчики/хорошие девочки), наш агент также должен знать, является ли она хорошим мальчиком. изменять свое окружение так, как ему хочется или нет. Вознаграждение — это числовое значение, которое мы присваиваем, чтобы сообщить агенту, «выигрывает» он или нет. Чтобы подкрепить хорошее поведение нашего агента (и, таким образом, воспрепятствовать плохому поведению), мы время от времени даем агенту понять, что у него все хорошо, вознаграждая его, или плохо, отняв вознаграждение. Однако есть определенные проблемы с созданием хорошо работающей системы вознаграждения: иногда вознаграждение из окружающей среды может проявляться медленно. Взятие ферзя в шахматной партии не означает, что вы выиграете игру, но это хороший показатель того, что вы, вероятно, выиграете в будущем. Таким образом, дисконтирование иногда необходимо. Другая проблема, которая может возникнуть, связана с приписыванием вознаграждения правильному действию: если я выиграю партию в шахматы, я не обязательно знаю, произошло ли это потому, что я сделал хороший ход и взял ферзя противника, или потому, что я использовал башню. заманить короля противника в ловушку.

Теперь, когда мы поняли основы обучения с подкреплением, давайте взглянем на нашу проблему пробок. Во-первых, нам нужна среда, в которой агент регулятора трафика может взаимодействовать. Конечно, мы можем собирать реальные данные, отправив реального агента в дорогу, но это очень дорого. Скорее, мы будем использовать симулированную среду: такую, которую можно настраивать и запускать миллионы раз без особых усилий.

Это простая смоделированная среда для однополосного движения, использующая ту же формулу, которую использовали Nagel & Schronecker. Игра с параметрами плотности показывает нам, что существует критическая плотность трафика, при которой начинают происходить загромождения (около 20% для этого конкретного набора правил). Далее, давайте определим три компонента в нашей проблеме:

  1. Состояние: для начала давайте упростим задачу для агента. Мы позволим агенту видеть всю дорогу (может быть, с камерами наблюдения или чем-то подобным): у него будет доступ к скорости автомобилей, которые в данный момент находятся на дороге. Таким образом, агент «увидит» массив размера N (где N — снимок дороги, на который мы смотрим), где N[i] — числовое значение, показывающее скорость автомобиля в точке i. Если в точке i нет машины, N[i] = -1.
  2. Действие: опять же, для облегчения работы агента, скажем, он может одновременно изменять скорости всех машин на полосе. Это крайне нереально, но это начало. Мы можем расширить это пространство действий позже, например, позволив агенту управлять только одной машиной или позволить агенту косвенно взаимодействовать с машинами, используя сигналы светофора. На данный момент агент создаст агента, используя массив C, где C[j] — величина изменения скорости автомобилей в позиции j.
  3. Награда: поскольку мы избегаем образования пробок, мы вознаграждаем агента количеством автомобилей с ненулевой скоростью (автомобили, которые не стоят на месте, что является большим разочарованием для водители). Таким образом, за каждое действие агент будет получать числовое вознаграждение от 0 до 1, которое представляет собой процент автомобилей, движущихся в данный момент по полосе.

Теперь, когда мы определили среду и агента, давайте углубимся в алгоритм. Алгоритм, который мы используем, — это Q-обучение, особая разновидность обучения с подкреплением. Почему это называется Q-обучение? Хороший вопрос из-за Q-функции: функции, которая вычисляет вознаграждение от этого временного шага до конца эпизода симуляции. Формально он определяется как:

Короче говоря, это ожидаемое значение вознаграждения с настоящего момента и до конца эпизода (с лямбдой в качестве коэффициента дисконтирования). Требуется ввод состояния и действия для получения награды, которую мы ожидаем получить, если выполним действие aв состоянии s. Конечно, это гипотетическая функция: обычно невозможно точно получить значение вознаграждения в будущем. К счастью, здесь наступает счастье современного глубокого обучения: хотя мы не можем точно вычислить Q, мы можем оценить его значение. Что является конечной оценкой в ​​​​глубоком обучении? Нейронная сеть! Идея проста: показывая нейросети текущее состояние среды, мы научим нейросеть оценивать для нас значение Q-функции. Но нейросети нужны метки, а истинных значений Q-функции мы не знаем. Вот тут-то и появляется следующий трюк, называемый Q-обучением. Оказывается, мы можем надежно оценить значение Q-функции, двигаясь вперед во времени: поскольку Q-функция дает ожидаемое вознаграждение за весь эпизод, мы можем просто смоделировать действие , получить вознаграждение, а затем вычислить предполагаемое значение Q для следующего временного шага. А именно, мы будем использовать:

в качестве метки для обучения нашей сети. Это имеет смысл, так как нам просто нужно сделать шаг вперед во времени (что мы можем сделать, потому что мы находимся в смоделированной среде), чтобы получить значение Q, которое будет хорошим прокси для текущего значения Q, поскольку, если Q-функция является хорошей оценщик ожидаемого вознаграждения, его значение будет аддитивным от временных шагов к временным шагам. Этот подход называется Deep-Q-Network или DQN.

Использованная литература:

https://hal.archives-ouvertes.fr/jpa-00246697/document
https://medium.com/@jonathan_hui/rl-dqn-deep-q-network-e207751f7ae4
Reinforcement learning: An Introduction (http://incompleteideas.net/book/the-book.html)