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）は、単純な微分不要の最適化アルゴリズムである。候選解の上に確率分布を保持し、通常は平均と対角分散を持つガウス分布を用いる。各反復で一群のサンプルを抽出し、それぞれのコストを評価し、スコアの良い上位の一部（エリート）を選び、分布の平均と分散をそのエリートに再フィットする。多くの場合、前回の値に向けてある程度の平滑化も行う。反復を重ねるにつれ、分布は良い解の周りに狭まっていく。この手法は 1990 年代後半に Reuven Rubinstein によって開発され、最初はまれな事象の確率推定に、その後最適化に用いられた。名称は、再フィットのステップがサンプリング分布と高スコアのサンプルに集中した分布との間の交差エントロピー、すなわち KL ダイバージェンスを最小化することに由来する。
ロボティクスでは、CEM はサンプリングベースのモデル予測制御の内部で使われる軌道最適化器として最もよく知られている。決定変数は計画ホライズンにわたる行動系列である。サンプリングした各系列を、物理シミュレータまたは学習済みモデルのいずれかのダイナミクスモデルでロールアウトし、コストの総和または予測報酬でスコアを付ける。CEM を数回反復した後、ロボットは平均系列または最良系列の最初の行動を実行し、次のステップで再計画する。その際、前回の解を時間方向に前へずらしてウォームスタートに使うのが一般的である。PETS や PlaNet といったモデルベース強化学習の手法は、このように CEM を学習済みモデルと組み合わせて使っており、派生手法では時間的に相関したノイズを加えたり、エリートをステップ間で再利用したり、サンプルを提案する学習済みポリシーと CEM を組み合わせたりする。
CEM の魅力は、勾配を必要とせず、滑らかでない、あるいは不連続なコストを扱え、GPU 上で容易に並列実行できることにある。弱点は、ホライズンの長さと行動の次元数に応じて急速に増えるサンプルコストと、分散を早すぎる段階で局所最適解に収縮させてしまう傾向である。すべてのサンプルをコストの指数で重み付けする MPPI と異なり、CEM はハードな打ち切りを使い、エリートを均等に扱う。iLQR や DDP のような勾配ベースの軌道最適化器と異なり、モデルの導関数を利用しないため、滑らかな問題では通常サンプル効率が低いが、学習済みモデルやブラックボックスモデルに対してはより寛容である。
重要な理由
CEM はダイナミクスモデルをコントローラに変える最も単純な方法の 1 つであり、多くのモデルベース学習の論文でデフォルトのプランナとして登場する。エリート選択、ホライズン、サンプル数のトレードオフを理解することは、それらの結果を再現するためにも、勾配ベースや MPPI 型のプランナのほうが問題に合うかどうかを判断するためにも必要である。
主な用途
- 学習済みダイナミクスモデルを用いたサンプリングベースのモデル予測制御
- 視覚制御のための潜在世界モデル内でのプランニング
- 候選のサンプリングとスコア付けによる把持と行動の選択
- 勾配を使わないポリシー探索とパラメータ調整
- 連続行動空間を持つ Q-learning における行動の最適化
実際の使われ方
押し動作のタスクに学習済みダイナミクスモデルを使うチームが、制御ステップごとに CEM ベースの MPC を実行する。ガウス分布から短いホライズンの行動系列を数百本サンプリングし、GPU 上でそれぞれを学習済みモデルでロールアウトし、予測コストで上位 10 分の 1 を残して平均と分散を再フィットする。これを数回繰り返してから最初の行動を実行する。プランナがステップ間で細かく揺れる場合は、前回の平均をずらして再利用するウォームスタートを行い、探索が収縮しきらないよう分散に下限を設ける。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