Cross-Entropy Method (CEM)
- 又稱: CEM
- 類別: Planning & manipulation › Trajectory optimisation
- 標籤: optimization, sampling-based-planning, model-predictive-control, model-based-rl, trajectory-optimization
一種以取樣為基礎的最佳化器，反覆取樣候選解，保留得分最好的一部分，並據以重新擬合取樣分布；廣泛用於在以模型為基礎的控制中最佳化動作序列。
定義
交叉熵方法（Cross-entropy method，CEM）是一種簡單的無導數最佳化演算法。它在候選解上維持一個機率分布，通常是具有平均值與對角變異數的高斯分布。每次迭代時，它抽取一批樣本，評估每個樣本的成本，選出得分最好的一部分（稱為菁英樣本），再以這些菁英樣本重新擬合分布的平均值與變異數，通常還會朝先前的數值做一些平滑。隨著迭代進行，分布會在一個良好的解附近收窄。此方法由 Reuven Rubinstein 於 1990 年代末提出，最初用於估計稀有事件的機率，之後才用於最佳化；其名稱來自重新擬合這一步會最小化取樣分布與集中在高分樣本上的分布之間的交叉熵（也就是 KL 散度）。
在機器人學中，CEM 最為人所知的是作為以取樣為基礎的模型預測控制中的軌跡最佳化器。決策變數是規劃時域內的一串動作序列。每個取樣出的序列都會透過動力學模型（物理模擬器或學習而得的模型）推演，並依累計成本或預測獎勵評分。經過幾次 CEM 迭代後，機器人執行平均序列或最佳序列的第一個動作，接著在下一步重新規劃，通常會把上一次的解在時間上往前平移，作為暖啟動。PETS 與 PlaNet 等以模型為基礎的強化學習方法，就是以這種方式將 CEM 搭配學習而得的模型使用；各種變體則加入時間相關雜訊、跨步驟重複使用菁英樣本，或把 CEM 與負責提出樣本的學習策略結合。
CEM 的吸引力在於不需要梯度、能處理不平滑或不連續的成本，而且容易在 GPU 上平行執行。其缺點是樣本成本會隨時域長度與動作維度快速成長，而且容易過早把變異數收縮到某個局部最佳解上。與依成本的指數為所有樣本加權的 MPPI 不同，CEM 採用硬性截斷，並平等看待各個菁英樣本。與 iLQR 或 DDP 等以梯度為基礎的軌跡最佳化器不同，它不利用模型的導數，因此在平滑問題上通常樣本效率較低，但對學習而得的模型或黑箱模型較為寬容。
為何重要
CEM 是把動力學模型轉成控制器最簡單的方法之一，也是許多以模型為基礎的學習論文中的預設規劃器。要重現這些結果，或判斷以梯度為基礎的規劃器或 MPPI 類型的規劃器是否更適合某個問題，就必須了解它在菁英選擇、時域與樣本數之間的取捨。
主要應用
- 搭配學習而得的動力學模型，進行以取樣為基礎的模型預測控制
- 在潛在世界模型中為視覺控制進行規劃
- 透過取樣與評分候選項目來選擇夾取方式與動作
- 不需梯度的策略搜尋與參數調校
- 在連續動作空間的 Q-learning 中最佳化動作
實際應用
一個團隊在推動任務中使用學習而得的動力學模型，並在每個控制步驟執行以 CEM 為基礎的 MPC。他們從高斯分布取樣數百個短時域的動作序列，在 GPU 上讓每個序列通過學習而得的模型推演，依預測成本保留前十分之一，重新擬合平均值與變異數，重複幾次後再執行第一個動作。當規劃器在相鄰步驟之間來回抖動時，他們把上一次的平均值平移後重複使用作為暖啟動，並設定最小變異數，避免搜尋過早收斂。由於 CEM 會鑽那些預測出不切實際低成本的模型誤差，他們也對遠離模型訓練資料的動作序列加上懲罰。
常見誤解
- CEM 是一種強化學習演算法 — 它是通用的最佳化器；在以模型為基礎的 RL 中，它利用模型做規劃，學習則發生在模型或價值函數中
- CEM 迭代次數越多一定越好 — 變異數可能過早收縮到不佳的局部最佳解，而使用學習而得的模型時，額外的最佳化可能會鑽模型誤差的漏洞
- CEM 與 MPPI 是同一回事 — 兩者都會取樣動作序列，但 CEM 依硬性選出的菁英集合重新擬合，MPPI 則依指數化的成本為每個樣本加權
誰需要了解
- 以模型為基礎的強化學習研究人員
- 使用以取樣為基礎之 MPC 的控制工程師
- 以學習而得或模擬的模型進行規劃的操作工程師
- 比較軌跡最佳化方法的學生
相關技術
- PETS
- PlaNet
- iCEM
- 隨機射擊法（Random Shooting）
- CMA-ES
- JAX
相關術語
- Model Predictive Path Integral
- Model Predictive Control
- Forward Dynamics Model
- World Model
- Differential dynamic programming
- Trajectory Planning
相關專案
- 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