Cross-Entropy Method (CEM)

Auch genannt: CEM
Kategorie: Planning & manipulation › Trajectory optimisation
Schlagwörter: optimization, sampling-based-planning, model-predictive-control, model-based-rl, trajectory-optimization

Ein sampling-basierter Optimierer, der wiederholt Kandidatenlösungen zieht, den am besten bewerteten Anteil behält und die Sampling-Verteilung neu daran anpasst; weit verbreitet zur Optimierung von Aktionsfolgen in der modellbasierten Regelung.

Definition

Die Kreuzentropie-Methode (cross-entropy method, CEM) ist ein einfacher ableitungsfreier Optimierungsalgorithmus. Sie hält eine Wahrscheinlichkeitsverteilung über Kandidatenlösungen, meist eine Gauß-Verteilung mit einem Mittelwert und einer diagonalen Varianz. In jeder Iteration zieht sie einen Stapel von Stichproben, bewertet die Kosten jeder einzelnen, wählt den am besten bewerteten Anteil (die Eliten) aus und passt Mittelwert und Varianz der Verteilung neu an diese Eliten an, oft mit einer gewissen Glättung hin zu den vorherigen Werten. Über die Iterationen zieht sich die Verteilung um eine gute Lösung zusammen. Die Methode wurde Ende der 1990er-Jahre von Reuven Rubinstein entwickelt, zunächst zur Schätzung von Wahrscheinlichkeiten seltener Ereignisse und dann zur Optimierung; ihr Name rührt daher, dass der Anpassungsschritt die Kreuzentropie, also die KL-Divergenz, zwischen der Sampling-Verteilung und einer auf hoch bewertete Stichproben konzentrierten Verteilung minimiert.

In der Robotik ist CEM vor allem als Trajektorienoptimierer innerhalb sampling-basierter modellprädiktiver Regelung bekannt. Die Entscheidungsvariable ist eine Aktionsfolge über einen Planungshorizont. Jede gesampelte Folge wird durch ein Dynamikmodell, entweder einen Physiksimulator oder ein gelerntes Modell, ausgerollt und anhand der summierten Kosten oder der vorhergesagten Belohnung bewertet. Nach einigen CEM-Iterationen führt der Roboter die erste Aktion der mittleren oder der besten Folge aus und plant im nächsten Schritt neu, typischerweise mit einem Warmstart, bei dem die vorherige Lösung zeitlich nach vorn verschoben wird. Methoden des modellbasierten Reinforcement Learning wie PETS und PlaNet verwenden CEM auf diese Weise mit gelernten Modellen, und Varianten fügen zeitlich korreliertes Rauschen hinzu, verwenden Eliten über Schritte hinweg wieder oder kombinieren CEM mit einer gelernten Policy, die Stichproben vorschlägt.

Der Reiz von CEM liegt darin, dass sie keine Gradienten braucht, nicht glatte oder unstetige Kosten verarbeitet und sich leicht parallel auf einer GPU ausführen lässt. Ihre Schwächen sind der Stichprobenaufwand, der mit der Länge des Horizonts und der Zahl der Aktionsdimensionen schnell wächst, und die Neigung, ihre Varianz zu früh auf ein lokales Optimum zusammenfallen zu lassen. Anders als MPPI, das alle Stichproben mit einer Exponentialfunktion ihrer Kosten gewichtet, verwendet CEM einen harten Schnitt und behandelt die Eliten gleich. Anders als gradientenbasierte Trajektorienoptimierer wie iLQR oder DDP nutzt sie keine Modellableitungen und ist daher bei glatten Problemen meist weniger stichprobeneffizient, aber nachsichtiger gegenüber gelernten oder Blackbox-Modellen.

Warum es wichtig ist

CEM ist einer der einfachsten Wege, aus einem Dynamikmodell einen Regler zu machen, und taucht in vielen Papern zum modellbasierten Lernen als Standardplaner auf. Wer die Kompromisse bei Elitenauswahl, Horizont und Stichprobenzahl versteht, kann diese Ergebnisse reproduzieren oder entscheiden, ob ein gradientenbasierter oder ein MPPI-artiger Planer besser zu einem Problem passt.

Wichtige Anwendungen

Sampling-basierte modellprädiktive Regelung mit gelernten Dynamikmodellen
Planung in latenten Weltmodellen für visuelle Regelung
Griff- und Aktionsauswahl durch Sampling und Bewertung von Kandidaten
Policy-Suche und Parameterabstimmung ohne Gradienten
Optimierung von Aktionen in Q-Learning mit kontinuierlichen Aktionsräumen

In der Praxis

Ein Team, das für eine Schiebeaufgabe ein gelerntes Dynamikmodell verwendet, führt in jedem Regelschritt eine CEM-basierte MPC aus. Es zieht einige Hundert Aktionsfolgen über einen kurzen Horizont aus einer Gauß-Verteilung, rollt jede auf der GPU durch das gelernte Modell aus, behält das beste Zehntel nach vorhergesagten Kosten, passt Mittelwert und Varianz neu an und wiederholt dies einige Male, bevor es die erste Aktion ausführt. Wenn der Planer zwischen den Schritten hin und her springt, verschiebt das Team den vorherigen Mittelwert und verwendet ihn als Warmstart wieder und fügt eine Mindestvarianz hinzu, damit die Suche nicht zusammenfällt. Da CEM Modellfehler ausnutzt, die unrealistisch niedrige Kosten vorhersagen, fügt das Team außerdem eine Strafe für Aktionsfolgen hinzu, die sich weit von den Trainingsdaten des Modells entfernen.

Häufige Missverständnisse

CEM ist ein Reinforcement-Learning-Algorithmus — sie ist ein Allzweckoptimierer; im modellbasierten RL plant sie mit einem Modell, während das Lernen im Modell oder in der Wertfunktion stattfindet
Mehr CEM-Iterationen helfen immer — die Varianz kann vorzeitig auf ein schlechtes lokales Optimum zusammenfallen, und mit einem gelernten Modell kann zusätzliche Optimierung Modellfehler ausnutzen
CEM und MPPI sind dasselbe — beide samplen Aktionsfolgen, aber CEM passt sich an eine hart ausgewählte Elitenmenge an, während MPPI jede Stichprobe mit ihren exponentiierten Kosten gewichtet

Wer das wissen sollte

Forscher im modellbasierten Reinforcement Learning
Regelungstechniker, die sampling-basierte MPC einsetzen
Manipulationsingenieure, die mit gelernten oder simulierten Modellen planen
Studierende, die Methoden der Trajektorienoptimierung vergleichen

Open Source Robotics