Approximating Analytically-Intractable Likelihood Densities with Deterministic Arithmetic for Optimal Particle Filtering

1. Il Problema

I filtri particellari (Particle Filters - PF) sono diventati lo standard per la stima dello stato in tempo reale di sistemi non lineari e non gaussiani, trovando applicazione in robotica autonoma, tracciamento di bersagli ed econometria. Tuttavia, questi algoritmi presentano una debolezza intrinseca: la necessità di calcolare esplicitamente la densità di verosimiglianza (likelihood) delle osservazioni.

In molti scenari reali (sistemi ricchi di sensori, modelli dinamici complessi), la funzione di verosimiglianza è:

• Analiticamente intrattabile: Non esiste una soluzione chiusa per l'integrazione necessaria a calcolare la probabilità predittiva.
• Costosa da calcolare: Richiede risorse computazionali elevate, inadatte a sistemi embedded con vincoli di potenza e latenza.
• Soggetta a degenerazione: I metodi tradizionali, come la simulazione Monte Carlo (MC) per approssimare l'integrale, introducono variabilità stocastica. In particolare, per modelli con incertezza di misura stretta (uniforme), il metodo MC fallisce frequentemente nel campionare la regione di supporto della distribuzione, assegnando erroneamente una verosimiglianza zero (fenomeno noto come "likelihood collapse"), il che porta al collasso del filtro.

2. Metodologia Proposta

Gli autori introducono un nuovo approccio per l'implementazione del filtro particellare che sostituisce il campionamento stocastico con aritmetica deterministica su distribuzioni di probabilità.

Il Nucleo: UxHw (Uncertainty-extended Hardware)

Il metodo si basa su una piattaforma hardware recente (UxHw) capace di eseguire operazioni aritmetiche direttamente su rappresentazioni digitali di funzioni di densità di probabilità (PDF), senza ricorrere a metodi stocastici.

• Concetto Chiave: Invece di campionare singoli punti rumorosi e valutare la densità (come fa il Monte Carlo), l'approccio UxHw propaga l'intera distribuzione dell'incertezza attraverso i modelli di transizione e osservazione.
• Implementazione:
  1. Il modello di transizione $f$ prende lo stato precedente e la distribuzione del rumore di transizione, producendo una distribuzione predittiva dello stato futuro.
  2. Questa distribuzione viene passata al modello di osservazione $h$, insieme alla distribuzione del rumore di osservazione, generando una distribuzione predittiva dell'osservazione.
  3. La densità di questa distribuzione predittiva viene valutata direttamente nel punto della misura reale $z_k$ per ottenere la verosimiglianza.
• Vantaggio Computazionale: Questo processo è deterministico, offre garanzie temporali prevedibili (cruciali per sistemi real-time) e utilizza trasformazioni Turing-complete su variabili casuali scritte in sintassi di linguaggio di programmazione convenzionale.

Integrazione nel Filtro

Il metodo è stato applicato specificamente al Filtro Particellare Ausiliario con "Lookahead" Predittivo (Predictive-Lookahead Auxiliary Particle Filter). Invece di valutare la verosimiglianza su una singola previsione puntuale, il metodo calcola la verosimiglianza predittiva $p(z_k | x_{k-1})$ integrando l'incertezza di transizione e osservazione, migliorando la robustezza del filtro.

3. Contributi Chiave

1. Approccio Approssimativo Tunabile: Un metodo per calcolare verosimiglianze da densità arbitrarie utilizzando trasformazioni su variabili casuali. Offre un compromesso tra velocità e fedeltà della distribuzione controllabile tramite un parametro di configurazione ($\eta$).
2. Validazione Sperimentale Estensiva: Confronto su 294.840 punti di valutazione su 540 configurazioni di sistema (combinando rumore Gaussiano, Laplaciano e Uniforme) utilizzando il sistema di riferimento di Gordon–Salmond–Smith.
3. Dimostrazione di Superiorità: Prove che l'approccio UxHw supera i metodi Monte Carlo sia in termini di velocità che di accuratezza in scenari non lineari e non gaussiani.

4. Risultati Sperimentali

I test sono stati condotti su un FPGA (FPGA-17k) che ospita un processore RISC-V con supporto nativo per il tracciamento dell'incertezza.

• Velocità (Speedup):

  • Rispetto a un approccio Monte Carlo con la stessa accuratezza (99% di confidenza), il metodo UxHw ha mostrato un speedup fino a 37.7 volte (configurazione UxHw $\eta=8$ contro 701 iterazioni MC).
  • Anche con configurazioni più precise ($\eta=64$), lo speedup rimane significativo (7.9x contro 11.046 iterazioni MC).

• Accuratezza (RMSE):

  • Rispetto a un approccio Monte Carlo con lo stesso tempo di esecuzione, UxHw ha migliorato l'errore quadratico medio (RMSE) in media del 3.3%, con picchi fino al 18.9% (con 600 particelle e $\eta=8$).
  • L'approccio UxHw utilizza le particelle in modo più efficiente, aumentando la dimensione del campione effettivo (ESS).

• Robustezza (Likelihood Collapse):

  • Questo è il risultato più critico. Per modelli con incertezza di misura stretta (uniforme), il filtro Monte Carlo assegna erroneamente una verosimiglianza zero fino all'81.89% delle volte (con 20 iterazioni), portando al collasso del filtro.
  • L'approccio UxHw riduce drasticamente questo tasso di errore, con un tasso di "falso zero" di soli 1.52% (configurazione UxHw 8).
  • Di conseguenza, il tasso di collasso della distribuzione dei pesi del filtro è ridotto di circa 2 punti percentuali, migliorando la stabilità a lungo termine.

5. Significato e Impatto

Questo lavoro rappresenta un passo avanti significativo per l'elaborazione di segnali in sistemi embedded con risorse limitate:

• Superamento dei limiti del Monte Carlo: Dimostra che è possibile eseguire inferenza bayesiana complessa su modelli non lineari/non gaussiani senza la variabilità e l'instabilità dei metodi stocastici.
• Real-Time Guaranteed: L'uso di aritmetica deterministica su hardware dedicato (UxHw) garantisce tempi di esecuzione prevedibili, rendendo fattibile l'uso di modelli di verosimiglianza potenti in applicazioni critiche come la guida autonoma e i droni.
• Nuovo Paradigma Hardware-Software: Introduce l'idea di trattare le distribuzioni di probabilità come tipi di dati nativi eseguibili direttamente sull'hardware, semplificando la modellazione fisica dei sensori e riducendo la complessità algoritmica per gli sviluppatori.

In sintesi, il paper propone una soluzione hardware-software co-design che risolve il collo di bottiglia computazionale e di stabilità dei filtri particellari moderni, rendendo possibili sistemi di stima dello stato più precisi, robusti e veloci.