Cross-Entropy Method (CEM)

Também chamado: CEM
Categoria: Planning & manipulation › Trajectory optimisation
Tags: optimization, sampling-based-planning, model-predictive-control, model-based-rl, trajectory-optimization

Um otimizador baseado em amostragem que repetidamente sorteia soluções candidatas, mantém a fração com melhor pontuação e reajusta a elas a distribuição de amostragem; muito usado para otimizar sequências de ações no controle baseado em modelo.

Definição

O método da entropia cruzada (cross-entropy method, CEM) é um algoritmo de otimização simples e sem derivadas. Ele mantém uma distribuição de probabilidade sobre as soluções candidatas, geralmente uma gaussiana com uma média e uma variância diagonal. A cada iteração, ele sorteia um lote de amostras, avalia o custo de cada uma, seleciona a fração com melhor pontuação (as elites) e reajusta a média e a variância da distribuição a essas elites, muitas vezes com alguma suavização em direção aos valores anteriores. Ao longo das iterações, a distribuição se estreita em torno de uma boa solução. O método foi desenvolvido por Reuven Rubinstein no final da década de 1990, primeiro para estimar probabilidades de eventos raros e depois para otimização; seu nome vem do fato de que o passo de reajuste minimiza a entropia cruzada, ou divergência KL, entre a distribuição de amostragem e uma distribuição concentrada nas amostras de alta pontuação.

Em robótica, o CEM é mais conhecido como o otimizador de trajetórias dentro do controle preditivo baseado em modelo por amostragem. A variável de decisão é uma sequência de ações ao longo de um horizonte de planejamento. Cada sequência amostrada é simulada através de um modelo de dinâmica, seja um simulador físico ou um modelo aprendido, e pontuada pelo custo somado ou pela recompensa prevista. Após algumas iterações do CEM, o robô executa a primeira ação da sequência média ou da melhor e replaneja no passo seguinte, normalmente com partida a quente, deslocando a solução anterior para a frente no tempo. Métodos de aprendizado por reforço baseado em modelo como PETS e PlaNet usam o CEM dessa forma com modelos aprendidos, e variantes acrescentam ruído correlacionado no tempo, reutilizam elites entre passos ou combinam o CEM com uma política aprendida que propõe amostras.

O atrativo do CEM é que ele não precisa de gradientes, lida com custos não suaves ou descontínuos e é fácil de executar em paralelo em uma GPU. Suas fraquezas são o custo em amostras, que cresce rapidamente com o comprimento do horizonte e o número de dimensões da ação, e a tendência de colapsar sua variância cedo demais sobre um ótimo local. Diferentemente do MPPI, que pondera todas as amostras por uma exponencial de seu custo, o CEM usa um corte rígido e trata as elites igualmente. Diferentemente de otimizadores de trajetória baseados em gradiente como iLQR ou DDP, ele não explora as derivadas do modelo, por isso costuma ser menos eficiente em amostras em problemas suaves, porém mais tolerante a modelos aprendidos ou de caixa-preta.

Por que importa

O CEM é uma das formas mais simples de transformar um modelo de dinâmica em um controlador e aparece como o planejador padrão em muitos artigos de aprendizado baseado em modelo. Entender seus compromissos entre seleção de elites, horizonte e número de amostras é necessário para reproduzir esses resultados ou para decidir se um planejador baseado em gradiente ou no estilo MPPI se adequa melhor a um problema.

Principais aplicações

Controle preditivo baseado em modelo por amostragem com modelos de dinâmica aprendidos
Planejamento em modelos de mundo latentes para controle visual
Seleção de preensões e ações por amostragem e pontuação de candidatos
Busca de políticas e ajuste de parâmetros sem gradientes
Otimização de ações em Q-learning com espaços de ação contínuos

Na prática

Uma equipe que usa um modelo de dinâmica aprendido para uma tarefa de empurrar executa MPC baseado em CEM a cada passo de controle. Ela amostra várias centenas de sequências de ações ao longo de um horizonte curto a partir de uma gaussiana, simula cada uma no modelo aprendido na GPU, mantém o décimo superior pelo custo previsto, reajusta a média e a variância e repete algumas vezes antes de executar a primeira ação. Quando o planejador oscila entre os passos, a equipe desloca e reutiliza a média anterior como partida a quente e acrescenta uma variância mínima para que a busca não colapse. Como o CEM vai explorar os erros do modelo que preveem custos irrealisticamente baixos, ela também acrescenta uma penalidade para sequências de ações que se afastam muito dos dados de treinamento do modelo.

Equívocos comuns

O CEM é um algoritmo de aprendizado por reforço — ele é um otimizador de uso geral; no RL baseado em modelo, ele planeja com um modelo, enquanto o aprendizado acontece no modelo ou na função de valor
Mais iterações do CEM sempre ajudam — a variância pode colapsar prematuramente sobre um ótimo local ruim e, com um modelo aprendido, a otimização extra pode explorar os erros do modelo
CEM e MPPI são a mesma coisa — ambos amostram sequências de ações, mas o CEM se reajusta a um conjunto de elites selecionado por corte rígido, enquanto o MPPI pondera cada amostra pela exponencial de seu custo

Quem deve saber

Pesquisadores de aprendizado por reforço baseado em modelo
Engenheiros de controle que usam MPC baseado em amostragem
Engenheiros de manipulação que planejam com modelos aprendidos ou simulados
Estudantes que comparam métodos de otimização de trajetória

Tecnologias relacionadas

PETS
PlaNet
iCEM
Random Shooting
CMA-ES
JAX

Termos relacionados

Projetos 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