Сверточная нейронная сеть (CNN) — популярная модель для решения таких задач, как классификация изображений, сегментация, обнаружение объектов и т. д. Это эксперимент по оценке ее применения для решения простых задач планирования 2D-пути. Используемый язык программирования — Python, с PyTorch, NumPy и OpenCV в качестве основных библиотек. Вы можете найти исходный код на моем GitHub.

Задание

Проще говоря, с учетом карты сетки занятости двухмерное планирование пути заключается в поиске кратчайшего возможного пути от заданной начальной точки до желаемой целевой позиции (цели), избегая любых препятствий во время траектории. Робототехника является одной из основных областей, в которых планирование пути имеет решающее значение. Алгоритмы типа A*, D*, D* lite и родственные варианты были разработаны для решения такого рода задач. В настоящее время искусственный интеллект (ИИ), особенно с обучением с подкреплением, широко используется для объяснения этого. Действительно, CNN обычно являются основой некоторых алгоритмов обучения с подкреплением. В этом эксперименте мы пытаемся решить простые задачи планирования пути с помощью исключительно сверточной нейронной сети.

Набор данных

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

  • Начнем с квадратной пустой матрицы M размером 100x100 пикселей.
  • Для каждого элемента (пикселя) в матрице нарисуйте случайное число r от 0 до 1 из равномерного распределения. Если r › diff, установите для этого пикселя значение 1; в противном случае установите его равным 0. Здесь diff – это параметр,представляющий вероятность того, что пиксель является препятствием (т. , это пропорционально сложности поиска допустимого пути по этой карте.
  • Затем давайте воспользуемся морфологическим оператором открытия, чтобы получить блочный эффект, который больше напоминает настоящие карты сетки занятости. Варьируя размер элемента морфологической структуры и параметра diff, мы можем генерировать карты разного уровня сложности.

  • Далее для каждой карты мы должны выбрать 2 разные позиции: начало (s) и цель (g). Этот выбор снова случайный, но на этот раз мы должны убедиться, что евклидово расстояние между s и g больше заданного порога, чтобы сделать экземпляр сложным. В противном случае наша сеть мало что из этого извлечет.
  • Наконец, нам нужно найти кратчайший путь от s до g. Это будет основной истиной для нашего обучения. С этой целью я использовал популярный алгоритм D* lite. В частности, я написал пользовательскую реализацию, которая ограничивает решение, сохраняя запас по крайней мере в 1 свободную ячейку от любого препятствия. Причина этого просто в том, что я работал над роботизированным проектом, где нам требовалась такая модификация, поскольку наш робот часто натыкался на стены, следуя оригинальной траектории D* lite. Используя ограничение маржи, мы смогли решить эту проблему. И учитывая, что (изначально) предполагалось, что эта CNN будет использоваться на том же самом роботе, я решил сохранить нашу собственную реализацию.

Набор данных содержит около 230 тыс. образцов (170 тыс. для обучения, 50 тыс. для тестирования и 15 тыс. для проверки). Генерация такого количества данных с использованием описанного выше процесса оказалась невыполнимой для моего стандартного ноутбука. Вот почему я переписал кастомизированную реализацию D* lite в виде модуля расширения python, используя библиотеку Boost c++. У меня нет бенчмарков, но с модулем расширения я смог генерировать более 10 000 сэмплов в час, в то время как с реализацией на чистом Python скорость составляла около 1 000 семплов в час (на моем старом, но золотом Intel Core i7–6500U с 8 ГБ ОЗУ). Пользовательская реализация D* lite доступна здесь.

Обратите внимание, что иногда может показаться, что целевая позиция расположена на препятствии. В этих случаях наземная траектория истинности заканчивается последней возможной (т. е. ячейкой, которая не является препятствием, 0 на матричной карте) позицией, ближайшей к цели. Это еще одно небольшое отличие от оригинального D* lite.

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

Я загрузил набор данных на kaggle, где вы также можете найти простую записную книжку, показывающую, как получить доступ к образцам. В репозитории GitHub вы также можете найти удобный скрипт, позволяющий создать собственный набор данных с нуля.

Архитектура модели

Модель следует архитектуре кодер-декодер, в общей сложности 20 сверточных слоев, разделенных на 3 блока свертки (часть кодирования), за которыми следуют другие 3 блока транспонированной свертки (часть декодирования). Каждый блок состоит из 3-х сверточных слоев 3x3, с пакетной нормализацией и активацией ReLU между каждым из них. Наконец, есть еще 2 конверсионных слоя плюс выходной слой. С точки зрения высокого уровня цель кодировщика состоит в том, чтобы найти сжатое, но релевантное представление ввода. Затем это будет передано части декодера, которая попытается восстановить ту же входную карту, но на этот раз внедрив полезную информацию, которая должна помочь найти оптимальный путь от s до g.

Ожидаемые входы этой сети:

  • map: тензор [n, 3, 100, 100], представляющий карты сетки занятости. Далее n — это размер пакета. Обратите внимание, что количество каналов равно 3, а не просто 1. Подробнее об этом позже.
  • start: тензор [n, 2], содержащий координаты начальной точки s на каждой карте.
  • цель: тензор [n, 2], содержащий координаты целевой точки g на каждой карте.

Выходной слой сети применяет функцию сигмоид, эффективно предоставляя карту оценок, в которой каждый элемент имеет значение от 0 до 1, пропорциональное вероятности принадлежности к кратчайшему пути из с в г. Затем вы можете реконструировать путь, начиная с s и итеративно выбирая точку с наибольшим количеством очков в текущей 8-окрестности. Процесс завершится, как только вы найдете точку с такими же координатами, как g. Ради эффективности я использовал для этой цели алгоритм двунаправленного поиска. На эту идею меня натолкнула эта бумага.

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

Обучение

Я тренировал модель около 15 часов или 23 эпохи в Google Colab. Используемая функция потерь представляла собой среднеквадратичную ошибку (MSE) между картой оценок, предоставленной моделью, и картой истинности (GT). Последнее было получено путем создания матрицы 100x100, заполненной нулями, а затем добавления 1 в каждом месте, соответствующем точке, принадлежащей пути, полученному с помощью D * lite. Вероятно, есть варианты получше, чем MSE, но я остановился на нем из-за его простоты и удобства использования.

Скорость обучения изначально была установлена ​​на 0,001 с помощью планировщика CosineAnnealingWithWarmRestart (слегка измененного, чтобы уменьшить максимальную скорость обучения после каждого перезапуска). Размер партии был установлен на 160 образцов.

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

Проблема с извилинами

Сначала я скормил модель, используя карту сетки занятости, как они есть. То есть на входе был тензор формы [n, 1, 100, 100] (плюс начальная и целевая позиции). С этой настройкой я не смог добиться каких-либо удовлетворительных результатов. Убыток перестал уменьшаться практически мгновенно. Следовательно, реконструированные пути были просто случайными траекториями, которые полностью не попали в целевую позицию и прошли через препятствия.

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

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

Позиционное кодирование в помощь

Позиционное кодирование — это метод введения информации о положении данных путем ее встраивания (обычно в виде простой суммы) в сами данные. Обычно это применяется в обработке естественного языка (NLP), чтобы модель осознавала положение слов в предложении. Я подумал, что что-то подобное может быть полезно и для нашей задачи.

Классическое позиционное кодирование (см. статью Внимание — это все, что вам нужно) использует серию синусоид для кодирования каждой позиции.

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

Идея, которая у меня возникла, основана на наблюдении, что при планировании пути нас на самом деле интересуют позиции не в абсолютных единицах, а только в относительных область действия. В частности, нас интересует положение каждой ячейки на карте заполнения относительно начальной точки s и конечной точки g. Например, возьмем ячейку с координатами (x, y). Мне все равно, равно ли (x, y) (45, 89), а не (0, 5). Должно быть гораздо полезнее знать, что (x, y) находится в 34 ячейках от s и в 15 ячейках от g.

Что я сделал, так это создал 2 дополнительных канала для каждой карты сетки занятости, которая теперь имеет форму [3, 100, 100] (без учета размера пакета). Первый канал — это ванильная карта, как это было раньше. Второй канал представляет собой позиционное кодирование, которое присваивает каждому пикселю значение относительно начальной позиции. Та же история с третьим, но на этот раз с использованием позиции. Такие кодировки выполняются путем создания двух карт объектов из двумерной функции Гаусса с центром в s и g соответственно. Sigma была выбрана равной пятой части размера ядра (как обычно в гауссовских фильтрах). Так в нашем случае сигма была 20, так как размер ядра равен стороне карты, которая равна 100.

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

Результаты и выводы

Я протестировал обученную модель на 51103 образцах.

  • 95% всех тестовых образцов смогли найти решение с помощью двунаправленного поиска. То есть алгоритму удалось найти путь от s до g в 48556 выборках, используя карту оценок, предоставленную моделью, в то время как он не смог этого сделать для остальные 2547 шт.
  • 87% всех тестовых образцов представили правильное решение. То есть траектория от s до g, которая не пересекает никаких препятствий (это значение не учитывает ограничение границы препятствия в 1 ячейку).
  • На действительных выборках средняя ошибка между наземными путями истины и решениями, предлагаемыми моделью, составляет 33 ячейки. Это довольно много, учитывая, что карты имеют размер 100x100 ячеек. Ошибки варьируются от минимума 0 (то есть «идеальная» реконструкция истинного пути, найденного в 2491 образце) до максимума… 745 ячеек (хорошо, эта модель точно не заменит автопилот Теслы).

Сразу же вы найдете некоторые результаты из тестового набора. В левой части изображений показано решение, предоставленное обученной сетью, а в правой части показано решение алгоритма D* lite.

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