Data-driven Reachable Set Estimation with Tunable Adversarial and Wasserstein Distributional Guarantees

1. Problema e Contesto

Il lavoro si concentra sulla stima degli insiemi raggiungibili (reachable sets) per sistemi dinamici discreti a tempo con dinamiche sconosciute. L'obiettivo è inferire l'insieme di tutti gli stati che un sistema può raggiungere entro un orizzonte temporale finito, basandosi esclusivamente su un numero limitato di traiettorie di stato campionate (dati sperimentali o simulati).

Le sfide principali affrontate sono tre, spesso non risolte simultaneamente nella letteratura esistente:

1. Trade-off regolabile: La necessità di bilanciare la "grandezza" dell'insieme raggiunto (che deve essere il più piccolo possibile per essere utile) con la sua affidabilità (garantire che includa le traiettorie future).
2. Robustezza ai dati perturbati: La capacità di gestire dati di addestramento contaminati da rumore o attacchi avversariali (perturbazioni limitate).
3. Robustezza distribuzionale: La garanzia che le prestazioni teoriche non collassino se la distribuzione dei dati di test (deployment) si discosta da quella di addestramento, misurata tramite la distanza di Wasserstein.

2. Metodologia Proposta

Gli autori propongono un quadro unificato basato sull'approccio scenario (scenario optimization), esteso per includere variabili di rilassamento e robustezza avversariale.

A. Formulazione del Programma Scenario Rilassato

Invece di trattare le traiettorie osservate come verità assoluta con vincoli rigidi, il metodo introduce variabili di rilassamento ($\xi_i$) per ogni traiettoria campionata.
Il problema di ottimizzazione ($P_{N,\rho}$) minimizza una funzione obiettivo composta da:

• Una misura della "grandezza" dell'insieme raggiungibile (es. volume, raggio, fattori di scala).
• Una penalità lineare sulle variabili di rilassamento, ponderata da un parametro $\rho$.

I vincoli richiedono che le traiettorie campionate (o le loro versioni perturbate) siano contenute nell'insieme, permettendo una violazione controllata ($\xi_i$) a costo di un aumento della funzione obiettivo.

• Ruolo di $\rho$: Agisce come iperparametro di sintonizzazione. Un $\rho$ alto penalizza le violazioni, forzando un insieme più grande ma più robusto (maggior inclusione di traiettorie future). Un $\rho$ basso favorisce insiemi più piccoli ma più rischiosi.

B. Robustezza Avversariale

Per gestire dati perturbati (rumore o attacchi), il metodo assume che ogni traiettoria campionata $x^{(i)}$ possa subire perturbazioni limitate all'interno di un insieme $\mathcal{A}_{x^{(i)}}$ (definito da una metrica, es. norma-$p$).
Il problema viene riformulato come un programma robusto ($\hat{P}_{N,\rho,A}$), dove i vincoli devono essere soddisfatti per tutte le possibili perturbazioni all'interno dell'insieme avversariale. Questo porta a una formulazione che considera i vertici di approssimazioni poliopiche degli insiemi di perturbazione.

C. Garanzie Probabilistiche e Complessità Avversariale

Utilizzando risultati recenti sull'ottimizzazione scenario robusta, gli autori definiscono la complessità avversariale ($s^*_A$), che conta il numero di traiettorie "critiche" che determinano i confini dell'insieme.

• Teorema 1: Fornisce un limite probabilistico a posteriori sulla probabilità di esclusione di una nuova traiettoria (violazione). Il limite dipende dal numero di campioni $N$, dal livello di confidenza $\beta$ e dalla complessità avversariale $s^*_A$.
• Teorema 2 (Robustezza Distribuzionale): Estende il risultato al caso in cui la distribuzione dei dati di test si sposti all'interno di una palla di Wasserstein di raggio $\tilde{\mu}$ rispetto alla distribuzione di addestramento. Il limite di violazione aumenta linearmente con il rapporto tra il raggio di Wasserstein e il raggio della perturbazione avversariale.

D. Riformulazioni Convessità

Per rendere il problema computazionalmente trattabile, il paper deriva riformulazioni convesse per diverse geometrie degli insiemi:

• Palle $p$-norme: Minimizzazione del raggio.
• Ellissoidi: Minimizzazione del determinante (o log-determinante) della matrice di forma.
• Zonotopi: Minimizzazione della somma delle semilarghezze.
  Tutte le riformulazioni risultano essere problemi di ottimizzazione convessa risolvibili efficientemente.

3. Contributi Chiave

1. Framework Unificato con Trade-off Tunable: Introduce l'uso di variabili di rilassamento nell'ottimizzazione scenario per la stima degli insiemi raggiungibili, permettendo un controllo esplicito tra la compattezza dell'insieme e la garanzia di inclusione futura.
2. Robustezza Avversariale Integrata: Estende l'approccio scenario per gestire perturbazioni limitate sui dati di addestramento, derivando garanzie probabilistiche valide anche in presenza di dati "avvelenati" o rumorosi.
3. Garanzie di Robustezza Distribuzionale (Wasserstein): Fornisce un limite esplicito su come degradano le garanzie probabilistiche quando la distribuzione dei dati di deployment si sposta, offrendo una metrica di sicurezza per scenari di non-stazionarietà.
4. Riformulazioni Pratiche: Dimostra come applicare il framework a geometrie comuni (palle, ellissoidi, zonotopi) ottenendo problemi convessi risolvibili.

4. Risultati Sperimentali

Le simulazioni sono state condotte su un sistema dinamico stocastico non lineare (con funzione $\tanh$) su un orizzonte temporale di 25 passi.

• Geometrie Confrontate: Sono stati testati insiemi basati su palle euclidee, ellissoidi e zonotopi.
• Effetto di $\rho$: I risultati mostrano che all'aumentare di $\rho$, la dimensione degli insiemi cresce, migliorando la copertura delle traiettorie (inclusione) a scapito della compattezza.
• Confronto Teoria vs Empiria: Le probabilità empiriche di violazione (su un set di test) sono rimaste sempre al di sotto dei limiti teorici calcolati, confermando la validità delle garanzie.
• Robustezza Distribuzionale: In esperimenti con distribuzione di test spostata (cambiamento di media e varianza), il limite teorico derivato dal Teorema 2 ha correttamente delimitato la violazione empirica, dimostrando la resilienza del metodo agli shift distribuzionali.
• Efficienza: Gli zonotopi, pur richiedendo più campioni per ottenere le stesse garanzie teoriche rispetto a palle ed ellissoidi, hanno prodotto regioni stimate più strette (meno conservative).

5. Significato e Impatto

Questo lavoro rappresenta un passo significativo verso l'applicazione pratica della verifica di sicurezza nei sistemi dinamici basati sui dati.

• Superamento del "Black-Box": Trasforma l'ottimizzazione scenario da uno strumento teorico in un metodo ingegnerizzabile con parametri sintonizzabili ($\rho$) per bilanciare sicurezza e prestazioni.
• Sicurezza Reale: Affronta direttamente le preoccupazioni sulla qualità dei dati (rumore, attacchi) e sulla non stazionarietà dell'ambiente (shift distribuzionale), aspetti critici per il controllo autonomo e la robotica.
• Fondamento Teorico Solido: Fornisce garanzie probabilistiche rigorose che non dipendono da assunzioni forti sulla conoscenza del modello, rendendo il metodo applicabile a sistemi complessi e parzialmente noti.

In sintesi, il paper offre un metodo robusto, flessibile e teoricamente garantito per costruire "scatole di sicurezza" attorno alle traiettorie di sistemi sconosciuti, essenziale per la progettazione di controllori sicuri in ambienti incerti.