Cross-Entropy Method (CEM)

• También llamado: CEM
• Categoría: Planning & manipulation › Trajectory optimisation
• Etiquetas: optimization, sampling-based-planning, model-predictive-control, model-based-rl, trajectory-optimization

Un optimizador basado en muestreo que extrae repetidamente soluciones candidatas, conserva la fracción con mejor puntuación y reajusta a ellas la distribución de muestreo; muy usado para optimizar secuencias de acciones en el control basado en modelos.

Definición

El método de entropía cruzada (cross-entropy method, CEM) es un algoritmo de optimización sencillo y sin derivadas. Mantiene una distribución de probabilidad sobre las soluciones candidatas, normalmente una gaussiana con una media y una varianza diagonal. En cada iteración extrae un lote de muestras, evalúa el coste de cada una, selecciona la fracción con mejor puntuación (las élites) y vuelve a ajustar la media y la varianza de la distribución a esas élites, a menudo con cierto suavizado hacia los valores anteriores. A lo largo de las iteraciones, la distribución se estrecha alrededor de una buena solución. El método lo desarrolló Reuven Rubinstein a finales de la década de 1990, primero para estimar probabilidades de eventos raros y después para optimización; su nombre se debe a que el paso de reajuste minimiza la entropía cruzada, o divergencia KL, entre la distribución de muestreo y una distribución concentrada en las muestras de alta puntuación.

En robótica, el CEM es conocido sobre todo como el optimizador de trayectorias dentro del control predictivo basado en modelo por muestreo. La variable de decisión es una secuencia de acciones a lo largo de un horizonte de planificación. Cada secuencia muestreada se simula a través de un modelo de dinámica, ya sea un simulador físico o un modelo aprendido, y se puntúa por el coste acumulado o la recompensa predicha. Tras unas pocas iteraciones de CEM, el robot ejecuta la primera acción de la secuencia media o de la mejor, y luego vuelve a planificar en el paso siguiente, normalmente con un arranque en caliente que desplaza en el tiempo la solución anterior. Métodos de aprendizaje por refuerzo basado en modelos como PETS y PlaNet usan el CEM de esta forma con modelos aprendidos, y algunas variantes añaden ruido correlacionado en el tiempo, reutilizan las élites entre pasos o combinan el CEM con una política aprendida que propone muestras.

El atractivo del CEM es que no necesita gradientes, admite costes no suaves o discontinuos y es fácil de ejecutar en paralelo en una GPU. Sus debilidades son el coste en muestras, que crece rápidamente con la longitud del horizonte y el número de dimensiones de la acción, y la tendencia a colapsar su varianza demasiado pronto sobre un óptimo local. A diferencia de MPPI, que pondera todas las muestras con una exponencial de su coste, el CEM usa un corte estricto y trata a las élites por igual. A diferencia de los optimizadores de trayectorias basados en gradientes como iLQR o DDP, no aprovecha las derivadas del modelo, por lo que suele ser menos eficiente en muestras en problemas suaves, pero más tolerante con modelos aprendidos o de caja negra.

Por qué importa

El CEM es una de las formas más sencillas de convertir un modelo de dinámica en un controlador, y aparece como planificador por defecto en muchos artículos de aprendizaje basado en modelos. Entender sus compromisos de selección de élites, horizonte y número de muestras es necesario para reproducir esos resultados o para decidir si un planificador basado en gradientes o de estilo MPPI encaja mejor en un problema.

Aplicaciones clave

• Control predictivo basado en modelo por muestreo con modelos de dinámica aprendidos
• Planificación en modelos del mundo latentes para control visual
• Selección de agarres y acciones mediante el muestreo y la puntuación de candidatos
• Búsqueda de políticas y ajuste de parámetros sin gradientes
• Optimización de acciones en Q-learning con espacios de acción continuos

En la práctica

Un equipo que usa un modelo de dinámica aprendido para una tarea de empuje ejecuta MPC basado en CEM en cada paso de control. Muestrean varios cientos de secuencias de acciones sobre un horizonte corto a partir de una gaussiana, simulan cada una con el modelo aprendido en la GPU, conservan la décima parte con menor coste predicho, reajustan la media y la varianza y repiten unas pocas veces antes de ejecutar la primera acción. Cuando el planificador oscila entre pasos, desplazan y reutilizan la media anterior como arranque en caliente y añaden una varianza mínima para que la búsqueda no colapse. Como el CEM explotará los errores del modelo que predicen costes irrealmente bajos, también añaden una penalización para las secuencias de acciones que se alejan mucho de los datos de entrenamiento del modelo.

Ideas erróneas comunes

• El CEM es un algoritmo de aprendizaje por refuerzo — es un optimizador de propósito general; en el RL basado en modelos planifica con un modelo, mientras que el aprendizaje ocurre en el modelo o en la función de valor
• Más iteraciones de CEM siempre ayudan — la varianza puede colapsar prematuramente sobre un óptimo local pobre, y con un modelo aprendido la optimización adicional puede explotar los errores del modelo
• El CEM y MPPI son lo mismo — ambos muestrean secuencias de acciones, pero el CEM se reajusta a un conjunto de élites seleccionado con un corte estricto, mientras que MPPI pondera cada muestra por la exponencial de su coste

Quién debería saberlo

• Investigadores en aprendizaje por refuerzo basado en modelos
• Ingenieros de control que usan MPC basado en muestreo
• Ingenieros de manipulación que planifican con modelos aprendidos o simulados
• Estudiantes que comparan métodos de optimización de trayectorias

Tecnologías relacionadas

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

Términos relacionados

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

Proyectos relacionados

• 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