Particle Filter

Detto anche: sequential Monte Carlo, SMC, bootstrap filter
Categoria: State estimation & navigation › Localisation
Tag: state-estimation, localization, bayesian-filtering, probabilistic-robotics, monte-carlo

Un metodo di stima dello stato che rappresenta una credenza come un insieme di campioni pesati, spostandoli con un modello di moto, pesandoli in base alla verosimiglianza del sensore e ricampionandoli.

Definizione

Filtro a particelle (particle filter) è uno stimatore bayesiano ricorsivo che rappresenta la distribuzione di probabilità sullo stato di un sistema con un insieme di campioni, chiamati particelle, ciascuno con un peso. L'approccio è noto anche come Monte Carlo sequenziale (sequential Monte Carlo); la sua forma più citata, il filtro bootstrap, è stata pubblicata da Gordon, Salmond e Smith nel 1993. In robotica è diventato uno standard grazie alla localizzazione Monte Carlo (Monte Carlo localization), sviluppata da Dellaert, Fox, Burgard e Thrun, ed è trattato in modo approfondito in Probabilistic Robotics.

Ogni aggiornamento ha tre passi. Nel passo di predizione, ogni particella viene spostata secondo il modello di moto, con rumore aggiunto per riflettere l'incertezza dell'odometria o del controllo. Nel passo di aggiornamento, ogni particella riceve un peso in base a quanto l'ultima misura del sensore concorda con lo stato che rappresenta. Nel passo di ricampionamento, si estrae un nuovo insieme di particelle in proporzione ai pesi, così che le ipotesi probabili vengano duplicate e quelle improbabili scompaiano. La stima si può leggere dalla media pesata, dalla particella migliore o da un cluster di particelle.

A differenza del filtro di Kalman e delle sue estensioni, un filtro a particelle non presuppone che la credenza sia gaussiana. Può mantenere più ipotesi separate contemporaneamente, come un robot che potrebbe trovarsi in uno di due corridoi identici, o un oggetto tenuto in mano che potrebbe essere in diverse pose compatibili con i contatti percepiti fino a quel momento. Il costo è computazionale: il numero di particelle necessarie cresce rapidamente con la dimensione dello stato, e se troppo poche particelle cadono vicino allo stato reale il filtro può collassare su una risposta sbagliata. I filtri pratici usano quindi il ricampionamento a bassa varianza, ricampionano solo quando la dimensione effettiva del campione cala, adattano il numero di particelle e iniettano particelle casuali per riprendersi dai fallimenti.

Perché è importante

Molti problemi di stima in robotica sono non lineari e ambigui, con credenze che hanno più picchi anziché uno solo. Il filtro a particelle li gestisce direttamente, ed è per questo che è alla base della localizzazione 2D standard sui robot mobili e uno strumento comune per stimare la posa di un oggetto dal contatto e dal tatto.

Applicazioni principali

Localizzazione di robot mobili rispetto a una mappa nota (localizzazione Monte Carlo)
Stima della posa di un oggetto in mano dalla propriocezione e dal contatto tattile
Tracciamento di persone e oggetti in scene ingombre o con occlusioni
SLAM con filtri a particelle Rao–Blackwellizzati come FastSLAM e GMapping
Localizzazione globale e recupero quando un robot viene spostato a sua insaputa

In pratica

Un robot da magazzino che usa lo stack di navigazione di ROS di solito si localizza con AMCL, un pacchetto di localizzazione Monte Carlo adattiva. All'avvio l'operatore fornisce una posa iniziale approssimativa, e qualche migliaio di particelle viene distribuito intorno a essa. Mentre il robot si muove, l'odometria delle ruote sposta le particelle e ogni scansione lidar le ripesa rispetto alla mappa di occupazione memorizzata; la nuvola si stringe attorno alla posa reale nel giro di pochi metri di percorso. Gli ingegneri regolano i parametri di rumore dell'odometria per farli corrispondere alla trasmissione reale, impostano il numero minimo e massimo di particelle e osservano la nuvola di particelle in RViz: una nuvola che si divide in due cluster in una corsia ripetitiva è segno che il filtro sta seguendo due ipotesi e ha bisogno di un elemento distintivo per risolverle.

Idee sbagliate comuni

Più particelle risolvono sempre i problemi di accuratezza — il numero di particelle necessarie cresce rapidamente con la dimensione dello stato, quindi i problemi ad alta dimensione richiedono distribuzioni di proposta migliori o più struttura, non solo più campioni
Un filtro a particelle è solo un filtro di Kalman più lento — rappresenta credenze non gaussiane e con più picchi che i filtri di tipo Kalman non possono rappresentare
Ricampionare a ogni passo è sempre la scelta migliore — ricampionare troppo spesso elimina diversità; molti filtri ricampionano solo quando la dimensione effettiva del campione scende sotto una soglia
Il filtro si riprenderà sempre da una stima sbagliata — una volta che le particelle sono collassate lontano dallo stato reale non possono tornare indietro, a meno che non si iniettino particelle casuali

Chi dovrebbe saperlo

Ingegneri di localizzazione e navigazione di robot mobili
Sviluppatori di stima dello stato e SLAM
Ricercatori di manipolazione che stimano la posa degli oggetti tramite il tatto
Studenti di robotica che studiano la robotica probabilistica

Tecnologie correlate

Localizzazione Monte Carlo (Monte Carlo Localization, AMCL)
Filtro di Kalman (Kalman Filter)
FastSLAM
Campionamento per importanza (Importance Sampling)
Mappa a griglia di occupazione (Occupancy Grid Map)

Termini correlati

Progetti correlati

Cartographer: Google's real-time 2D and 3D SLAM system for multi-platform robotics
Nav2: ROS 2 navigation stack with path planning and obstacle avoidance for mobile robots
GTSAM: Factor-graph optimization library powering many modern SLAM backends
OpenVINS: The reference open platform for visual-inertial state estimation research
AprilTag: The standard visual fiducial marker system for robot localization and pose estimation
GLIM: GPU-accelerated 3D lidar SLAM framework for any range sensor, from AIST

Video

Understanding the Particle Filter | | Autonomous Navigation, Part 2: MATLAB
Particle Filter - 5 Minutes with Cyrill: Cyrill Stachniss