Фильтры частиц

Более техническая версия этого поста изначально была опубликована в блоге Udacity .

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

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

Локализация : Где мы?
Планирование маршрута : как добраться до пункта назначения?
Восприятие : Что еще есть вокруг?
Прогноз : как будет выглядеть окружающая среда чуть позже?
Планирование : каким курсом мы будем следовать в следующие несколько секунд?
Контроль : Как мы собираемся следовать намеченному курсу?

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

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

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

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

Если этого недостаточно, скорость, с которой GPS обновляет информацию о местоположении, также довольно низкая, в диапазоне от 1 до 10 Гц. Даже при частоте 10 Гц автомобиль, движущийся со скоростью 20 км/ч с опозданием, продвинулся бы примерно на полметра между двумя обновлениями GPS.

Чтобы уменьшить неопределенность в локализации из-за движения, автономные транспортные средства используют инерциальные измерительные блоки (IMU). IMU являются быстрыми и точными и измеряют ускорение автомобиля и скорость поворота. Затем эту информацию можно использовать для определения положения автомобиля между двумя последовательными обновлениями GPS. IMU имеют тенденцию накапливать небольшие ошибки аппроксимации с течением времени, но это не та проблема, с которой мы здесь имеем дело.

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

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

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

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

Чтобы быстро сориентироваться, вы используете окружение. Сначала вы представляете себя в разных местах на кровати. Затем вы ощущаете «знаковые» объекты в окружении, прикасаясь к ним и идентифицируя их. Вы можете столкнуть бутылку с водой с соседнего стола или удариться ногой о стул. Эти наблюдения дают вам важные подсказки о том, где вы, вероятно, находитесь в сфере гостиничной кровати. Поскольку вы помните, где находились бутылка, стол и стул относительно кровати, вы можете более точно определить свое положение на кровати. С каждым новым наблюдением вы можете исключить определенные места на кровати и увеличить свои шансы оказаться в других местах.

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

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

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

Фильтрация частиц — невероятно простой алгоритм, на котором работают многие роботы и автономные автомобили. Nvidia Drive Labs выпустила короткое видео о том, как локализация может помочь в использовании расширенных карт с различными достопримечательностями. Uber ATG опубликовал здесь блог о том, как они повышают точность GPS .