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

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

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

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

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

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

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

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

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

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

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

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

Во время обновления движения робот прогнозирует свое новое местоположение на основе поданной команды срабатывания, применяя смоделированное движение к каждой из частиц. ^[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] Фактически, любой алгоритм фильтра частиц может случайно отбросить все частицы, близкие к правильному состоянию, на этапе повторной выборки. ^[4] ${\displaystyle M\leq 50}$

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

Варианты

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

выборка КЛД

Локализация Монте-Карло может быть улучшена за счет отбора частиц адаптивным способом на основе оценки ошибки с использованием расхождения Кульбака – Лейблера (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}}$

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

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