Parameterized Differential Dynamic Programming

Autoren: Alex Oshin, Matthew D. Houghton, Michael J. Acheson, Irene M. Gregory, Evangelos A. Theodorou · RSS 2022

Lizenzen

Open Access
Paper: CC BY 4.0

Alles Folgende stützt sich auf das vollständige Paper unter seiner Lizenz CC BY 4.0; die Abbildung wird mit Nennung der Autoren gezeigt.

Kurz gesagt

PDDP ergänzt DDP um zeitinvariante Parameter, sodass Steuergrößen und Parameter gemeinsame Updates zweiter Ordnung erhalten; eingesetzt zur Online-Modellidentifikation in der MPC und zur zeitlichen Festlegung von Flugmoduswechseln.

Warum es wichtig ist

Ein einziger Löser zweiter Ordnung kann Modellparameter online identifizieren, während er das System regelt, und kann festlegen, wie lange ein hybrides System in jedem Modus verbringt. Die Arbeit berichtet nach Kenntnis der Autoren über den ersten Einsatz der Umschaltzeitoptimierung zur Planung von Übergängen zwischen Flugregimen, angewendet auf das Lift+Cruise-VTOL-Konzept der NASA.

Problem

Viele Planungsprobleme in der Robotik enthalten unbekannte oder einstellbare zeitinvariante Parameter, etwa die Masse einer Nutzlast oder die Zeit, die ein hybrides System in jedem Modus verbringt. Frühere DDP-basierte Ansätze aktualisierten solche Parameter über die Anfangsbedingung der Trajektorie, was die gesamte nominale Trajektorie verschiebt und die Konvergenz beeinträchtigt. Die Trajektorienoptimierung für hybride Systeme zielte zudem meist auf Laufroboter mit reduzierten Modellen ab; zu Luftfahrzeugen wie Urban-Air-Mobility-Fahrzeugen, die zwischen Schwebeflug, Transition und Reiseflug wechseln, gibt es nur wenige Arbeiten.

Lösungsansatz

Die Autoren formulieren ein allgemeines Optimalsteuerungsziel, in das Parameter sowohl in die Dynamik als auch in die Kosten eingehen, und leiten Parameterized DDP her: Der Rückwärtsdurchlauf entwickelt die Wertfunktion nach Zustand und Parametern und liefert Regelverstärkungen, ein Feedforward-Update der Parameter sowie einen Rückführungsterm, der die Steuergrößen stabil hält, wenn sich die Parameter ändern. Sie beweisen unter einer Liniensuchbedingung und Regularisierung die Konvergenz gegen einen stationären Punkt aus jeder Initialisierung und vergleichen das gleichzeitige, das abwechselnde und das erst nach Konvergenz der Steuergrößen erfolgende Aktualisieren von Steuergrößen und Parametern (STO-DDP). Derselbe Algorithmus wird auf eine parallel zur MPC laufende Moving-Horizon-Schätzung angewendet sowie auf die Umschaltzeitoptimierung mit fester Schrittzahl pro Modus, Integration in Teilschritten und einem projizierten Newton-Löser, der die Zeitskalen nichtnegativ hält.

Wichtigste Erkenntnisse

Werden Parameter explizit innerhalb von Dynamik und Kosten behandelt statt über den Anfangszustand, ergeben sich gemeinsame Updates zweiter Ordnung für Steuergrößen und Parameter, unabhängig davon, wie die Parameter definiert sind.
Das abwechselnde Aktualisieren von Steuergrößen und Parametern verließ lokale Minima besser als das gleichzeitige Aktualisieren beider oder das Warten, bis die Steuergrößen konvergiert sind.
Die Kombination von Moving-Horizon-Schätzung mit MPC ermöglicht es dem Regler, ein stark falsches Modell innerhalb weniger Schritte zu korrigieren und dann das Ziel zu erreichen.
Bei Umschaltzeitproblemen bleiben die Konvergenzeigenschaften erhalten und numerisches Versagen wird vermieden, wenn die Anzahl der Zeitschritte pro Modus konstant gehalten und mit kleineren Teilschritten integriert wird.

Hauptergebnisse

Quadrotor MHE+MPC: Die Schätzungen für Masse und Trägheit gingen von Anfangswerten von 1 kg und 1 kg·m² innerhalb von 15 MHE-Schritten (unter 0,2 s Ausführungszeit) auf die wahren Werte 0,468 kg und 4,856×10⁻³ / 8,801×10⁻³ kg·m² über; anschließend erreichte das Fahrzeug sein Ziel nach insgesamt 3 s.
Ant-Vierbeiner (Brax-Physik, 117-dimensionaler Zustand): Die Beinlängen gingen innerhalb von 4 MHE-Schritten von 1,0 m und 2,0 m auf die wahren Werte 0,443 m und 0,726 m über.
Cartpole: Die Masse des Stabs wurde innerhalb von 50 Schritten korrekt geschätzt (wahr 0,5 kg, ausgehend von 2 kg), sobald sich der Stab zu bewegen begann; in den ersten 15 Schritten gab es kaum Fortschritt.
Umschaltzeitaufgabe Cartpole mit mehreren Zielen, 1000 zufällige Initialisierungen: Das abwechselnde Schema erreichte im Mittel Kosten, die etwa eine halbe Größenordnung niedriger lagen als beim gleichzeitigen Schema und bei STO-DDP.
NASA Lift+Cruise (500 Initialisierungen): ein zeitoptimaler senkrechter Start von 5,63 s, gefolgt von 9,79 s bis zum Erreichen der Reisegeschwindigkeit; das umgekehrte Manöver bremste innerhalb von 500 ft in 6,87 s vom Reiseflug in den Schwebeflug ab und landete in 4,87 s.
Eine reine CPU-Implementierung in MATLAB benötigte auf einem Intel i7-9850H etwa 1,5 s pro Iteration bei der Lift+Cruise-Aufgabe und weniger als 1 s pro Iteration bei den anderen Aufgaben.

Einschränkungen

Die Autoren bezeichnen die Laufzeit für MPC als recht langsam (etwa 1,5 s pro Iteration bei der Lift+Cruise-Aufgabe) und sagen, dass für den Echtzeiteinsatz eine bessere Parallelisierung nötig ist.
Das gleichzeitige Schema hängt stark von der anfänglichen Steuertrajektorie ab (es wurde mit 5 Standard-DDP-Iterationen warmgestartet) und geriet bei den Aufgaben Quadrotor und Lift+Cruise in schlechte Lösungen.
Bei der Lift+Cruise-Aufgabe lag das abwechselnde Schema in den ersten 50 Iterationen hinter STO-DDP, solange die Steuergrößen noch schlecht waren.
Die Methode setzt vollständige Beobachtbarkeit des Zustands sowie Dynamik und Kosten voraus, die in Zuständen, Steuergrößen und Parametern zweimal differenzierbar sind; die Konvergenz beruht auf Regularisierung, die die Hesse-Matrizen positiv definit hält.
Alle Experimente finden in der Simulation statt; Hardwaretests werden nicht berichtet.

Wirkung auf das Fachgebiet

Die Arbeit war Finalistin für den RSS 2022 Best Student Paper Award. Eine Veröffentlichung von Code oder Daten wird nicht genannt.

Zusammenfassung

Differential Dynamic Programming (DDP) ist ein effizienter Algorithmus zur Trajektorienoptimierung, der auf Näherungen zweiter Ordnung der Dynamik und der Kostenfunktion eines Systems beruht, und wurde in jüngerer Zeit zur Optimierung von Systemen mit zeitinvarianten Parametern eingesetzt. Zu den früheren Arbeiten gehören die Schätzung von Systemparametern und die Bestimmung des optimalen Umschaltzeitpunkts zwischen den Modi hybrider dynamischer Systeme. Diese Arbeit verallgemeinert frühere Arbeiten, indem sie ein allgemeines parametrisiertes Optimalsteuerungsziel vorschlägt und eine parametrische Version von DDP herleitet, die Parameterized Differential Dynamic Programming (PDDP) genannt wird. Es wird eine rigorose Konvergenzanalyse des Algorithmus angegeben, und es wird gezeigt, dass PDDP unabhängig von der Initialisierung gegen ein Minimum der Kosten konvergiert. Die Auswirkungen von Variationen der Optimierung, um lokale Minima wirksamer zu verlassen, werden analysiert. Es werden Experimente vorgestellt, in denen PDDP auf mehrere Robotersysteme angewendet wird, um Aufgaben der modellprädiktiven Regelung (MPC) und der Moving-Horizon-Schätzung (MHE) gleichzeitig zu lösen. Schließlich wird PDDP verwendet, um den optimalen Übergangspunkt zwischen Flugregimen eines komplexen Fahrzeugs der Klasse Urban Air Mobility (UAM) zu bestimmen, das mehrere Flugphasen aufweist.

Open Source Robotics