Роман Удовиченко, Яндекс: алгоритмы построения пути для беспилотного автомобиля

Материал подготовил: Аркадий Софрыгин, основатель сайта Беспилот.
Присоединяйтесь к обсуждению темы в Facebook

Друзья, сегодня предлагаю вам посмотреть лекцию руководителя группы обработки дорожных ситуаций из минского офиса Яндекса Романа Удовиченко "Алгоритмы построения пути для беспилотного автомобиля". Можно скачать, что лекция уже архивная (2017 г.), и это часть истории развития беспилотников в России. Весь текст далее - выступление Романа Удовиченко.   

Как научить машину ездить самостоятельно?

Для начала нужно понять, как научить машину ездить самостоятельно. При условии, что мы обвесили ее всеми нужными датчиками, разместили на ней камеры, радары, лидары. Все это мы можем сделать, и в предположении нам остается только написать код. 

Мы можем использовать классический подход из робототехники. Для этого мы разбиваем большую задачу автономного движения машины на 4 модуля:

• Локализация. Машина должна понимать, где она находится. 
• Распознавание. Определение и классификация объектов вокруг машины. 
• Планирование. Построение маршрута, исходя из информации от модулей локализации и распознавания. 
• Управление. Непосредственно движение по маршруту по заданной траектории. 

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

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

Поэтому сегодня мы поговорим о классическом подходе и в частности о планировании пути - построении траектории, по которой мы будем ехать. 

Планирование пути беспилотника

Почему планирование пути это сложная задача, которую нельзя решить быстро? Дело в том, что автомобиль обладает рядом существенных ограничений. Это не шар, находящийся в пространстве, который может катиться в любую сторону и мгновенно останавливаться, когда нам нужно. 

У автомобиля есть текущее направление движения, угол поворота колес, и машина не может просто взять и оказаться например на 2 метра левее своего текущего положения. Она может ехать вперед или назад, поворачивая на какой-то угол, но тем не менее перемещение очень сильно ограничено.

И траектория, которую мы строим, подвержена различным ограничениям из телематики. Например, мы не можем мгновенно разогнаться или увеличить свое ускорение. Поэтому сегодня мы рассмотрим такие разновидности алгоритмов для построения пути, по которым потом хорошо может ехать машина, в частности это:

• Алгоритмы на графах. 
• Оптимизационные методы, использующие непрерывные математические оптимизации. 
• Стохастические алгоритмы, которые рассматривают случайное поведение.
• Специализированные методы, которые решают какую-то очень частную задачу, но решают ее хорошо, лучше чем в общем случае. 

Алгоритмы на графах

Первый вопрос, который нас здесь интересует, это как в принципе построить граф. Например у нас стоит машина, но в реальности графа никакого нет: вершин, ребер не нарисовано. И нам этот граф нужно придумать самим. 

Первое, что мы сделаем, это разобьем все пространство на клетки. Мы можем взять всю поверхность Земли и разбить на клетки, допустим 50 на 50, 25 на 25 или 10 на 10 см, затем соединим соседние клетки ребрами и будем искать на них путь. Это будет далеко от того пути, по которому машина может проехать, но тем не менее какое-то приближение пути это даст. В-общем у нас будут вершины в 2-мерном пространстве. 

Дальше мы можем усложнять наше пространство, добавляя туда например текущий угол поворота машины. И у нас будут клетки уже не просто X, Y, а еще и текущая ориентация беспилотника - дискретизированное направление Север-Юг-Запад-Восток. 

Понятно, что кроме направления мы можем еще много чего учитывать: текущую скорость машины, ускорение, тангентальное ускорение. Все это важно учитывать, но чем больше мы усложняем наше пространство, тем более сложным становится наш граф. 

Помимо разбиения пространства на клетки мы можем взять какую-то изначальную точку и дальше двигаться небольшими шагами в виде примитивов. Что такое примитив? Это например проехать 50 см вперед, или проехать 50 см вперед и повернуть налево или направо.

И такими примитивами мы можем замостить все пространство. Даже если в явном виде клеточек у нас нет, но эти мелкие шаги хорошо согласованы друг с другом, то у нас получается регулярная сетка, которая хорошо и аккуратно покрывает пространство.

В то же время, если мы рассмотрим не столь хорошо стыкующиеся друг с другом примитивы, например скажем что у нас поворот налево происходит под уголом 89°, а поворот направо под углов 90°, то у нас то же самое количество вершин будет занимать существенно меньшую площадь пространства из-за того, что они плохо друг с другом стыкуются. Плотность точек будет очень высокая, а далеко мы покрыть пространство не сможем. 

Но мы можем объединить эти 2 подхода и сказать что мы рассматриваем какие-то примитивы движения под любыми углами, но при этом все-равно разобьем пространство на клетки и скажем, что в одной клетке не может быть больше 1-2 К-вершин. 

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

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

Допустим у нас есть граф и мы хотим применить к нему какой-то алгоритм. 

Алгоритм Дейкстры

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

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

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

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

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

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

Продолжение лекции Романа Удовиченко смотрите в видео ниже

Сайт беспилотников Яндекса: sdc.yandex.com и да пребудет с вами беспилот!  

Cмотрите видео выступления Романа Удовиченко с лекцией "Алгоритмы построения пути для беспилотного автомобиля".

Материалы по теме:

Друзья, всё общение как всегда в моем фейсбуке: https://www.facebook.com/arksofrygin

Аркадий Софрыгин

основатель BesPilot.com

Добавляйтесь в Facebook

Этот адрес электронной почты защищён от спам-ботов. У вас должен быть включен JavaScript для просмотра. Этот адрес электронной почты защищён от спам-ботов. У вас должен быть включен JavaScript для просмотра.