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

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

Основное описание [ править ]

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

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

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

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

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

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

Обзор [ править ]

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

Каждый раз алгоритм принимает в качестве входных данных предыдущее убеждение , команду срабатывания и данные, полученные от датчиков ; и алгоритм выводит новое убеждение . ^[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}}$

 Алгоритм MCL : для к : motion_update sensor_update${\displaystyle (X_{t-1},u_{t},z_{t})}$${\displaystyle {\bar {X_{t}}}=X_{t}=\emptyset }$${\displaystyle m=1}$${\displaystyle M}$${\displaystyle x_{t}^{[m]}=}$ ${\displaystyle (u_{t},x_{t-1}^{[m]})}$ ${\displaystyle w_{t}^{[m]}=}$ ${\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}$
Обновление движения : робот перемещается на некоторое расстояние влево. Все частицы также перемещаются влево, и применяется некоторый шум. Робот физически находится у второй двери.	Обновление датчика : робот обнаруживает дверь . Он присваивает вес каждой из частиц. Частицы, которые могут дать показания датчика, получают больший вес.	Передискретизация : робот генерирует набор новых частиц, большинство из которых генерируются вокруг предыдущих частиц с большим весом. Робот успешно локализовался.

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

Обновление движения [ править ]

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

Обновление датчика [ править ]

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

Свойства [ править ]

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

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

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

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

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

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

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

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

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

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

Варианты [ править ]

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

Выборка KLD [ править ]

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

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

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

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

Ссылки [ править ]