Создание оптимального алгоритма переключения светофора на перекрестке

Введение в область

Каждый из нас хоть раз в жизни сталкивался с плохой работой светофора на перекрестке: неравномерное движение трафика по нему, слишком долгие интервалы переключения и т. д. Всё это из‑за наивного способа переключения «зеленого» и «красного»: светофоры просто работают по расписанию, а где‑то за ними даже присматривают люди, чтоб вовремя переключить. Выглядит как проблема, которую надо решать. Поэтому наша команда поставила перед собой цель разработать «мозг» для светофора, где будут приниматься эффективные решения о переключении его сигналов.

Примитивные алгоритмы и идея с ML

По существу, для работы светофора нужна «коробочка», которая принимает какие‑то данные о состоянии перекрестка и сообщает оптимальный сигнал. Соберем в кучу идеи, которые могут быть внутри «коробочки»:

• Стандартный светофор, который циклически переключает сигнал. Рассчитан на конкретное соотношение загруженности дорог, неэффективен при изменении загруженности

• Алгоритм, включающий зеленый свет более загруженной дороге. На первый взгляд хороший алгоритм, однако при равной загруженности дорог светофор будет постоянно переключать сигнал, что приведет к большому количеству задержек (при переключении светофора нужна задержка, чтобы машины успели уехать с перекрестка)

• Алгоритм, включающий зеленый сигнал автомобилям, которые дольше всех стоят на перекрестке. Неэффективен при разной загруженности дорог.

Видно, что хороший алгоритм должен уметь классифицировать ситуацию на перекрестке в зависимости от загруженности дорог, длины задержки и времени ожидания. Поскольку различных соотношений загруженности может быть очень много даже в самом простом перекрестке (загруженность 1:0, 1:1, 1:2, 1:10), создавать примитивный алгоритм с кучей условий нецелесообразно, поэтому, как часто делается в подобных случаях, мы решили обучить нейронную сеть определять оптимальный сигнал.

Отступление про собственный эмулятор

«Стартер пак» для обучения нейросети почти готов — осталось лишь обзавестись хорошей средой (он же эмулятор). Причем хочется, чтобы среда была как можно эффективнее, ведь учатся нейронки не быстро. К сожалению, эмулятора только с одним светофором и удобным API просто не нашлось в дикой природе. Наиболее подходящий под наши нужды вариант — Carla. Это тяжеловесный реалистичный симулятор дорожного движения, разработанный огромной командой. Однако его использование на раннем этапе было нерациональным из‑за излишнего масштаба и сложностей (но позже мы к нему вернемся). Поэтому было принято решение сделать собственный простой эмулятор на Python с отрисовкой на PyGame. Теперь модели (нейросети) можно «скармливать» саму картинку перекрестка, количества машин на дорогах и т. д. Этим и займемся

Для обучения модели будем использовать обучение с подкреплением (оно же Reinforcement Learning). Если совсем просто, то процесс обучения состоит из непрерывной череды двух фаз: действия модели и реакции среды. В первой модель получает сведения о среде (состояние перекрестка в каком‑то виде) и совершает действие (переключает сигнал светофора), во второй среда обрабатывает совершенное действие (машинки катятся) и передает модели новые сведения о себе, включая вознаграждение (reward) за предыдущее действие. Наверное, вы догадались, что самая творческая и трудная задача здесь — изобрести принцип этого вознаграждения. Теперь, наконец, попробуем вразумить сам светофор.

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

Обучение модели через количество машин

Как светофору понимать, нужно ли переключать свет? Первая идея — передавать ему количества машин на дорогах перекрестка и делать из этого выводы. Понятно, что это не привязать к реальности (откуда, например, брать точные координаты машин?), но в качестве первой пробы решили реализовать такую идею. После этого перед нами возникла новая задача — придумать reward‑функцию. Мы провели множество экспериментов, выясняя, как лучше «поощрять» нашу модель, чтобы понять, какие факторы действительно «роляют». В итоге получилась довольно сложная формула, зависящая от загруженности дорог, от изменений этой загруженности и того, сколько уже не переключался сигнал на светофоре (на удивление это действительно важный параметр, до которого мы не сразу догадались), с некоторыми коэффициентами. Такая формула показала себя лучше всего в ходе экспериментов.

Для реализации алгоритма DQN мы решили воспользоваться библиотекой torch, получилась вот такая нейронная сеть:

class QNetwork(nn.Module):
    def __init__(self, env):
        super().__init__()
        self.network = nn.Sequential(
            nn.Linear(np.array(env.single_observation_space.shape).prod(), 120),
            nn.ReLU(),
            nn.Linear(120, 84),
            nn.ReLU(),
            nn.Linear(84, env.single_action_space.n),
        )

    def forward(self, x):
        return self.network(x)

Модель принимает на вход 5 чисел — 4 из них обозначают количество ожидающих машин на разных дорогах, и пятое число обозначает текущий сигнал светофора. Нейронная сеть возвращает 1 число (env.single_action_space.n = 1 из конфигурации среды) — оптимальный сигнал светофора в данной ситуации.

Результаты данной модели были заметно лучше примитивных алгоритмов в большинстве дорожных ситуаций, поэтому мы решили приблизить наши наработки к реальной жизни — подключить обработку картинок, чтобы можно было отслеживать дорожную ситуацию через камеры видеонаблюдения.

Обучение модели через картинку

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

Количество пикселей на изображении слишком велико, чтобы использовать каждый пиксель как входной параметр для нейронной сети, поэтому, перед передачей данных на вход нейросети, надо их обработать. Сделаем это при помощи библиотек Numpy и PIL:

pil_string_image = pygame.image.tostring(self.painter.canvas, "RGB", False)
pil_image = Image.frombytes("RGB", (1_200, 1_200), pil_string_image)

width = 64
height = 64

resized_image = pil_image.resize((width, height))
cam1 = np.array(resized_image.crop((0, 0, 44, 44)))  # high left angle
cam2 = np.array(resized_image.crop((20, 20, 64, 64)))  # down right angle
cam1 = np.transpose(cam1, (2, 0, 1)) 
cam2 = np.transpose(cam2, (2, 0, 1))

observation = np.array([cam1, cam2]) # result

Вход для нейросети готов. Поговорим об её устройстве. Ясно, что нейросети нужно понять, что делать со светофором, используя лишь изображения местности, которые для неё лишь трехмерные массивы чисел‑пикселей. Чтоб облегчить ей задачу, добавим в этот «путь понимания» ещё один узел, где она поймет для себя (не важно, в каком виде), какая ситуация на перекрестке сложилась на языке цифр. На этой половине пути модель «зашифрует» (encode) для себя состояние перекрестка. А на следующей, «расшифрует» (decode) в вид, плюс‑минус понятный для принятия решения для переключения светофора. Итого, нейросеть — по сути склейка этих двух путей: Encoder и Decoder. А так как изображений 2, то и Encoder»ов тоже 2. Они оба «зашифруют» свои изображения в массивы по 32 числа, которые мы передадим Decoder»у, добавив текущий сигнал светофора. Наконец, Decoder выдаст 2 числа — на какой дороге врубить зеленый.

А вот и реализация вышесказанного

class Encoder(nn.Module):
    def __init__(self):
        super().__init__()
        self.seq = nn.Sequential(
            nn.Conv2d(3, 16, 3),
            nn.ReLU(),
            nn.MaxPool2d(3, 3),
            nn.Conv2d(16, 64, 3),
            nn.ReLU(),
            nn.MaxPool2d(3, 3),
            nn.Conv2d(64, 8, 3)
        )

    def forward(self, x):
        x = self.seq(x)
        return x.view(x.shape[0], -1)


class Decoder(nn.Module):
    def __init__(self, n):
        super().__init__()
        self.seq = nn.Sequential(
            nn.Linear(n, 2 * n),  # nn.Linear(n + 1, 2 * n),
            nn.ReLU(),
            nn.Linear(2 * n, 8 * n),
            nn.ReLU(),
            nn.Linear(8 * n, 2)
        )

    def forward(self, x):
        # input shape: torch.Size([2, 2, 2])
        # output shape: torch.Size([2, 2, 1])
        x = self.seq(x)
        return x


class Net(nn.Module):
    def __init__(self):
        super().__init__()
        self.enc1 = Encoder()
        self.enc2 = Encoder()
        self.dec = Decoder(n=32+1)  # +1 - signal

    def forward(self, img1, img2, current_signal):
        if len(img1.shape) == 3:
            img1 = torch.unsqueeze(img1, 0)
            img2 = torch.unsqueeze(img2, 0)
            current_signal = torch.tensor([[current_signal]])
        else:
            current_signal = torch.unsqueeze(current_signal, 1)

        x = self.enc1(img1) + self.enc2(img2)
        x = torch.concat((x, current_signal), dim=1)
        x = self.dec(x)
        return x  # logits

Такая нейросеть обучается значительно дольше, чем предыдущая, однако показывает лучшие результаты тестов, про них мы написали в конце статьи

Генератор трафика

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

Реализация скорректированного алгоритма для обучения с Carla

Сменим среду с кастомной на Carla. Принцип обучения оставим такой же, однако стоит увеличить размер изображений перекрестка, потому как машины заметны сильно хуже на городском фоне, чем фиолетовые кружки на черном полотне. Обратная сторона такого решения — сильное увеличение процесса обучения такой нейросети по времени. Если предыдущая модель смогла успешно обучиться в нашей «песочнице» за пол часа, то нынешней не хватило и суток.

Итоги

Самое время для обещанных экспериментов и сравнений методов обучения!

Из результатов тестов видно, что полученный нами алгоритм машинного обучения работает эффективнее примитивных алгоритмов в различных ситуациях на перекрестке, что не может не радовать!