⚡ electrical engineering

Time-Varying Reach-Avoid Control Certificates for Stochastic Systems

Dit artikel introduceert een raamwerk voor tijd-variërende en tijd-invariante reach-avoid certificaten voor discrete-tijd stochastische systemen, waarbij som-van-kwadraten (SOS)-optimalisatie wordt gebruikt voor het verifiëren en gezamenlijk synthetiseren van feedbackcontrollers om de waarschijnlijkheid van het bereiken van doelwitten en het vermijden van onveilige gebieden te maximaliseren.

Oorspronkelijke auteurs: Rayan Mazouz, Luca Laurenti, Morteza Lahijanian

Gepubliceerd 2026-03-30

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Rayan Mazouz, Luca Laurenti, Morteza Lahijanian

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 zelfrijdende auto bestuurt die door een drukke stad moet rijden. Het doel is duidelijk: kom veilig aan op je bestemming (de "reach"-doelstelling) en vermijd alle ongelukken (de "avoid"-doelstelling).

Maar er is een probleem: de wereld is niet perfect. Er is regen, een plotselinge windvlaag, of een fietser die onverwacht de weg op rijdt. In de technische taal noemen we dit stochastische systemen: systemen met een vleugje chaos en onzekerheid.

Dit artikel beschrijft een nieuwe, slimme manier om te garanderen dat zo'n systeem (zoals een robot of een drone) zijn doel bereikt zonder in de problemen te komen, zelfs als het weer meewerkt of niet.

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

1. Het Probleem: De Onzekere Reis

Vroeger probeerden ingenieurs om de wereld in blokjes te hakken (zoals een pixelated spelletje) om te berekenen of een robot veilig zou blijven. Maar dat werkt niet goed voor complexe systemen; het wordt te zwaar voor de computer, net als het proberen te tellen van elk zandkorreltje op een strand.

Andere methoden gebruiken kunstmatige intelligentie (AI) om te "gokken" wat de beste route is. Maar AI is vaak een "black box": het werkt misschien, maar je kunt niet 100% bewijzen dat het altijd veilig is. Voor kritieke systemen (zoals vliegtuigen of medische apparaten) is "misschien" niet genoeg; je wilt een garantie.

2. De Oplossing: Het "Magische Kompas" (De Certificate)

De auteurs van dit paper hebben een nieuw soort magisch kompas ontworpen. Ze noemen dit een "Reach-Avoid Certificate".

Stel je voor dat je een kompas hebt dat niet alleen de weg naar het noorden aangeeft, maar ook een onzichtbaar schild om je heen houdt.

Het Kompas (De Certificate): Dit is een wiskundige formule die op elk moment in de reis zegt: "Hoe groot is de kans dat je nog veilig aankomt?"
De Garantie: Als dit kompas een bepaalde waarde aangeeft, weten we wiskundig bewezen dat je met een kans van bijvoorbeeld 95% veilig aankomt, ongeacht de windvlaag.

3. Twee Soorten Kompas: Statisch vs. Dynamisch

Het paper introduceert twee soorten van deze magische kompassen:

Het Statische Kompas (Time-Invariant):
Dit is als een ouderwetse papieren kaart. Het zegt: "Vanaf hier is de route veilig." Het is simpel en snel te gebruiken, maar het is niet heel flexibel. Als de situatie verandert (bijvoorbeeld een plotselinge storm), kan deze kaart wat te pessimistisch zijn. Het is alsof je zegt: "Ik ga nooit sneller dan 20 km/u, want dan kan ik niet remmen." Het is veilig, maar misschien niet de snelste route.
Het Dynamische Kompas (Time-Varying):
Dit is als een slimme GPS-app die live updates krijgt. Deze weet: "Op dit moment is het veilig, maar over 5 minuten moet je iets anders doen."
- De kracht: Omdat dit kompas weet wanneer je waar bent, kan het veel preciezer zijn. Het kan zeggen: "Nu mag je hard rijden, maar over een seconde moet je voorzichtig zijn."
- Het nadeel: Het is rekenkundig zwaarder voor de computer, omdat het de hele reis stap voor stap moet berekenen in plaats van één grote kaart te gebruiken.

4. Hoe werkt het in de praktijk? (De Wiskunde als Kookrecept)

De auteurs gebruiken een techniek genaamd Sum-of-Squares (SOS).

De Analogie: Stel je voor dat je wilt bewijzen dat een koekje altijd zoet is. Je kunt niet elk koekje proeven. In plaats daarvan schrijf je een recept (een formule) op dat garandeert dat elk koekje dat volgens dit recept gemaakt is, suiker bevat.
In dit paper gebruiken ze een soort "wiskundig recept" (polynomen) om te bewijzen dat het systeem veilig blijft. Ze zetten dit om in een convex optimalisatie probleem.
Wat betekent dat? Het klinkt ingewikkeld, maar het betekent simpelweg: "We hebben een recept gevonden dat de computer in één keer kan oplossen, zonder te hoeven gissen." Het is alsof je een puzzel hebt die eruitziet alsof je uren moet zoeken, maar waarvoor er een slimme truc is om het direct op te lossen.

5. Wat hebben ze bewezen?

Ze hebben hun theorie getest op verschillende scenario's:

Een simpele lijn: Een auto die rechtuit rijdt.
Een draaiende robot: Een robot die in een kamer moet navigeren zonder tegen de muren aan te vliegen.
Een vliegtuig: Een modelvliegtuigje dat door turbulentie moet vliegen.

De resultaten:

Hun nieuwe methode (vooral het dynamische kompas) gaf veel betere garanties dan oude methoden.
Waar andere methoden zeiden: "De kans op succes is misschien 16%", zeiden zij: "De kans is gegarandeerd 96%."
Ze konden zelfs een controller (de "bestuurder" van de robot) ontwerpen die samenwerkte met het kompas om de veiligste route te vinden.

Samenvatting in één zin

Dit paper biedt een nieuwe, wiskundig onweerlegbare manier om te bewijzen dat robots en machines veilig hun doel bereiken in een onzekere wereld, door slimme, dynamische "veiligheidsschilden" te gebruiken die de computer snel kan berekenen.

Het is alsof je niet meer hoopt dat je niet crasht, maar een onzichtbaar, onbreekbaar schild om je heen bouwt dat je wiskundig bewijst dat je veilig aankomt.

Titel: Time-Varying Reach-Avoid Control Certificates for Stochastic Systems

Auteurs: Rayan Mazouz, Luca Laurenti, Morteza Lahijanian

1. Probleemstelling

Het paper richt zich op het waarborgen van veiligheid en het bereiken van doelstellingen voor discrete-tijd, continue-ruimte stochastische systemen. In veel veiligheidskritieke toepassingen (zoals autonome systemen) moeten systemen niet alleen veilig blijven (het vermijden van onveilige gebieden $X_u$ ), maar ook een specifiek doel bereiken (het bereiken van een doelset $X_r$ ) binnen een bepaalde tijdshorizon, terwijl ze zich binnen een veilige set $X_s$ bevinden.

De uitdagingen zijn:

Stochastische onzekerheid: Systemen worden beïnvloed door ruis (bijv. procesruis).
Continue ruimtes: Zowel de toestandsruimte als de actie-ruimte zijn continu, wat het gebruik van traditionele discretisatiemethoden (zoals Markov-beslissingsprocessen) computatiekundig onhaalbaar maakt in hoge dimensies.
Niet-lineariteit: De dynamica zijn vaak niet-lineair (polynomen).
Tijdsafhankelijkheid: Bestaande methoden zijn vaak beperkt tot tijdsinvariante certificaten of oneindige horizons, wat leidt tot conservatieve schattingen of moeilijk te verifiëren neural network-approaches.

Het doel is om een reach-avoid kans te garanderen (de kans dat het systeem het doel bereikt zonder de onveilige set te betreden) en, indien nodig, een feedback-controller te synthetiseren die deze kans maximaliseert.

2. Methodologie

De auteurs introduceren een raamwerk gebaseerd op Reach-Avoid Certificaten, afgeleid van het optimaliteitsprincipe van Bellman (Dynamic Programming). Ze stellen twee formuleringen voor:

A. Certificaten (Verificatie)

In plaats van de exacte kans te berekenen (wat onmogelijk is voor continue systemen), zoeken ze naar een functie (het certificaat) die een ondergrens garandeert voor deze kans.

Tijdsvariërende Certificaten (Time-Varying): Een reeks functies $R(x, i)$ die per tijdstap $i$ evolueert. Dit biedt een strakkere benadering van de waarde-functie maar vereist meer rekentijd.
Tijdsinvariante Certificaten (Time-Invariant): Een enkele functie $R(x)$ die voor alle tijdstappen geldt. Dit is computatie-efficiënter maar kan conservatiever zijn.

De methodologie introduceert slack-variabelen ( $\alpha, \beta$ ) om de harde randvoorwaarden van de dynamica (zoals de indicatorfunctie voor doel- en onveilige sets) te versoepelen. Dit maakt het probleem oplosbaar voor continue functies.

B. Sum-of-Squares (SOS) Optimalisatie

Om de functionele optimalisatieproblemen oplosbaar te maken, beperken de auteurs de certificaten en controllers tot polynomen.

Ze gebruiken Sum-of-Squares (SOS) optimalisatie om de voorwaarde "niet-negatief op een semi-algebraïsche set" om te zetten in een Semidefinite Programming (SDP) probleem.
Dit transformeert het niet-convexe probleem in een convex optimalisatieprobleem, wat efficiënt opgelost kan worden.

C. Gezamenlijke Synthese (Control Synthesis)

Het paper presenteert een innovatieve methode voor de gezamenlijke synthese van de controller $\pi$ en het certificaat $R$ .

Dit wordt geformuleerd als een min-max probleem: minimaliseer over de controller parameters en maximaliseer over de toestandsruimte.
Door gebruik te maken van moment-relaxaties en duale SOS-programmering (gebaseerd op Putinar's Positivstellensatz), wordt dit niet-convexe min-max probleem omgezet in een enkel convex SOS-programma. Hierdoor kunnen de optimale feedback-controller en het bijbehorende certificaat simultaan worden gevonden.

3. Belangrijkste Bijdragen

Unificatie van Formuleringen: Een unificerend raamwerk voor zowel tijdsvariërende als tijdsinvariante reach-avoid certificaten voor zowel eindige als oneindige horizons.
Convexe Formulering: Het bewijzen dat deze certificaten en controllers kunnen worden gesynthetiseerd via SOS-optimalisatie, wat een convex probleem oplevert zonder extra conservatisme (in tegenstelling tot eerdere methoden die vaak te conservatief waren of niet-convex).
Gezamenlijke Synthese: Een nieuwe SOS-benadering voor het gelijktijdig ontwerpen van een optimale feedback-controller en het bijbehorende certificaat, wat de kans op succes maximaliseert.
Verbeterde Schaalbaarheid: Het aantonen dat tijdsvariërende certificaten, hoewel ze meer decision-variabelen hebben, vaak kunnen worden opgelost met polynomen van lagere graad dan tijdsinvariante certificaten, wat ze schaalbaarder maakt voor hogere dimensies.

4. Resultaten en Experimenten

De auteurs hebben hun methode getest op diverse lineaire en niet-lineaire systemen (1D, 2D en 3D), waaronder:

Lineaire systemen met stabiele en instabiele dynamica.
2D contractiekaarten met rotatie.
Een gelijneerd vliegtuigmodel (3D).
Temperatuurregelsystemen (2D en 3D) met polynoomdynamica.

Kernbevindingen:

Vergelijking met State-of-the-Art: De voorgestelde methode presteert aanzienlijk beter dan bestaande methoden (zoals [8] en [19]). Bijvoorbeeld, voor een 1D lineair systeem bereikte de tijdsinvariante methode een ondergrens van 0.96 (graad 10), terwijl de methode uit [8] slechts 0.17 haalde.
Tijdsvariërend vs. Tijdsinvariant: Tijdsvariërende certificaten leveren consistent strakkere ondergrenzen op (dichter bij de empirische Monte Carlo-schattingen) dan tijdsinvariante certificaten.
- In de 2D contractiekaarten kon een tijdsvariërend certificaat een graad van 6 gebruiken om een kans van 0.99 te garanderen, terwijl een tijdsinvariant certificaat een graad van 24 nodig had voor vergelijkbare resultaten.
Controller Synthese: De synthese van feedback-controllers verbeterde de reach-avoid kansen aanzienlijk. Bijvoorbeeld, bij een 2D systeem steeg de kans van 0.19 (zonder controle) naar 0.95 met de gesynthetiseerde controller.
Computatiekosten: Hoewel tijdsvariërende methoden meer rekentijd vereisen, zijn ze vaak efficiënter in termen van polynoomgraad, wat cruciaal is voor hogere dimensies waar de complexiteit exponentieel groeit met de graad.

5. Betekenis en Conclusie

Dit paper biedt een praktisch en rigoureus gereedschap voor het verifiëren en controleren van stochastische systemen in continue ruimtes.

Theoretische Garantie: Het biedt formele probabilistische garanties voor veiligheid en doelbereiking, wat essentieel is voor veiligheidskritieke toepassingen.
Overbrug van de Kloof: Het overbrugt de kloof tussen klassieke value-iteration-methoden (die vaak discretisatie vereisen) en continue analyse.
Toepasbaarheid: Door het gebruik van SOS en SDP, is de methode toepasbaar op een breed scala aan systemen zonder de noodzaak van diepe leermethodes die moeilijk te verifiëren zijn.

De conclusie is dat tijdsvariërende certificaten, ondanks hun hogere rekentijd, de voorkeur verdienen voor complexe, hoog-dimensionale systemen omdat ze strakkere garanties bieden met lagere polynoomgraden, waardoor ze schaalbaarder zijn dan traditionele tijdsinvariante benaderingen.