⚡ electrical engineering

Computing Sound Lower and Upper Bounds on Hamilton-Jacobi Reach-Avoid Value Functions

Questo articolo presenta un algoritmo che calcola limiti superiori e inferiori rigorosi per le funzioni valore dell'analisi di raggiungibilità Hamilton-Jacobi, garantendo sovrastime e sottostime sicure degli insiemi raggiungibili e introducendo un metodo di raffinamento per migliorare la precisione della griglia.

Autori originali: Ihab Tabbara, Eliya Badr, Hussein Sibai

Pubblicato 2026-03-31

📖 4 min di lettura☕ Lettura da pausa caffè

CC BY 4.0

Autori originali: Ihab Tabbara, Eliya Badr, Hussein Sibai

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immagina di dover insegnare a un'auto a guida autonoma o a un robot chirurgico come muoversi in un ambiente pieno di ostacoli, senza mai sbattere contro nulla e arrivando sempre a destinazione. Il problema è che il mondo reale è continuo (puoi essere ovunque, non solo su una griglia di punti fissi) e le leggi della fisica sono complicate.

Gli scienziati usano una tecnica matematica chiamata Analisi di Raggiungibilità di Hamilton-Jacobi (HJ) per risolvere questo problema. È come se volessimo disegnare una mappa perfetta che ci dica: "Da qui puoi arrivare alla meta in sicurezza" (zona verde) oppure "Da qui, anche se guidi alla perfezione, finirai per sbattere" (zona rossa).

Il problema con i metodi attuali è che, per fare i calcoli, devono trasformare il mondo continuo in una griglia di quadratini (come un pixel art). Questo crea due errori:

Errori di approssimazione: I quadratini sono grossolani, quindi la mappa potrebbe dire che sei al sicuro quando in realtà sei troppo vicino al bordo.
Mancanza di certezza: Non sono sicuri al 100% che la loro mappa non stia nascondendo pericoli.

La soluzione proposta: "La Doppia Mappa di Sicurezza"

Gli autori di questo articolo hanno creato un nuovo metodo che non si accontenta di una sola mappa, ma ne calcola due contemporaneamente:

La Mappa "Pessimista" (Il limite inferiore): Questa mappa è molto cauta. Se dice che sei al sicuro, allora sei davvero al sicuro. Non commette errori di "falso positivo". È come un guardiano che non ti fa entrare in una stanza a meno che non sia certo al 100% che non ci siano mostri.
La Mappa "Ottimista" (Il limite superiore): Questa mappa è molto prudente nel dire che sei in pericolo. Se dice che sei in pericolo, allora sei davvero in pericolo. Non commette errori di "falso negativo". È come un allarme antincendio che suona anche se c'è solo un po' di fumo, per essere sicuro di non bruciare la casa.

L'analogia della "Zona Grigia":
Immagina di voler sapere se una persona è alta abbastanza per andare su un'altalena (che ha un limite di altezza).

La Mappa Ottimista dice: "Sei troppo alto, non puoi salire" (anche se forse sei solo quasi troppo alto).
La Mappa Pessimista dice: "Sei abbastanza basso, puoi salire" (anche se forse sei quasi troppo alto).
Se le due mappe sono d'accordo, la risposta è certa.
Se c'è una zona grigia dove una dice "sì" e l'altra "no", significa che la nostra mappa è troppo grossolana in quel punto.

Il "Segreto": Affinare la mappa dove serve

Il vero trucco del loro metodo è un algoritmo di rifinitura automatica.
Quando le due mappe non si accordano (la zona grigia), il sistema non si arrende. Invece, prende quel quadratino della griglia e lo taglia a metà, rendendolo più piccolo e preciso. Poi ricalcola le due mappe su questa nuova griglia più dettagliata.

È come se avessi una foto sfocata di un territorio. Se vedi un confine tra "sicuro" e "pericoloso" che non è chiaro, non indovini: ingrandisci quella parte della foto (zoom) e ridisegni i confini con più precisione. Ripeti questo processo solo dove serve, risparmiando tempo e risorse.

Perché è importante?

Sicurezza Garantita: Non devi più fidarti ciecamente del computer. Ora hai due confini matematici che ti garantiscono: "Se sei dentro la zona verde, non morirai mai".
Gestione degli errori: Anche se il computer si ferma prima di aver finito tutti i calcoli (per risparmiare tempo), il metodo sa correggere l'errore e dire: "Ehi, mi sono fermato presto, ma ho aggiunto un margine di sicurezza extra per essere sicuro".
Efficienza: Invece di rendere tutta la mappa super-dettagliata (che richiederebbe anni di calcolo), rende dettagliata solo la parte dove i confini sono confusi.

In sintesi

Immagina di dover costruire un recinto per un animale pericoloso.

I vecchi metodi disegnavano il recinto basandosi su una mappa approssimativa: a volte lasciavano buchi, a volte facevano il recinto troppo grande e inutilmente costoso.
Questo nuovo metodo disegna due recinti: uno interno (sicuro al 100%) e uno esterno (che copre tutto il possibile pericolo). Se c'è spazio tra i due, il sistema "zooma" su quella zona e disegna nuovi recinti più precisi finché non si sovrappongono perfettamente.

Il risultato è un sistema di guida autonoma o di robotica che non solo sa dove andare, ma può garantire matematicamente che non farà mai un errore fatale, anche in situazioni complesse e impreviste.

Titolo: Calcolo di Limiti Inferiori e Superiori "Sound" (Validi) per le Funzioni di Valore di Raggiungimento-Evitamento Hamilton-Jacobi

1. Il Problema

L'analisi di raggiungibilità Hamilton-Jacobi (HJ) è uno strumento fondamentale per la verifica della sicurezza e la sintesi del controllo nei sistemi di controllo non lineari. L'obiettivo è determinare l'insieme degli stati da cui un sistema può evitare un insieme di fallimento $F$ (Backward Reachable Set - BRS) o raggiungere un insieme target $T$ evitando $F$ (Reach-Avoid Set - RAS).

I metodi classici risolvono le equazioni alle derivate parziali (PDE) di HJ su griglie che discretizzano lo spazio degli stati continuo. Tuttavia, questi approcci presentano due limitazioni critiche:

Errori di discretizzazione: Non tengono conto esplicitamente degli errori introdotti dalla discretizzazione dello spazio.
Mancanza di garanzie di "Soundness": Non garantiscono che gli insiemi calcolati sovrastimino (over-approximate) il BRS o sottostimino (under-approximate) il RAS. Di conseguenza, potrebbero classificare erroneamente stati sicuri come insicuri o viceversa, il che è inaccettabile in contesti safety-critical (es. veicoli autonomi, robot chirurgici).

2. Metodologia Proposta

Gli autori propongono un framework che calcola limiti superiori e inferiori "sound" (validi) per la funzione di valore HJ, garantendo approssimazioni corrette degli insiemi di raggiungibilità.

Astrazione Discreta e Griglia: Lo spazio degli stati continuo viene discretizzato in una griglia finita. Viene costruita un'astrazione discreta del sistema, dove ogni cella della griglia rappresenta un insieme di stati continui.
Limiti delle Funzioni di Costo: Vengono calcolati limiti superiori ( $\bar{l}, \bar{r}$ ) e inferiori ( $\underline{l}, \underline{r}$ ) per le funzioni di fallimento e di ricompensa all'interno di ogni cella, sfruttando le costanti di Lipschitz delle funzioni originali.
Due Funzioni di Valore: Invece di calcolare una singola funzione di valore, l'algoritmo ne calcola due sulla griglia discreta:
- $V^\gamma$ : Una funzione che sottostima (lower bound) la funzione di valore HJ continua.
- $\bar{V}^\gamma$ : Una funzione che sovrastima (upper bound) la funzione di valore HJ continua.
- Queste funzioni sono definite tramite operatori di Bellman specifici che considerano la non-deterministicità delle transizioni tra le celle.
Gestione dell'Arresto Anticipato (Early Stopping): Un contributo chiave è la capacità di fermare l'iterazione del valore prima della convergenza completa.
- Per la sottostima, viene introdotto un termine di correzione basato sulla differenza minima tra le iterazioni successive ( $\delta_k$ ) per garantire che il limite inferiore rimanga valido anche se l'iterazione non ha raggiunto il punto fisso.
- Per la sovrastima, viene dimostrato che, con un'inizializzazione appropriata, ogni iterazione è già un limite superiore valido.
Algoritmo di Raffinamento Adattivo: Se i limiti calcolati non sono sufficientemente stretti per classificare una cella come sicura o insicura (cioè se il limite inferiore è $\le 0$ e il limite superiore è $> 0$ ), l'algoritmo divide (rifine) quella cella in celle più piccole. Questo processo viene ripetuto iterativamente per ottenere approssimazioni più precise solo dove necessario, evitando la complessità computazionale di una griglia uniforme fine su tutto lo spazio.

3. Contributi Chiave

Garanzie di Soundness: L'algoritmo fornisce limiti superiori e inferiori provati per le funzioni di valore HJ, garantendo che il BRS sia sovrastimato e il RAS sottostimato, tenendo conto degli errori di discretizzazione.
Gestione dell'Arresto Anticipato: Viene stabilita la correttezza dei limiti calcolati anche quando l'iterazione del valore viene interrotta prima della convergenza, un aspetto cruciale per l'efficienza computazionale.
Raffinamento Adattivo: Sviluppo di un algoritmo che divide dinamicamente solo le celle "non classificate" (quelle al confine tra sicurezza e insicurezza), ottenendo griglie non uniformi che offrono una maggiore precisione ai bordi degli insiemi di raggiungibilità.
Estensione al Caso "Reach-Avoid": A differenza di lavori precedenti focalizzati solo sull'evitamento, questo metodo gestisce la specifica generale di raggiungere un target evitando un ostacolo.

4. Risultati Sperimentali

Gli autori hanno validato il metodo su due casi di studio:

Auto di Dubins: Un veicolo con dinamica non lineare che deve evitare un ostacolo cilindrico e raggiungere un target.
Evasione 3D: Uno scenario di inseguimento ed evasione tra due aeromobili.

Risultati principali:

Confronto con Toolbox Esistenti: Il metodo proposto è stato confrontato con il toolbox HJ esistente (che risolve PDE numeriche) e ROCS 2.0 (sintesi di controllo simbolico).
- Il toolbox HJ standard, con risoluzioni di griglia basse, tende a produrre approssimazioni non sound (marchia stati sicuri come insicuri).
- Rispetto a ROCS 2.0, il metodo proposto calcola un RAS più ampio (meno conservativo) con tempi di esecuzione competitivi o migliori, fornendo al contempo una funzione di valore (non solo una classificazione binaria) che permette di quantificare il margine di sicurezza.
Efficienza del Raffinamento: L'algoritmo di raffinamento adattivo (Algoritmo 2) riesce a classificare con precisione le regioni critiche riducendo il numero di celle non classificate, migliorando la precisione dell'approssimazione senza aumentare esponenzialmente il costo computazionale su tutto lo spazio.
Tempo di Esecuzione: I tempi di esecuzione crescono quasi linearmente con la dimensione della griglia, ma l'approccio adattivo evita di dover rifinire l'intera griglia.

5. Significato e Impatto

Questo lavoro risolve una lacuna fondamentale nell'analisi di raggiungibilità HJ: la mancanza di garanzie formali di sicurezza dovute alla discretizzazione e all'arresto anticipato degli algoritmi numerici.

Sicurezza Formale: Permette di utilizzare l'analisi HJ in applicazioni safety-critical con la certezza matematica che gli stati classificati come sicuri lo siano realmente (nel caso di sottostima del RAS) o che gli stati classificati come insicuri lo siano davvero (nel caso di sovrastima del BRS).
Flessibilità: L'approccio adattivo bilancia precisione e costo computazionale, rendendo l'analisi fattibile per sistemi con dimensioni moderate.
Analisi Quantitativa: Fornendo limiti sulla funzione di valore, il metodo permette di analizzare non solo se un sistema può raggiungere un obiettivo, ma quanto è "sicuro" o "vicino" al fallimento, offrendo informazioni preziose per la sintesi del controllo.

In sintesi, il paper propone un framework robusto che trasforma l'analisi di raggiungibilità HJ da un metodo puramente numerico/approssimativo a uno strumento di verifica formale con garanzie matematiche rigorose.