Filtrul de particule este o metoda de localizare folosita in robotica. Presupunand ca avem un robot, in starea initiala el stie ca se afla intr-un spatiu predefinit, dar nu stie unde anume. Dispune de o harta (care sa presupunem ca are un numar de puncte de reper/remarcabile), dar este incapabil sa distinga pozitia in care s-ar afla pe acea harta. De aceea, isi creeaza ("in imaginatia lui") un set de particule ce reprezinta "copii in miniatura" ale sale si le plaseaza in diverse locuri. Pot fi 10, 100, 1000 sau oricate particule raspandite la random in intreg spatiul. Se presupune ca particulele au fost raspandite cat de cat uniform, astfel incat in fiecare pozitie sa se gaseasca o particula ceea ce inseamna ca exista o sansa ca robotul sa se afle chiar acolo. Robotul nu stie efectiv unde se afla, dar este capabil sa detecteze distante pana la anumite puncte de reper cu o anumita acuratete, folosind laseri.
Apoi se intampla urmatoarele: robotul doreste sa se miste si o data cu el se misca si particulele. Dupa ce robotul s-a miscat, coordonatele lui s-au schimbat si robotul doreste sa verifice (sa masoare) distantele de la locul unde se afla pana la punctele de reper ale hartii. Si obtine un set de distante. Particulele, la randul lor, fiind niste robotei fictivi, isi vor modifica pozitia _reala_ si vor si ele sa masoare distantele pana la aceste puncte remarcabile ale hartii. Particulele calculeaza aceste distante "de mana" pentru ca dispun atat de coordonatele in care se afla cat si de coordonatele punctelor de reper. In schimb, robotul nu isi stie coordonatele proprii dar poate afla distantele pana la punctele de reper (toate, sau doar o parte) folosind laseri.
Compararea acestor distante obtinute poate oferi un indiciu despre cat de apropiat e robotul fata de particule (adica cat de reale sunt ipotezele oferite de particule). De aceea, fiecarei particule i se va atribui ulterior o greutate/probabilitate ca EA sa indice pozitia corecta.
Apoi, cele 10, 100, 1000, etc particule vor fi filtrate (sampling with replacement). Unele dintre ele se dovedesc a returna distante prea aberante fata de punctele de reper, comparativ cu masuratorile robotului (care in continuare nu stie unde se afla), acelea cu siguranta vor avea greutati mici si _probabil_ vor muri. Din cele N particule initiale se vor alege, la intamplare, tot N, cu posibilitatea ca dintr-o singura particula initiala sa rezulte 1,2 sau mai multe particule noi. In final va fi acelasi numar de particule, dar unele probabil se vor repeta, ceea ce va indica faptul ca pozitia exprimata de acea particula este mai probabila decat altele. Alegerea noilor particule se face la intamplare, dar o particula cu greutate mare are o sansa mai mare sa fie aleasa (si o sansa destul de mica, dar existenta, de a "muri").
Cand robotul se misca din nou, procesul se repeta si dupa mai multi pasi vom vedea in jurul lui mai multe particule aglomerate care il vor insoti oriunde acesta se plimba. Poate, intr-un final, va rezulta o singura particula, care va spune cu o probabilitate mare (dar nu cu certitudine) ca robotul se afla la pozitia indicata de aceasta.
Ce se intampla cand avem de la inceput un filtru de particule cu o singura particula? Aceasta va fi asezata intr-un loc, la intamplare, care poate fi atat locul "cel bun" cat si foarte departe de locul real. Si cum posibilitatile de asezare sunt numeroase, cel mai probabil particula nu va oferi o localizare buna. Masuratorile robotului nu vor afecta durata de viata a particulei, deoarece suntem siguri ca la urmatorul resampling noua particula este chiar cea anterioara (care are probabilitate 1 sa fie realeasa). Deci, masuratorile nu vor afecta in niciun fel localizarea oferita de particula. In schimb, miscarea robotului influenteaza miscarea particulei pentru ca cei doi se misca la fel (aceleasi translatii, rotatii, etc).
Apoi se intampla urmatoarele: robotul doreste sa se miste si o data cu el se misca si particulele. Dupa ce robotul s-a miscat, coordonatele lui s-au schimbat si robotul doreste sa verifice (sa masoare) distantele de la locul unde se afla pana la punctele de reper ale hartii. Si obtine un set de distante. Particulele, la randul lor, fiind niste robotei fictivi, isi vor modifica pozitia _reala_ si vor si ele sa masoare distantele pana la aceste puncte remarcabile ale hartii. Particulele calculeaza aceste distante "de mana" pentru ca dispun atat de coordonatele in care se afla cat si de coordonatele punctelor de reper. In schimb, robotul nu isi stie coordonatele proprii dar poate afla distantele pana la punctele de reper (toate, sau doar o parte) folosind laseri.
Compararea acestor distante obtinute poate oferi un indiciu despre cat de apropiat e robotul fata de particule (adica cat de reale sunt ipotezele oferite de particule). De aceea, fiecarei particule i se va atribui ulterior o greutate/probabilitate ca EA sa indice pozitia corecta.
Apoi, cele 10, 100, 1000, etc particule vor fi filtrate (sampling with replacement). Unele dintre ele se dovedesc a returna distante prea aberante fata de punctele de reper, comparativ cu masuratorile robotului (care in continuare nu stie unde se afla), acelea cu siguranta vor avea greutati mici si _probabil_ vor muri. Din cele N particule initiale se vor alege, la intamplare, tot N, cu posibilitatea ca dintr-o singura particula initiala sa rezulte 1,2 sau mai multe particule noi. In final va fi acelasi numar de particule, dar unele probabil se vor repeta, ceea ce va indica faptul ca pozitia exprimata de acea particula este mai probabila decat altele. Alegerea noilor particule se face la intamplare, dar o particula cu greutate mare are o sansa mai mare sa fie aleasa (si o sansa destul de mica, dar existenta, de a "muri").
Cand robotul se misca din nou, procesul se repeta si dupa mai multi pasi vom vedea in jurul lui mai multe particule aglomerate care il vor insoti oriunde acesta se plimba. Poate, intr-un final, va rezulta o singura particula, care va spune cu o probabilitate mare (dar nu cu certitudine) ca robotul se afla la pozitia indicata de aceasta.
Ce se intampla cand avem de la inceput un filtru de particule cu o singura particula? Aceasta va fi asezata intr-un loc, la intamplare, care poate fi atat locul "cel bun" cat si foarte departe de locul real. Si cum posibilitatile de asezare sunt numeroase, cel mai probabil particula nu va oferi o localizare buna. Masuratorile robotului nu vor afecta durata de viata a particulei, deoarece suntem siguri ca la urmatorul resampling noua particula este chiar cea anterioara (care are probabilitate 1 sa fie realeasa). Deci, masuratorile nu vor afecta in niciun fel localizarea oferita de particula. In schimb, miscarea robotului influenteaza miscarea particulei pentru ca cei doi se misca la fel (aceleasi translatii, rotatii, etc).
Niciun comentariu:
Trimiteți un comentariu