⚡ electrical engineering

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

Dit paper introduceert een algoritme dat geluidse boven- en ondergrenzen berekent voor Hamilton-Jacobi reachability-waardefuncties om discretisatiefouten aan te pakken en zo gegarandeerde over- en onderbenaderingen van bereikbare en vermijdbare verzamelingen in niet-lineaire controlesystemen mogelijk te maken.

Oorspronkelijke auteurs: Ihab Tabbara, Eliya Badr, Hussein Sibai

Gepubliceerd 2026-03-31

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Ihab Tabbara, Eliya Badr, Hussein Sibai

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een zeer complexe, onvoorspelbare auto bestuurt in een stad vol struiken, gaten en obstakels. Je doel is om een specifieke plek te bereiken (bijvoorbeeld een parkeerplaats), maar je mag absoluut niet tegen de struiken aanrijden.

De vraag is: Vanuit welke startpunten kun je veilig aankomen, en vanuit welke punten is een crash onvermijdelijk, hoe goed je ook probeert te sturen?

In de wereld van de robotica en zelfrijdende auto's noemen wetenschappers dit een "bereik-ontwijk"-probleem. Het artikel dat je hebt gedeeld, presenteert een nieuwe, slimmere manier om dit probleem op te lossen, zodat we 100% zeker weten dat onze berekeningen kloppen.

Hier is de uitleg in simpele taal, met wat creatieve vergelijkingen:

1. Het Probleem: De "Ruwe Schets"

Stel je voor dat je een kaart tekent van de stad om te zien waar het veilig is. De oude methoden (de "klassieke" manier) tekenden deze kaart op een rooster van vierkante vakjes, net als een pixelated video-game.

Het probleem: Omdat de echte wereld glad en rond is, maar je kaart uit vierkante blokjes bestaat, ontstaan er kleine foutjes. Het is alsof je een ronde bal probeert te meten met een liniaal die alleen rechte lijnen kan.
Het risico: Soms denken deze oude methoden dat een plek veilig is, terwijl je er eigenlijk al tegen een muur aanrijdt. Of ze denken dat je vastzit, terwijl je er eigenlijk wel uit kunt. Ze geven geen garantie. Ze zeggen: "Dit ziet er ongeveer goed uit," maar voor levensreddende robots (zoals chirurgische robots of zelfrijdende auto's) is "ongeveer" niet goed genoeg.

2. De Oplossing: Twee Vloeren en een Plafond

De auteurs van dit paper zeggen: "Laten we niet één kaart maken, maar twee."

Stel je voor dat je een kamer hebt waarin je wilt weten of een bal veilig kan rollen.

De Ondergrens (De Vloer): We bouwen een vloer die altijd onder de echte situatie ligt. Als de vloer veilig is, dan is de echte ruimte erboven ook veilig. Dit is een garantie voor veiligheid.
De Bovenlijn (Het Plafond): We bouwen een plafond dat altijd boven de echte situatie ligt. Als het plafond onveilig is (bijvoorbeeld een gat erin), dan is de ruimte eronder ook onveilig. Dit is een garantie voor gevaar.

Door tussen deze twee lijnen te werken, sluiten ze de "grijze zone" (de onzekerheid) in. Als de vloer en het plafond dicht bij elkaar liggen, weten we precies waar we staan.

3. De Slimme Truc: De "Stop-Op-Tijd" Correctie

Om deze kaarten te maken, gebruiken computers een proces dat lijkt op het oplossen van een raadsel stap voor stap (waarde-iteratie). Normaal gesproken moet je wachten tot het raadsel helemaal opgelost is, wat eeuwen kan duren.

De truc: De auteurs zeggen: "We hoeven niet tot het einde te wachten!" Maar als je vroegtijdig stopt, maak je een foutje.
De oplossing: Ze voegen een kleine "correctie" toe aan hun berekening. Stel je voor dat je een schatting maakt van hoe lang je moet lopen. Als je stopt voordat je klaar bent, tel je een extra "veiligheidsmarge" toe aan je schatting. Zo weet je zeker dat je nooit denkt dat je sneller bent dan je eigenlijk bent. Hierdoor kunnen ze stoppen wanneer ze willen, maar blijft de garantie dat hun berekening klopt.

4. De "Zoom-in" Functie: Het Oplossen van Grijze Zones

Soms zijn de vloer en het plafond nog te ver uit elkaar op bepaalde plekken. De computer weet dan niet zeker of een vakje veilig of onveilig is.

De oplossing: Het algoritme kijkt naar die twijfelachtige vakjes en deelt ze op in kleinere stukjes (net als het inzoomen op Google Maps).
Op die kleinere stukjes wordt de berekening opnieuw gedaan. Vaak zijn de grenzen op die kleine schaal veel scherper. Dit proces herhaalt zich totdat alles duidelijk is. Dit heet adaptieve verfijning. Het is alsof je alleen de gebieden inzoomt waar het moeilijk is, in plaats van de hele wereld in detail te tekenen (wat te veel rekenkracht zou kosten).

5. Waarom is dit belangrijk?

In het verleden moesten we kiezen tussen:

Snelle, onnauwkeurige berekeningen (veiligheid is een gok).
Uiterst nauwkeurige berekeningen die duizenden jaren duren om te rekenen.

Dit nieuwe algoritme biedt het beste van beide werelden:

Het is veilig: Het geeft een wiskundige garantie dat als het zegt "veilig", het echt veilig is.
Het is efficiënt: Het stopt vroeg en zoomt alleen in waar nodig.

Samenvatting in één zin

Stel je voor dat je een veiligheidsinspecteur bent die een gebouw controleert: in plaats van te raden of de vloer sterk genoeg is, bouw je een betonnen vloer eronder en een betonnen plafond erboven; als die twee dicht genoeg bij elkaar zitten, weet je zeker dat het gebouw veilig is, en je hoeft alleen maar de twijfelachtige hoekjes extra te controleren.

Deze methode maakt het mogelijk om veiligere zelfrijdende auto's, drones en robotchirurgen te bouwen, omdat we nu wiskundig kunnen bewijzen dat ze niet zullen crashen.

Titel: Het Berekenen van Betrouwbare Onder- en Bovengrenzen voor Hamilton-Jacobi Reach-Avoid Waardefuncties

Auteurs: Ihab Tabbara, Eliya Badr, Hussein Sibai

1. Probleemstelling

Hamilton-Jacobi (HJ) bereikbaarheidsanalyse is een fundamentele techniek voor veiligheidsverificatie en controlesynthese van niet-lineaire regelsystemen. Het doel is vaak om de Backward Reachable Set (BRS) te bepalen (de set van toestanden waarvan het falen onvermijdelijk is) of de Reach-Avoid Set (RAS) (de set van toestanden waaruit het systeem een doel kan bereiken zonder een falend gebied te betreden).

Bestaande methoden lossen de HJ-partiële differentiaalvergelijking (PDE) numeriek op op een gediscretiseerde rooster (grid) van de continue toestandsruimte. De belangrijkste beperkingen van deze benaderingen zijn:

Discretisatiefouten: Ze houden geen expliciete rekening met fouten die ontstaan door het rooster.
Gebrek aan garanties: Ze garanderen niet dat de berekende sets de werkelijke BRS overbenaderen (over-approximation) of de RAS onderbenaderen (under-approximation). Dit kan leiden tot onveilige conclusies (bijv. een onveilige toestand wordt als veilig gemarkeerd).
Vroege stopzetting: Als de iteratie wordt gestopt voordat convergentie is bereikt (voor tijdsbesparing), worden de resultaten niet langer als betrouwbare grenzen beschouwd.

Het paper richt zich op het oplossen van dit probleem door een framework te ontwikkelen dat wiskundig bewezen (sound) onder- en bovengrenzen berekent voor de HJ-waardefuncties, zelfs bij gediscretiseerde ruimtes en vroege stopzetting.

2. Methodologie

De auteurs stellen een framework voor dat werkt met discrete tijdssystemen en een adaptief rooster. De kerncomponenten zijn:

A. Discrete Abstraktie en Foutbegrenzing

De continue toestandsruimte wordt opgedeeld in een eindig rooster van cellen.
Voor elke cel worden Lipschitz-continuïteitsconstanten gebruikt om onder- en bovengrenzen te berekenen voor de falingsfunctie ( $l$ ) en de beloningsfunctie ( $r$ ) over de hele cel.
Er wordt een niet-deterministische transitierelatie ( $\Delta$ ) geconstrueerd die een overbenadering is van de werkelijke bereikbare toestanden. Dit zorgt ervoor dat als een cel in de abstraktie als "veilig" wordt geclassificeerd, alle continue toestanden in die cel ook veilig zijn.

B. Berekening van Waardefunctie-Grenzen

In plaats van één waardefunctie te berekenen, worden er twee gedefinieerd over het discrete rooster:

$V^\gamma$ (Ondergrens): Benadert de waardefunctie van onderen.
$V_\gamma$ (Bovengrens): Benadert de waardefunctie van boven.

Deze worden berekend via waarde-iteratie met specifieke Bellman-operatoren die respectievelijk het maximum en minimum over de mogelijke volgende toestanden nemen.

C. Omgaan met Vroege Stopzetting (Early Stopping)

Een cruciale innovatie is de behandeling van fouten wanneer de iteratie wordt gestopt voordat de exacte convergentie is bereikt:

Voor de ondergrens ( $V^\gamma$ ) wordt een correctieterm toegevoegd die gebaseerd is op de minimale verandering tussen iteraties ( $\delta_k$ ). Dit garandeert dat de berekende waarde nog steeds een geldige ondergrens is voor de continue waardefunctie, zelfs als de iteratie voortijdig stopt.
Voor de bovengrens ( $V_\gamma$ ) wordt bewezen dat, bij een juiste initialisatie, elke iteratie een geldige bovengrens blijft.

D. Adaptieve Verfijning (Refinement)

Als de berekende grenzen voor een cel te breed zijn om te bepalen of deze tot de veilige set (RAS) of de onveilige set (BRS) behoort (d.w.z. de grenzen "omvatten" de nul-drempel), wordt deze cel verfijnd:

De cel wordt opgesplitst in kleinere cellen (langs de langste zijde).
De waarde-iteratie wordt opnieuw uitgevoerd op het verfijnde rooster.
Dit proces herhaalt zich totdat alle cellen kunnen worden geclassificeerd of een minimale resolutie is bereikt.

3. Belangrijkste Bijdragen

Sound Bounds: Het paper presenteert een algoritme dat wiskundig bewezen onder- en bovengrenzen berekent voor HJ-waardefuncties. Dit garandeert dat de berekende BRS de werkelijke BRS overbenadert (veilig voor vermijding) en de berekende RAS de werkelijke RAS onderbenadert (veilig voor bereiken).
Robuustheid bij Vroege Stopzetting: Het framework bewijst dat de ondergrens correct blijft zelfs als de waarde-iteratie niet is geconvergeerd naar een vast punt, door het gebruik van een correctieterm.
Adaptieve Verfijning: Een algoritme dat specifiek cellen opsplitst die niet kunnen worden geclassificeerd, wat leidt tot nauwkeurigere benaderingen zonder het hele rooster uniform te verfijnen (wat computatieel duur zou zijn).
Toepassing op Reach-Avoid: In tegenstelling tot veel eerdere werken die zich beperken tot "avoid-only" (vermijden), behandelt dit werk de complexere "reach-avoid" specificatie (doel bereiken én vermijden).

4. Resultaten en Case Studies

De methode is gevalideerd in twee casestudies:

Dubins-auto: Een voertuigmodel dat een obstakel moet vermijden en een doel moet bereiken.
3D Ontwijking (Evasion): Een scenario met een jager en een vluchter in 3D.

Vergelijking met bestaande tools:

Tegenover HJ PDE-oplossers (bijv. [25]): Bestaande methoden tonen bij lage resolutie fouten waarbij onveilige toestanden als veilig worden gemarkeerd (geen soundness). De voorgestelde methode garandeert dit niet. Bovendien is de voorgestelde methode sneller dan de HJ-toolbox bij dezelfde discretisatieparameters, terwijl ze soundness biedt.
Tegenover Symbolische Controle (ROCS 2.0): De voorgestelde methode berekent een grotere (dus minder conservatieve) RAS dan ROCS 2.0 bij vergelijkbare parameters, en doet dit in minder tijd.
Kwaliteit van de output: In tegenstelling tot tools die alleen een binaire classificatie (veilig/ongevaarlijk) geven, levert deze methode een waardefunctie op. Dit stelt gebruikers in staat om de "veiligheidsmarge" te kwantificeren (hoeveel buffer er is tussen de huidige toestand en het falen).

Performance:

De runtime groeit bijna lineair met de grootte van het rooster, maar het aantal cellen groeit exponentieel bij elke verfijningstap.
De adaptieve verfijning zorgt ervoor dat de resolutie alleen hoog is in de kritieke gebieden (grenzen tussen veilig en onveilig), terwijl andere gebieden grof blijven, wat efficiëntie oplevert.

5. Betekenis en Conclusie

Dit paper biedt een significante doorbraak in het veld van formele verificatie van niet-lineaire systemen. De belangrijkste implicaties zijn:

Veiligheidsgaranties: Het elimineert het risico van "valse positieven" in veiligheidsverificatie door discretisatiefouten expliciet te modelleren en te corrigeren.
Efficiëntie: Door adaptieve verfijning en het toestaan van vroege stopzetting met correcties, wordt de berekeningslast verlaagd zonder in te leveren op de garanties.
Kwantitatieve Analyse: Het leveren van een waardefunctie in plaats van alleen een set geeft engineers meer inzicht in de kwaliteit van de regeling en de veiligheidsmarges.

De auteurs concluderen dat hun framework een robuust alternatief biedt voor bestaande methoden, met name voor toepassingen in veiligheidskritieke systemen zoals autonome voertuigen en medische robots, waar fouten in de veiligheidsanalyse niet acceptabel zijn. Toekomstig werk richt zich op het versnellen van de berekeningen via GPU-parallelisatie en het uitbreiden naar continue tijdssystemen.