L’algoritmo Particle Filter: la ricerca al buio.

L’algoritmo Particle Filter: la ricerca al buio.

Immagina di essere in una stanza buia e di dover trovare un gatto che si muove senza fare rumore. Non puoi vederlo, ma hai una torcia che illumina solo una piccola parte della stanza alla volta. Allora, cosa fai?

Inizi ad accendere e spegnere la torcia in posti diversi della stanza, cercando di indovinare dove potrebbe essere il gatto.

Ogni volta che accendi la torcia, fai una supposizione: “Potrebbe essere qui?“.

Il Filtro a Particelle funziona più o meno così. Invece di cercare un gatto in una stanza, cerca di indovinare, per esempio, dove si trova un robot in un edificio. Usa tante “mini-torce” (che sono come piccole supposizioni o indizi) per fare tante ipotesi su dove possa essere. Alcune di queste ipotesi saranno giuste, altre no.

Man mano che il robot si muove, il Filtro a Particelle aggiorna le sue ipotesi, eliminando quelle sbagliate (come quando realizzi che il gatto non è in un certo angolo della stanza) e concentrandosi su quelle più probabili (come quando senti il miagolio del gatto da un certo punto della stanza). Così, anche se all’inizio non sai dove si trova il robot, usando questi indizi e aggiornando le supposizioni, puoi farti un’idea sempre più precisa della sua posizione.

L’algoritmo del filtro a particelle, noto anche come Particle Filter, trova applicazioni in diversi campi grazie alla sua capacità di stimare e tracciare un insieme di ipotesi multiple in sistemi dinamici non lineari e non gaussiani, a differenza dell’algoritmo di Kalman che è più adatto al tracciamento in sistemi lineari. (Leggi l’articolo sul filtro di Kalman)

Applicazioni

Uno degli usi più noti del filtro a particelle è, come abbiamo già anticipato, nella localizzazione dei robot, specialmente in ambienti sconosciuti o complessi. Il filtro aiuta i robot a determinare la loro posizione esatta utilizzando varie misure sensoriali.

Nel campo della visione artificiale, il filtro delle particelle è utilizzato per tracciare il movimento di oggetti. Questo può essere applicato dalla sorveglianza alla tracciatura di oggetti in video sportivi.

Il filtro a particelle è spesso impiegato per fondere dati provenienti da diversi sensori. Per esempio, in un veicolo autonomo, può combinare dati da GPS, lidar e radar per migliorare l’accuratezza della localizzazione del veicolo.

In finanza, è usato per modellare e prevedere i movimenti dei prezzi degli asset. Aiuta ad adattarsi a modelli finanziari non lineari e a cambiamenti imprevisti del mercato.

In ingegneria del controllo, può essere utilizzato per ottimizzare e controllare processi dinamici complessi, come quelli in impianti chimici o sistemi di energia.

Nelle scienze della vita, il filtro a particelle è applicato nella modellazione di sistemi biologici complessi e nella stima di parametri incogniti in modelli biochimici.

Nelle telecomunicazioni, è usato per decodificare segnali in ambienti rumorosi o per tracciare canali di comunicazione variabili nel tempo.

Come funziona nel dettaglio?

Immagina di giocare a nascondino in un parco grande e pieno di posti dove nascondersi. Ora, invece di cercare direttamente la persona nascosta, usi un gruppo di robot piccoli per aiutarti a trovarla.

Inizializzazione: All’inizio, distribuisci tutti i tuoi piccoli robot (le particelle) nel parco in posti casuali. Non sai ancora dove sia la persona, quindi i robot partono da punti diversi.

Ciclo Iterativo: Ora, comincia la vera ricerca.
Aggiornamento delle Particelle: Ogni volta che senti un rumore o ricevi un indizio, fai muovere i robot in quella direzione. Questo è come aggiustare le tue supposizioni su dove potrebbe essere la persona.

Calcolo dei Pesi: Poi, decidi quanto ogni robot sia vicino alla persona nascosta, basandoti sugli indizi. I robot più vicini all’indizio ricevuto avranno un “peso” maggiore, cioè sembreranno più importanti.

Normalizzazione dei Pesi: Assicurati che la somma dei pesi dei robot sia sempre 1. È come bilanciare le possibilità.

Resampling: Scegli alcuni robot basandoti sui loro pesi. I robot con pesi maggiori hanno più probabilità di essere scelti, perché pensi che siano più vicini alla persona nascosta.

Aggiornamento dell’Insieme di Particelle: Sostituisci i robot vecchi con quelli appena scelti.

Stima dello Stato: Infine, fai una stima di dove potrebbe essere la persona nascosta, guardando dove si trovano i robot ora.

Uscita: Alla fine del gioco, fai l’ultima supposizione su dove si trova la persona nascosta, basandoti sulla posizione dei robot.

Ecco uno schema molto semplificato:

Approfondimenti matematici

Le eseguenti formule catturano l’essenza matematica del filtro a particelle, evidenziando come le particelle vengono aggiornate e utilizzate per stimare lo stato di un sistema in presenza di incertezza.

Ulteriori approfondimenti:
Filtraggio e stima dello stato nei sistemi dinamici
non lineari (tesi di laurea)

Codice Python d’esempio (In un caso reale la variabile misurazione assume appunto il valore del risultato di una misurazione da parte dei sensori. Nell’esempio assume valori casuali)


import numpy as np

# Numero di particelle
num_particelle = 1000

# Stato iniziale e particelle iniziali
stato_vero = 0.0
particelle = np.random.normal(0, 1, num_particelle)

# Funzione per l'aggiornamento del filtro a particelle
def filtro_particelle(z, particelle):
    rumore_misurazione = 0.5**2
    # Movimento delle particelle (qui assumiamo un movimento casuale)
    particelle += np.random.normal(0, 0.5, num_particelle)

    # Peso delle particelle basato sulla misurazione
    pesi = np.exp(-((z - particelle) ** 2) / rumore_misurazione)
    pesi /= np.sum(pesi)

    # Resampling
    indici = np.random.choice(range(num_particelle), num_particelle, p=pesi)
    particelle = particelle[indici]

    return np.mean(particelle), particelle

# Esempio di esecuzione
rumore_misurazione = 0.5**2
for _ in range(10):
    misurazione = np.random.normal(stato_vero, np.sqrt(rumore_misurazione))
    stima, particelle = filtro_particelle(misurazione, particelle)
    print(f"Stima attuale dello stato: {stima}")

Schema dell’Algoritmo del Filtro a Particelle

Inizializzazione
Definire il Numero di Particelle: Impostare num_particelle, il numero totale di particelle da utilizzare.
Generare Particelle Iniziali: Creare l’insieme iniziale di particelle, tipicamente distribuite casualmente. Per esempio, particelle = np.random.normal(0, 1, num_particelle).

Ciclo Iterativo

Per Ogni Misurazione Ricevuta:


Aggiornare le Particelle:
Simulare il movimento o la transizione delle particelle. Ad esempio, aggiungendo un movimento casuale: particelle += np.random.normal(0, 0.5, num_particelle).

Calcolare i Pesi:
Assegnare un peso a ciascuna particella basandosi sulla misurazione ricevuta. I pesi riflettono la probabilità che ciascuna particella rappresenti accuratamente lo stato reale.
Per esempio: pesi = np.exp(-((misurazione – particelle) ** 2) / rumore_misurazione).

Normalizzare i Pesi:
Assicurarsi che la somma dei pesi sia uguale a 1: pesi /= np.sum(pesi).

Resampling:
Selezionare un nuovo insieme di particelle basandosi sui pesi. Particelle con pesi maggiori sono più probabili di essere scelte, Per esempio: indici = np.random.choice(range(num_particelle), num_particelle, p=pesi).

Aggiornare l’Insieme di Particelle:
Aggiornare l’insieme di particelle basandosi sui risultati del resampling: particelle = particelle[indici].

Stimare lo Stato:
Calcolare una stima dello stato, ad esempio, prendendo la media delle particelle: stima = np.mean(particelle).

Restituzione della Stima dello Stato

Alla fine del ciclo iterativo, restituire la stima corrente dello stato del sistema.

In ogni iterazione, le particelle vengono aggiornate per riflettere le nuove informazioni ricevute dalle misurazioni, e la stima dello stato del sistema viene continuamente raffinata.