Differential dynamic programming

Auch genannt: DDP
Kategorie: Planning & manipulation › Trajectory optimisation
Schlagwörter: trajectory-optimization, optimal-control, model-predictive-control, numerical-optimization, shooting-methods

Ein Verfahren der Trajektorienoptimierung, das eine Steuerfolge durch wiederholte Rückwärts- und Vorwärtsdurchläufe verbessert und dabei lokale quadratische Modelle der Restkosten (cost-to-go) entlang der aktuellen Trajektorie nutzt.

Definition

Differential Dynamic Programming (DDP) ist ein Algorithmus zur Trajektorienoptimierung: Gegeben ein Dynamikmodell, Kosten über Zustände und Steuergrößen sowie ein Anfangszustand, findet er eine Steuerfolge, die die Gesamtkosten lokal minimiert. Es wurde 1966 von David Mayne eingeführt und in Jacobsons und Maynes gleichnamigem Buch von 1970 weiterentwickelt. DDP ist ein Shooting-Verfahren: Die Entscheidungsvariablen sind die Steuergrößen, und in der klassischen Form werden die Zustände stets durch Vorwärtssimulation der Dynamik gewonnen, sodass jede Iterierte eine dynamisch zulässige Trajektorie ist.

Jede Iteration besteht aus zwei Durchläufen. Der Rückwärtsdurchlauf beginnt beim letzten Zeitschritt, arbeitet sich zum Anfang vor und wendet dabei Bellmans Optimalitätsprinzip lokal an: Er bildet aus ersten und zweiten Ableitungen von Dynamik und Kosten eine quadratische Näherung der Restkosten (cost-to-go) um die aktuelle Trajektorie und löst in jedem Schritt nach einer affinen Steuerungsaktualisierung, bestehend aus einem Vorsteuerterm k und einer Rückführverstärkungsmatrix K. Der Vorwärtsdurchlauf simuliert das System dann mit den aktualisierten Steuergrößen u = ū + αk + K(x − x̄), wobei α eine Schrittweite der Liniensuche ist. Da die Entwicklung Terme zweiter Ordnung der Dynamik enthält, konvergiert DDP in der Nähe eines lokalen Minimums quadratisch, wie das Newton-Verfahren, während der Aufwand pro Iteration nur linear mit der Horizontlänge wächst.

Die zweiten Ableitungen der Dynamik sind aufwendig zu berechnen, daher verwirft die meistgenutzte Variante, der iterative lineare quadratische Regler (iterative linear quadratic regulator, iLQR), sie und behält ein Dynamikmodell erster Ordnung bei, eine Gauß-Newton-Näherung. Praxistaugliche Löser regularisieren den Rückwärtsdurchlauf, um ihn gut konditioniert zu halten, und erweitern das Verfahren auf Stellgrößenbeschränkungen (control-limited DDP), allgemeine Nebenbedingungen (Augmented-Lagrangian-Verfahren wie ALTRO), unzulässige Startschätzungen (feasibility-driven DDP in Crocoddyl) und, wie bei Parameterized DDP, zeitinvariante Parameter, die zusammen mit den Steuergrößen optimiert werden. DDP findet nur lokale Optima, daher hängen die Ergebnisse von der Startschätzung ab. Ein nützliches Nebenprodukt ist der Satz von Rückführverstärkungen, mit denen sich der Roboter um die optimierte Trajektorie stabilisieren lässt.

Warum es wichtig ist

DDP und iLQR gehören zu den meistgenutzten Lösern für die Trajektorienoptimierung von Robotern und die nichtlineare modellprädiktive Regelung. Sie nutzen die zeitliche Struktur des Problems, skalieren linear mit der Horizontlänge und liefern zusammen mit der Trajektorie eine lokale Rückführ-Policy. Deshalb lassen Laufroboter, Humanoide und Drohnen sie in Echtzeit an Bord laufen.

Wichtige Anwendungen

Nichtlineare modellprädiktive Regelung für Laufroboter und Humanoide
Trajektorienoptimierung für Drohnen und agile Fahrzeuge
Bewegungsplanung auf Drehmomentebene für Manipulatoren
Aufschwingen und Balancieren unteraktuierter Systeme
Gemeinsame Optimierung von Trajektorien und Modell- oder Entwurfsparametern

In der Praxis

Ein Team, das eine modellprädiktive Ganzkörperregelung für einen Vierbeiner entwickelt, formuliert das Problem in Crocoddyl. Die Kontaktsequenz stammt aus einem festen Gangplan, sodass jede Phase bekannte Kontakte hat, und die Kosten kombinieren Basisfolgeregelung, Fußplatzierung, Stellaufwand und Strafterme, die die Kontaktkräfte innerhalb der Reibungskegel halten. In jedem Regelzyklus wird der Löser mit der um einen Schritt verschobenen vorherigen Lösung warmgestartet und führt nur eine oder wenige Iterationen aus. Die erste Steuergröße und ihre Rückführverstärkung gehen an den unterlagerten Gelenkregler, der mit der Verstärkung Zustandsänderungen zwischen den Löser-Aktualisierungen ausgleicht. Der größte Teil des Abstimmungsaufwands fließt in Kostengewichte, Regularisierung und die Horizontlänge, die Vorausschau gegen Lösungszeit abwägt.

Häufige Missverständnisse

DDP findet die global optimale Trajektorie — es ist ein lokales Verfahren; das Ergebnis hängt von der Startschätzung ab und kann ein schlechtes lokales Minimum sein
iLQR und DDP sind derselbe Algorithmus — iLQR lässt die Dynamikterme zweiter Ordnung weg, was viel günstigere Iterationen ergibt, auf Kosten langsamerer Konvergenz in der Nähe der Lösung
DDP kann keine Nebenbedingungen behandeln — der Grundalgorithmus ist unbeschränkt, aber Varianten mit Stellgrößenbeschränkungen und Augmented-Lagrangian-Varianten sind weit verbreitet
DDP ist dynamische Programmierung über den gesamten Zustandsraum — es wendet Bellmans Rekursion nur entlang einer Trajektorie an, was den Fluch der Dimensionalität vermeidet, aber nur lokale Ergebnisse liefert

Wer das wissen sollte

Regelungstechniker, die modellprädiktive Regler für Laufroboter und Drohnen entwickeln
Forschende in der Trajektorienoptimierung
Entwickler für Humanoide und Ganzkörperregelung
Robotikstudierende, die optimale Steuerung lernen

Open Source Robotics