Монте карло локализација (роботика)

Монте Карло локацизација, позната и како particle филтер локализација (што буквално може да се преведе како локализација со филтер на честички) е употреба на таканаречениот particle филтер метод, кој спаѓа во групата на Монте Карло методи, за локализирање на роботи. При дадена мапа од околината, алгоритмот врши проценка на позицијата и ориентацијата на одреден робот додека истиот се движи и врши мерење на околината. Алгоритмот користи particle филтер за претставување на веројатносната распределба на можни позиции, така што секоја честичка претставува една можна состојба, односно хипотеза за тоа каде се наоѓа роботот. Алгоритмот најчесто започнува со униформна веројатносна распределба на честички распространети низ целиот конфигурациски простор, што всушност значи дека роботот не знае каде се наоѓа, па претпоставува дека е подеднакво можно да биде на која и да е позиција во просторот. Штом роботот изврши некакво движење, позицијата на честичките се променува со цел да се изврши предвидување на состојбата после движењето; од друга страна, штом роботот изврши мерење на околината, алгоритмот создава ново множество од честички со користење на рекурзивна Баесова проценка, што значи дека новото множество е избрано така што рефлектира колкава е корелацијата на предвидената состојба и состојбата која ја даваат вистинските мерења. Со едноставни зборови, изборот на честички за новото множество се врши со случајно избирање на честички од старото множество (со повторување), така што веројатноста да се избере одредена честичка е пропорционална со тоа колку честичката ја претставува реалната состојба во која се наоѓа роботот. Со повторување на овој процес, честичките треба да конвергираат кон вистинската поза на роботот.

Претставување на состојбата

Начинот на кој е претставена состојбата на роботот зависи од примената. На пример, состојбата на дводимензионален робот најчесто се состои од вектор $(x,y,\theta )$, каде $x,y$ се координати, а $\theta$ ја претставува ориентацијата на роботот. За роботска рака со 10 зглобови, состојбата може да биде претставена преку агол за секој зглоб: $(\theta _{1},\theta _{2},...,\theta _{10})$.

Мислењето на роботот, што всушност претставува проценката на роботот за сопствената состојба, е веројатносна распределба низ просторот. Particle филтер алгоритмот го претставува мислењето во временската точка $t$ преку множество од $M$ честички $X_{t}=\lbrace x_{t}^{[1]},x_{t}^{[2]},\ldots ,x_{t}^{[M]}\rbrace$. Секоја честичка претставува состојба и може да биде гледана како хипотеза за вистинската состојба на роботот. Регионите од просторот кои имаат поголем број на честички индицираат дека роботот се наоѓа тука со поголема веројатност; од друга страна, веројатноста дека роботот е во регион со многу малку честички е значително помала.

Алгоритмот се заснова на Марковата одлика според која веројатносната распределба на моменталната состојба зависи само од претходната состојба, но не и од состојбите пред неа; математички, тоа значи дека $X_{t}$ зависи само од $X_{t-1}$. Оваа одлика е валидна само доколку околината е статична и не се менува со текот на времето. Роботот најчесто не знае каде се наоѓа пред употребата на овој алгоритам; поради тоа, честичките се униформно дистрибуирани низ конфигурацискиот простор.

Основен алгоритам

Целта на алгоритмот е да ја определи позата на роботот, под претпоставка дека е дадена мапа од околината на роботот. Во секој временски период $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}$.

   Алгоритам MCL$(X_{t-1},u_{t},z_{t})$:
       ${\bar {X_{t}}}=X_{t}=\emptyset$
       for $m=1$ до $M$:
           $x_{t}^{[m]}=$ ажурирање_засновано_на_командата_за_движење$(u_{t},x_{t-1}^{[m]})$
           $w_{t}^{[m]}=$ ажурирање_засновано_на_сензорските_мерења$(z_{t},x_{t}^{[m]})$
           ${\bar {X_{t}}}={\bar {X_{t}}}+\langle x_{t}^{[m]},w_{t}^{[m]}\rangle$
       endfor
       for $m=1$ до $M$:
           избери $x_{t}^{[i]}$ од ${\bar {X_{t}}}$ со веројатност $\propto w_{t}^{[i]}$
           $X_{t}=X_{t}+x_{t}^{[i]}$
       endfor
       return $X_{t}$

Пример за еднодимензионален робот

Робот се движи низ еднодимензионален ходник, така што има сензор кој може да каже дали има врата (слика лево) или не (слика десно).

Да замислиме робот во еднодимензионален кружен ходник со три идентични врати, користејќи сензор кој враќа точно или погрешно во зависност од тоа дали гледа врата.

$t=0$
Алгоритмот се иницијализира со униформна дистрибуција на честички. Роботот смета дека е подеднакво можно да се наоѓа на која и да било позиција во ходникот, иако физички се наоѓа пред првата врата.	Сензорско ажурирање: роботот детектира врата и доделува „тежина“ на секоја од честичките. Честичките кои даваат такво мерење со голема веројатност добиваат поголема тежина.	Создавање на ново множество честички: роботот создава ново множество честички, при што повеќето од честичките се сконцентрирани онаму каде се наоѓаат честичките со поголема тежина. Сега роботот знае дека се наоѓа пред една од трите врати, но сè уште не знае пред која точно.

$t=1$
Движечко ажурирање: роботот се движи надесно. Исто така и честичките се поместуваат надесно, а на движењето се додава и случајна грешка. Физички, роботот се наоѓа помеѓу втората и третата врата.	Сензорско ажурирање: роботот детектира ѕид. и доделува „тежина“ на секоја од честичките. Честичките кои даваат такво мерење со голема веројатност добиваат поголема тежина.	Создавање на ново множество честички: роботот создава ново множество честички, при што повеќето од честичките се сконцентрирани онаму каде се наоѓаат честичките со поголема тежина. Сега поголемиот дел од честичките е сконцентриран на две локации.

$t=2$
Движечко ажурирање: роботот се движи налево. Исто така и честичките се поместуваат надесно, а на движењето се додава и случајна грешка. Физички, роботот се наоѓа пред втората врата.	Сензорско ажурирање: роботот детектира врата. и доделува „тежина“ на секоја од честичките. Честичките кои даваат такво мерење со голема веројатност добиваат поголема тежина.	Создавање на ново множество честички: роботот создава ново множество честички, при што повеќето од честичките се сконцентрирани онаму каде се наоѓаат честичките со поголема тежина. Овојпат роботот успеа во намерата да се локализира, така што најголемиот дел од честичките се наоѓа на вистинската локација.

После три повторувања на алгоритмот, честичките конвергираа на позицијата на која се наоѓа роботот.

Ажурирање засновано на командата за движење (движечко ажурирање)

Проценка на позицијата после неколку движења на дводимензионален робот користејќи типичен модел на движење без сензорски мерења.

За време на движечкото ажурирање, роботот врши проценка на својата позиција како резултат на посакуваната движечка команда, користејќи симулација на движењето за секоја честичка. Доколку роботот се движи нанапред, сите честички ќе бидат поместени нанапред, без разлика на нивната ориентација. Доколку роботот се сврти за 90 степени во насока на часовникот, сите честички ќе бидат свртени за 90 степени без разлика каде се наоѓаат. Меѓутоа, актуаторите не се совршени во реалниот свет: истите може да се придвижат за нијанса повеќе или помалку во споредба со посакуваното движење; на пример, при посакувано праволиниско движење на роботот, вистинската траекторија ќе биде за нијанса искривена како резултат на минијатурни разлики во полупречникот на тркалата. Поради тоа, моделот за движење мора да вклучи и случајни грешки (анг. noise). Како резултат на тоа, и движењето на честичките нема да биде совршено и истите ќе дивергираат од вистинската позиција. Всушност, тоа е очекувано бидејќи довербата на роботот во сопствената позиција се намалува доколку истиот се движи без да врши мерења на околината.

Ажурирање засновано на сензорските мерења (сензорско ажурирање)

Кога роботот врши мерења на околината, честичките се ажурираат така што истите поточно ја рефлектираат вистинската позиција на роботот. За секоја честичка, роботот ја пресметува веројатноста да бидат извршени вистинските сензорски мерења доколку се наоѓа онаму каде што е честичката (анг. pose likelihood). По завршувањето на овој чекор, роботот врши случаен избор на $M$ нови честички од претходното множеството, така што шансата да се избере $x_{t-1}^{[i]}$ е пропорционална со $w_{t}^{[i]}$. Честичките кои повеќе одговараат на сензорските мерења уживаат поголема шанса да бидат избрани (можеби и повеќепати, со оглед на тоа што изборот се врши со повторување), а додека останатите честички се избираат поретко. Како резултат на тоа, честичките конвергираат кон подобра проценка на состојбата на роботот. И ова е очекуван резултат поради тоа што роботот станува посигурен за својата позиција штом изврши мерење на околината.

Особености

Непараметарност

Particle филтерот, кој е централна алатка во Монте Карло локализацијата, може да претстави многу веројатносни дистрибуции, со оглед на тоа што е непараметарски. Други алгоритми за локализација, како на пример Калмановиот филтер (и неговите варијанти, надградениот Калманов филтер и unscented Калмановиот филтер), претпоставуваат дека дистрибуцијата со која роботот ја претставува својата проценка е Гаусова, па поради тоа не произведуваат добри резултати кога вистинската дистрибуција е мултимодална. На пример, робот кој се наоѓа во ходник со неколку слични врати може да процени дека дистрибуцијата има локален врв пред секоја врата, но не може да определи пред која врата се наоѓа. Во такви ситуации, particle филтерот дава подобри резултати отколку параметарските филтри.

Друг непараметарски пристап е локализацијата заснована на мрежа која користи хистограм за претставување на веројатносната распределба. Споредено со локализацијата заснована на мрежа, Монте Карло локализацијата дава подобри резултати поради тоа што околината претставена со честички не е дискретизирана.

Пресметковна комплексност

Временската комплексност на particle филтерот е линеарна во однос на бројот на честички. Од друга страна, бројот на честички ја подобрува точноста на алгоритмот, па секогаш постои компромис помеѓу посакуваната брзина и точност. Една стратегија за избор на бројот на честички $M$ е продолжено генерирање на честички до оној момент кога ќе пристигнат наредната команда $u_{t}$ и сензорско мерење $z_{t}$. На овој начин се добива најголемиот можен број на честички кој софтверот може да го издржи без значително влијание на останатите функции на роботот. Како резултат на тоа, имплементацијата се адаптира на компјутерските ресурси: доколку постои побрз процесор, алгоритмот ќе создаде повеќе честички и точноста ќе биде поголема.

Споредено со локализацијата заснована на мрежа, Монте Карло локализацијата има помали мемориски побарувања поради тоа што истите зависат само од бројот на честички, а не од големината на мапата , што значи дека мерењата можe да бидат интегрирани со повисока честота.

Губење на честички

Еден недостаток на наивната имплементација на Монте Карло локализацијата може да се забележи кога роботот стои на една локација и постојано врши мерења без да се движи. Да претпоставиме дека честичките конвергираат на погрешна локација или пак роботот е киднапиран и пренесен на нова локација по конвергенцијата на честичките. Поради тоа што честичките кои се наоѓаат далеку од регионот на конвергенција се губат при создавањето на ново множество честички, нивниот број се намалува при секоја итерација и истите наскоро исчезнуваат. Во ваков случај, алгоритмот не може да ја надомести штетата. Овој проблем најчесто се случува поради малиот број на честички, на пример $M\leq 50$, но и кога честичките се распространети на голем простор. Всушност, секој particle филтер алгоритам би можел случајно да ги занемари сите честички кои се наоѓаат блиску до вистинската локација при создавањето на ново множество честички.

Едно решение за овој проблем е да се додаде одреден број на случајни честички при секоја итерација. Тоа е еквивалентно на претпоставување дека роботот може да биде киднапиран на некоја случајна позиција во било кој момент, што значи дека постои одреден број на случајни настани во моделот на движење. Гарантирајќи дека ниту еден дел од мапата нема да остане без честички, алгоритмот го елиминира проблемот со губење на честички.