Differentiable Invariant Sets for Hybrid Limit Cycles with Application to Legged Robots

Diese Arbeit stellt eine dreistufige Methode zur Berechnung und formalen Verifikation einer vorwärtsinvarianten Menge um einen hybriden Grenzzyklus eines bipedalen Roboters vor, die mittels einer JAX-basierten Bibliothek und einer zweistufigen Optimierung verwendet wird, um einen Tracking-Regler zu entwerfen, der die Größe dieser invarianten Menge maximiert.

Das Wesentliche

Das große Ziel: Roboter, die nicht stolpern

Stellen Sie sich einen Roboter vor, der wie ein Mensch auf zwei Beinen läuft. Das ist eine riesige Herausforderung für die Mathematik. Warum? Weil der Roboter ständig zwischen zwei Zuständen wechselt:

1. Laufen: Die Beine bewegen sich flüssig durch die Luft.
2. Aufprall: Der Fuß trifft den Boden. Das ist ein plötzlicher, harter "Knall", der die Bewegung sofort verändert.

In der Technik nennen wir das ein hybrides System (eine Mischung aus fließender Bewegung und plötzlichen Sprüngen). Die Forscher wollen wissen: Wie stark kann dieser Roboter wackeln oder vom Weg abkommen, bevor er hinfällt?

Die Antwort darauf ist ein sicherer Bereich (in der Mathematik ein "invarianter Satz"). Wenn der Roboter innerhalb dieses Bereichs ist, wird er automatisch wieder zurück zum stabilen Gang finden, egal wie sehr man ihn schubst.

Das Problem: Die alten Methoden sind zu langsam

Früher haben Wissenschaftler versucht, diese sicheren Bereiche zu berechnen. Das war aber wie der Versuch, einen ganzen Ozean mit einem kleinen Eimer auszupumpen.

• Die alten Methoden (wie "Sum-of-Squares") waren extrem rechenintensiv.
• Sie funktionierten nur bei sehr einfachen, kleinen Robotern.
• Bei komplexeren Robotern (wie einem echten Laufroboter) brachen die Computer vor lauter Rechnen zusammen oder brauchten Tage für eine einzige Antwort.

Die neue Lösung: Ein "Gummiband"-Modell

Die Autoren dieses Papiers haben eine clevere neue Methode entwickelt, die schnell, präzise und anpassbar ist. Hier ist die Analogie, wie sie es gemacht haben:

1. Der "Gummiband"-Koffer (Die Normotope)

Stellen Sie sich vor, Sie packen den Roboter in einen unsichtbaren, elastischen Koffer aus Gummiband.

• Wenn der Roboter läuft, dehnt sich dieser Koffer mit ihm mit.
• Die Forscher berechnen nicht jeden einzelnen Punkt im Koffer, sondern nur die Hülle (die Grenzen).
• Das ist wie wenn Sie sagen: "Solange der Ball innerhalb dieser unsichtbaren Box bleibt, ist er sicher."

2. Der "Sprung" durch den Boden (Hybride Dynamik)

Das Schwierige ist der Moment, wenn der Fuß den Boden berührt.

• Der Koffer trifft auf eine unsichtbare Wand (den "Guard").
• In diesem Moment wird der Koffer nicht einfach weitergeschoben, sondern er wird zusammengedrückt und neu geformt (durch die "Reset-Map").
• Die neue Methode kann genau berechnen, wie sich dieser Koffer beim Aufprall verformt, ohne den ganzen Koffer Punkt für Punkt zu simulieren.

3. Der "Sicherheits-Check" (Forward Invariance)

Das Geniale an ihrer Methode ist der folgende Test:

• Sie lassen den Koffer einen kompletten Schritt laufen (Luftphase + Aufprall).
• Am Ende des Schritts schauen sie: Passt der neue Koffer noch komplett in den alten Koffer?
• Wenn ja: Super! Der Roboter ist sicher. Selbst wenn er am Anfang des Schritts etwas aus der Mitte gerutscht ist, wird er am Ende wieder in den sicheren Bereich zurückfallen.
• Wenn nein: Der Koffer ist zu groß geworden, der Roboter könnte fallen.

Der Clou: Der "selbstoptimierende" Koffer

Die Forscher haben noch einen weiteren Trick im Ärmel. Da ihre Methode auf moderner Software (JAX) basiert, ist sie differenzierbar. Das klingt kompliziert, ist aber einfach gesagt: Der Computer kann "fühlen", wie sich Änderungen auswirken.

• Das Problem: Der anfängliche Koffer war vielleicht nicht optimal geformt.
• Die Lösung: Sie haben einen Algorithmus geschrieben, der den Koffer immer wieder neu formt und die Regler des Roboters (die "Muskelsteuerung") justiert.
• Das Ergebnis: Der Algorithmus hat den sicheren Bereich um das 4,25-fache vergrößert!
  • Vorher: Der Roboter musste sehr perfekt laufen, sonst fiel er.
  • Nachher: Der Roboter kann viel stärker wackeln, stolpern oder vom Kurs abkommen und trotzdem wieder stabil laufen.

Warum ist das wichtig? (Die Analogie zum Autofahren)

Stellen Sie sich vor, Sie fahren ein Auto.

• Die alte Methode war wie ein Fahrlehrer, der Ihnen sagt: "Fahren Sie nur auf dieser einen, winzigen Linie, sonst stürzen Sie." Das ist sicher, aber unpraktisch.
• Die neue Methode ist wie ein moderner Fahrerassistent, der Ihnen sagt: "Sie können ruhig mal 2 Meter nach links oder rechts ausweichen, das Auto wird sich selbst korrigieren."

Zusammenfassung für den Alltag

Die Forscher haben einen neuen, schnellen Weg gefunden, um zu berechnen, wie "robust" ein laufender Roboter ist.

1. Sie nutzen eine Art elastische Hülle, um den möglichen Bewegungsbereich zu umreißen.
2. Sie berechnen genau, wie sich diese Hülle beim Aufprall auf den Boden verformt.
3. Sie nutzen die Rechenkraft moderner Computer, um den Roboter so zu steuern, dass dieser sichere Bereich maximal groß wird.

Das Ergebnis: Roboter, die nicht nur laufen, sondern stolperfest sind. Und das alles in Sekunden statt in Tagen. Das ist ein riesiger Schritt hin zu Robotern, die wirklich in unserer Welt herumlaufen können, ohne ständig umzufallen.

Technische Zusammenfassung

1. Problemstellung

Die Analyse der Robustheit nichtlinearer dynamischer Systeme erfolgt häufig durch die Untersuchung invarianter Mengen, die einen Grenzzyklus (Limit Cycle) enthalten. Bei hybriden Systemen, die sowohl kontinuierliche Dynamik als auch diskrete Übergänge (z. B. durch Kontakt oder Stöße) aufweisen, ist die genaue Charakterisierung dieser Mengen jedoch besonders schwierig.

• Herausforderungen: Bestehende Methoden wie Sum-of-Squares (SoS)-Programmierung oder Hamilton-Jacobi (HJ)-Formulierungen leiden unter der „Fluch der Dimensionalität" (curse of dimensionality). SoS skaliert schlecht mit der Systemdimension (oft auf <10 Zustände beschränkt), und HJ-Methoden haben eine exponentielle Komplexität.
• Ziel: Es wird eine skalierbare, effiziente und differenzierbare Methode benötigt, um überapproximierende, vorwärts-invariante Mengen für hybride periodische Orbits in hochdimensionalen Systemen (wie beinbasierten Robotern) zu berechnen und für das Reglerdesign zu nutzen.

2. Methodik

Die Autoren erweitern den Ansatz der parametrischen Erreichbarkeitsanalyse (basierend auf dem Tool immrax und JAX) auf hybride Systeme. Der Kern der Methode besteht aus einem dreistufigen Prozess:

A. Hybrides Systemmodell

Das System wird als autonomes hybrides System mit kontinuierlichem Fluss $\dot{x} = f(x, u)$ und einem diskreten Reset-Mapping $\Delta$ bei Erreichen einer Guard-Oberfläche $S$ modelliert. Die Stabilität wird über eine „Step-to-Step"-Abbildung $F$ (eine Verallgemeinerung der Poincaré-Abbildung) analysiert.

B. Parametrische Einbettung und Normotope

Statt exakter Trajektorien werden $\ell_2$-Normotope (ellipsoide Mengen) verwendet, um den Erreichbarkeitsbereich zu überapproximieren.

• Lineare Inklusionen: Die Dynamik wird durch lineare Inklusionen (basierend auf Intervallanalyse und gemischten Jacobi-Matrizen) gebunden.
• Einbettungssystem: Ein parametrisches Einbettungssystem wird definiert, das den Mittelpunkt $\bar{x}$, die Formmatrix $\alpha$ und den Offset $y$ des Normotops entwickelt. Dies garantiert, dass alle Trajektorien innerhalb des berechneten Rohrs (Tube) bleiben.

C. Verifikation der Invarianz (Theorem 1 & 2)

Um zu beweisen, dass ein solches Rohr vorwärts-invariant ist, wird ein dreistufiger Algorithmus angewendet:

1. Kontinuierlicher Fluss: Das Normotop wird vom Startpunkt bis weit über die Guard-Oberfläche hinaus simuliert.
2. Schnittanalyse: Es wird katalogisiert, wann und wo das Normotop die Guard-Oberfläche schneidet. Mithilfe von Lemma 1 wird der Schnitt eines $n$-dimensionalen Ellipsoids mit einer affinen Hyperebene als $(n-1)$-dimensionales Ellipsoid dargestellt.
3. Reset-Mapping: Die Schnittpunkte werden durch die Reset-Map $\Delta$ geführt. Theorem 2 liefert eine obere Schranke für den Verstärkungsfaktor $\gamma$.
4. Bedingung: Wenn der resultierende Satz nach einem Schritt eine strikte Teilmenge des ursprünglichen Satzes ist ($\gamma \leq 1$), ist die Menge vorwärts-invariant.

D. Differenzierbarkeit und Optimierung

Ein entscheidender Vorteil ist die Differenzierbarkeit des gesamten Prozesses dank der Nutzung von JAX. Dies ermöglicht es, den Verstärkungsfaktor $\gamma$ bezüglich der Systemparameter und Reglergewinne zu differenzieren.

• Bilevel-Optimierung: Ein Regler wird so entworfen, dass die Größe des invarianten Satzes maximiert wird. Dies geschieht durch Gradientenabstieg auf den Reglergewinnen $K$ und eine Bisektions-Suche für die Skalierung des Startellipsoids.

3. Wichtige Beiträge

1. Theoretische Erweiterung: Erweiterung der Theorie der parametrischen Erreichbarkeit auf hybride Systeme, um Bedingungen für die Vorwärtsinvarianz von parametrischen Erreichbarkeitsmengen zu identifizieren.
2. Effiziente Verifikationsprozedur: Einführung eines Verfahrens zur effizienten Verifikation der Vorwärtsinvarianz unter Verwendung von Intervallanalyse und linearen Inklusionen, das Skalierbarkeit für hochdimensionale Systeme bietet.
3. Anwendung auf Reglerdesign: Demonstration der Methode an einem vereinfachten planaren Zweibein-Läufer (Bipedal Walker). Die Differenzierbarkeit wird genutzt, um einen Tracking-Regler in einem bilevel-Optimierungsrahmen zu entwerfen, der die Größe des invarianten Satzes maximiert.

4. Ergebnisse

Die Methode wurde an einem vereinfachten planaren Zweibein-Modell (inspiriert vom Compass-Gait-Walker, aber mit teleskopischem Bein) getestet.

• Invarianz-Verifikation: Ein hybrider invariantier Schlauch wurde berechnet und durch Monte-Carlo-Simulationen (100 Trajektorien über 15 Schritte) empirisch verifiziert. Alle Trajektorien blieben innerhalb der berechneten Grenzen.
• Reglerdesign: Durch die Optimierung der Reglergewinne mittels Gradientenabstieg (unter Nutzung der automatischen Differentiation) konnte die Größe des invarianten Satzes um einen Faktor von 4,25 erhöht werden.
• Recheneffizienz: Die Berechnung des Erreichbarkeitsbereichs für das 4-dimensionale System dauerte insgesamt 19,56 Sekunden (davon 4,55 s für JIT-Kompilierung).
  • Zum Vergleich: SoS-Methoden benötigten für ein ähnliches Problem ca. 17,7 Minuten, und HJ-Methoden ca. 36 Stunden. Dies unterstreicht die Überlegenheit in Bezug auf Skalierbarkeit und Geschwindigkeit.

5. Bedeutung und Ausblick

• Skalierbarkeit: Die Arbeit zeigt, dass Erreichbarkeitsanalysen für hybride Systeme in höheren Dimensionen praktikabel werden, wenn Intervallanalyse und moderne Hardware-Beschleunigung (JAX) genutzt werden.
• Integration in das Design: Die Differenzierbarkeit der Invarianz-Bedingung erlaubt eine direkte Integration der Robustheitsanalyse in den Reglerentwurf (Reachability-guided Control Design), was bisher aufgrund der Nicht-Differenzierbarkeit vieler Methoden schwierig war.
• Limitationen: Die Methode erfordert, dass die Guard-Oberfläche in den gewählten Koordinaten linear ist (was hier durch eine Koordinatentransformation erreicht wurde). Zudem ist die Überapproximation konservativ. Zukünftige Arbeiten sollen diese Konservativität durch verfeinerte Einbettungssysteme reduzieren und die Methode auf komplexere, realistischere Robotermodelle anwenden.

Fazit: Das Paper stellt einen bedeutenden Schritt dar, um formale Garantien für die Robustheit hybrider robotischer Systeme (insbesondere bei Kontakt) effizient zu berechnen und diese Garantien aktiv zur Optimierung der Systemleistung zu nutzen.