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

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

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

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

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

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

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

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

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

Обзор

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

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

   Algorithm MCL $(X_{t-1},u_{t},z_{t})$ :
        ${\bar {X_{t}}}=X_{t}=\emptyset$ 
       for  $m=1$  to  $M$ :
            $x_{t}^{[m]}=$  motion_update $(u_{t},x_{t-1}^{[m]})$ 
            $w_{t}^{[m]}=$  sensor_update $(z_{t},x_{t}^{[m]})$ 
            ${\bar {X_{t}}}={\bar {X_{t}}}+\langle x_{t}^{[m]},w_{t}^{[m]}\rangle$ 
       endfor
       for  $m=1$  to  $M$ :
           draw  $x_{t}^{[m]}$  from  ${\bar {X_{t}}}$  with probability  $\propto w_{t}^{[m]}$ 
            $X_{t}=X_{t}+x_{t}^{[m]}$ 
       endfor
       return  $X_{t}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Варианты

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

выборка КЛД

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

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

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

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

Ссылки

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

[Rekleitis-1] Jump up to: ^а ^б ^с ^д Иоаннис М. Реклейтис. « Учебное пособие по фильтру частиц для локализации мобильных роботов ». Центр интеллектуальных машин, Университет Макгилла, Техн. Отчет TR-CIM-04-02 (2004 г.).

[icra1999-2] Jump up to: ^а ^б ^с ^д Фрэнк Деллаерт , Дитер Фокс, Вольфрам Бургард , Себастьян Трун . « Локализация Монте-Карло для мобильных роботов. Архивировано 17 сентября 2007 г. в Wayback Machine ». Учеб. Международной конференции IEEE по робототехнике и автоматизации Vol. 2. ИИЭР, 1999.

[aaai1999-3] Дитер Фокс, Вольфрам Бургард, Фрэнк Деллаерт и Себастьян Трун, « Локализация Монте-Карло: эффективная оценка положения мобильных роботов ». Учеб. Шестнадцатой национальной конференции по искусственному интеллекту John Wiley & Sons Ltd, 1999 г.

[pr-4] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м ^н ^тот ^п ^д ^р ^с ^т ^в ^v ^В ^х ^и Себастьян Трун, Вольфрам Бургард, Дитер Фокс. Вероятностная робототехника MIT Press, 2005. Гл. 8.3 ISBN 9780262201629 .

[robust-5] Себастьян Трун, Дитер Фокс, Вольфрам Бургард, Фрэнк Делларт. « Надежная локализация мобильных роботов по методу Монте-Карло ». Искусственный интеллект 128.1 (2001): 99–141.

[kldpaper-6] Дитер Фокс. « KLD – Отбор проб: адаптивные фильтры частиц ». Департамент компьютерных наук и инженерии Вашингтонского университета. НИПС, 2001.

[1]

[2]

[3]

[4]

[5]

[6]