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

Од Википедија — слободната енциклопедија
Прејди на: содржини, барај

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

Претставување на состојбата[уреди | уреди извор]

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

Мислењето на роботот, што всушност претставува проценката на роботот за сопствената состојба, е веројатносна дистрибуција низ просторот. [1][4] Particle филтер алгоритмот го претставува мислењето во временската точка 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]

   Алгоритам 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
Движечко ажурирање: роботот се движи налево. Исто така и честичките се поместуваат надесно, а на движењето се додава и случајна грешка. Физички, роботот се наоѓа пред втората врата.
Сензорско ажурирање: роботот детектира врата. и доделува „тежина“ на секоја од честичките. Честичките кои даваат такво мерење со голема веројатност добиваат поголема тежина.
Создавање на ново множество честички: роботот создава ново множество честички, при што повеќето од честичките се сконцентрирани онаму каде се наоѓаат честичките со поголема тежина. Овојпат роботот успеа во намерата да се локализира, така што најголемиот дел од честичките се наоѓа на вистинската локација.

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

Ажурирање базирано на командата за движење (движечко ажурирање)[уреди | уреди извор]

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

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

Ажурирање базирано на сензорските мерења (сензорско ажурирање)[уреди | уреди извор]

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

Карактеристики[уреди | уреди извор]

Непараметарност[уреди | уреди извор]

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

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

Пресметковна комплексност[уреди | уреди извор]

Временската комплексност на particle филтерот е линеарна во однос на бројот на честички. Од друга страна, бројот на честички ја подобрува точноста на алгоритмот, па секогаш постои компромис помеѓу посакуваната брзина и точност. Една стратегија за избор на бројот на честички M е продолжено генерирање на честички до оној момент кога ќе пристигнат наредната команда u_t и сензорско мерење z_t.[4] На овој начин се добива најголемиот можен број на честички кој софтверот може да го издржи без значително влијание на останатите функции на роботот. Како резултат на тоа, имплементацијата се адаптира на компјутерските ресурси: доколку постои побрз процесор, алгоритмот ќе создаде повеќе честички и точноста ќе биде поголема.[4]

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

Губење на честички[уреди | уреди извор]

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

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

Наводи[уреди | уреди извор]

  1. 1,0 1,1 1,2 1,3 Ioannis M. Rekleitis. "A Particle Filter Tutorial for Mobile Robot Localization." Centre for Intelligent Machines, McGill University, Tech. Rep. TR-CIM-04-02 (2004).
  2. 2,0 2,1 2,2 2,3 Frank Dellaert, Dieter Fox, Wolfram Burgard, Sebastian Thrun. "Monte Carlo Localization for Mobile Robots." Proc. of the IEEE International Conference on Robotics and Automation Vol. 2. IEEE, 1999.
  3. Dieter Fox, Wolfram Burgard, Frank Dellaert, and Sebastian Thrun, "Monte Carlo Localization: Efficient Position Estimation for Mobile Robots." Proc. of the Sixteenth National Conference on Artificial Intelligence John Wiley & Sons Ltd, 1999.
  4. 4,00 4,01 4,02 4,03 4,04 4,05 4,06 4,07 4,08 4,09 4,10 4,11 4,12 4,13 4,14 4,15 4,16 4,17 4,18 4,19 Sebastian Thrun, Wolfram Burgard, Dieter Fox. Probabilistic Robotics MIT Press, 2005. Ch. 8.3 ISBN 9780262201629.
  5. Sebastian Thrun, Dieter Fox, Wolfram Burgard, Frank Dellaert. "Robust monte carlo localization for mobile robots." Artificial Intelligence 128.1 (2001): 99–141.