微分動的計画法

微分動的計画法 (DDP)（びぶんどうてきけいかくほう、英: Differential Dynamic Programming）は軌道最適化のために用いられる最適制御アルゴリズムの一つである。 本アルゴリズムは1966年に Mayne によって紹介され、 その後JacobsonとMayneによるその名の由来となった著作の中で分析された。 このアルゴリズムはシステムのダイナミクスとコスト関数を局所的な二次形式によってモデル化し、2次収束を示す。 また、Pantojaのstep-wise Newton法とも密接に関連している。 次式のダイナミクスを考える。 x i + 1 = f ( x i , u i ) {\displaystyle \mathbf {x} _{i+1}=\mathbf {f} (\mathbf {x} _{i},\mathbf {u} _{i})} (1) これは制御入力 u {\displaystyle \mathbf {u} } のもとでの状態 x {\displaystyle \textstyle \mathbf {x} } の時刻 i {\displaystyle i}  から i + 1 {\displaystyle i+1} までの時間発展を表している。  総コスト J 0 {\displaystyle J_{0}}  は、ランニングコスト ℓ {\displaystyle \textstyle \ell }  と最終コスト ℓ f {\displaystyle \ell _{f}} 　の和として与えられ、状態 x {\displaystyle \mathbf {x} }  と終端時刻までに適用する制御系列 U ≡ { u 0 , u 1 … , u N − 1 } {\displaystyle \mathbf {U} \equiv \{\mathbf {u} _{0},\mathbf {u} _{1}\dots ,\mathbf {u} _{N-1}\}}  によって定まる: J 0 ( x , U ) = ∑ i = 0 N − 1 ℓ ( x i , u i ) + ℓ f ( x N ) , {\displaystyle J_{0}(\mathbf {x} ,\mathbf {U} )=\sum _{i=0}^{N-1}\ell (\mathbf {x} _{i},\mathbf {u} _{i})+\ell _{f}(\mathbf {x} _{N}),} ここで  x 0 ≡ x {\displaystyle \mathbf {x} _{0}\equiv \mathbf {x} } であり、時刻 i > 0 {\displaystyle i>0} における状態　 x i {\displaystyle \mathbf {x} _{i}} は式(1)によって与えられる。この最適制御問題の解は、上式を最小化する制御系列 U ∗ ( x ) ≡ argmin U ⁡ J 0 ( x , U ) . {\displaystyle \mathbf {U} ^{*}(\mathbf {x} )\equiv \operatorname {argmin} _{\mathbf {U} }J_{0}(\mathbf {x} ,\mathbf {U} ).} である。 これに対し、ありえる初期状態すべてを考えるのではなく、特定の初期状態 x 0 {\displaystyle \mathbf {x} _{0}} に対して最適な入力系列  U ∗ ( x ) {\displaystyle \mathbf {U} ^{*}(\mathbf {x} )}  を求めるのが 軌道最適化である。 今、  U i {\displaystyle \mathbf {U} _{i}} を制御入力の部分系列  U i ≡ { u i , u i + 1 … , u N − 1 } {\displaystyle \mathbf {U} _{i}\equiv \{\mathbf {u} _{i},\mathbf {u} _{i+1}\dots ,\mathbf {u} _{N-1}\}} 　とし、 残余コスト(cost-to-go) J i {\displaystyle J_{i}} 　を  i {\displaystyle i}  から  N {\displaystyle N} までの部分和として定義する: J i ( x , U i ) = ∑ j = i N − 1 ℓ ( x j , u j ) + ℓ f ( x N ) . {\displaystyle J_{i}(\mathbf {x} ,\mathbf {U} _{i})=\sum _{j=i}^{N-1}\ell (\mathbf {x} _{j},\mathbf {u} _{j})+\ell _{f}(\mathbf {x} _{N}).} 最適な残余コスト、または時刻  i {\displaystyle i}  での価値関数 は、以下のような制御系列による最小化で与えられる : V ( x , i ) ≡ min U i J i ( x , U i ) . {\displaystyle V(\mathbf {x} ,i)\equiv \min _{\mathbf {U} _{i}}J_{i}(\mathbf {x} ,\mathbf {U} _{i}).}   V ( x , N ) ≡ ℓ f ( x N ) {\displaystyle V(\mathbf {x} ,N)\equiv \ell _{f}(\mathbf {x} _{N})} を出発点として、 時間を遡る方向に制御入力を一ステップ毎に最小化することにより、動的計画法の原理は全体の最小化に必要な計算量を削減する。 V ( x , i ) = min u [ ℓ ( x , u ) + V ( f ( x , u ) , i + 1 ) ] . {\displaystyle V(\mathbf {x} ,i)=\min _{\mathbf {u} }[\ell (\mathbf {x} ,\mathbf {u} )+V(\mathbf {f} (\mathbf {x} ,\mathbf {u} ),i+1)].} (2) これがベルマン方程式である。 微分動的計画法 (DDP) では、新しい制御系列を計算するために、ノミナルな軌道に沿って逆方向パスの計算を行い、次に（得られた制御系列のもとでの）新しい軌道とその評価値を得るために順方向パスの計算を行うことを繰り返す。逆方向パスの計算から始めよう。 式(2)の  min [   ] {\displaystyle \min[~]}  演算子の引数 ℓ ( x , u ) + V ( f ( x , u ) , i + 1 ) {\displaystyle \ell (\mathbf {x} ,\mathbf {u} )+V(\mathbf {f} (\mathbf {x} ,\mathbf {u} ),i+1)} に関して、その値の変分を時刻 i {\displaystyle i} の状態-入力ペア ( x , u ) {\displaystyle (\mathbf {x} ,\mathbf {u} )} 周辺でとったものを Q {\displaystyle Q} としよう: Q ( δ x , δ u ) ≡ ℓ ( x + δ x , u + δ u ) + V ( f ( x + δ x , u + δ u ) , i + 1 ) − ℓ ( x , u ) − V ( f ( x , u ) , i + 1 ) {\displaystyle {\begin{aligned}Q(\delta \mathbf {x} ,\delta \mathbf {u} )\equiv &\ell (\mathbf {x} +\delta \mathbf {x} ,\mathbf {u} +\delta \mathbf {u} )&&{}+V(\mathbf {f} (\mathbf {x} +\delta \mathbf {x} ,\mathbf {u} +\delta \mathbf {u} ),i+1)\\-&\ell (\mathbf {x} ,\mathbf {u} )&&{}-V(\mathbf {f} (\mathbf {x} ,\mathbf {u} ),i+1)\end{aligned}}} これを、二次形式に展開する。 Q ( δ x , δ u ) ≈ 1 2 [ 1 δ x δ u ] T [ 0 Q x T Q u T Q x Q x x Q x u Q u Q u x Q u u ] [ 1 δ x δ u ] {\displaystyle Q(\delta \mathbf {x} ,\delta \mathbf {u} )\approx {\frac {1}{2}}{\begin{bmatrix}1\\\delta \mathbf {x} \\\delta \mathbf {u} \end{bmatrix}}^{\mathsf {T}}{\begin{bmatrix}0&Q_{\mathbf {x} }^{\mathsf {T}}&Q_{\mathbf {u} }^{\mathsf {T}}\\Q_{\mathbf {x} }&Q_{\mathbf {x} \mathbf {x} }&Q_{\mathbf {x} \mathbf {u} }\\Q_{\mathbf {u} }&Q_{\mathbf {u} \mathbf {x} }&Q_{\mathbf {u} \mathbf {u} }\end{bmatrix}}{\begin{bmatrix}1\\\delta \mathbf {x} \\\delta \mathbf {u} \end{bmatrix}}} (3) ここで用いる  Q {\displaystyle Q} の表記は、森本淳 (ATR脳情報研究所) の記法の変形版であり、添え字は偏微分の分母を示している。 見やすくするため、添え字の i {\displaystyle i} を省略し、次の時間ステップの変数は  V ′ ≡ V ( i + 1 ) {\displaystyle V'\equiv V(i+1)} のようにプライムをつけて示そう。テイラー展開により係数は以下となる。 Q x = ℓ x + f x T V x ′ Q u = ℓ u + f u T V x ′ Q x x = ℓ x x + f x T V x x ′ f x + V x ′ ⋅ f x x Q u u = ℓ u u + f u T V x x ′ f u + V x ′ ⋅ f u u Q u x = ℓ u x + f u T V x x ′ f x + V x ′ ⋅ f u x . {\displaystyle {\begin{alignedat}{2}Q_{\mathbf {x} }&=\ell _{\mathbf {x} }+\mathbf {f} _{\mathbf {x} }^{\mathsf {T}}V'_{\mathbf {x} }\\Q_{\mathbf {u} }&=\ell _{\mathbf {u} }+\mathbf {f} _{\mathbf {u} }^{\mathsf {T}}V'_{\mathbf {x} }\\Q_{\mathbf {x} \mathbf {x} }&=\ell _{\mathbf {x} \mathbf {x} }+\mathbf {f} _{\mathbf {x} }^{\mathsf {T}}V'_{\mathbf {x} \mathbf {x} }\mathbf {f} _{\mathbf {x} }+V_{\mathbf {x} }'\cdot \mathbf {f} _{\mathbf {x} \mathbf {x} }\\Q_{\mathbf {u} \mathbf {u} }&=\ell _{\mathbf {u} \mathbf {u} }+\mathbf {f} _{\mathbf {u} }^{\mathsf {T}}V'_{\mathbf {x} \mathbf {x} }\mathbf {f} _{\mathbf {u} }+{V'_{\mathbf {x} }}\cdot \mathbf {f} _{\mathbf {u} \mathbf {u} }\\Q_{\mathbf {u} \mathbf {x} }&=\ell _{\mathbf {u} \mathbf {x} }+\mathbf {f} _{\mathbf {u} }^{\mathsf {T}}V'_{\mathbf {x} \mathbf {x} }\mathbf {f} _{\mathbf {x} }+{V'_{\mathbf {x} }}\cdot \mathbf {f} _{\mathbf {u} \mathbf {x} }.\end{alignedat}}} 最後の三つの方程式に現れる最終項はベクトルとテンソルの縮約(contraction)を表す。 二次形式で近似された式(3) を入力 δ u {\displaystyle \delta \mathbf {u} } に関して最小化することで次式を得る。 δ u ∗ = argmin δ u ⁡ Q ( δ x , δ u ) = − Q u u − 1 ( Q u + Q u x δ x ) , {\displaystyle {\delta \mathbf {u} }^{*}=\operatorname {argmin} \limits _{\delta \mathbf {u} }Q(\delta \mathbf {x} ,\delta \mathbf {u} )=-Q_{\mathbf {u} \mathbf {u} }^{-1}(Q_{\mathbf {u} }+Q_{\mathbf {u} \mathbf {x} }\delta \mathbf {x} ),} (4) これにより、オープンループ項  k = − Q u u − 1 Q u {\displaystyle \mathbf {k} =-Q_{\mathbf {u} \mathbf {u} }^{-1}Q_{\mathbf {u} }}  とフィードバック項 K = − Q u u − 1 Q u x {\displaystyle \mathbf {K} =-Q_{\mathbf {u} \mathbf {u} }^{-1}Q_{\mathbf {u} \mathbf {x} }} が与えられる。この結果を式(3) に代入することにより 時間 i {\displaystyle i} における価値関数が得られる。 Δ V ( i ) = − 1 2 Q u Q u u − 1 Q u V x ( i ) = Q x − Q u Q u u − 1 Q u x V x x ( i ) = Q x x − Q x u Q u u − 1 Q u x . {\displaystyle {\begin{alignedat}{2}\Delta V(i)&=&{}-{\tfrac {1}{2}}Q_{\mathbf {u} }Q_{\mathbf {u} \mathbf {u} }^{-1}Q_{\mathbf {u} }\\V_{\mathbf {x} }(i)&=Q_{\mathbf {x} }&{}-Q_{\mathbf {u} }Q_{\mathbf {u} \mathbf {u} }^{-1}Q_{\mathbf {u} \mathbf {x} }\\V_{\mathbf {x} \mathbf {x} }(i)&=Q_{\mathbf {x} \mathbf {x} }&{}-Q_{\mathbf {x} \mathbf {u} }Q_{\mathbf {u} \mathbf {u} }^{-1}Q_{\mathbf {u} \mathbf {x} }.\end{alignedat}}} i = N − 1 {\displaystyle i=N-1} から i = 1 {\displaystyle i=1} に向かって、再帰的に価値関数  V ( i ) {\displaystyle V(i)}  の局所的な二次形式のモデルと、制御の修正量  { k ( i ) , K ( i ) } {\displaystyle \{\mathbf {k} (i),\mathbf {K} (i)\}} を求めるのが逆方向パスの計算である。 先に述べたように、価値関数の初期値は  V ( x , N ) ≡ ℓ f ( x N ) {\displaystyle V(\mathbf {x} ,N)\equiv \ell _{f}(\mathbf {x} _{N})} である。逆方向パスの完了後、新しい軌道にそって順方向パスの計算を行う。  x