Cross-Entropy Method (CEM)

• Aussi appelé: CEM
• Catégorie: Planning & manipulation › Trajectory optimisation
• Mots-clés: optimization, sampling-based-planning, model-predictive-control, model-based-rl, trajectory-optimization

Un optimiseur à base d'échantillonnage qui tire de façon répétée des solutions candidates, conserve la fraction la mieux notée et réajuste sur elle la distribution d'échantillonnage ; largement utilisé pour optimiser des séquences d'actions en commande fondée sur un modèle.

Définition

La méthode de l'entropie croisée (cross-entropy method, CEM) est un algorithme d'optimisation simple sans dérivées. Elle maintient une distribution de probabilité sur les solutions candidates, généralement une gaussienne avec une moyenne et une variance diagonale. À chaque itération, elle tire un lot d'échantillons, évalue le coût de chacun, sélectionne la fraction la mieux notée (les élites) et réajuste la moyenne et la variance de la distribution sur ces élites, souvent avec un certain lissage vers les valeurs précédentes. Au fil des itérations, la distribution se resserre autour d'une bonne solution. La méthode a été développée par Reuven Rubinstein à la fin des années 1990, d'abord pour estimer des probabilités d'événements rares, puis pour l'optimisation ; son nom vient du fait que l'étape de réajustement minimise l'entropie croisée, ou divergence KL, entre la distribution d'échantillonnage et une distribution concentrée sur les échantillons les mieux notés.

En robotique, la CEM est surtout connue comme l'optimiseur de trajectoire au sein de la commande prédictive par modèle à base d'échantillonnage. La variable de décision est une séquence d'actions sur un horizon de planification. Chaque séquence échantillonnée est déroulée à travers un modèle dynamique, soit un simulateur physique, soit un modèle appris, et notée par le coût cumulé ou la récompense prédite. Après quelques itérations de CEM, le robot exécute la première action de la séquence moyenne ou de la meilleure séquence, puis replanifie au pas suivant, généralement en démarrant à chaud par un décalage de la solution précédente dans le temps. Des méthodes d'apprentissage par renforcement fondé sur un modèle comme PETS et PlaNet utilisent la CEM de cette façon avec des modèles appris, et des variantes ajoutent un bruit corrélé dans le temps, réutilisent les élites d'un pas à l'autre ou combinent la CEM avec une politique apprise qui propose des échantillons.

L'intérêt de la CEM est qu'elle ne nécessite aucun gradient, gère des coûts non lisses ou discontinus et s'exécute facilement en parallèle sur un GPU. Ses faiblesses sont le coût en échantillons, qui croît rapidement avec la longueur de l'horizon et le nombre de dimensions d'action, et une tendance à effondrer sa variance trop tôt sur un optimum local. Contrairement à MPPI, qui pondère tous les échantillons par une exponentielle de leur coût, la CEM utilise un seuil strict et traite les élites à égalité. Contrairement aux optimiseurs de trajectoire à base de gradient comme iLQR ou DDP, elle n'exploite pas les dérivées du modèle ; elle est donc généralement moins efficace en échantillons sur les problèmes lisses, mais plus tolérante envers les modèles appris ou boîte noire.

Pourquoi c'est important

La CEM est l'un des moyens les plus simples de transformer un modèle dynamique en contrôleur, et elle apparaît comme planificateur par défaut dans de nombreux articles d'apprentissage fondé sur un modèle. Comprendre ses compromis entre sélection des élites, horizon et nombre d'échantillons est nécessaire pour reproduire ces résultats ou pour décider si un planificateur à base de gradient ou de type MPPI convient mieux à un problème.

Applications principales

• Commande prédictive par modèle à base d'échantillonnage avec des modèles dynamiques appris
• Planification dans des modèles du monde latents pour la commande visuelle
• Sélection de saisies et d'actions par échantillonnage et notation de candidats
• Recherche de politique et réglage de paramètres sans gradients
• Optimisation des actions en Q-learning avec des espaces d'actions continus

En pratique

Une équipe qui utilise un modèle dynamique appris pour une tâche de poussée exécute une MPC fondée sur la CEM à chaque pas de commande. Elle échantillonne plusieurs centaines de séquences d'actions sur un horizon court à partir d'une gaussienne, déroule chacune à travers le modèle appris sur le GPU, garde le meilleur dixième selon le coût prédit, réajuste la moyenne et la variance, et recommence quelques fois avant d'exécuter la première action. Quand le planificateur oscille d'un pas à l'autre, elle décale et réutilise la moyenne précédente comme démarrage à chaud et ajoute une variance minimale pour que la recherche ne s'effondre pas. Comme la CEM exploite les erreurs du modèle qui prédisent des coûts irréalistement bas, l'équipe ajoute aussi une pénalité pour les séquences d'actions qui s'éloignent beaucoup des données d'entraînement du modèle.

Idées reçues

• La CEM est un algorithme d'apprentissage par renforcement — c'est un optimiseur généraliste ; en RL fondé sur un modèle, elle planifie avec un modèle, tandis que l'apprentissage se fait dans le modèle ou la fonction de valeur
• Davantage d'itérations de CEM aident toujours — la variance peut s'effondrer prématurément sur un mauvais optimum local, et avec un modèle appris, une optimisation supplémentaire peut exploiter les erreurs du modèle
• La CEM et MPPI sont la même chose — les deux échantillonnent des séquences d'actions, mais la CEM se réajuste sur un ensemble d'élites sélectionné strictement, tandis que MPPI pondère chaque échantillon par son coût exponentié

Qui devrait le savoir

• Chercheurs en apprentissage par renforcement fondé sur un modèle
• Ingénieurs en commande utilisant la MPC à base d'échantillonnage
• Ingénieurs en manipulation qui planifient avec des modèles appris ou simulés
• Étudiants qui comparent des méthodes d'optimisation de trajectoire

Technologies associées

• PETS
• PlaNet
• iCEM
• Tir aléatoire (Random Shooting)
• CMA-ES
• JAX

Termes associés

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

Projets associés

• 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