Warm Start

Auch genannt: warm starting
Kategorie: Planning & manipulation › Trajectory optimisation
Schlagwörter: optimization, model-predictive-control, trajectory-optimization, numerical-methods, real-time

Das Initialisieren eines iterativen Lösers mit einer guten Schätzung, oft einer vorherigen oder verwandten Lösung, statt bei null anzufangen, um die Lösungszeit zu verkürzen und ihn zu einem brauchbaren lokalen Optimum zu lenken.

Definition

Ein Warmstart (warm start) initialisiert einen iterativen Optimierer oder numerischen Löser mit Informationen aus einem verwandten Problem statt von einem voreingestellten oder beliebigen Startpunkt aus, was als Kaltstart bezeichnet wird. Die Informationen können die primalen Variablen sein (die Entscheidungsvariablen selbst, etwa eine Trajektorie), die dualen Variablen oder Lagrange-Multiplikatoren, die aktive Menge der Ungleichungsnebenbedingungen oder Näherungen wie eine Quasi-Newton-Hesse-Matrix. Da nichtlineare Probleme in der Robotik meist viele lokale Optima haben, beeinflusst der Startpunkt nicht nur, wie schnell ein Löser konvergiert, sondern auch, welche Lösung er findet.

Modellprädiktive Regelung ist die häufigste Anwendung. In jedem Regelzyklus löst der Regler eine Optimierung über einen Horizont, der sich fast vollständig mit dem vorherigen überschneidet, sodass die vorherige Lösung, um einen Zeitschritt nach vorn verschoben und mit verlängertem letztem Schritt, bereits nahe am neuen Optimum liegt. Ein solcher Warmstart reduziert den Löser oft auf wenige Iterationen pro Zyklus, und das Real-Time-Iteration-Schema von Diehl und Kollegen geht noch weiter, indem es pro Zyklus nur eine einzige Iteration der sequentiellen quadratischen Programmierung ausführt. Samplingbasierte Regler wie MPPI und die Kreuzentropie-Methode nutzen einen Warmstart, indem sie die vorherige mittlere Steuerfolge wiederverwenden.

Wie viel ein Warmstart bringt, hängt vom Löser ab. Aktive-Mengen-Verfahren, etwa das in qpOASES, und Verfahren erster Ordnung wie der ADMM-Löser OSQP profitieren stark, weil eine nahe primale und duale Schätzung oder eine korrekte aktive Menge sie schnell zum Ende kommen lässt. Innere-Punkte-Verfahren lassen sich schwerer warm starten, weil ihre Iterierten strikt im Inneren des zulässigen Bereichs liegen müssen, fern von den Rändern der Nebenbedingungen, an denen frühere Lösungen meist liegen. In der Offline-Trajektorienoptimierung kann ein Warmstart aus einem einfacheren Modell stammen, aus einer gröberen Diskretisierung, einer relaxierten Version des Problems, einer gespeicherten Lösungsbibliothek oder einem neuronalen Netz, das darauf trainiert ist, gute Startschätzungen vorherzusagen. Physik-Engines starten iterative Kontaktlöser ebenso warm mit den Impulsen des vorherigen Schritts. Im maschinellen Lernen wird der Begriff auch für das Initialisieren eines Trainings mit einem zuvor trainierten Modell verwendet.

Warum es wichtig ist

Echtzeitfähige optimierungsbasierte Regler laufen mit zehn bis tausenden Hertz und erreichen diese Raten meist nur, weil jeder Lösungslauf nahe an seiner Antwort beginnt. In der Offline-Planung macht ein guter Warmstart oft den Unterschied zwischen einem Löser, der zu einer sinnvollen Bewegung konvergiert, und einem, der scheitert oder ein schlechtes lokales Minimum findet.

Wichtige Anwendungen

Modellprädiktive Echtzeitregelung bei Laufrobotern, Drohnen und Manipulatoren
Kontaktimplizite und nichtlineare Trajektorienoptimierung
Folgen verwandter quadratischer Programme in der Ganzkörperregelung
Iterative Kontaktlöser in Physik-Engines
Gelernte Startschätzungen für schnelle Bewegungsplanung

In der Praxis

Ein Laufroboter führt eine nichtlineare MPC mit 100 Hz aus. Nach jedem Lösungslauf speichert der Regler die optimalen Zustands- und Eingangstrajektorien sowie die Multiplikatoren. Im nächsten Zyklus verschiebt er diese um einen Schritt, kopiert den letzten Schritt, um das Ende des Horizonts zu füllen, ersetzt den ersten Zustand durch den neu gemessenen Zustand und übergibt das Ergebnis dem Löser als Startschätzung. Typische Lösungsläufe brauchen dann zwei oder drei Iterationen statt zwanzig. Die Ingenieure behandeln auch die Fälle, in denen der Warmstart versagt: Nach einem starken Stoß oder einem Wechsel der Gangart liegt die verschobene Schätzung weit vom neuen Optimum entfernt, daher greift der Regler auf eine gespeicherte Nominaltrajektorie für diese Gangart zurück und erlaubt in diesem Zyklus mehr Iterationen.

Häufige Missverständnisse

Ein Warmstart beschleunigt nur — bei nichtkonvexen Problemen entscheidet er auch, welches lokale Optimum gefunden wird, sodass ein schlechter Warmstart den Löser an eine schlechte Lösung binden kann
Jeder Löser profitiert gleichermaßen — Aktive-Mengen-Verfahren und Verfahren erster Ordnung gewinnen am meisten; Innere-Punkte-Verfahren gewinnen weniger und brauchen unter Umständen eine besondere Behandlung
Ein Warmstart braucht nur die vorherigen Entscheidungsvariablen — auch die dualen Variablen oder die aktive Menge mitzugeben, ist für schnelle Konvergenz oft genauso wichtig
Die vorherige Lösung ist immer eine gute Schätzung — nach großen Störungen, Moduswechseln oder Zieländerungen kann sie weit vom neuen Optimum entfernt sein und braucht eine Rückfallebene

Wer das wissen sollte

Ingenieure für modellprädiktive Regelung
Entwickler für Trajektorienoptimierung
Ingenieure für Beinfortbewegung und Drohnenregelung
Praktiker numerischer Optimierung in der Robotik

Open Source Robotics