From Kinematics to Dynamics: Learning to Refine Hybrid Plans for Physically Feasible Execution

1. Problemstellung

Roboter müssen oft eine Abfolge räumlicher Regionen durchqueren, um eine Mission zu erfüllen. Diese Probleme sind inhärent hybrid: Sie erfordern eine diskrete Abfolge von Aktionen (logische Planung) und eine physikalisch machbare, kontinuierliche Trajektorie.

Das zentrale Problem liegt in der Diskrepanz zwischen der Modellierung in hybriden Zeitplanern (wie dem Scotty-Planer) und der Realität:

• Erste Ordnung vs. Zweite Ordnung: Die meisten hybriden Planer modellieren die Systemdynamik als erste Ordnung (Geschwindigkeit ist die Steuervariable, $\dot{x} = v$). Dies ermöglicht effiziente Optimierungsformulierungen wie Second-Order Cone Programs (SOCP) oder Mixed-Integer Linear Programs (MILP).
• Physikalische Realität: Reale Roboter unterliegen jedoch zweiter Ordnung (Beschleunigung ist die Steuervariable, $\ddot{x} = u$), inklusive Begrenzungen für Beschleunigung, Geschwindigkeit und oft nichtlinearer Effekte wie Luft- oder Wasserwiderstand (Drag).
• Folge: Ein von einem ersten-Ordnung-Planer generierter Plan ist unter zweiten-Ordnung-Dynamiken fast immer physikalisch nicht ausführbar. Die Nachverfolgung solcher Pläne durch einen Low-Level-Controller führt zu Aktorsättigung, großen Tracking-Fehlern und Instabilität.
• Lücke: Bestehende Methoden können zwar erkennen, wo ein Plan physikalisch unmöglich ist (durch Minimum-Time Validation, MTV), aber sie können den Plan innerhalb ihrer ersten-Ordnung-Modelle nicht so anpassen, dass er zweite-Ordnung-konform wird.

2. Methodik

Die Autoren schlagen einen neuro-symbolischen Verfeinerungsrahmen vor, der hybride Planung, analytische Validierung zweiter Ordnung und Reinforcement Learning (RL) kombiniert.

A. Problemformulierung als CSA-MDP

Das Verfeinerungsproblem wird als Continuous-State-and-Action Markov Decision Process (CSA-MDP) formuliert:

• Zustand (State): Der aktuelle Plan wird als Graph $G=(V, E)$ dargestellt. Knoten repräsentieren Ereignisse (Start/Ende von Aktionen) mit Attributen wie Position, Zeit und Geschwindigkeit. Kanten repräsentieren Übergänge mit Geschwindigkeitsgrenzen und Dauerbeschränkungen.
• Aktion (Action): Ein RL-Agent (basierend auf einem Graph Neural Network, GNN) gibt kontinuierliche Skalierungsfaktoren aus, die die Geschwindigkeitsgrenzen für alle Bewegungssegmente gleichzeitig anpassen.
• Dynamik:
  1. Der Agent passt die Geschwindigkeitsgrenzen an.
  2. Ein SOCP-Löser berechnet basierend auf diesen neuen Grenzen eine neue Trajektorie unter Minimierung der Gesamtzeit (Makespan).
  3. Die resultierende Trajektorie wird mittels Minimum-Time Validation (MTV) auf physikalische Machbarkeit unter zweiten-Ordnung-Dynamiken (inkl. Drag) überprüft.
• Belohnung (Reward):
  • Falls der SOCP-Löser scheitert: $-1$.
  • Falls der Plan erster Ordnung machbar ist, aber MTV-Verletzungen aufweist: Ein negativer Reward basierend auf der Lücke zwischen zugewiesener Zeit und der minimal physikalisch benötigten Zeit ($t_{min}$).
  • Falls der Plan sowohl erster als auch zweiter Ordnung machbar ist: Ein positiver Reward, der die Verbesserung der Gesamtzeit (Makespan) im Vergleich zum ursprünglichen Plan belohnt.

B. Algorithmus

• RL-Algorithmus: Es wird Proximal Policy Optimization (PPO) verwendet, da die Optimierungslandschaft (Interaktion zwischen SOCP-Löser, MTV und RL) hochgradig nichtlinear und nicht-differenzierbar ist.
• Architektur: Ein geteilter Encoder-Aktor-Kritiker mit GNN. Der GNN verarbeitet die Graphstruktur, um räumliche, zeitliche und dynamische Beziehungen zu erfassen.
• MTV (Minimum-Time Validation): Dies dient als strenger Validator. Es berechnet die theoretisch kürzeste Zeit für einen Übergang zwischen zwei Zuständen unter Berücksichtigung von Beschleunigungsgrenzen und quadratischem Widerstand. Es liefert geschlossene Formeln für die Bewegungsprofile (Bang-Constant-Bang oder Bang-Bang).

3. Schlüsselbeiträge

1. Formulierung als CSA-MDP: Die Umwandlung des Planverfeinerungsproblems in einen MDP über einer graphbasierten Darstellung, die strukturiertes Schlussfolgern über zeitliche, räumliche und dynamische Beziehungen ermöglicht.
2. Erster automatisierter Verfeinerungsrahmen: Ein System, das Pläne erster Ordnung durch die Integration von geschlossenen analytischen Lösungen zweiter Ordnung (MTV) und Reinforcement Learning in physikalisch gültige Trajektorien transformiert.
3. Empirische Validierung: Der Nachweis, dass Pläne erster Ordnung unter realistischen zweiten-Ordnung-Dynamiken fast immer versagen und dass der vorgeschlagene Ansatz diese Lücke zuverlässig schließt.

4. Ergebnisse

Die Methode wurde in vier hybriden Planungsdomainen evaluiert (AUV-2D, NORM-AUV-2D, OnAir-Refuel, Sailing), wobei der Scotty-Planer als Basis diente.

• Physikalische Machbarkeit: Alle initialen Pläne des ersten-Ordnung-Planers waren unter zweiten-Ordnung-Dynamiken zu 0 % machbar. Der Verfeinerungsansatz erreichte in 100 % der Fälle physikalische Machbarkeit.
• Makespan (Gesamtzeit): Um die physikalische Machbarkeit zu erreichen, musste die Gesamtzeit erhöht werden (Verhältnis > 1, z.B. 1,20 für AUV-2D). Dies spiegelt die Unterschätzung der ersten-Ordnung-Modelle wider.
• Vergleich mit Baselines: Der RL-basierte Ansatz übertraf konservative Baselines (konstante Geschwindigkeitsreduktion um 10 % oder 0,5 % pro Schritt) deutlich:
  • Er erreichte niedrigere Makespans als die Baselines.
  • Er benötigte deutlich weniger Iterationsschritte, um eine machbare Lösung zu finden (die feinkörnige Baseline benötigte im Durchschnitt ~1785 % mehr Schritte für nur marginale Verbesserungen).
• Konvergenz: Die Trainingkurven zeigten eine konsistente Verbesserung der Belohnung und einen stabilen Übergang in den physikalisch machbaren Bereich.

5. Bedeutung und Ausblick

• Überbrückung der Lücke: Die Arbeit schließt die kritische Lücke zwischen symbolischer Planung (die oft vereinfachte Modelle nutzt) und der realen physikalischen Ausführung. Sie zeigt, dass reine erste-Ordnung-Planung für reale Roboter unzureichend ist.
• Effizienz: Der Ansatz bietet eine effiziente Möglichkeit, komplexe nichtlineare Dynamikprobleme zu lösen, ohne die diskrete Struktur des Plans (Reihenfolge der Aktionen) ändern zu müssen.
• Einschränkungen & Zukunft: Das aktuelle Modell geht von störungsfreien, entkoppelten Achsen und fehlenden Zeitfenstern aus. Zukünftige Arbeiten sollen diese Annahmen lockern, um Zeitfenster-Constraints und gekoppelte Achsen in variablen Umgebungen zu behandeln.

Zusammenfassend demonstriert das Paper, wie Reinforcement Learning genutzt werden kann, um die Lücke zwischen mathematisch vereinfachten Planungsmodellen und den strengen Anforderungen der physikalischen Robotik zu schließen, indem es einen robusten Verfeinerungsprozess für hybride Pläne etabliert.