⚡ electrical engineering

Extending and Unifying the Fundamental Tasks of Hamilton-Jacobi Reachability Analysis

Dieses Paper führt die verallgemeinerte Reach-Avoid-Aufgabe (GRA) als ein vereinendes Primitiv ein, das die Hamilton-Jacobi-Erreichbarkeitsanalyse erweitert, um eine breitere Klasse fundamentaler und zusammengesetzter Aufgaben zu lösen, einschließlich solcher aus der zeitgesteuerten temporalen Logik, während es gleichzeitig eine umfassende PDE-Perspektive zur Darstellung regulärer Lösungen bereitstellt.

Ursprüngliche Autoren: Dylan Hirsch, William Sharpless, Donggun Lee, Sylvia Herbert

Veröffentlicht 2026-08-19

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Dylan Hirsch, William Sharpless, Donggun Lee, Sylvia Herbert

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

In der Welt der Robotik und autonomen Fahrzeuge ist Sicherheit nicht nur ein Merkmal; sie ist das Fundament. Ingenieure müssen Systeme entwerfen, die in der Lage sind, durch eine chaotische Welt voller beweglicher Hindernisse, unvorhersehbarer Witterung und mechanischer Ausfälle zu navigieren, während sie gleichzeitig ein bestimmtes Ziel erreichen. Um dies zu tun, verlassen sie sich auf einen mathematischen Rahmen, der als Hamilton-Jacobi-Erreichbarkeitsanalyse bekannt ist. Man kann sich diesen Rahmen als eine Methode vorstellen, um die „Sicherheitszone“ einer Maschine zu berechnen. Er stellt eine einfache, aber tiefgründige Frage: Kann die Maschine sich trotz der schlimmsten möglichen Störungen durch die Umgebung so steuern, dass sie ihr Ziel erreicht, ohne zu kollidieren? Durch die Beantwortung dieser Frage kann das System einen Regler generieren, der die Maschine sicher hält, egal was passiert. Jahrzehntelang haben Forscher diese Methode genutzt, um spezifische Arten von Problemen zu lösen, wie etwa das Erreichen eines Ziels, das Vermeiden eines Hindernisses oder das Verbleiben in einem sicheren Bereich bis zu einer bestimmten Frist. Diese Probleme wurden jedoch oft als getrennte, eigenständige Herausforderungen behandelt, die jeweils einen eigenen, einzigartigen mathematischen Aufbau erforderten.

Ein Team von Forschern der University of California, San Diego, und der North Carolina State University hat diese getrennten Herausforderungen nun zu einem einzigen, leistungsfähigeren Werkzeug vereinheitlicht. Sie führten ein neues Konzept namens „generalized reach-avoid task“ (verallgemeinerte Erreichungs-Vermeidungs-Aufgabe) ein. Dieser neue Ansatz löst nicht nur die alten Probleme; er kombiniert sie zu einem flexiblen Rahmen, der Situationen bewältigen kann, in denen eine Maschine mehrere Wege zum Erfolg hat. In der Vergangenheit, wenn eine Drohne entweder auf einer Plattform landen oder in der Nähe eines Kommunikationsturms bleiben musste, mussten Ingenieure dies als zwei verschiedene Szenarien behandeln. Die neue Methode erkennt, dass dies eigentlich zwei Seiten derselben Medaille sind. Sie ermöglicht es dem System, eine einzige Sicherheitskarte zu berechnen, die die Möglichkeit berücksichtigt, ein Ziel zu erreichen, in einer sicheren Zone zu verbleiben oder zu einem bestimmten Zeitpunkt an einem bestimmten Ort anzukommen – und das alles gleichzeitig.

Die Forscher zeigten, dass diese vereinheitlichte Aufgabe nicht nur eine theoretische Kuriosität, sondern eine praktische Notwendigkeit für komplexe, reale Szenarien ist. Sie zeigten, dass sie mit diesem einzigen Rahmen Probleme lösen konnten, die mit Standardmethoden schwierig oder gar unmöglich zu adressieren waren. Beispielsweise gingen sie ein Szenario an, bei dem eine Drohne über Wasser bei starkem, unvorhersehbarem Wind flog. Die Drohne hatte zwei Optionen, um eine zehnsekündige Böe zu überstehen: Sie konnte zu einer Landeplattform fliegen oder die gesamte Dauer über in einem sicheren Abstand zu einer Kommunikationsantenne bleiben. Mit älteren Methoden hätten Ingenieure versucht, die Sicherheit für das Landen und die Sicherheit für das Verbleiben am Ort separat zu berechnen und dann die Ergebnisse zu kombinieren. Die Forscher bewiesen, dass dieser Ansatz fehlerhaft war; das kombinierte Ergebnis war oft unkorrekt, da sich die beiden Strategien auf komplexe Weise beeinflussen. Durch den Einsatz ihrer neuen, verallgemeinerten Methode berechneten sie die wahre Sicherheitszone und zeigten exakt auf, wo die Drohne starten konnte und dennoch überleben würde, unabhängig davon, welchen Weg sie wählte.

Diese Vereinheitlichung öffnet auch die Tür zur Lösung von Aufgaben, die eine zeitsensitive Logik beinhalten, was für Roboter in Lagern oder Krankenhäusern entscheidend ist. Die Forscher wandten ihre Methode auf ein Szenario mit zwei Robotern an, die mit dem Aufnehmen von Paketen beauftragt waren. Ein Roboter war schneller, hatte aber ein kürzeres Zeitfenster zum Handeln, während der andere langsamer, aber mehr Zeit hatte. Das Ziel war, dass entweder der eine oder der andere Roboter das Regal erreicht, ohne Wände oder einander zu rammen. Der neue Rahmen ermöglichte es dem System, diese komplexe, zeitgesteuerte Anforderung in eine Sequenz einfacherer Schritte zu zerlegen. Er sagte dem langsameren Roboter effektiv, dass er Platz machen sollte, damit der schnellere vorbeikommen konnte, wodurch die Gesamtmission erfolgreich war. Diese Art des dynamischen Entscheidungsfindens, bei der das System seine Strategie basierend auf Zeit und Beschränkungen anpasst, ist nun mit ihrer einzigen, vereinheitlichten Gleichung berechenbar.

Darüber hinaus zeigten die Forscher, dass diese neue Aufgabe der natürliche mathematische Baustein für das gesamte Feld ist. Sie bewiesen, dass fast jede reguläre Lösung der zugrunde liegenden Sicherheitsgleichungen durch diese verallgemeinerte Aufgabe dargestellt werden kann. Das bedeutet, dass Ingenieure, anstatt einen Werkzeugkasten voller verschiedener, spezialisierter Gleichungen für unterschiedliche Arten von Sicherheitsproblemen zu besitzen, sich nun auf eine einzige Master-Gleichung verlassen können. Sie passen einfach die Parameter an, um das spezifische Ziel, die Hindernisse und die Zeitlimits zu definieren. Diese Vereinfachung ist bedeutend, da sie eine konsistente Möglichkeit bietet, Systeme zu handhaben, die ihr Verhalten im Laufe der Zeit ändern, wie etwa eine medizinische Infusionspumpe, die zwischen aktiver Behandlung und Ruhephasen wechselt. Durch das Zerlegen des Problems in kleinere Zeitsegmente und das Zusammenfügen der Lösungen stellt die Methode die Sicherheit auch dann sicher, wenn sich die Regeln des Systems abrupt ändern.

Die Arbeit löst nicht das Problem der hochdimensionalen Komplexität, bei der die Anzahl der Variablen die Berechnungen für aktuelle Computer zu schwer macht, aber sie bietet einen klareren Weg nach vorn. Die Forscher stellten fest, dass ihre Methode unter sehr allgemeinen Bedingungen funktioniert und lediglich voraussetzt, dass das Verhalten des Systems kontinuierlich und innerhalb kleiner Schritte vorhersehbar ist. Sie validierten ihre Ergebnisse durch strenge mathematische Beweise und numerische Simulationen und zeigten, dass der neue Ansatz sowohl theoretisch fundiert als auch praktisch nützlich ist. Durch die Erweiterung und Vereinheitlichung der grundlegenden Aufgaben der Erreichbarkeitsanalyse bietet diese Forschung einen robusteren und flexibleren Weg, um sicherzustellen, dass autonome Systeme die reale Welt sicher, effizient und intelligent navigieren können.

Technisches Resümee: Erweiterung und Vereinheitlichung der fundamentalen Aufgaben der Hamilton-Jacobi-Erreichbarkeitsanalyse

Problemstellung

Die Hamilton-Jacobi-Erreichbarkeitsanalyse (HJR) ist ein grundlegendes Framework für sicherheitskritische Steuerung, das in der Differenzialspieltheorie verwurzelt ist. Traditionell adressiert HJR fünf kanonische Aufgaben mit endlichem Horizont: (I) Terminal-Menge (Terminal-set), (II) Erreichen (Reach), (III) Vermeiden (Avoid), (IV) Beschränkte Terminal-Menge (Constrained Terminal-set) und (V) Erreichen-Vermeiden (Reach-avoid). Während diese Aufgaben über Hamilton-Jacobi-Terminalwertprobleme (HJ-TVPs) gelöst werden, die dieselbe Struktur einer partiellen Differentialgleichung (PDE) teilen, werden sie als distinkte Primitivfunktionen mit spezifischen Randbedingungen behandelt.

Eine wesentliche Einschränkung des bestehenden Frameworks besteht darin, dass komplexe, zusammengesetzte Aufgaben – wie sie durch temporale Logik spezifiziert werden oder piecewise-stetige Dynamiken involvieren – oft nicht einfach durch das Maximum oder Minimum der Wertfunktionen der kanonischen Aufgaben gelöst werden können. Die algebraische Beziehung zwischen Leistungsfunktionalen gilt im Allgemeinen nicht für deren entsprechende Wertfunktionen aufgrund der zugrunde liegenden Minimax-Natur des Differenzialspiels. Folglich besteht ein Bedarf an einem allgemeineren Primitiv, das diese Aufgaben vereinheitlicht, eine rigorose Zerlegung der Wertfunktionen für zusammengesetzte Probleme ermöglicht und eine vollständige Charakterisierung der Lösungen der kanonischen HJ-PDE bietet.

Methodik

Die Autoren führen die Generalisierte Erreichen-Vermeiden-Aufgabe (Generalized Reach-Avoid, GRA) ein, definiert durch ein Tupel $(r, q, \ell; T)$ , wobei:

$r(x,t)$ eine Zielröhre (target tube, ein bewegliches Ziel) definiert.
$q(x,t)$ eine Beschränkungsröhre (constraint tube, ein Sicherheitsbereich) definiert.
$\ell(x)$ eine Terminal-Menge (terminal set, ein Ziel zum Zeitpunkt $T$ ) definiert.
$T$ die Endzeit ist.

Die GRA-Aufgabe erfordert, dass das System entweder:

Die Zielröhre $r$ bis zum Zeitpunkt $T$ erreicht, während es bis zum Erreichzeitpunkt in der Beschränkungsröhre $q$ bleibt; ODER
Zum Zeitpunkt $T$ in der Terminal-Menge $\ell$ ist, während es bis zum Zeitpunkt $T$ in der Beschränkungsröhre $q$ bleibt.

Das Leistungsfunktional $J_{GRA}$ ist so formuliert, dass es diese "ODER"-Logik erfasst. Die Wertfunktion $V_{GRA}$ wird dann als die eindeutige stetige viskose Lösung eines spezifischen HJ-TVP charakterisiert. Entscheidend ist, dass die zugrunde liegende Hamilton-Jacobi-PDE für die GRA-Aufgabe identisch mit der des kanonischen Erreichen-Vermeiden-Aufgabe ist, aber die terminale Randbedingung verallgemeinert wurde, um die Terminal-Mengen-Funktion $\ell$ zu integrieren.

Die Methodik etabliert ferner ein Wertfunktions-Zerlegungstheorem (Theorem 1). Dieses Theorem zeigt auf, dass die Wertfunktion einer zusammengesetzten Aufgabe – bestehend aus einer vorgelagerten GRA-Aufgabe gefolgt von einer nachgelagerten Aufgabe – exakt berechnet werden kann, indem man die Terminal-Mengen-Funktion der vorgelagerten GRA-Aufgabe modifiziert, um die Wertfunktion der nachgelagerten Aufgabe zum Zeitpunkt des Wechsels einzubeziehen.

Zentrale Beiträge

Einführung der GRA-Aufgabe: Das Paper definiert die GRA-Aufgabe als ein fundamentales Primitiv, das die fünf kanonischen HJR-Aufgaben strikt erweitert und vereinheitlicht. Durch Setzen spezifischer Parameter (z. B. $r = -\infty$ oder $q = \infty$ ) werden die kanonischen Aufgaben (I) bis (V) als Spezialfälle der GRA-Formulierung wiederhergestellt.
Vereinheitlichte HJ-TVP-Formulierung: Die Autoren zeigen, dass die Wertfunktion für die GRA-Aufgabe die eindeutige viskose Lösung eines HJ-TVP ist, bei dem die PDE die Standardform der kanonischen Form beibehält, aber die Terminalbedingung zu $v(x, T) = \min\{q(x, T), \max\{r(x, T), \ell(x)\}\}$ relaxiert wird. Dies vereinheitlicht die mathematische Behandlung aller fünf kanonischen Aufgaben unter einer einzigen Randbedingungsstruktur.
Wertfunktions-Zerlegung (Theorem 1): Ein kritischer theoretischer Befund stellt fest, dass die Wertfunktion einer zusammengesetzten Aufgabe (GRA gefolgt von einer beliebigen nachgelagerten Aufgabe) als eine einzige GRA-Wertfunktion dargestellt werden kann. Dies wird erreicht, indem die Terminal-Mengen-Funktion $\ell$ zu $\tilde{\ell}(x) = \max\{\ell(x), V_{downstream}(x, T)\}$ aktualisiert wird. Dies ermöglicht die Berechnung von Wertfunktionen für komplexe, zeitgesteuerte Aufgaben (z. B. zeitgesteuerte temporale Logik), ohne separate, nicht-kommutierende Optimierungsprobleme lösen zu müssen.
Vollständigkeit der Repräsentation (Korollar 2): Das Paper beweist, dass jede hinreichend reguläre viskose Lösung der kanonischen HJ-PDE als die Wertfunktion einer GRA-Aufgabe mit einer angemessen gewählten Terminal-Mengen-Funktion $\ell$ dargestellt werden kann. Dies legt nahe, dass die GRA-Formulierung "vollständig" ist im Sinne der Fähigkeit, den vollen Lösungsraum der kanonischen PDE zu repräsentieren, während einzelne kanonische Aufgaben (wie Erreichen-Vermeiden) nur spezifische Schnitte dieses Raums darstellen.
Umgang mit piecewise-stetigen Dynamiken: Die Autoren schlagen einen iterativen Algorithmus (Algorithmus 1) vor, um GRA-Wertfunktionen für Systeme mit zeitlich piecewise-stetigen Dynamiken (z. B. Schalt-Systeme) zu berechnen. Dies geschieht durch sequenzielles Lösen des GRA-TVP über kontinuierliche Intervalle und die Verwendung der Wertfunktion zum Schaltzeitpunkt als neue Terminal-Mengen-Funktion für das nachfolgende Intervall.

Ergebnisse und Beispiele

Das Paper validiert das theoretische Framework durch drei Beispiele:

Erreichen-Vermeiden oder Dauerhaft-Vermeiden: Ein Drohnen-Szenario, bei dem die Aufgabe darin besteht, entweder eine Landeplattform zu erreichen oder die Kommunikation unendlich lange aufrechtzuerhalten. Die Ergebnisse zeigen, dass die wahre Wertfunktion (berechnet via GRA) strikt von dem Maximum der individuellen Erreichen-Vermeiden- und Vermeiden-Wertfunktionen abweicht, was die Notwendigkeit des vereinheitlichten Ansatzes beweist.
Zeitgesteuerte temporale Logik: Ein Multi-Roboter-Lagerhaus-Szenario mit einer Disjunktion von zeitgesteuerten Erreichen-Vermeiden-Constraints. Das Zerlegungstheorem ermöglicht es, die komplexe Spezifikation durch das Verketten von GRA-Aufgaben zu lösen, wodurch die Struktur der temporalen Logik effektiv gehandhabt wird.
Piecewise-stetige Dynamiken: Ein Pharmakologie-Modell mit Medikamenteninfusion und On/Off-Zyklen. Der iterative Algorithmus verbindet die Wertfunktionen über die Diskontinuitäten der Systemdynamik hinweg erfolgreich, was den Nutzen der Terminal-Mengen-Funktion als "Port" für die dynamische Programmierung demonstriert.

Bedeutung

Das Paper behauptet, dass die GRA-Aufgabe als natürliches und vereinheitlichendes Primitiv für HJR sowohl aus der Perspektive der Aufgabenstellung als auch der PDE dient.

Theoretische Vereinheitlichung: Es löst die Fragmentierung der fünf kanonischen Aufgaben in einem einzigen Framework auf und etabliert einheitliche theoretische Ergebnisse (Existenz, Eindeutigkeit und Stetigkeit) unter schwächeren Annahmen als frühere separate Studien.
Praktischer Nutzen: Es ermöglicht die rigorose Berechnung von Wertfunktionen für zusammengesetzte Aufgaben, die zuvor schwer zu adressieren waren, insbesondere solche mit zeitgesteuerter temporaler Logik oder Schalt-Dynamiken.
PDE-Vollständigkeit: Es liefert ein Konversum zu Standard-Existenztheoremen, indem es zeigt, dass die GRA-Formulierung jede hinreichend reguläre Lösung der kanonischen HJ-PDE repräsentieren kann, und vervollständigt damit den Satz der lösbaren Aufgaben innerhalb des HJR-Frameworks.

Die Arbeit beansprucht nicht, den Fluch der Dimensionalität zu lösen, der in HJR inhärent ist, bietet aber ein robusteres und flexibleres mathematisches Fundament für die Anwendung von HJR auf zunehmend komplexere Kontrollprobleme.