Data-Driven Reachability of Nonlinear Lipschitz Systems via Koopman Operator Embeddings

Diese Arbeit stellt einen datengesteuerten Ansatz zur Berechnung von erreichbaren Mengen für nichtlineare Lipschitz-Systeme vor, der durch die Einbettung mittels des Koopman-Operators und zonotopischer Darstellungen konservativere Schätzungen als herkömmliche Methoden reduziert und dabei formale Sicherheitsgarantien für autonome Systeme bewahrt.

Das Wesentliche

Das Problem: Die unvorhersehbare Reise

Stell dir vor, du planst eine Reise mit einem Auto, das du noch nie gefahren hast. Du weißt nicht genau, wie es auf Kurven reagiert oder wie stark der Motor ist. Außerdem gibt es kleine Störungen: Windböen, eine unebene Straße oder einen kleinen Fehler im Tacho (das ist der Rauschen oder Noise).

Wenn du jetzt vorhersagen willst, wo das Auto in 10 Minuten sein wird, ist das schwierig.

• Der alte Weg: Die Ingenieure haben oft gesagt: "Wir nehmen an, das Auto ist super unvorhersehbar und fährt vielleicht überall hin!" Das Ergebnis war eine riesige, unsichere Wolke, in der das Auto irgendwo sein könnte. Das ist zwar sicher (das Auto ist garantiert drin), aber zu ungenau. Man kann damit nicht gut planen, weil die Wolke so groß ist, dass sie alles andere auf der Straße mit einschließt.
• Das Ziel: Wir wollen eine viel kleinere, präzisere Wolke, die immer noch garantiert das Auto enthält, aber uns sagt: "Es wird hier und hier sein, nicht dort."

Die Lösung: Der "Koopman-Zaubertrick"

Die Autoren dieses Papers haben eine clevere Methode entwickelt, die auf etwas namens Koopman-Operator basiert. Hier ist die Analogie:

Stell dir vor, das Verhalten deines Autos ist wie ein verwirrter Tanz in einem kleinen, dunklen Raum (dem nichtlinearen System). Der Tanz ist chaotisch, springt hin und her und ist schwer zu berechnen.

Der Koopman-Operator ist wie ein Zauberer, der den Tanz in einen riesigen, hell erleuchteten Ballsaal (den erweiterten Raum) hebt.

• Im dunklen Raum (der Realität) tanzt das Auto chaotisch.
• Im hellen Ballsaal (dem "lifted space") sieht der Tanz plötzlich aus wie eine einfache, gerade Linie oder ein perfekter Kreis. Er ist linear geworden.

Warum ist das toll? Weil wir lineare Bewegungen (wie eine gerade Linie) viel besser berechnen können als chaotische Tänze. Wir können die Vorhersage im hellen Ballsaal machen, wo alles einfach ist, und dann das Ergebnis zurück in den dunklen Raum projizieren.

Der neue Ansatz: Nicht nur "Auto", sondern "Auto + Gaspedal"

Frühere Methoden haben oft nur geschaut: "Wie bewegt sich das Auto?" (Das ist wie ein LTI-Modell – Linear Time Invariant). Das funktioniert gut, wenn das Auto immer gleich fährt. Aber wenn du das Gaspedal drückst oder loslässt, ändert sich das Verhalten.

Die Autoren sagen: "Nein, wir müssen den Tanz nicht nur nach dem Auto, sondern auch nach dem Gaspedal und dem Lenkrad benennen."
Sie bauen eine Abhängigkeit vom Input (State-Input-dependent) in ihren Zaubertrick ein. Das bedeutet, ihr Modell weiß: "Wenn ich Gas gebe, passiert im hellen Ballsaal etwas anderes als wenn ich bremse." Das macht die Vorhersage viel genauer.

Wie sie die Sicherheit garantieren (Die "Sicherheitsnetz"-Methode)

Aber Vorsicht: Der Zaubertrick ist nicht perfekt. Wenn wir den Tanz in den hellen Raum heben, gibt es kleine Verzerrungen. Und da wir das Auto nur aus Daten (Messungen) kennen, gibt es auch Messfehler.

Um sicherzustellen, dass das Auto garantiert in unserer Vorhersage ist, machen sie folgendes:

1. Daten sammeln: Sie fahren das Auto viele Male und notieren jede Bewegung.
2. Fehler messen: Sie schauen sich an, wo ihre Vorhersage im hellen Raum von der echten Messung abgewichen ist.
3. Das Sicherheitsnetz (Residual Set): Sie nehmen diese Abweichungen, packen sie in ein extra großes "Sicherheitsnetz" (einen mathematischen Bereich, der alle möglichen Fehler abdeckt).
4. Zonotope (Die Form der Wolke): Anstatt eine riesige, klobige Kugel als Unsicherheit zu nehmen, nutzen sie eine spezielle Form namens Zonotop. Stell dir das vor wie einen gestreckten, flexiblen Gummiballon, der sich genau um die Vorhersage legt, ohne unnötig viel Platz zu verschwenden.

Das Ergebnis ist eine Vorhersage, die:

• Sicher ist: Das Auto ist garantiert drin (wegen des Sicherheitsnetzes).
• Präzise ist: Die Wolke ist viel kleiner als bei alten Methoden, weil der "Zaubertrick" (Koopman) die Nichtlinearitäten besser versteht.

Das Ergebnis in der Praxis

Die Autoren haben das an einem echten autonomen Rennauto (JetRacer) getestet.

• Andere Methoden: Sagten: "Das Auto könnte in 10 Sekunden irgendwo in diesem riesigen Feld sein." (Zu groß, zu vorsichtig).
• Ihre Methode: Sagte: "Das Auto wird in 10 Sekunden genau hier auf der Strecke sein." (Viel genauer, aber immer noch sicher).

Zusammenfassung in einem Satz

Die Autoren haben eine Methode erfunden, die chaotische, nichtlineare Systeme (wie ein echtes Auto) in eine einfache, lineare Welt "hebt", dort präzise vorhersagt, was passiert, und dann mit einem mathematischen Sicherheitsnetz garantiert, dass die Vorhersage auch in der chaotischen Realität stimmt – und das alles nur basierend auf gesammelten Daten, ohne dass man die genaue Physik des Autos kennen muss.

Technische Zusammenfassung

1. Problemstellung

Die Sicherheitsverifikation robotischer Systeme in dynamischen und unsicheren Umgebungen erfordert oft eine Erreichbarkeitsanalyse (Reachability Analysis), um sicherzustellen, dass das System keine unsicheren Zustände erreicht.

• Herausforderung: Herkömmliche modellbasierte Methoden benötigen exakte Systemdynamiken, die für komplexe Roboter oft unbekannt oder schwer zu beschaffen sind. Datengetriebene Ansätze nutzen gemessene Daten, leiden jedoch oft unter Überkonservatismus (zu große Sicherheitsmargen), insbesondere bei nichtlinearen Systemen, über lange Vorhersagehorizonte und bei Vorhandensein von Messrauschen.
• Ziel: Entwicklung eines datengetriebenen Rahmens, der für nichtlineare, Lipschitz-stetige Systeme (auch nicht-affin) garantierte Überapproximationen der erreichbaren Mengen liefert, dabei aber deutlich weniger konservativ ist als bestehende lineare oder modellbasierte Methoden.

2. Methodik

Der vorgeschlagene Ansatz kombiniert die Koopman-Operator-Theorie mit Zonotopen (einer effizienten Mengenrepräsentation) und datengetriebener Systemidentifikation.

A. Koopman-Operator-Embedding

Anstatt die nichtlineare Dynamik direkt zu modellieren, wird das System in einen höherdimensionalen Raum von Observablen (Lifting) transformiert.

• Lifting-Funktionen: Es werden zustands- und eingangsabhängige Lifting-Funktionen $\psi(x, u)$ verwendet, die das nichtlineare System in einen endlichdimensionalen, linearen (oder bilinearen) Raum heben.
• Modellform: Im gehobenen Raum ($z = \psi(x)$) verhält sich die Dynamik annähernd linear:
  $$z_{k+1} = A z_k + B \nu(x_k, u_k) + \text{Residuen}$$
  Dies ermöglicht die Nutzung effizienter linearer Propagierungsmethoden.

B. Datengetriebene Identifikation

Da das exakte Modell unbekannt ist, wird der Koopman-Operator direkt aus verrauschten Eingangs-Zustands-Daten ($D = \{u, x\}$) mittels Least-Squares-Regression (EDMD - Extended Dynamic Mode Decomposition) identifiziert.

• Die Matrix $K = [A, B]$ wird durch Minimierung des Fehlers zwischen vorhergesagten und tatsächlichen gehobenen Trajektorien berechnet.

C. Behandlung von Unsicherheiten und Fehlern

Ein kritischer Aspekt ist die rigorose Berücksichtigung aller Fehlerquellen, um formale Sicherheitsgarantien zu gewährleisten. Die erreichbaren Mengen im gehobenen Raum werden durch folgende Komponenten erweitert:

1. Linearisierungsfehler: Da die gehobene Dynamik nur approximativ linear ist, wird ein Restterm $\bar{L}_k$ (basierend auf Taylor-Entwicklung und Hessischen Matrizen) hinzugefügt.
2. Modellierungsfehler (Residuen): Der Fehler zwischen dem gelernten Koopman-Modell und den echten Daten wird über alle verfügbaren Trajektorien berechnet und als Intervall-Zonotop $\mathcal{L}_k$ überapproximiert.
3. Rauschen: Das Prozessrauschen $w_k$ wird in den gehobenen Raum transformiert und durch Lipschitz-Stetigkeit der Lifting-Funktion abgeschätzt ($\mathcal{Z}_{w\psi}$).
4. Abdeckungsradius (Covering Radius): Um sicherzustellen, dass die aus den Daten abgeleiteten Fehlergrenzen auch für Zustände gelten, die nicht direkt in den Trainingsdaten vorkommen, wird ein Abdeckungsradius $\delta$ verwendet. Dies erweitert die Fehlergrenzen auf den gesamten erreichbaren Bereich.

D. Berechnung der Erreichbarkeitsmengen

1. Propagierung: Die Mengen werden im gehobenen Raum unter Verwendung von Zonotopen (Minkowski-Summen und lineare Transformationen) schrittweise vorwärts propagiert.
2. Projektion: Die berechneten Mengen werden zurück in den ursprünglichen Zustandsraum projiziert.
3. Kombination: Die projizierten Mengen werden mit den Unsicherheitsmengen (Modellierungsfehler, Rauschen, Abdeckung) mittels Minkowski-Summe kombiniert, um eine garantierte Überapproximation der wahren erreichbaren Menge zu erhalten.

3. Hauptbeiträge

• Neuer Rahmen: Einführung eines datengetriebenen Erreichbarkeitsframeworks für nichtlineare, nicht-affine Lipschitz-Systeme unter Verwendung von Koopman-Embeddings.
• Zustands-Eingangs-Abhängigkeit: Entwicklung einer Identifikationsmethode mit Lifting-Funktionen, die sowohl vom Zustand als auch vom Eingang abhängen. Dies verbessert die Approximationsgenauigkeit im Vergleich zu Standard-LTI-Modellen (Linear Time-Invariant).
• Formale Garantien: Beweis, dass die berechneten Mengen die wahren erreichbaren Mengen überapproximieren ($\bar{X}_k \subseteq R'_k$), indem alle Fehlerquellen (Rauschen, Linearisierung, Datenlücken) rigoros abgeschätzt werden.
• Skalierbarkeit: Nutzung von Zonotopen ermöglicht eine effiziente Berechnung auch über lange Zeithorizonte.

4. Ergebnisse und Evaluation

Die Methode wurde an drei Szenarien getestet und mit etablierten Methoden (CORA v2025, klassische Least-Squares-Modelle) verglichen:

1. Affines System (CSTR): Ein chemischer Reaktor. Die Koopman-Methode zeigte über lange Horizonte deutlich weniger konservativere (engere) erreichbare Mengen als lineare Datenmodelle.
2. Nicht-affines System: Ein komplexes nichtlineares System. Auch hier lieferte der Ansatz engere Schranken als konkurrierende Methoden, was die Überlegenheit der nichtlinearen Lifting-Funktionen unterstreicht.
3. Reale Anwendung (Autonomes Fahrzeug): Experimente mit einem JetRacer-Rennroboter. Die Ergebnisse bestätigten, dass die Methode in der realen Welt signifikant präzisere Vorhersagen liefert als rein lineare datengetriebene Ansätze, insbesondere bei langen Vorhersagezeiträumen.

5. Bedeutung und Fazit

Das Paper adressiert eine wesentliche Lücke in der Sicherheitsverifikation: Die Notwendigkeit von Methoden, die sowohl datengetrieben (ohne exaktes physikalisches Modell) als auch formal sicher (garantierte Überapproximation) sind, ohne dabei durch übermäßigen Konservatismus unbrauchbar zu werden.

• Innovation: Die Kombination von Koopman-Operatoren mit Zonotopen und einer rigorosen Fehlerabschätzung für den datengetriebenen Kontext ist ein Durchbruch.
• Praktischer Nutzen: Die Methode ermöglicht es Robotikern, Sicherheitsgarantien für komplexe, nichtlineare Systeme zu geben, die in der realen Welt operieren und nur durch Messdaten charakterisiert werden können.
• Zukunft: Die Autoren planen, die Methode auf zeitvariante nichtlineare Systeme zu erweitern.

Zusammenfassend bietet das Paper einen robusten, skalierbaren und weniger konservativen Ansatz für die Sicherheitsanalyse nichtlinearer Systeme, der die Vorteile linearer Analysemethoden mit der Flexibilität datengetriebener Modellierung vereint.