微分動的計画法

微分動的計画法（びぶんどうてきけいかくほう、テンプレート:Lang-en-short、略称：DDP）は軌道最適化のために用いられる最適制御アルゴリズムの一つである。本アルゴリズムは1966年にテンプレート:仮リンクによって紹介され、その後JacobsonとMayneによるその名の由来となった著作の中で分析された。このアルゴリズムはシステムのダイナミクスとコスト関数を局所的な二次形式によってモデル化し、2次収束を示す。また、Pantojaのstep-wise Newton法とも密接に関連している。

有限horizon離散時間問題

次式のダイナミクスを考える。

これは制御入力 $𝐮$ の下での状態 $𝐱$ の時刻 $i$ から $i+1$　までの時間発展を表している。  総コスト $J_0$ は、ランニングコスト $\ell$ と最終コスト ${\ell }_f$ の和として与えられ、状態 $𝐱$ と終端時刻までに適用する制御系列 $𝐔\equiv \{{𝐮}_0,{𝐮}_1\dots ,{𝐮}_{N-1}\}$ によって定まる:

$J_0(𝐱,𝐔)=\sum _{i=0}^{N-1}\ell ({𝐱}_i,{𝐮}_i)+{\ell }_f({𝐱}_N),$

ここで ${𝐱}_0\equiv 𝐱$ であり、時刻 $i>0$ における状態 ${𝐱}_i$ は式テンプレート:EquationNoteによって与えられる。この最適制御問題の解は、上式を最小化する制御系列 ${𝐔}^{*}(𝐱)\equiv {\mathrm{argmin}}_{𝐔}{J}_0(𝐱,𝐔)$ である。 これに対し、ありえる初期状態すべてを考えるのではなく、特定の初期状態 ${𝐱}_0$ に対して最適な入力系列 ${𝐔}^{*}(𝐱)$ を求めるのが軌道最適化である。

動的計画法

今、${𝐔}_i$ を制御入力の部分系列 ${𝐔}_i\equiv \{{𝐮}_i,{𝐮}_{i+1}\dots ,{𝐮}_{N-1}\}$ とし、残余コスト（cost-to-go）$J_i$ を $i$ から $N$ までの部分和として定義する:

$J_i(𝐱,{𝐔}_i)=\sum _{j=i}^{N-1}\ell ({𝐱}_j,{𝐮}_j)+{\ell }_f({𝐱}_N).$

最適な残余コスト、または時刻 $i$ での価値関数は、以下のような制御系列による最小化で与えられる:

$V(𝐱,i)\equiv \underset{{𝐔}_i}{\min }{J}_i(𝐱,{𝐔}_i).$

$V(𝐱,N)\equiv {\ell }_f({𝐱}_N)$　を出発点として、時間を遡る方向に制御入力を一ステップ毎に最小化することにより、動的計画法の原理は全体の最小化に必要な計算量を削減する。

これがベルマン方程式である。

微分動的計画法 (DDP)

微分動的計画法（DDP）では、新しい制御系列を計算するために、ノミナルな軌道に沿って逆方向パスの計算を行い、次に（得られた制御系列のもとでの）新しい軌道とその評価値を得るために順方向パスの計算を行うことを繰り返す。逆方向パスの計算から始めよう。

式テンプレート:EquationNoteの $\min []$ 演算子の引数

$\ell (𝐱,𝐮)+V(𝐟(𝐱,𝐮),i+1)$

に関して、その値の変分を時刻 $i$ の状態-入力ペア $(𝐱,𝐮)$ 周辺でとったものを $Q$ としよう:

$\begin{array}{cccc}Q(\delta 𝐱,\delta 𝐮)\equiv & \ell (𝐱+\delta 𝐱,𝐮+\delta 𝐮)& & +V(𝐟(𝐱+\delta 𝐱,𝐮+\delta 𝐮),i+1)\\ -& \ell (𝐱,𝐮)& & -V(𝐟(𝐱,𝐮),i+1)\end{array}$

これを、二次形式に展開する。

ここで用いる $Q$ の表記は、森本淳（ATR脳情報研究所）の記法の変形版であり、添字は偏微分の分母を示している。

見やすくするため、添字の $i$ を省略し、次の時間ステップの変数は $V^{\prime }\equiv V(i+1)$のようにプライムをつけて示そう。テイラー展開により係数は以下となる。

$\begin{array}{cc}{Q}_{𝐱}& ={\ell }_{𝐱}+{𝐟}_{𝐱}^{𝖳}V{\text{'}}_{𝐱}\\ Q_{𝐮}& ={\ell }_{𝐮}+{𝐟}_{𝐮}^{𝖳}V{\text{'}}_{𝐱}\\ Q_{𝐱𝐱}& ={\ell }_{𝐱𝐱}+{𝐟}_{𝐱}^{𝖳}V{\text{'}}_{𝐱𝐱}{𝐟}_{𝐱}+{V_{𝐱}}^{\prime }\cdot {𝐟}_{𝐱𝐱}\\ Q_{𝐮𝐮}& ={\ell }_{𝐮𝐮}+{𝐟}_{𝐮}^{𝖳}V{\text{'}}_{𝐱𝐱}{𝐟}_{𝐮}+V{\text{'}}_{𝐱}\cdot {𝐟}_{𝐮𝐮}\\ Q_{𝐮𝐱}& ={\ell }_{𝐮𝐱}+{𝐟}_{𝐮}^{𝖳}V{\text{'}}_{𝐱𝐱}{𝐟}_{𝐱}+V{\text{'}}_{𝐱}\cdot {𝐟}_{𝐮𝐱}.\end{array}$

最後の三つの方程式に現れる最終項はベクトルとテンソルの縮約（contraction）を表す。 二次形式で近似された式テンプレート:EquationNote を入力$\delta 𝐮$に関して最小化することで次式を得る。

これにより、オープンループ項 $𝐤=-Q_{𝐮𝐮}^{-1}{Q}_{𝐮}$ とフィードバック項 $𝐊=-Q_{𝐮𝐮}^{-1}{Q}_{𝐮𝐱}$ が与えられる。この結果を式テンプレート:EquationNoteに代入することにより 時間 $i$ における価値関数が得られる。

$\begin{array}{ccc}\mathrm{\Delta }V(i)& =& -\frac{1}{2}{Q}_{𝐮}{Q}_{𝐮𝐮}^{-1}{Q}_{𝐮}\\ V_{𝐱}(i)& =Q_{𝐱}& -Q_{𝐮}{Q}_{𝐮𝐮}^{-1}{Q}_{𝐮𝐱}\\ V_{𝐱𝐱}(i)& =Q_{𝐱𝐱}& -Q_{𝐱𝐮}{Q}_{𝐮𝐮}^{-1}{Q}_{𝐮𝐱}.\end{array}$

$i=N-1$ から $i=1$ に向かって、再帰的に価値関数 $V(i)$ の局所的な二次形式のモデルと、制御の修正量 $\{𝐤(i),𝐊(i)\}$ を求めるのが逆方向パスの計算である。 先に述べたように、価値関数の初期値は $V(𝐱,N)\equiv {\ell }_f({𝐱}_N)$ である。逆方向パスの完了後、新しい軌道にそって順方向パスの計算を行う。 

$\begin{array}{cc}\widehat{𝐱}(1)& =𝐱(1)\\ \widehat{𝐮}(i)& =𝐮(i)+𝐤(i)+𝐊(i)(\widehat{𝐱}(i)-𝐱(i))\\ \widehat{𝐱}(i+1)& =𝐟(\widehat{𝐱}(i),\widehat{𝐮}(i))\end{array}$

以上の逆方向パスと順方向パスの計算を収束するまで繰り返す。

正則化と直線探索

微分動的計画法は、ニュートン法と同様に、二次収束を示すアルゴリズムである。そのため、最小値に向けて大きな修正ステップが発生するため、収束を保証するために、正則化および/または直線探索が必要となる。

DDPの文脈における正則化とは、式テンプレート:EquationNoteの行列 $Q_{𝐮𝐮}$ の正定値性を保証することである。DDPにおける直線検索は、オープンループ制御修正量 $𝐤$ をスカラー $0<\alpha <1$ でスケーリングすることに対応する。

関連項目

• ベルマン方程式
• ハミルトン-ヤコビ-ベルマン方程式
• 動的計画法
• 最適制御

外部リンク

• PythonによるDDPの実装例
• MATLABによるDDPの実装例