⚡ electrical engineering

Steering with Contingencies: Combinatorial Stabilization and Reach-Avoid Filters

Diese Arbeit stellt einen rechnerisch effizienten Regelungsrahmen vor, der durch die Kombination von Control-Lyapunov-Funktionen und Hamilton-Jacobi-Erreichbarkeitsmengen sicherstellt, dass ein System nicht nur ein Ziel ansteuert, sondern gleichzeitig die Fähigkeit behält, bei Störungen auf mindestens $r$ von $p$ Alternativstandorten auszuweichen, ohne dabei durch kombinatorische Explosion in Echtzeit-Anwendungen zu scheitern.

Ursprüngliche Autoren: Yana Lishkova, Pio Ong, Sander Tonkens, Sylvia Herbert, Aaron D. Ames

Veröffentlicht 2026-04-07

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Yana Lishkova, Pio Ong, Sander Tonkens, Sylvia Herbert, Aaron D. Ames

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stell dir vor, du steckst mitten in einem komplexen Abenteuer: Du bist ein autonomes Fahrzeug, ein Drohnen-Pilot oder sogar ein Astronaut, der gerade landet. Dein Ziel ist klar: Du willst sicher an einem bestimmten Ort ankommen (z. B. auf einer Landebahn oder an einer Ladestation).

Aber das Leben ist voller Überraschungen. Was passiert, wenn plötzlich ein Hindernis auftaucht? Oder wenn der Akku schwächer wird? Ein normaler Steuerungsalgorithmus würde stur auf sein Ziel zusteuern und könnte dabei in eine Sackgasse oder einen Unfall geraten.

Dieser Paper beschreibt eine intelligente „Notfall-Planungs-Strategie", die sicherstellt, dass du nicht nur dein Ziel erreichst, sondern immer mehrere Auswege offen hältst.

Hier ist die Idee, einfach erklärt mit ein paar bildhaften Vergleichen:

1. Das Problem: Der „Blinde" Weg

Stell dir vor, du fährst durch eine Stadt mit einem Navi, das dir nur den kürzesten Weg zu einem Ziel zeigt. Plötzlich siehst du eine Baustelle. Wenn du stur weiterfährst, landest du in der Sackgasse. Du hättest gerne gewusst: „Hey, ich bin zwar auf dem Weg zu Ziel A, aber ich muss sicherstellen, dass ich immer noch zu Ziel B oder C kommen kann, falls etwas schiefgeht."

Frühere Methoden waren wie ein riesiges, kompliziertes Labyrinth: Um zu prüfen, ob du zu irgendeinem von 10 Zielen (oder sogar zu 3 davon gleichzeitig) kommen kannst, müsste der Computer jede denkbare Kombination durchrechnen. Das wäre wie der Versuch, alle möglichen Wege durch ein riesiges Schloss zu Fuß zu erkunden – das dauert zu lange für eine echte Entscheidung in Echtzeit.

2. Die Lösung: Der „Rettungsring"-Filter

Die Autoren haben einen cleveren Trick entwickelt, den sie „Combinatorial Stabilization" (Kombinatorische Stabilisierung) nennen. Stell dir das wie einen intelligenten Sicherheitsgurt vor, der nicht nur deinen Körper hält, sondern auch sicherstellt, dass du immer in der Nähe von mindestens r Rettungsinseln bist.

Statt alle Kombinationen durchzurechnen, nutzen sie zwei magische Werkzeuge:

Der CLF-Filter (Der „Sicherheitsball"):
Stell dir vor, um jedes mögliche Ziel gibt es eine unsichtbare, schützende Blase (eine „Attraktionsregion"). Solange du in dieser Blase bist, kannst du sicher zum Ziel fliegen. Der neue Filter sorgt dafür, dass du dich zwar zu deinem gewählten Ziel bewegst, aber niemals aus der Blase von mindestens r anderen Zielen herausfliegst.
- Die Metapher: Es ist wie ein Tanz, bei dem du dich zu deinem Partner drehst, aber gleichzeitig immer in Reichweite von drei anderen Partnern bleibst, falls der Tanzpartner ausfällt.
Der HJR-Filter (Der „Zeit-Timer"):
Manchmal hast du nicht unendlich Zeit (z. B. weil der Treibstoff knapp wird). Hier wird die Blase kleiner, je mehr Zeit vergeht. Der Filter berechnet nicht nur, wo du bist, sondern auch, wie viel Zeit du noch hast, um sicher zu landen. Er sorgt dafür, dass du auch mit schrumpfender Zeit immer noch r sichere Landeplätze erreichen kannst.
- Die Metapher: Stell dir vor, du hast eine brennende Kerze. Je kürzer die Kerze wird, desto kleiner wird der Bereich, in dem du sicher sein kannst. Der Filter sorgt dafür, dass du immer noch in der Nähe von mindestens zwei anderen Kerzen bist, falls deine eigene ausgeht.

3. Der große Vorteil: Einfachheit statt Komplexität

Das Geniale an dieser Methode ist, dass sie den „Rechen-Explosion"-Effekt verhindert.

Alt: Um zu prüfen, ob du zu 3 von 10 Zielen kommen kannst, müsste der Computer 120 verschiedene Szenarien berechnen.
Neu: Der Filter braucht nur 11 einfache Regeln (p + 1), um das Gleiche zu erreichen.

Das ist wie der Unterschied zwischen dem Versuch, jeden einzelnen Weg durch einen Wald zu Fuß zu messen, und dem Nutzen eines Hubschraubers, der sofort sieht: „Solange ich über diesem grünen Bereich fliege, habe ich immer drei sichere Landeplätze in Sicht."

4. Was bringt das in der Praxis?

Die Autoren haben das an zwei Beispielen getestet:

Ein einfaches Robotersystem: Es zeigte, dass das System sicher zu einem Ziel fährt, aber sofort umschwenken kann, wenn ein Hindernis auftaucht, ohne zu crashen, weil es immer noch „Ziel 2" und „Ziel 3" im Hinterkopf hatte.
Ein Flugzeug: Ein Flugzeug muss zwischen Gebäuden hindurchfliegen, um auf einer von 6 Landebahnen zu landen. Wenn der Treibstoff knapp wird, schrumpft der sichere Bereich. Der Filter sorgt dafür, dass das Flugzeug nicht nur auf die eine Landebahn zusteuert, sondern sicherstellt, dass es immer noch mindestens zwei andere Landebahnen erreichen kann. Wenn die geplante Landebahn plötzlich blockiert ist, kann es sofort und sicher auf eine der anderen ausweichen.

Zusammenfassung

Dieses Paper ist wie ein Notfall-Planungs-Assistent für Roboter. Er sagt: „Fahre zwar auf dein Ziel zu, aber halte immer mindestens r andere Fluchtwege offen." Und das Beste: Er macht das so schnell und einfach, dass es in Echtzeit funktioniert, ohne dass der Computer überhitzt. Es ist der Unterschied zwischen „Hoffen, dass alles gut geht" und „Sicherstellen, dass es immer einen Plan B, C und D gibt".

1. Problemstellung

In autonomen Systemen (z. B. autonome Landung von Raumfahrzeugen oder Drohnen, Navigation von Fahrzeugen) ist es oft entscheidend, nicht nur ein aktives Ziel anzusteuern, sondern gleichzeitig die Fähigkeit zu bewahren, im Falle von Gefahren oder Ressourcenmangel (z. B. Batterieentladung) auf alternative Ziele ausweichen zu können.

Das Kernproblem besteht darin, ein System so zu steuern, dass es asymptotisch zu einem ausgewählten Ziel (Target) konvergiert, während sichergestellt wird, dass zu jedem Zeitpunkt entlang der Trajektorie mindestens $r$ von $p$ potenziellen Alternativzielen (Kandidaten) noch erreichbar sind.

Herausforderung: Naive Formulierungen dieses „ $r$ -out-of- $p$ "-Anforderungsprofils sind rechnerisch nicht handhabbar, da sie alle möglichen Kombinationen von $r$ Zielen aus $p$ Kandidaten berücksichtigen müssten (kombinatorische Explosion).
Ziel: Entwicklung von handhabbaren (tractable) Kontrollfiltern, die diese kombinatorische Sicherheit gewährleisten, ohne die Echtzeitfähigkeit zu verlieren.

2. Methodik

Die Autoren erweitern bestehende Ansätze der Kontrolltheorie (Control Lyapunov Functions - CLFs und Control Barrier Functions - CBFs) sowie der Hamilton-Jacobi-Reichbarkeitsanalyse (HJR), um kombinatorische Logik effizient zu integrieren.

A. Kombinatorische Stabilisierung (CLF-basiert)

Für Probleme mit unendlichem Zeithorizont (Stabilisierung):

Konzept: Es werden für jedes der $p$ Gleichgewichtspunkte lokale CLFs ( $V_j$ ) definiert, die ihre jeweiligen Einzugsbereiche (Regions of Attraction, $R_j$ ) beschreiben.
Kombinatorische Region: Die Menge der Zustände, von denen aus mindestens $r$ der $p$ Ziele erreichbar sind, wird als kombinatorische Einzugsbereichs-Menge $\tilde{R}$ definiert.
Umsetzung: Die CLFs werden in CBFs umgewandelt ( $h_j(x) = c_j - V_j(x)$ ). Anstatt alle $p$ Barrieren gleichzeitig zu erzwingen (UND-Verknüpfung), wird eine kombinatorische Pivot-Funktion $\tilde{h}(x)$ eingeführt, die den $r$ -ten größten Wert der $h_j$ -Werte zurückgibt.
Optimierung: Ein quadratisches Programm (QP) wird gelöst, das eine nominale Steuerung minimiert, während es die CLF-Bedingung für das gewählte Ziel und die kombinatorische CBF-Bedingung für $\tilde{R}$ erfüllt.
Schlüsselinnovation: Durch die Einführung einer Hilfsvariable ( $\omega$ ) und einer Relaxation wird sichergestellt, dass das QP mit nur $p+1$ Nebenbedingungen lösbar ist, anstatt exponentiell viele Kombinationen zu prüfen. Dies verhindert die kombinatorische Explosion.

B. Kombinatorische Zielerreichung (HJR-basiert)

Für Probleme mit endlichem Zeithorizont oder Ressourcenverbrauch (z. B. Treibstoff):

Konzept: Hier werden Hamilton-Jacobi-Rückwärts-Erreichbarkeits-Set (Backward Reach-Avoid Sets, BRA) verwendet. Diese Sets definieren Zustände, von denen aus ein Ziel innerhalb eines Zeitfensters $\tau$ sicher erreicht werden kann, ohne Hindernisse zu berühren.
Dynamik: Da sich die erreichbaren Sets mit fortschreitender Zeit und Ressourcenverbrauch verkleinern, wird ein dynamischer Feedback-Controller benötigt, der innere Zustände (für die verbleibende Zeit $\tau$ ) verwaltet.
Umsetzung: Ähnlich wie bei den CLFs werden die BRA-Sets durch eine kombinatorische Funktion $\tilde{h}(x, \tau)$ (basierend auf den $r$ -ten größten Wert der Reach-Avoid-Wertfunktionen) charakterisiert.
Filter: Ein QP-Filter wird entworfen, das die Erreichung des gewählten Ziels innerhalb des Horizonts garantiert, während die Trajektorie innerhalb des kombinatorischen BRA-Sets $\tilde{R}(\tau)$ bleibt.

3. Wichtige Beiträge

Formalisierung des kombinatorischen Notwendigkeitsprinzips: Die Arbeit definiert mathematisch präzise, was „Steering with Contingencies" bedeutet (asymptotische Stabilität eines Ziels bei gleichzeitiger Invarianz einer kombinatorischen Menge von $r$ -out-of- $p$ Alternativen).
Vermeidung der kombinatorischen Explosion: Der wichtigste algorithmische Beitrag ist die Entwicklung von Filtern, die nur $p+1$ lineare Nebenbedingungen benötigen, um die komplexe Logik „mindestens $r$ von $p$ " zu erfüllen. Dies ermöglicht Echtzeit-Implementierungen.
Zwei komplementäre Frameworks:
- Ein CLF-basierter Ansatz für Stabilisierungsprobleme.
- Ein HJR-basierter Ansatz für zeitbegrenzte Probleme mit schrumpfenden erreichbaren Mengen.
Beweis der Stetigkeit und Sicherheit: Es wird gezeigt, dass die resultierenden Controller stetig sind (unter Slater-Bedingungen) und dass das System garantiert innerhalb der sicheren kombinatorischen Mengen bleibt, was einen sicheren Wechsel zwischen Zielen ermöglicht.

4. Ergebnisse und Simulationen

Die Autoren validieren den Ansatz an zwei Beispielen:

Beispiel 1 (Lineares System, CLF-basiert):
- Ein System mit 3 Zielen und 3 Hindernissen.
- Ergebnis: Der gefilterte Controller hält das System innerhalb der Einzugsbereiche von mindestens 2 Zielen ( $r=2$ ), während es zum Ziel 1 steuert. Ein Wechsel zum Ziel 2 bei $t=0.5s$ ist sicher möglich, da das System bereits im gemeinsamen sicheren Bereich war. Die unfilterte (nominale) Steuerung kollidiert mit Hindernissen.
- Beobachtung: Das System „schmiegt" sich an die Grenzen der sicheren Mengen, um die Kontingenz zu wahren.
Beispiel 2 (Flugzeuglandung, HJR-basiert):
- Ein vereinfachtes Flugzeugmodell, das zwischen Gebäuden zu einem von 6 Landebahnen navigiert.
- Ergebnis: Der Filter berücksichtigt schrumpfende Zeitfenster (durch Ressourcenverbrauch).
  - Ohne Kontingenz ( $r=0$ ) kollidiert das Flugzeug.
  - Mit $r=2$ Kontingenzzielen bleibt das Flugzeug so lange in der Nähe von zwei Landebahnen, bis eine Landung möglich ist.
  - Wenn das ursprüngliche Ziel aufgrund von Zeitmangel nicht mehr erreichbar ist, schaltet der Filter nahtlos auf ein alternatives Ziel um, ohne die Sicherheit zu gefährden.
- Die Simulationen zeigen, dass die Wertfunktionen (sowohl für das Ziel als auch die Pivot-Funktion) entlang der Trajektorie nicht-negativ bleiben, was die Sicherheit zertifiziert.

5. Bedeutung und Ausblick

Praktische Relevanz: Die Methode löst ein fundamentales Problem in der autonomen Sicherheit: Wie man Flexibilität und Notfallplanung (Contingency Planning) in Echtzeit-Steuerungsalgorithmen integriert, ohne die Rechenleistung zu überlasten.
Skalierbarkeit: Durch die Reduktion auf $p+1$ Constraints ist der Ansatz skalierbar für Systeme mit vielen potenziellen Zielen, was bei früheren MIP-Ansätzen (Mixed-Integer Programming) oder naiven Logik-Verknüpfungen nicht der Fall war.
Zukunft: Die Autoren sehen zukünftige Arbeiten in der Behandlung von Störungen (Robustheit) und der rigorosen Behandlung der Nicht-Glattheit (Nonsmoothness) der HJR-Wertfunktionen, da diese in der Praxis oft nur als Viskositätslösungen vorliegen.

Zusammenfassend bietet das Paper einen mathematisch fundierten und rechnerisch effizienten Rahmen, um autonome Systeme nicht nur sicher zu einem Ziel zu führen, sondern ihnen auch die notwendige Flexibilität zu geben, auf unvorhergesehene Änderungen der Umgebung oder des Systemzustands zu reagieren.