Maximizing Reach-Avoid Probabilities for Linear Stochastic Systems via Control Architectures

Sintesi Tecnica: Massimizzazione delle Probabilità di Reach-Avoid per Sistemi Lineari Stocastici tramite Architetture di Controllo

Formulazione del Problema
Il documento affronta la sfida di massimizzare la probabilità di reach-avoid (raggiungimento-evitamento) per sistemi lineari stocastici su un orizzonte temporale finito. Il sistema è definito da dinamiche che contengono sia stati che evolvono deterministicamente ($x_d$) sia stati che evolvono probabilisticamente ($x_s$), soggetti a rumore i.i.d. additivo. L'obiettivo di controllo è trovare una politica che massimizzi la probabilità che il sistema raggiunga un insieme target $T$ rimanendo al contempo all'interno di un insieme sicuro $S$ per una durata $[0, T]$, il tutto soddisfacendo i vincoli deterministici $G$ (come i limiti di input e i limiti di stato) in ogni momento.

I metodi esistenti affrontano un compromesso: gli approcci basati su limiti statistici (ad esempio, stochastic tubes, scenario MPC) offrono scalabilità ma spesso producono prestazioni conservative, mentre i metodi di ottimizzazione diretta (ad esempio, i Processi Decisionali di Markov - MDP) forniscono garanzie precise ma sono computazionalmente intrattabili per spazi di stato ad alta dimensionalità o continui.

Metodologia
Gli autori propongono un'architettura di controllo a strati che combina la scalabilità del Controllo Predittivo del Modello (MPC) con l'ottimalità della Programmazione Dinamica (DP). L'innovazione principale risiede nel trattare il sistema a ciclo chiuso (pianta + MPC) come un Processo Decisionale di Markov (MDP) in cui le "azioni" sono segnali di riferimento inviati all'MPC, piuttosto che input di controllo diretti.

1. Architettura a Strati:

   • Strato Inferiore (MPC): Un controllore MPC traccia i segnali di riferimento generati dallo strato superiore. L'MPC è progettato per essere agnostico rispetto all'obiettivo di reach-avoid stocastico; il suo unico scopo è garantire che il sistema soddisfi i vincoli deterministici $G$ e i limiti di input $U$. Per colmare il divario tra l'ottimizzazione MPC in tempo discreto e la soddisfazione dei vincoli in tempo continuo, gli autori derivano tecniche di restringimento dei vincoli (Lemma III.1) che tengono conto della dinamica del sistema e del rumore durante l'intervallo di campionamento.
   • Strato Superiore (Generatore di Riferimento DP): Una politica basata su DP opera a intervalli temporali fissi ($\Delta t$). Essa seleziona sequenze di riferimento (comandi) per l'MPC al fine di massimizzare la probabilità di raggiungere il target evitando al contempo le regioni non sicure. Lo spazio degli stati di questo MDP è lo stato del sistema $x_k$, e lo spazio delle azioni consiste in un insieme finito di traiettorie di riferimento.

2. Gestione degli Spazi di Stato Continui e Astrazione:
   Poiché lo spazio degli stati è continuo, gli autori impiegano un'astrazione basata su una griglia finita per rendere la DP computazionalmente trattabile. Per garantire che le garanzie teoriche siano preservate nonostante questa discretizzazione, introducono un framework di robustizzazione:

   • MPC Robusto (RMPC): L'MPC viene modificato per generare sequenze di input che siano invarianti rispetto allo specifico stato iniziale all'interno di una cella della griglia (partizione). Ciò si ottiene inizializzando la predizione dell'MPC dal centro della cella anziché dallo stato misurato, garantendo che la stessa sequenza di controllo venga applicata a tutti gli stati all'interno di una partizione.
   • Iterazione del Valore Robusta: Gli insiemi sicuri e target vengono ristretti di un raggio $r$ (derivato dalla massima deviazione delle traiettorie entro un passo temporale) per tenere conto degli errori di astrazione. L'algoritmo DP viene modificato per calcolare un limite inferiore sulla probabilità di reach-avoid considerando le transizioni peggiore caso all'interno del vicinato di ogni cella della griglia.

Contributi Chiave

• Architettura di Controllo: Il documento introduce un'architettura innovativa che riduce la dimensionalità dello spazio di pianificazione della DP dalla dimensione completa dello stato $n$ alla dimensione della componente che evolve probabilisticamente $n_s$. Ciò viene ottenuto sfruttando l'evoluzione deterministica di $x_d$ e le capacità di inseguimento dell'MPC.
• Garanzie Teoriche: Gli autori forniscono certificati formali per l'approccio. Dimostrano che l'architettura robustizzata garantisce la soddisfazione dei vincoli in tempo continuo e che il valore calcolato dall'algoritmo DP robusto funge da limite inferiore rigoroso sulla reale probabilità di reach-avoid ottenuta dal sistema (Teorema IV.4).
• Scalabilità e Flessibilità: Il metodo è stato dimostrato scalabile per sistemi ad alta dimensionalità (specificamente un modello di quadricottero a 12D) e sufficientemente flessibile da gestire ambienti complessi e ingombri.

Risultati
L'approccio è stato validato su un modello di quadricottero a 12D perturbato che naviga in vari ambienti ingombri (ad esempio, labirinti, percorsi a zigzag e campi di ostacoli).

• Prestazioni: In uno scenario di labirinto, l'architettura ha raggiunto un tasso di successo del 40%, superando significativamente i baselines conservativi.
• Confronto: In molteplici scenari, la probabilità empirica di reach-avoid ($V_0(x_0)$) ha costantemente eguagliato o superato il limite inferiore calcolato dall'iterazione del valore robusta ($\tilde{V}_0(x_0)$), validando le garanzie teoriche. Ad esempio, in un ambiente "zigzag", il tasso di successo empirico è stato del 44% rispetto a un limite inferiore teorico dello 0,3%.
• Compromessi: Il documento dimostra anche la capacità dell'architettura di risolvere problemi di controllo ottimo vincolati. Regolando un moltiplicatore di Lagrange, il sistema può scambiare il costo del percorso (mantenere la traiettoria vicina a un centro) con la probabilità di reach-avoid, generando una frontiera di Pareto di soluzioni.

Significatività e Rivendicazioni
Il documento sostiene che questo lavoro colma il divario tra l'ottimalità teorica dei metodi basati su MDP e la scalabilità pratica dell'MPC. Decoupling (disaccoppiando) l'applicazione della sicurezza (gestita dall'MPC robusto) dall'ottimizzazione probabilistica (gestita dal generatore di riferimento DP), gli autori ottengono una strategia di controllo che è sia computazionalmente fattibile per sistemi ad alta dimensionalità, sia capace di fornire certificati formali di reach-avoid senza ricorrere a eccessivamente conservativi limiti statistici. Gli autori sottolineano che il loro metodo fornisce certificati formali per sistemi stocastici, una caratteristica spesso assente negli approcci euristici scalabili, evitando al contempo l'intrattabilità computazionale delle soluzioni MDP a stato completo.