Differential dynamic programming
- 別名: DDP
- カテゴリ: Planning & manipulation › Trajectory optimisation
- タグ: trajectory-optimization, optimal-control, model-predictive-control, numerical-optimization, shooting-methods
現在の軌道に沿った残りコスト（cost-to-go）の局所的な 2 次モデルを用い、後退パスと前進パスを繰り返して制御入力列を改善する軌道最適化手法。
定義
微分動的計画法（Differential dynamic programming、DDP）は軌道最適化のアルゴリズムである。ダイナミクスモデル、状態と制御入力に関するコスト、初期状態が与えられると、総コストを局所的に最小化する制御入力列を求める。1966 年に David Mayne が提案し、Jacobson と Mayne による 1970 年の同名の書籍でさらに発展した。DDP はシューティング法の一種である。決定変数は制御入力であり、古典的な形式では状態は常にダイナミクスを前向きにシミュレーションして得られるため、各反復の結果は常に動力学的に実行可能な軌道になる。
各反復は 2 つのパスからなる。後退パスは最終時刻ステップから始点に向かって進み、Bellman の最適性原理を局所的に適用する。ダイナミクスとコストの 1 階および 2 階微分から、現在の軌道まわりで残りコスト（cost-to-go）の 2 次近似を構成し、各ステップでフィードフォワード項 k とフィードバックゲイン行列 K からなるアフィンな制御更新を解く。続いて前進パスが、更新された制御入力 u = ū + αk + K(x − x̄) でシステムをシミュレーションする。ここで α は直線探索のステップ幅である。展開にダイナミクスの 2 次の項が含まれるため、DDP は局所最小解の近くでニュートン法と同様に 2 次収束し、1 反復あたりの計算量はホライズン長に対して線形にしか増えない。
ダイナミクスの 2 階微分は計算コストが高いため、最も広く使われている変種である反復線形二次レギュレータ（iLQR）はこれを省き、ダイナミクスの 1 次モデル、すなわち Gauss-Newton 近似を用いる。実用的なソルバーは後退パスを正則化して良条件に保ち、手法を制御入力の制限（制御制約付き DDP）、一般的な制約（ALTRO などの拡張ラグランジュ法）、実行不可能な初期推定（Crocoddyl の feasibility-driven DDP）、そして Parameterized DDP のように制御入力と同時に最適化する時不変パラメータへと拡張している。DDP は局所最適解しか見つけないため、結果は初期推定に依存する。有用な副産物としてフィードバックゲインの組が得られ、最適化された軌道のまわりでロボットを安定化するのに使える。
重要な理由
DDP と iLQR は、ロボットの軌道最適化と非線形モデル予測制御で最もよく使われるソルバーの一つである。問題の時間構造を利用し、ホライズン長に対して線形にスケールし、軌道とともに局所的なフィードバックポリシーを返す。これが、脚ロボット、ヒューマノイドロボット、ドローンがこれらを機上でリアルタイムに実行している理由である。
主な用途
- 脚ロボットとヒューマノイドロボットの非線形モデル予測制御
- ドローンや俊敏な移動体の軌道最適化
- ロボットアームのトルクレベルの動作計画
- 劣駆動システムの振り上げとバランス
- 軌道とモデルパラメータまたは設計パラメータの同時最適化
実際の使われ方
四足ロボットの全身モデル予測制御を構築するチームが、問題を Crocoddyl で定式化する。接触シーケンスは固定の歩容スケジュールから与えられるので、各フェーズの接触は既知であり、コストはベースの追従、足の配置、制御入力の大きさ、そして接触力を摩擦円錐の内側に保つためのペナルティを組み合わせたものである。各制御周期で、ソルバーは前回の解を 1 ステップずらしたものでウォームスタートし、1 回か数回だけ反復する。最初の制御入力とそのフィードバックゲインは下位の関節コントローラに送られ、関節コントローラはそのゲインを使ってソルバーの更新と更新の間の状態変化を補正する。調整作業の大部分はコストの重み、正則化、ホライズン長に費やされ、これらが先読みと求解時間のトレードオフを決める。
よくある誤解
- DDP は大域的に最適な軌道を見つける — DDP は局所的な手法であり、結果は初期推定に依存し、質の悪い局所最小解になることもある
- iLQR と DDP は同じアルゴリズムである — iLQR はダイナミクスの 2 次の項を省くため、1 反復がはるかに安価になる代わりに、解の近くでの収束が遅くなる
- DDP は制約を扱えない — 基本のアルゴリズムは制約なしだが、制御制約付きや拡張ラグランジュの変種が広く使われている
- DDP は状態空間全体にわたる動的計画法である — Bellman の再帰を 1 本の軌道に沿ってのみ適用するため、次元の呪いを避けられるが、得られるのは局所的な結果だけである
知っておくべき人
- 脚ロボットやドローン向けのモデル予測制御コントローラを構築する制御エンジニア
- 軌道最適化の研究者
- ヒューマノイドロボットと全身制御の開発者
- 最適制御を学ぶロボティクスの学生
関連技術
- iLQR
- Crocoddyl
- ALTRO
- Riccati 再帰（Riccati Recursion）
- シューティング法（Shooting Methods）
関連用語
- Direct Collocation
- Model Predictive Control
- Trajectory Planning
- Moving horizon estimation
- Underactuated system
- Hybrid system
関連プロジェクト
- 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
- python_simple_mppi: MPPI control derived and implemented in numpy, with four worked examples
- mjbatch: Runs thousands of MuJoCo simulations in parallel on the CPU
- Quadruped-PyMPC: Python MPC framework for quadruped locomotion with gradient and sampling control
- STLCG: JAX toolbox for differentiable Signal Temporal Logic robustness