차동 동적 프로그래밍

DDP(Differential Dynamic Programming)는 궤도 최적화 등급의 최적 제어 알고리즘이다.이 알고리즘은 메인에 의해^[1] 1966년에 도입되었고, 이후 제이콥슨과 메인의 eponymous book에서 분석되었다.^[2]알고리즘은 역학 및 비용 함수의 국소 2차 모델을 사용하며 2차 수렴을 표시한다.판토자의 단계적 뉴턴의 방법과 밀접한 관련이 있다.^[3][4]

유한수평 이산 시간 문제

역학

${\displaystyle \mathbf {x} _{i+1}=\mathbf {f}(\mathbf {x} _{i},\mathbf {u} _{i})}$

(1)

컨트롤 $u{\displaystyle \mathbf{}}$ ${\$$textstyle \$$mathbf {x$$}$이$(가$) 지정된 상태 $x{\displaystyle \mathbf{}}$ ${\$ $i}$에서 $시간{\displaystyle }$ $i{\displaystyle }$ ${\displaystyle$ i}${\displaystyle }$+ ${\displaystyle 1}$ ${\displaysty i+1}$까지의 진화에 대해 설명하십시오$.$총비용 $J{\displaystyle {}_{}}$ ${\$은$($는) $상태{\displaystyle \mathbf{}}$ x ${\$$\$$textstyle \$$ell$$$$_{f}$을$($를) 시작하고 제어$$ 시퀀스 $U{\displaystyle \mathbf{}}$ ${\displaystyle \equiv }${${\displaystyle {}_{}}$0${\displaystyle ,{\mathrm{}}_{}}$ … ${\displaystyle {}_{}}$, U${\displaystyle {}_{}}$- ${\displaystyle 1_{}}$을(를) 적용할 때 발생하는 실행비용의 ${\displaystyle {합}_{}}$이다$.$수평선에 도달할 때까지$$ ${\displaystyle \mathbf {U} \equiv \{\mathbf {u} _{0},\mathbf {u},\mathbf {u} _{N$:1$}}:$

${\displaystyle J_{0}(\mathbf {x},\mathbf {U})=\sum _{i=0}^{N-1}\ell(\mathbf {x} _{i}}},\mathbf {u}+\ell(\mathb {x}), _{N}}}$

여기서 $x{\displaystyle {\mathbf{}}_{}}$ ${\displaystyle {\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle x\mathbf{}}$ ${\$$displaystyle \mathbf {x} _{0}\equiv$ $\$$mathbf {x} }$}과$)$ 에 대한$$ ${\displaystyle {}_{}}$ i {\$displaystyle$ \$mathbf {x} _{i$$}}$이(가) Eq. 1에 의해 주어진다.The solution of the optimal control problem is the minimizing control sequence ${\displaystyle \mathbf {U} ^{*}(\mathbf {x} )\equiv \operatorname {argmin} _{\mathbf {U} }J_{0}(\mathbf {x} ,\mathbf {U} ).}$ Trajectory optimization means finding ${\displaystyle$$\mathbf {U} ^{*}(\mathbf {x}$_${0$}) 특정 x ${\displaystyle {\mathrm{}}_{}}$ ${\$$_${0$}$에 대해 가능한 모든 초기 상태가 아닌,

동적 프로그래밍

Let ${\displaystyle \mathbf {U} _{i}}$ be the partial control sequence ${\displaystyle \mathbf {U} _{i}\equiv \{\mathbf {u} _{i},\mathbf {u} _{i+1}\dots ,\mathbf {u} _{N-1}\}}$ and define the cost-to-go ${\displaystyle J_{i}}$ as the partial sum of costs$i {\displaystyle$ i$}$에서 $N{\displaystyle }$ ${\displaystyle N}$까지$:$

${\displaystyle J_{i}(\mathbf {x}),\mathbf {U}_{i}\sum _{j=i}^{{j-1}\ell(\mathbf {x} _{j}}}+\ell) _{f}(\mathbf {x} _{n}).}$

$시간{\displaystyle }$ i ${\displaystyle i}$에서 최적의 이동 비용 또는 가치 함수는 최소화된 제어 시퀀스를 고려할 때 이동 비용이다$$.

${\displaystyle V(\mathbf {x},i)\equiv \min _{\mathbf {U} _{i})J_{i}(\mathbf {x},\mathbf {U} _{i}).}$

${\displaystyle V_{}}$( ${\displaystyle x\mathbf{}}$, ${\displaystyle N}$ ) ${\displaystyle \equiv }$ ${\displaystyle )}$ ${\displaystyle {}_{}}$( ${\displaystyle {}_{}}$ N$){\displaystyle V(\mathbf {x} ,N)\equiv \ell _{f}(\mathbf {x} _{N})$를 설정하면 동적 프로그래밍 원리는 제어의 전체 시퀀스에 대한 최소화를 단일 제어에 대한 최소화로 축소하여 다음 시간을 거꾸로 진행한다$.$

${\displaystyle V(\mathbf {x},i)=\min _{\mathbf {u}[\mathbf {x},\mathbf {u}]+V(\mathbf {x},\mathbf {u}),i+1)]}$

(2)

이것이 벨만 방정식이다.

차동 동적 프로그래밍

DDP는 새로운 제어 시퀀스를 생성하기 위해 공칭 궤적에 대한 역방향 패스를 반복적으로 수행하여 새로운 공칭 궤적을 계산하고 평가하기 위한 전진 패스를 수행한다.우리는 후진 패스부터 시작한다.만약

${\displaystyle \ell(\mathbf {x},\mathbf {u} )+V(\mathbf {f {f},\mathbf {u}),i+1)}$

Eq. 2의 ${\displaystyle 최소}$[${\displaystyle }$] ${\displaystyle \min[]$ 연산자의$$ 인수인 경우, $Q{\displaystyle }$ ${\displaystyle Q}$을(를) $i{\displaystyle }$ ${\displaystyle i}$ -th$$$({\displaystyle x\mathbf{}}$, ${\displaystyle u\mathbf{}}$) ${\displaystyle(\mathbf {x} ,\mathbf {u})$ 쌍 주위에$$ 이 수량의 변동을 두십시오$$.

${\displaystyle{\begin{정렬}(\delta \mathbf{x},\delta \mathbf{너})\equiv&\ell(\mathbf{x}+\delta \mathbf{x},\mathbf{너}+\delta \mathbf{너})&,&{}(\mathbf{f}(\mathbf{x}+\delta \mathbf{x},\mathbf{너}+\delta \mathbf{너}),i+1)\\-&, \ell(\mathbf{x},\mathbf{너})&,&{}(\mathbf{f}(\mathbf{x},\mathbf{너}).,i+1)\end{정렬}}}$

그리고 2순위로 확장한다.

${\displaystyle \approx{\frac{1}{2}};\mathbf{)}\\\delta\mathbf{u}\end{bmatrix}}^{\mathsf{T}}{\begin{bmatrix}0&{\begin{bmatrix}1\\\delta.Q_{\mathbf{)}}^{\mathsf{T}}&Q_{\mathbf{너}}^{\mathsf{T}}\\Q_{\mathbf{)}}&.Q_{\mathbf{)}({)}}&.Q_{\mathbf{)}({u}}\\Q_{\mathbf{너}}&.Q_{\mathbf{너}({)}}&.Q_{\mathbf{너}\mathbf{u} }\end{bmatrix}{{bmatrix}}{\\nd \mathbf {x}\\nd \mathbf {u} \end{bmatrix}}}}$

(3)

여기서 사용되는 $Q{\displaystyle }$ ${\displaystyle Q}$ 표기법은$$ 첨자가 분모 레이아웃에서 차이를 나타내는 모리모토 표기법의 변형이다.^[5]읽기 쉽도록$$ $인덱스{\displaystyle }$ i ${\displaystyle$ i$}$을(를) 삭제하면 다음 시간 단계 V v${\displaystyle {}^{}\equiv }$ ${\displaystyle V(i}$+ ${\displaystyle 1}$) ${\displaystyle V'\equiv V(i+1$ 확장 계수는

${\displaystyle {\reasonedat}{2}Q_{\mathbf{)}}&=\ell _{\mathbf{)}}+\mathbf{f}_{\mathbf{)}}^{\mathsf{T}}V'_{\mathbf{)}}\\Q_{\mathbf{너}}&=\ell _{\mathbf{너}}+\mathbf{f}_{\mathbf{너}}^{\mathsf{T}}V'_{\mathbf{)}}\\Q_{\mathbf{)}\mathbf{)}}&=\ell _{\mathbf{)}\mathbf{)}}+\mathbf{f}_{\mathbf{)}}^{\mathsf{T}}V'_{\mathbf{)}({)}}\mathb.f{f}_{\matHbf{)}}+V_{\mathbf{)}}'\cdot\mathbf{f}_{\mathbf{)}\mathbf{)}};=\ell _{\mathbf{너}\mathbf{u}}+\mathbf{f}_{\mathbf{너}}^{\mathsf{T}}V'_{\mathbf{)}({)}}\mathbf{f}_{\mathbf{너}}+{V'_{\mathbf{)}}\mathbf{u}}및 \\Q_{\mathbf{너}}\cdot \mathbf}\mathbf{)}}및 \\Q_{\mathbf{너}, =\ell_{\mat _{\mathbf{너}\mathbf{u}{f}.hbf{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}}}$

마지막 세 방정식의 마지막 항은 텐서(tensor)를 가진 벡터의 수축을 의미한다.$\Delta {\displaystyle }$ ${\displaystyle u\mathbf{}}$ ${\$에 대한 2차 근사치(3) 최소화$$

${\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)

giving an open-loop term ${\displaystyle \mathbf {k} =-Q_{\mathbf {u} \mathbf {u} }^{-1}Q_{\mathbf {u} }}$ and a feedback gain term ${\displaystyle \mathbf {K} =-Q_{\mathbf {u} \mathbf {u} }^{-1}Q_{\mathbf {u} \mathbf {x} }}$. Plugging the result back into (3) 이제 시간 $i{\displaystyle }$ ${\displaystyle i}$의 값에 대한 2차 모델이 제공됨$:$

${\displaystyle {\begin{alignedat}{2}\Delta V(i)&=&{}-{\tfrac {1}{2}}Q_{\mathbf {u} }^{T}Q_{\mathbf {u} \mathbf {u} }^{-1}Q_{\mathbf {u} }\\V_{\mathbf {x} }(i)&=Q_{\mathbf {x}{}-Q_{}-Q_{\mathbf {xu}}Q_{}{\mathbf {u}^{-1}Q_{\mathbf {u}\\V_{\mathbf {x} \mathbf {x}}}{x} \mathbf {x}}}}}&}=Q_{\mathbf {x} \mathbf {x}{}-Q_{\mathbf {x} \mathbf {u} {}Q_{\mathbf {u} \mathbf {u}^{-1}Q_{\mathbf {u} \mathbf {x}}}}}\end{aignedat}}}}}}}}}}}}}}}}}}$

Recursively computing the local quadratic models of ${\displaystyle V(i)}$ and the control modifications ${\displaystyle \{\mathbf {k} (i),\mathbf {K} (i)\}}$, from ${\displaystyle i=N-1}$ down to ${\displaystyle i=1}$, constitutes the backward pass.위와 같이 $V{\displaystyle }$( ${\displaystyle x}$, N${\displaystyle }$) ${\displaystyle \equiv }$ ${\displaystyle {}_{}}$ ${\displaystyle f_{}}$( x N${\displaystyle {}_{}}$) { ℓ ℓ f ( ${\displaystyle {\mathbf{}}_{}}$ ${\displaystyle {}_{}}$ ) ${\displaystyle V(\mathbf {x},$ N$)\equiv \ell \{f}(\mathbf {x} _{N}).$ 후진 패스가 완료되면 전진 패스가 새로운 궤적을 계산한다$.$

${\displaystyle {\begin{aligned}{\hat {\mathbf {x} }}(1)&=\mathbf {x} (1)\\{\hat {\mathbf {u} }}(i)&=\mathbf {u} (i)+\mathbf {k} (i)+\mathbf {K} (i)({\hat {\mathbf {x} }}(i)-\mathbf {x} (i))\\{\hatbf{x}}}}}}({\hattbf {x}})(i) {\hattbf {x}}}}{\hatbf {u}}}}}(i)}{\hattbf {}}}}}(i)\end{정렬}}}$

후진 패스 및 전진 패스는 수렴될 때까지 반복된다.

정규화 및 라인 검색

차동 동적 프로그래밍은 뉴턴의 방식과 같은 2차 알고리즘이다.따라서 최소화를 향해 큰 걸음을 내딛고 종종 정규화 및/또는 라인 검색을 필요로 한다.^[7] DDP 컨텍스트에서 정규화는 Eq $4$의 ${\displaystyle {Q\mathbf{}}_{}}$u {\$displaystyle$Q_{\$mathbf {u$} \$mathbf${u$$$}}}}$ 행렬이 양적으로 확실한지 확인하는 것을 의미한다.DDP의 라인 검색은 오픈 루프 제어 수정 $k{\displaystyle \mathbf{}}$ ${\$을(를) < $<<\displaystyle 0>\alpha <1}$만큼$$ 확장하는 것이다

몬테카를로 버전

샘플링된 차동 동적 프로그래밍(SaDDP)^[8][9][10]은 차동 동적 프로그래밍의 몬테카를로 변종이다.그것은 차동 동적 프로그래밍의 이차적 비용을 볼츠만 분포의 에너지로 처리하는 것에 기초한다.이 방법으로 DDP의 수량을 다차원 정규 분포의 통계량과 일치시킬 수 있다.그 통계는 분화되지 않고 샘플링된 궤도로부터 다시 계산될 수 있다.

샘플링된 차동 동적 프로그래밍은 차동 동적 프로그래밍을 통한 경로 통합 정책 개선으로 확장되었다.^[11]이것은 확률론적 최적 제어의 ^[12]틀인 차동적 프로그래밍과 경로 적분 제어 사이의 연결을 만든다.

제한된 문제

내부 포인트 차동형 프로그래밍(Internal Point Differential Dynamic Programming, IPDDP)은 비선형 상태 및 입력 제약으로 최적의 제어 문제를 해결할 수 있는 DDP의 내부 포인트 방식 일반화다.^[13]

참고 항목

• 최적제어

참조

외부 링크

• Python의 DDP 구현
• DDP의 MATLAB 구현