Particle filtering

Jedná se o podobný princip jako u Kalmanova filtru (akorát jinak). Rozdíl je v tom, že se vezme řada náhodných částeček, následně se podle daného modelu modeluje jejich pohyb. Na základě měření se určí ty „lepší“ částečky, které odpovídají měření. V následném kroku se generují částečky nové, na základě těch „lepších“. To znamená, že vývoj, který se více blíží měření má větší šanci na to, aby se použil v následujícím kroku.

Vychází se z „particlů“, které se pravděpodobnostně chovají jako sledovaný systém.

Začínáme s vzorky (particly), kterým přidělíme váhy. Z této soustavy na základě daných pravidel vypočteme stav v dalším kroku. Pro predikci nového stavu použijeme částice, které mají vyšší váhy (imprtance sampling), s vyšší pravděpodobností. Znamená to, že „úspěšné“ částice, které se podobají více hledanému jsou vybrány a tedy použity pro následující krok s vyšší pravděpodobností. Vygenerujeme stejný počet částic. Pro tyto nové částice vytvoříme opět váhy na základě známých pozorování – ty částice, které se více podobají pozorované „realitě“ budou mít větší váhu. Při správné volbě parametrů (model soustavy a měření a jejich neurčitosti...) budou mít particly tendenci se (po větším počtu kroků s použitým pozorováním/měřením) seskupit kolem nejlepšího/nejlepších řešení. Provedeme-li pro každý shluk výpočet například střední hodnoty, máme předpokládanmou polohu hledaného řešení.

Představme si situaci, kdy máme plochu se stěnami (například výstavní sál rozdělený příčkami, jehož mapu známe) a robota, který „zná“ pouze dva způsoby měření: ví jak daleko je nejbližší objekt (stěna) a ví o jakou vzdálenost se pohnul od minulého měření, nezná však směr.

Postup by mohl být asi takový:
1) náhodně se vygenerují polohy robota v mapě (tento krok by mohl být nahrazen tím, že se změří vzdálenost od nejbižší překážky a na jejím základě se budou generovat polohy (v dané vzdálenosti od stěn s nějakou tolerancí).
2) Na základě znalostí pohybu robota (za daný čas se posune o určitou vzdálenost libovolným směrem s jistou tolerancí) se provede posun všech simulovaných bodů (na základě náhodných čísel). Body se vybírají náhodně a ty, které více dpovídají minulému měření mají větší pravděpodobnost, že budou použity (to znamená, že body daleko od měření nebudou použity, zatímco body blíže měření budou použity vícekrát).
3) Provede se měření vzdálenosti. Na základě změřené hodnoty se přiřadí váhy simulovaným bodům – body které odpovídají naměřeným hodnotám budou mít větší váhu.
4) Pokračuje se v bodu 2.

Je zřejmé, že po určitém počtu iterací se simulované „částečky“ „shluknou“ v místě, které odpovídá pravděpodobné poloze robota, a že v tomto odhadu je zahrnuta i historie, i když ze samé podstaty algoritmu plyne, že řešení každého kroku je samostatné (měření -> váhování -> posun).

Tento princip umožňuje i sledování více objektů. Důležité je „naladit“ algoritmy tak, aby jeden z objektů simulaci „neutekl“ v tom případě si všechny „částečky“ „stáhnou“ ostatní objekty a tento objekt by byl ztracen až do doby, kdy by se přiblížil k objektu jinému od něhož by si částečky opět odebral.

První obrázek ukazuje scénu/místnost ve které je sloup. Prvotní náhled je (body v obrázku), že nevíme kde se nacházíme, a proto částice mohou být kdekoli.

Následující obrázek ukazuje výsledek po provedení dvou měření. První zjišťuje jak daleko jsme od zdi, druhé, jak daleko jsme od sloupu. Výsledkem jsou oblasti, ve kterých budou particly „zvýhodněny“. Šírky oblastí jsou dány přesností měření

Poslední úpravy 2009-09-11