Cross-Entropy Method (CEM)

• Detto anche: CEM
• Categoria: Planning & manipulation › Trajectory optimisation
• Tag: optimization, sampling-based-planning, model-predictive-control, model-based-rl, trajectory-optimization

Un ottimizzatore basato sul campionamento che estrae ripetutamente soluzioni candidate, conserva la frazione con il punteggio migliore e vi riadatta la distribuzione di campionamento; molto usato per ottimizzare sequenze di azioni nel controllo basato su modello.

Definizione

Il metodo dell'entropia incrociata (cross-entropy method, CEM) è un semplice algoritmo di ottimizzazione senza derivate. Mantiene una distribuzione di probabilità sulle soluzioni candidate, di solito una gaussiana con una media e una varianza diagonale. A ogni iterazione estrae un batch di campioni, valuta il costo di ciascuno, seleziona la frazione con il punteggio migliore (le élite) e riadatta media e varianza della distribuzione a queste élite, spesso con un certo smorzamento verso i valori precedenti. Nel corso delle iterazioni la distribuzione si restringe attorno a una buona soluzione. Il metodo è stato sviluppato da Reuven Rubinstein alla fine degli anni 1990, prima per stimare probabilità di eventi rari e poi per l'ottimizzazione; il nome deriva dal fatto che il passo di riadattamento minimizza l'entropia incrociata, o divergenza KL, tra la distribuzione di campionamento e una distribuzione concentrata sui campioni con punteggio alto.

In robotica il CEM è noto soprattutto come ottimizzatore di traiettorie all'interno del controllo predittivo basato su modello a campionamento. La variabile decisionale è una sequenza di azioni su un orizzonte di pianificazione. Ogni sequenza campionata viene fatta evolvere attraverso un modello dinamico, che sia un simulatore fisico o un modello appreso, e valutata in base al costo sommato o alla ricompensa prevista. Dopo alcune iterazioni del CEM, il robot esegue la prima azione della sequenza media o di quella migliore, poi ripianifica al passo successivo, di solito con un avvio a caldo che sposta in avanti nel tempo la soluzione precedente. Metodi di apprendimento per rinforzo basato su modello come PETS e PlaNet usano il CEM in questo modo con modelli appresi, e alcune varianti aggiungono rumore correlato nel tempo, riutilizzano le élite tra i passi o combinano il CEM con una policy appresa che propone i campioni.

Il pregio del CEM è che non richiede gradienti, gestisce costi non lisci o discontinui ed è facile da eseguire in parallelo su una GPU. I suoi punti deboli sono il costo in campioni, che cresce rapidamente con la lunghezza dell'orizzonte e il numero di dimensioni dell'azione, e la tendenza a far collassare troppo presto la varianza su un ottimo locale. A differenza di MPPI, che pesa tutti i campioni con un esponenziale del loro costo, il CEM usa una soglia netta e tratta le élite allo stesso modo. A differenza degli ottimizzatori di traiettorie basati sul gradiente come iLQR o DDP, non sfrutta le derivate del modello, quindi di solito è meno efficiente in termini di campioni sui problemi lisci ma più tollerante verso modelli appresi o a scatola nera.

Perché è importante

Il CEM è uno dei modi più semplici per trasformare un modello dinamico in un controllore e compare come pianificatore predefinito in molti articoli di apprendimento basato su modello. Capire i compromessi tra selezione delle élite, orizzonte e numero di campioni è necessario per riprodurre quei risultati o per decidere se un pianificatore basato sul gradiente o di tipo MPPI sia più adatto a un problema.

Applicazioni principali

• Controllo predittivo basato su modello a campionamento con modelli dinamici appresi
• Pianificazione in world model latenti per il controllo visivo
• Selezione di prese e azioni tramite campionamento e valutazione dei candidati
• Ricerca di policy e taratura di parametri senza gradienti
• Ottimizzazione delle azioni nel Q-learning con spazi di azione continui

In pratica

Un gruppo che usa un modello dinamico appreso per un compito di spinta esegue un MPC basato sul CEM a ogni passo di controllo. Campiona diverse centinaia di sequenze di azioni su un orizzonte breve da una gaussiana, fa evolvere ciascuna nel modello appreso sulla GPU, conserva il decimo migliore per costo previsto, riadatta media e varianza e ripete alcune volte prima di eseguire la prima azione. Quando il pianificatore oscila tra un passo e l'altro, il gruppo trasla e riutilizza la media precedente come avvio a caldo e aggiunge una varianza minima perché la ricerca non collassi. Poiché il CEM sfrutterà gli errori del modello che prevedono costi irrealisticamente bassi, aggiunge anche una penalità per le sequenze di azioni che si allontanano molto dai dati di addestramento del modello.

Idee sbagliate comuni

• Il CEM è un algoritmo di apprendimento per rinforzo — è un ottimizzatore di uso generale; nell'RL basato su modello pianifica con un modello, mentre l'apprendimento avviene nel modello o nella funzione di valore
• Più iterazioni del CEM aiutano sempre — la varianza può collassare prematuramente su un ottimo locale scadente, e con un modello appreso l'ottimizzazione aggiuntiva può sfruttare gli errori del modello
• CEM e MPPI sono la stessa cosa — entrambi campionano sequenze di azioni, ma il CEM si riadatta a un insieme di élite selezionato con soglia netta, mentre MPPI pesa ogni campione con l'esponenziale del suo costo

Chi dovrebbe saperlo

• Ricercatori di apprendimento per rinforzo basato su modello
• Ingegneri del controllo che usano MPC a campionamento
• Ingegneri della manipolazione che pianificano con modelli appresi o simulati
• Studenti che confrontano metodi di ottimizzazione delle traiettorie

Tecnologie correlate

• PETS
• PlaNet
• iCEM
• Random Shooting
• CMA-ES
• JAX

Termini correlati

• Model Predictive Path Integral
• Model Predictive Control
• Forward Dynamics Model
• World Model
• Differential dynamic programming
• Trajectory Planning

Progetti correlati

• Drake: MIT robotics toolbox for model-based dynamics, optimization, and control system design
• GTSAM: Factor-graph optimization library powering many modern SLAM backends
• PyRoki: Modular Python toolkit for kinematic optimization across CPU, GPU, and TPU via JAX
• MuJoCo MPC: DeepMind's interactive real-time model predictive control framework for MuJoCo
• PyPose: PyTorch library for differentiable robotics with deep learning and Lie group optimization
• NeuPAN: Real-time end-to-end planner that maps raw lidar points directly to robot actions