⚡ electrical engineering

Scalable Verification of Neural Control Barrier Functions Using Linear Bound Propagation

Die Autoren stellen einen skalierbaren Verifikationsrahmen für neuronale Kontrollbarrierefunktionen vor, der auf linearer Schrankenpropagation und McCormick-Relaxation basiert, um durch adaptive Verfeinerung die Rechenkosten zu senken und größere Netzwerke zu ermöglichen.

Ursprüngliche Autoren: Nikolaus Vertovec, Frederik Baymler Mathiesen, Thom Badings, Luca Laurenti, Alessandro Abate

Veröffentlicht 2026-04-15

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Nikolaus Vertovec, Frederik Baymler Mathiesen, Thom Badings, Luca Laurenti, Alessandro Abate

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

Das große Problem: Der "Blackbox"-Fahrer

Stell dir vor, du hast einen hochintelligenten, selbstlernenden Roboter-Fahrer (ein neuronales Netzwerk), der ein Auto steuern soll. Dieser Roboter ist extrem gut darin, komplexe Situationen zu meistern, weil er wie ein Mensch aus Erfahrung lernt. Aber es gibt ein riesiges Problem: Niemand weiß genau, wie er im Kopf denkt.

Wenn wir diesen Roboter auf die Straße lassen, müssen wir zu 100 % sicher sein, dass er niemals gegen eine Wand fährt oder einen Fußgänger umfährt. In der Technik nennen wir das "Sicherheitszertifizierung".

Das Problem ist: Um zu beweisen, dass dieser Roboter sicher ist, müssen wir jede einzelne seiner Entscheidungen mathematisch nachrechnen. Da er aber so komplex ist (wie ein riesiges Labyrinth aus Millionen von Schalter), dauert das Nachrechnen mit den bisherigen Methoden so lange, dass man nur ganz kleine, dumme Roboter testen kann. Große, intelligente Roboter bleiben ungetestet – und das ist gefährlich.

Die alte Methode: Der langsame Detektiv

Bisher haben Wissenschaftler versucht, die Sicherheit zu beweisen, indem sie wie Detektive jeden einzelnen Pfad im Labyrinth des Roboters einzeln abgegangen sind (man nennt das "SMT-Löser").

Das Problem: Stell dir vor, du willst prüfen, ob ein riesiges Schloss sicher ist. Die alte Methode wäre, jeden einzelnen Schlüssel einzeln auszuprobieren. Bei einem kleinen Schloss geht das schnell. Bei einem riesigen Schloss mit Millionen Schlüsseln würdest du ewig brauchen.
Das Ergebnis: Man konnte nur sehr einfache Roboter sicher machen.

Die neue Methode: Die "Karten-Methode" (Lineare Bound Propagation)

Die Autoren dieses Papiers haben eine geniale neue Idee entwickelt. Statt jeden einzelnen Pfad im Labyrinth zu prüfen, zeichnen sie grobe Karten (Lineare Grenzen) über das gesamte Gebiet.

Hier ist die Analogie:

Die grobe Schätzung (Lineare Bound Propagation):
Stell dir vor, du musst prüfen, ob ein Berg (die Entscheidung des Roboters) immer über dem Meeresspiegel liegt. Statt jeden einzelnen Stein auf dem Berg zu vermessen, zeichnest du eine untere Linie (eine gerade Platte), die garantiert unter dem Berg liegt, und eine obere Linie, die garantiert über dem Berg liegt.
- Wenn deine untere Linie schon über dem Meeresspiegel liegt, weißt du sofort: "Der ganze Berg ist sicher!" Du musst den Berg nicht mehr einzeln vermessen.
- Das ist viel schneller, weil gerade Linien viel einfacher zu berechnen sind als krumme Berge.
Das Verfeinern (Adaptive Verfeinerung):
Manchmal ist die grobe Karte zu ungenau. Vielleicht liegt die untere Linie knapp unter dem Meeresspiegel, aber der Berg selbst ist trotzdem hoch genug.
- Hier kommt der Clou: Die Autoren schneiden die Karte in kleine Stücke (Dreiecke, wie bei einem Puzzle).
- In den Bereichen, wo es "unklar" ist, schneiden sie die Karte in immer kleinere Stücke und zeichnen dort neue, passgenauere Linien.
- In den sicheren Bereichen lassen sie die Karte grob.
- Das ist wie bei Google Maps: Du siehst die ganze Welt auf einem kleinen Bildschirm, aber wenn du in eine Stadt zoomst, werden die Straßen detaillierter.
Der "Sicherheits-Filter" (Control Barrier Functions):
Der Roboter hat eine unsichtbare Mauer um den sicheren Bereich gezogen. Die Aufgabe der Wissenschaftler ist es zu beweisen, dass der Roboter diese Mauer nie überschreitet, egal wie schnell er fährt oder wie das Wetter ist. Die neue Methode berechnet diese Mauer so, dass sie auch dann funktioniert, wenn der Roboter "knifflige" Funktionen benutzt (nicht nur einfache Schalter, sondern auch komplexe Kurven).

Warum ist das so wichtig?

Geschwindigkeit: Die neue Methode ist wie ein Turbo. Sie kann Roboter mit viel mehr "Gehirn" (mehr Neuronen) prüfen als alle bisherigen Methoden.
Flexibilität: Sie funktioniert mit fast jeder Art von "Denkweise" des Roboters, nicht nur mit den einfachsten.
Sicherheit: Durch das Aufteilen in kleine Puzzleteile (Dreiecke) wird die Prüfung so genau, dass man sich wirklich sicher sein kann, ohne ewig zu warten.

Zusammenfassung in einem Satz

Die Autoren haben eine Methode entwickelt, die komplexe, unsichere KI-Systeme nicht mehr einzeln abhakt, sondern sie mit cleveren, sich selbst verfeinernden "Karten" umhüllt, um blitzschnell zu beweisen, dass sie sicher sind – und zwar auch für die größten und intelligentesten Roboter.

Das ist ein riesiger Schritt, damit wir bald wirklich autonome Autos und Roboter haben, die nicht nur schnell sind, sondern auch mathematisch beweisbar sicher.

1. Problemstellung

Die Sicherheitsverifikation autonomer Steuerungssysteme (z. B. Drohnen, Roboter) ist entscheidend für ihren Einsatz in realen Umgebungen. Eine etablierte Methode zur Sicherstellung der Sicherheit ist die Verwendung von Control Barrier Functions (CBFs), die sicherstellen, dass der Systemzustand innerhalb einer definierten „sicheren Menge" bleibt.

In jüngerer Zeit haben Neuronale CBFs (CBFs, die als neuronale Netze trainiert werden) an Popularität gewonnen, da sie aufgrund ihrer Ausdruckskraft (Expressivität) komplexe, nichtlineare Dynamiken und Sicherheitsbeschränkungen handhaben können. Ein Hauptproblem besteht jedoch in der post-hoc Verifikation: Es muss mathematisch bewiesen werden, dass ein trainiertes neuronales Netz tatsächlich eine gültige CBF ist.

Herausforderung: Herkömmliche Verifikationsmethoden basieren oft auf SMT-Solvern (Satisfiability Modulo Theories) oder gemischt-ganzzahliger Programmierung (MIP). Diese Methoden skalieren schlecht mit der Größe des neuronalen Netzes und der Dimensionalität des Zustandsraums.
Einschränkung bestehender Ansätze: Viele effiziente Ansätze sind auf Netzwerke mit ReLU-Aktivierungsfunktionen beschränkt, da diese die Gradientenberechnung vereinfachen. Für allgemeine nichtlineare Aktivierungsfunktionen (wie Tanh oder Sigmoid), die für komplexe Probleme oft notwendig sind, fehlen skalierbare Verifikationsverfahren.

2. Methodik

Die Autoren schlagen einen neuen, skalierbaren Rahmen vor, der auf Linear Bound Propagation (LBP) und McCormick-Relaxation basiert, um die Verifikation von neuronalen CBFs zu beschleunigen.

Kernkomponenten der Methode:

Erweiterung der Linearen Bound Propagation (LBP):
- Traditionelle LBP berechnet obere und untere Schranken für die Ausgaben eines neuronalen Netzes über einem Eingabebereich.
- Die Autoren erweitern dies, um auch Schranken für die Gradienten (Jacobi-Matrix) des Netzes zu berechnen. Dies ist essenziell, da die CBF-Bedingung die Lie-Ableitung (die den Gradienten der CBF mit der Systemdynamik verknüpft) enthält.
- Anstatt einen zusätzlichen Vorwärtsdurchlauf durchzuführen, nutzen sie eine rekursive Berechnung, die die Bilinearität der Produktterme in der Kettenregel durch McCormick-Relaxationen approximiert. Dies ermöglicht die Berechnung linearer Schranken für $\nabla B_\theta(x)$ .
Lineare Surrogate für die CBF-Bedingung:
- Die CBF-Bedingung (Gleichung 2 im Paper) ist nichtlinear und enthält Supremum-Terme über die Steuereingaben $u$ .
- Durch die Kombination der linearen Schranken für das Netz $B_\theta(x)$ , seine Gradienten und die Systemdynamik $f(x), g(x)$ (die ebenfalls durch Taylor-Entwicklungen linearisiert werden) wird die ursprüngliche nichtlineare Verifikationsformel $\phi$ in ein konservatives lineares Surrogat $\phi_{linear}$ umgewandelt.
- Wenn $\phi_{linear}$ erfüllt ist, ist garantiert, dass auch die ursprüngliche nichtlineare Bedingung erfüllt ist.
Adaptive Verfeinerungsstrategie (Refinement):
- Lineare Schranken sind über großen Domänen oft zu konservativ (zu locker), was zu unentscheidbaren Ergebnissen führt.
- Um dies zu lösen, wird der Zustandsraum nicht in Hyperrechtecke, sondern in ein simpliciales Gitter (Simplexe) unterteilt.
- Die Verifikation wird für jedes Simplex durchgeführt. Wenn das Ergebnis unentscheidbar ist, wird das Simplex entlang seiner längsten Kante geteilt (Splitting).
- Dieser Prozess ist parallelisierbar und nutzt GPUs effizient, um viele Regionen gleichzeitig zu verarbeiten.

3. Wichtige Beiträge

Neue Verifikationsmethode: Einführung einer Technik zur Verifikation neuronaler Barrierenfunktionen mittels LBP und McCormick-Relaxation. Dies eliminiert die Notwendigkeit rechenintensiver SMT-Solver und ermöglicht die Verifikation größerer Netze.
Gradienten-Bound-Propagation: Entwicklung einer Methode zur Berechnung linearer Schranken für die Gradienten neuronaler Netze, die für beliebige semidifferenzierbare Aktivierungsfunktionen gilt (nicht nur ReLU).
Skalierbare Verfeinerung: Entwicklung einer parallelisierbaren Strategie, die den Zustandsraum adaptiv in Simplexe unterteilt, um die Konservativität der linearen Schranken zu reduzieren.
Unterstützung von Steuereingaben: Der Ansatz berücksichtigt explizit Steuereingaben ( $u$ ) in der Invarianzbedingung, was ihn für Anwendungen wie Sicherheitsfilter (Safety Filters) geeignet macht.

4. Experimentelle Ergebnisse

Die Autoren evaluieren ihre Methode an mehreren Benchmarks (u. a. 2D-Control, Cart-Pole, Darboux, Barrier 2-4) und vergleichen sie mit dem SMT-Solver dreal.

Skalierbarkeit: Die Methode verifiziert erfolgreich neuronale Netze mit deutlich größeren Architekturen (z. B. [128, 256, 128] Neuronen) als SMT-basierte Verfahren, die bei diesen Größen oft einen Timeout erleiden.
Aktivierungsfunktionen: Im Gegensatz zu vielen ReLU-spezifischen Methoden funktioniert der Ansatz mit Tanh-Aktivierungen, die in den Experimenten größere invariante Mengen ermöglichten.
Leistung: In den Tests (Tabelle 1) zeigte die Methode signifikante Geschwindigkeitsvorteile. Während dreal bei komplexeren Benchmarks (wie Barrier 4 oder Darboux) einen Timeout erreichte, lieferte die neue Methode Ergebnisse in Sekunden bis Minuten.
Genauigkeit: Die adaptive Verfeinerung sorgt dafür, dass in kritischen Bereichen (nahe der Sicherheitsgrenze) eine hohe Auflösung erreicht wird, während in sicheren Regionen das Gitter grob bleibt.

5. Bedeutung und Fazit

Dieses Paper adressiert einen kritischen Engpass im Bereich des sicheren maschinellen Lernens für die Regelungstechnik. Durch die Umgehung von SMT-Solvern zugunsten einer effizienten linearen Relaxation in Kombination mit einer intelligenten Gitterverfeinerung ermöglichen die Autoren die Verifikation von größeren und ausdrucksstärkeren neuronalen CBFs.

Die Fähigkeit, beliebige nichtlineare Aktivierungsfunktionen und Steuereingaben zu handhaben, macht den Ansatz universell einsetzbar für komplexe nichtlineare dynamische Systeme. Dies ebnet den Weg für den sicheren Einsatz von lernbasierten Reglern in sicherheitskritischen Anwendungen, wo bisherige Verifikationsmethoden aufgrund von Skalierungsproblemen versagten. Zukünftige Arbeiten könnten diesen Rahmen auf andere Spezifikationen wie Erreichbarkeit (Reachability) erweitern.