Локализация Монте-Карло - Monte Carlo localization - Wikipedia

Робот в одномерном коридоре, в котором есть двери. Цель локализации по методу Монте-Карло - позволить роботу определять свое положение на основе наблюдений с помощью сенсора.

Локализация Монте-Карло (MCL), также известный как локализация сажевого фильтра,^[1] алгоритм для роботов локализовать используя фильтр твердых частиц.^[2][3][4][5] Учитывая карту окружающей среды, алгоритм оценивает положение и ориентация робота, когда он движется и ощущает окружающую среду.^[4] Алгоритм использует фильтр твердых частиц представлять распределение вероятных состояний, где каждая частица представляет возможное состояние, то есть гипотезу о том, где находится робот.^[4] Алгоритм обычно начинается с равномерного случайного распределения частиц по конфигурационное пространство, что означает, что робот не имеет информации о том, где он находится, и предполагает, что он с равной вероятностью может быть в любой точке пространства.^[4] Всякий раз, когда робот движется, он перемещает частицы, чтобы предсказать свое новое состояние после движения. Каждый раз, когда робот что-то ощущает, частицы пересчитываются на основе рекурсивная байесовская оценка, т.е. насколько хорошо фактические считанные данные коррелируют с прогнозируемым состоянием. В конечном итоге частицы должны сходиться к фактическому положению робота.^[4]

Основное описание

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

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

Государственное представительство

Состояние робота зависит от приложения и конструкции. Например, состояние типичного 2D-робота может состоять из кортежа ${\displaystyle (x,y,\theta )}$ для позиции ${\displaystyle x,y}$ и ориентация ${\displaystyle \theta }$. Для манипулятора с 10 суставами это может быть кортеж, содержащий угол в каждом суставе: ${\displaystyle (\theta _{1},\theta _{2},...,\theta _{10})}$.

В вера, которая является оценкой робота его текущего состояния, является функция плотности вероятности распределены по пространству состояний.^[1][4] В алгоритме MCL вера за раз ${\displaystyle t}$ представлен набором ${\displaystyle M}$ частицы ${\displaystyle X_{t}=\lbrace x_{t}^{[1]},x_{t}^{[2]},\ldots ,x_{t}^{[M]}\rbrace }$.^[4] Каждая частица содержит состояние и, таким образом, может рассматриваться как гипотеза состояния робота. Области в пространстве состояний с большим количеством частиц соответствуют большей вероятности того, что робот будет там, а области с небольшим количеством частиц вряд ли будут там, где находится робот.

Алгоритм предполагает Марковская собственность что распределение вероятностей текущего состояния зависит только от предыдущего состояния (а не от любого из предшествующих), т.е. ${\displaystyle X_{t}}$ зависит от Только на ${\displaystyle X_{t-1}}$.^[4] Это работает, только если среда статична и не меняется со временем.^[4] Обычно при запуске робот не имеет информации о своей текущей позе, поэтому частицы равномерно распределяются по поверхности. конфигурационное пространство.^[4]

Обзор

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

Каждый раз ${\displaystyle t}$ алгоритм принимает в качестве входных данных предыдущее убеждение ${\displaystyle X_{t-1}=\lbrace x_{t-1}^{[1]},x_{t-1}^{[2]},\ldots ,x_{t-1}^{[M]}\rbrace }$, команда срабатывания ${\displaystyle u_{t}}$, и данные, полученные с датчиков ${\displaystyle z_{t}}$; и алгоритм выводит новое убеждение ${\displaystyle X_{t}}$.^[4]

   Алгоритм MCL${\displaystyle (X_{t-1},u_{t},z_{t})}$:       ${\displaystyle {\bar {X_{t}}}=X_{t}=\emptyset }$       за ${\displaystyle m=1}$ к ${\displaystyle M}$:           ${\displaystyle x_{t}^{[m]}=}$ motion_update${\displaystyle (u_{t},x_{t-1}^{[m]})}$           ${\displaystyle w_{t}^{[m]}=}$ sensor_update${\displaystyle (z_{t},x_{t}^{[m]})}$           ${\displaystyle {\bar {X_{t}}}={\bar {X_{t}}}+\langle x_{t}^{[m]},w_{t}^{[m]}\rangle }$       конец для ${\displaystyle m=1}$ к ${\displaystyle M}$:           рисовать ${\displaystyle x_{t}^{[m]}}$ из ${\displaystyle {\bar {X_{t}}}}$ с вероятностью ${\displaystyle \propto w_{t}^{[m]}}$           ${\displaystyle X_{t}=X_{t}+x_{t}^{[m]}}$       конец для возврата ${\displaystyle X_{t}}$

Пример для 1D робота

Робот движется по одномерному коридору, вооруженный датчиком, который может только определить, есть ли дверь (слева) или нет (справа).

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

${\displaystyle t=0}$
Алгоритм инициализируется с равномерным распределением частиц. Робот считает, что он с равной вероятностью находится в любой точке коридора, даже если физически находится у первой двери.	Обновление датчика: робот обнаруживает Дверь. Он присваивает вес каждой из частиц. Частицы, которые могут дать показания датчика, получают больший вес.	Повторная выборка: робот генерирует набор новых частиц, большинство из которых генерируются вокруг предыдущих частиц с большим весом. Теперь он считает, что он находится у одной из трех дверей.

${\displaystyle t=1}$
Обновление движения: робот перемещается на некоторое расстояние вправо. Все частицы также движутся вправо, и применяется некоторый шум. Робот физически находится между второй и третьей дверями.	Обновление датчика: робот обнаруживает нет двери. Он присваивает вес каждой из частиц. Частицы, которые могут дать показания датчика, получают больший вес.	Повторная выборка: робот генерирует набор новых частиц, большинство из которых генерируются вокруг предыдущих частиц с большим весом. Теперь он считает, что он находится в одном из двух мест.

${\displaystyle t=2}$
Обновление движения: робот перемещается на некоторое расстояние влево. Все частицы также перемещаются влево, и применяется некоторый шум. Робот физически находится у второй двери.	Обновление датчика: робот обнаруживает Дверь. Он присваивает вес каждой из частиц. Частицы, которые могут дать показания датчика, получают больший вес.	Повторная выборка: робот генерирует набор новых частиц, большинство из которых генерируется вокруг предыдущих частиц с большим весом. Робот успешно локализовался.

В конце трех итераций большая часть частиц сходится к фактическому положению робота по желанию.

Обновление движения

Вера после перемещения на несколько шагов для 2D-робота используя типичную модель движения без ощущения.

Во время обновления движения робот предсказывает свое новое местоположение на основе заданной команды срабатывания, применяя смоделированное движение к каждой из частиц.^[1] Например, если робот движется вперед, все частицы движутся вперед в своих направлениях, независимо от того, в какую сторону они указывают. Если робот вращается на 90 градусов по часовой стрелке, все частицы вращаются на 90 градусов по часовой стрелке, независимо от того, где они находятся. Однако в реальном мире нет идеальных исполнительных механизмов: они могут перескакивать или недооценивать желаемое количество движения. Когда робот пытается двигаться по прямой, он неизбежно поворачивает в одну или в другую сторону из-за незначительной разницы в радиусе колес.^[1] Следовательно, модель движения должна компенсировать шум. Как следствие, частицы неизбежно расходятся во время обновления движения. Это ожидаемо, поскольку робот теряет уверенность в своем положении, если он движется вслепую, не ощущая окружающей среды.

Обновление датчика

Когда робот ощущает окружающую среду, он обновляет свои частицы, чтобы более точно отразить, где он находится. Для каждой частицы робот вычисляет вероятность того, что, если бы он находился в состоянии частицы, он бы воспринял то, что на самом деле почувствовали его сенсоры. Присваивает вес ${\displaystyle w_{t}^{[i]}}$ для каждой частицы пропорционально указанной вероятности. Затем он случайным образом рисует ${\displaystyle M}$ новые частицы из предыдущего убеждения, с вероятностью, пропорциональной ${\displaystyle w_{t}^{[i]}}$. Частицы, соответствующие показаниям датчика, будут выбраны с большей вероятностью (возможно, более одного раза), а частицы, несовместимые с показаниями датчика, собираются редко. Таким образом, частицы сходятся, чтобы лучше оценить состояние робота. Это ожидаемо, поскольку робот становится все более уверенным в своем положении, когда чувствует окружающую среду.

Характеристики

Непараметрическость

В фильтр твердых частиц центральный для MCL может приблизительно соответствовать нескольким различным видам распределения вероятностей, поскольку это непараметрическое представление.^[4] Некоторые другие алгоритмы байесовской локализации, такие как Фильтр Калмана (и варианты, расширенный фильтр Калмана и фильтр Калмана без запаха ), предположим, что вера в робота близка к тому, чтобы быть Гауссово распределение и не работают в ситуациях, когда вера мультимодальный.^[4] Например, робот в длинном коридоре с множеством похожих на вид дверей может прийти к убеждению, что у каждой двери есть пик, но робот не может различить который дверь это у. В таких ситуациях фильтр твердых частиц может дать лучшую производительность, чем параметрические фильтры.^[4]

Другой непараметрический подход к марковской локализации - это сеточная локализация, в которой используется гистограмма для представления распределения убеждений. По сравнению с сеточным подходом локализация Монте-Карло более точна, поскольку состояние, представленное в выборках, не дискретизируется.^[2]

Вычислительные требования

Фильтр твердых частиц временная сложность является линейный по количеству частиц. Естественно, чем больше частиц, тем выше точность, поэтому существует компромисс между скоростью и точностью, и желательно найти оптимальное значение ${\displaystyle M}$. Одна стратегия для выбора ${\displaystyle M}$ заключается в том, чтобы непрерывно генерировать дополнительные частицы до следующей пары команд ${\displaystyle u_{t}}$ и считывание датчика ${\displaystyle z_{t}}$ прибыл.^[4] Таким образом получается максимально возможное количество частиц, не мешая работе остальной части робота. Таким образом, реализация адаптируется к доступным вычислительным ресурсам: чем быстрее процессор, тем больше частиц может быть сгенерировано и, следовательно, тем точнее алгоритм.^[4]

По сравнению с марковской локализацией на основе сетки, локализация Монте-Карло уменьшила использование памяти, поскольку использование памяти зависит только от количества частиц и не масштабируется с размером карты.^[2] и может интегрировать измерения на гораздо более высокой частоте.^[2]

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

Депривация частиц

Недостаток наивной реализации локализации Монте-Карло возникает в сценарии, когда робот сидит в одном месте и неоднократно ощущает окружающую среду, не двигаясь.^[4] Предположим, что все частицы сходятся к ошибочному состоянию, или если оккультная рука поднимает робота и перемещает его в новое место после того, как частицы уже сошлись. Поскольку частицы, далекие от конвергентного состояния, редко выбираются для следующей итерации, они становятся все реже на каждой итерации, пока не исчезнут совсем. На данный момент алгоритм не может восстановиться.^[4] Эта проблема более вероятна для небольшого количества частиц, например, ${\displaystyle M\leq 50}$, и когда частицы распределены по большому пространству состояний.^[4] Фактически любой фильтр твердых частиц алгоритм может случайно отбросить все частицы около правильного состояния на этапе повторной выборки.^[4]

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

Варианты

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

KLD отбор проб

Локализация Монте-Карло может быть улучшена путем отбора проб частиц адаптивным способом на основе оценки ошибки с использованием Дивергенция Кульбака – Лейблера (КЛД). Изначально необходимо использовать большой ${\displaystyle M}$ из-за необходимости покрыть всю карту равномерно случайным распределением частиц. Однако, когда частицы собрались вокруг одного и того же места, поддержание такого большого размера выборки является затратным с точки зрения вычислений. ^[6]

KLD – выборка - это вариант локализации Монте-Карло, где на каждой итерации размер выборки ${\displaystyle M_{x}}$ рассчитывается. Размер выборки ${\displaystyle M_{x}}$ вычисляется так, что с вероятностью ${\displaystyle 1-\delta }$, ошибка между истинным апостериорным приближением и приближением на основе выборки меньше, чем ${\displaystyle \epsilon }$. Переменные ${\displaystyle \delta }$ и ${\displaystyle \epsilon }$ фиксированные параметры.^[4]

Основная идея - создать сетку (гистограмму), наложенную на пространство состояний. Каждая ячейка гистограммы изначально пуста. На каждой итерации новая частица извлекается из предыдущего (взвешенного) набора частиц с вероятностью, пропорциональной ее весу. Вместо повторной выборки, выполняемой в классической MCL, алгоритм KLD – выборки отбирает частицы из предыдущего взвешенного набора частиц и применяет обновления движения и датчика перед помещением частицы в свой бункер. Алгоритм отслеживает количество непустых ящиков, ${\displaystyle k}$. Если частица вставлена ​​в ранее пустой контейнер, значение ${\displaystyle M_{x}}$ пересчитывается, который увеличивается в основном линейно по ${\displaystyle k}$. Это повторяется до тех пор, пока размер выборки ${\displaystyle M}$ такой же как ${\displaystyle M_{x}}$. ^[4]

Легко увидеть, как KLD-выборка отбраковывает избыточные частицы из набора частиц, только увеличивая ${\displaystyle M_{x}}$ при заполнении нового места (бункера). На практике KLD-сэмплинг неизменно превосходит классический MCL и сходится быстрее.^[4]

Рекомендации

1. Иоаннис М. Реклейтис. "Учебное пособие по фильтрации частиц для локализации мобильного робота." Центр интеллектуальных машин, Университет Макгилла, Тех. Представитель TR-CIM-04-02 (2004).
2. Фрэнк Делларт, Дитер Фокс, Вольфрам Бургард, Себастьян Трун. "Локализация Монте-Карло для мобильных роботов В архиве 2007-09-17 на Wayback Machine." Proc. Международной конференции IEEE по робототехнике и автоматизации Vol. 2. IEEE, 1999.
3. Дитер Фокс, Вольфрам Бургард, Фрэнк Делларт и Себастьян Трун "Локализация Монте-Карло: эффективная оценка местоположения мобильных роботов." Proc. Шестнадцатой Национальной конференции по искусственному интеллекту John Wiley & Sons Ltd, 1999.
4. Себастьян Трун, Вольфрам Бургард, Дитер Фокс. Вероятностная робототехника MIT Press, 2005. Гл. 8,3 ISBN  9780262201629.
5. Себастьян Трун, Дитер Фокс, Вольфрам Бургард, Фрэнк Делларт. "Надежная локализация в монте-карло для мобильных роботов." Искусственный интеллект 128.1 (2001): 99–141.
6. Дитер Фокс. "KLD – Sampling: Адаптивные фильтры частиц." Департамент компьютерных наук и инженерии Вашингтонского университета. НИПС, 2001.