Dynamic Programming and Discrete LQR
Principle of Optimality, Bellman Recursion, and Riccati Equations
- Principle of Optimality
- Shortest Path and Cost-to-Go
- Finite-Horizon Bellman Recursion
- Discretizing a Continuous Control Problem
- A Small Dynamic Programming Example
- Curse of Dimensionality
- Discrete Linear Quadratic Regulator
- Evaluating a Suboptimal Feedback Law
- Infinite-Horizon Limit and the Algebraic Riccati Equation
- Interpretation of the LQR Weights
- Connection to Continuous Path Planning
- Summary
References: Jonathan P. How, 16.323 Principles of Optimal Control, Lecture 3: Dynamic Programming, MIT OpenCourseWare, Spring 2008.
Dynamic programming은 여러 단계에 걸친 의사결정 문제를 마지막 단계부터 거꾸로 푸는 방법이다. 핵심은 하나의 긴 경로를 통째로 비교하는 대신, 각 상태에서 목적지까지 남은 최소 비용을 저장하고 재사용하는 데 있다. 이 장에서는 Bellman의 최적성 원리로부터 이 재귀 구조를 유도하고, 연속시간 최적제어 문제를 이산화해 수치적으로 푸는 방법을 살펴본다. 마지막으로 동적계획법을 해석적으로 풀 수 있는 대표적인 경우인 discrete linear quadratic regulator를 유도한다.
Principle of Optimality
초기 상태 $(x_0,t_0)$에서 시작해 종단 조건을 만족하는 최적 궤적이 중간 상태 $(x_1,t_1)$을 지난다고 하자. Principle of Optimality는 이 최적 궤적의 $(x_1,t_1)$ 이후 부분도 $(x_1,t_1)$에서 시작하는 나머지 문제의 최적해여야 한다는 원리이다.
이를 모순으로 간단히 확인할 수 있다. 최적 궤적의 뒷부분보다 비용이 더 작은 다른 경로가 $(x_1,t_1)$에서 존재한다고 가정하자. 기존 궤적의 앞부분과 더 작은 비용의 뒷부분을 연결하면 원래 궤적보다 비용이 작은 전체 궤적을 만들 수 있다. 이는 원래 궤적이 최적이라는 가정과 모순이다.
이 원리는 최적 경로가 다음과 같은 부분구조를 가진다는 뜻이다.
- 전체 문제의 최적해 안에는 남은 부분문제의 최적해가 들어 있다.
- 같은 중간 상태에 도달한 과거 경로가 여러 개여도, 그 상태 이후의 최적 결정은 동일한 부분문제로 표현된다.
- 따라서 이미 계산한 부분문제의 값을 저장하면 동일한 미래를 반복해서 탐색할 필요가 없다.
경로계획 관점에서는 어떤 위치와 시간까지 도달한 뒤의 최적 경로가 그 이전에 어떤 경로를 따라왔는지가 아니라, 현재 상태가 미래 비용을 결정하는 데 필요한 정보를 모두 포함하고 있다는 가정이 중요하다. 이러한 상태의 충분성이 성립해야 Bellman recursion을 적용할 수 있다.
Shortest Path and Cost-to-Go
유한한 그래프에서 노드 $s$에 있을 때 선택 가능한 행동의 집합을 $\mathcal{A}(s)$라 하자. 행동 $a$를 선택하면 다음 상태
\[s^+=F(s,a)\]로 이동하고 비용 $c(s,a)$를 지불한다. 목적지 $s_{\mathrm{goal}}$까지 남은 최소 비용을 cost-to-go 또는 value function이라 하고
\[V(s)=\text{state }s\text{에서 목적지까지의 최소 비용}\]으로 정의한다. 목적지에서는 더 이동할 필요가 없으므로 $V(s_{\mathrm{goal}})=0$이다. 임의의 다른 상태에서는 첫 행동의 비용과 다음 상태에서의 최적 비용을 더한 뒤 가장 작은 값을 선택한다.
\[V(s) =\min_{a\in\mathcal{A}(s)} \left\{c(s,a)+V\bigl(F(s,a)\bigr)\right\}.\]이 식이 Bellman optimality equation의 가장 단순한 형태이다. 최적 행동은
\[\pi^\star(s) \in \underset{a\in\mathcal{A}(s)}{\operatorname{argmin}} \left\{c(s,a)+V\bigl(F(s,a)\bigr)\right\}\]으로 저장할 수 있다. $V$는 최적 비용을 알려 주고, $\pi^\star$는 실제로 어느 방향으로 이동해야 하는지를 알려 준다.
자료의 shortest-path 예에서 한 중간 노드 $x$로부터 두 경로의 남은 시간이 각각
\[6+10=16, \qquad 7+11=18\]이라면 $V(x)=16$이고 첫 번째 방향이 최적이다. 이후 시작점까지 한 단계씩 뒤로 이동하면서 같은 계산을 반복한다. 가능한 모든 전체 경로를 처음부터 끝까지 열거하는 대신, 각 노드에서 계산한 최적 cost-to-go를 한 번씩만 재사용하는 것이 핵심이다.
Finite-Horizon Bellman Recursion
시간이 $k=0,1,\ldots,N$의 유한한 단계로 나뉘어 있다고 하자. 시스템의 상태방정식과 비용을
\[x_{k+1}=f_k(x_k,u_k),\] \[J=\phi(x_N)+\sum_{k=0}^{N-1}\ell_k(x_k,u_k)\]로 쓴다. 여기서 $\phi$는 terminal cost이고 $\ell_k$는 한 단계 동안 발생하는 stage cost이다. 시간 $k$의 상태 $x$에서 시작했을 때의 최적 cost-to-go를
\[V_k(x) =\min_{u_k,\ldots,u_{N-1}} \left[ \phi(x_N)+\sum_{j=k}^{N-1}\ell_j(x_j,u_j) \right]\]로 정의하면 종단 조건은
\[V_N(x)=\phi(x)\]이다. 최적성 원리를 적용하면 $V_k$는 다음과 같이 한 단계의 최소화 문제로 분해된다.
\[V_k(x) =\min_{u\in\mathcal{U}_k(x)} \left\{ \ell_k(x,u)+V_{k+1}\bigl(f_k(x,u)\bigr) \right\}.\]이에 대응하는 최적 feedback policy는
\[\pi_k^\star(x) \in \underset{u\in\mathcal{U}_k(x)}{\operatorname{argmin}} \left\{ \ell_k(x,u)+V_{k+1}\bigl(f_k(x,u)\bigr) \right\}\]이다. 계산은 다음 순서로 진행된다.
- $V_N=\phi$로 종단 비용을 설정한다.
- $k=N-1,N-2,\ldots,0$의 순서로 모든 상태에서 $V_k$와 $\pi_k^\star$를 계산한다.
- 실제 운용에서는 현재 상태 $x_k$를 관측하고 $u_k=\pi_k^\star(x_k)$를 적용한다.
따라서 최적화를 뒤로 수행하더라도 실제 상태는 제어법칙을 따라 앞으로 전파된다. 이 과정에서 얻는 결과는 특정 초기점 하나에 대한 open-loop 입력열뿐 아니라, 격자 위의 각 상태에 어떤 입력을 적용할지를 정한 feedback policy이다.
Discretizing a Continuous Control Problem
다음의 연속시간 최적제어 문제를 생각하자.
\[\min_{u(\cdot)} J =h\bigl(x(t_f)\bigr) +\int_{t_0}^{t_f}g\bigl(x(t),u(t),t\bigr)\,dt\]subject to
\[\dot{x}(t)=a\bigl(x(t),u(t),t\bigr), \qquad x(t_0)=x_0.\]Dynamic programming으로 수치해를 구하려면 시간, 상태, 필요하다면 제어 입력을 유한한 집합으로 이산화한다. 시간 간격을 $\Delta t$라 하고 $t_{k+1}=t_k+\Delta t$로 두면 Euler approximation은
\[x_{k+1} \approx x_k+a(x_k,u_k,t_k)\Delta t\]를 준다. 같은 구간의 running cost는
\[\int_{t_k}^{t_{k+1}}g(x(t),u(t),t)\,dt \approx g(x_k,u_k,t_k)\Delta t\]로 근사한다. 따라서 이산화된 Bellman recursion은
\[V_k(x_i) =\min_{u\in\mathcal{U}_k(x_i)} \left\{ g(x_i,u,t_k)\Delta t +V_{k+1}\left(x_i+a(x_i,u,t_k)\Delta t\right) \right\}\]이 된다.
Transition을 구성하는 두 방식
첫 번째 방식은 현재 격자점 $x_k^i$와 다음 격자점 $x_{k+1}^j$를 먼저 선택한 뒤, 그 전이를 만드는 제어입력 $u_k^{ij}$를 구하는 것이다. 예를 들어 dynamics가 control-affine form
\[\dot{x}=f(x,t)+q(x,t)u\]이고 $q$가 가역이면 Euler approximation에서
\[u_k^{ij} =q(x_k^i,t_k)^{-1} \left[ \frac{x_{k+1}^j-x_k^i}{\Delta t}-f(x_k^i,t_k) \right]\]를 얻는다. 이 입력이 admissible set 안에 있을 때만 해당 전이를 허용한다.
두 번째 방식은 제어입력을 먼저 양자화하고 각 입력에 대해 다음 상태를 전파하는 것이다.
\[x_{k+1}^j =x_k^i+a(x_k^i,u_k^j,t_k)\Delta t.\]일반적으로 이렇게 얻은 다음 상태는 미리 정한 상태 격자와 정확히 일치하지 않는다. 이 경우 $V_{k+1}$을 주변 격자점에서 보간해야 한다. 첫 번째 방식은 격자 간 전이를 정확히 맞추지만 필요한 입력을 역으로 계산해야 하고, 두 번째 방식은 일반적인 dynamics에 적용하기 쉽지만 value interpolation이 필요하다는 차이가 있다.
Constraints
제어입력에 bound가 있으면 그 범위를 벗어나는 전이는 후보에서 제외한다. 장애물이나 안전영역처럼 상태 제약이 있으면 허용되지 않은 격자점에 무한대 비용을 부여하거나 해당 상태를 제거할 수 있다. 종단 상태가 제한되어 있다면 admissible terminal set $\mathcal{X}_f$에 대해
\[V_N(x)= \begin{cases} h(x), & x\in\mathcal{X}_f,\\ +\infty, & x\notin\mathcal{X}_f \end{cases}\]로 초기화할 수 있다. 이렇게 하면 backward recursion이 종단 조건을 만족할 수 없는 모든 경로를 자동으로 배제한다.
A Small Dynamic Programming Example
자료의 scalar example은 연속 시스템
\[\dot{x}=ax+u\]와 비용
\[J=x(T)^2+\lambda\int_0^T u(t)^2\,dt\]를 사용한다. $a=0$, $\lambda=2$, $T=2$, $\Delta t=1$로 두면
\[x_{k+1}=x_k+u_k, \qquad J=x_2^2+2\sum_{k=0}^{1}u_k^2\]가 된다. 상태와 입력을
\[\mathcal{X}=\{0,0.5,1.0,1.5\}, \qquad \mathcal{U}=\{-1,-0.5,0,0.5,1\}\]로 제한한다.
종단 비용은 $V_2(x)=x^2$이다. 한 단계 전의 value는
\[V_1(x) =\min_{u\in\mathcal{U}:\,x+u\in\mathcal{X}} \left\{2u^2+V_2(x+u)\right\}\]로 계산한다. 예를 들어 $x_1=1$일 때 허용되는 다음 상태와 총비용은
| $x_2$ | $u_1=x_2-x_1$ | $2u_1^2+V_2(x_2)$ |
|---|---|---|
| $0$ | $-1$ | $2$ |
| $0.5$ | $-0.5$ | $0.75$ |
| $1$ | $0$ | $1$ |
| $1.5$ | $0.5$ | $2.75$ |
따라서 $x_1=1$에서는 $x_2=0.5$로 이동하는 $u_1=-0.5$가 최적이고 $V_1(1)=0.75$이다. 모든 상태에 같은 계산을 적용하면
| $x_1$ | 최적 $x_2$ | $V_1(x_1)$ |
|---|---|---|
| $0$ | $0$ | $0$ |
| $0.5$ | $0.5$ | $0.25$ |
| $1$ | $0.5$ | $0.75$ |
| $1.5$ | $1$ | $1.5$ |
를 얻는다. 이제 $V_1$을 terminal cost처럼 사용해 $k=0$에서도
\[V_0(x) =\min_{u\in\mathcal{U}:\,x+u\in\mathcal{X}} \left\{2u^2+V_1(x+u)\right\}\]를 계산한다. 이처럼 다음 단계의 전체 경로를 다시 열거하지 않고 이미 계산된 $V_{k+1}$만 참조하는 것이 동적계획법의 계산 절약을 만든다.
Curse of Dimensionality
Dynamic programming은 경로의 조합적 열거를 피하지만 상태공간 자체를 격자로 표현하는 비용은 남는다. 상태의 각 차원마다 $N_x$개의 격자점을 사용하고 상태 차원이 $n$이면 한 시간단계의 상태점 수는
\[N_x^n\]이다. 시간 격자점이 $N_t$개라면 저장해야 할 value의 수는 대략
\[N_tN_x^n\]으로 증가한다. 제어입력도 각 차원마다 $N_u$개로 양자화하고 입력 차원이 $m$이면 Bellman update의 탐색 비용에는 추가로 $N_u^m$이 곱해진다. 이 지수적 증가는 Bellman이 지적한 curse of dimensionality이다.
공간 위치만 상태로 사용하는 저차원 경로계획에서는 규칙적인 격자 기반 DP가 실용적일 수 있다. 그러나 속도, 방향, 연료, 시간, 환경 상태 등을 함께 포함하면 차원이 빠르게 커진다. 따라서 실제 문제에서는 상태 표현, 격자 해상도, 보간 방법, 근사 value function 사이의 절충이 필요하다.
Discrete Linear Quadratic Regulator
일반적인 dynamic programming은 value function을 격자에 저장하고 각 상태에서 수치적인 최소화를 수행해야 한다. 그러나 dynamics가 선형이고 비용이 이차식인 discrete LQR은 Bellman recursion을 해석적인 행렬 recursion으로 줄일 수 있다.
다음의 유한시간 문제를 생각하자.
\[x_{k+1}=A_kx_k+B_ku_k,\] \[J =\frac{1}{2}x_N^THx_N +\frac{1}{2}\sum_{k=0}^{N-1} \left(x_k^TQ_kx_k+u_k^TR_ku_k\right),\]여기서
\[H=H^T\succeq0, \qquad Q_k=Q_k^T\succeq0, \qquad R_k=R_k^T\succ0\]라고 가정한다. $Q_k$와 $H$는 상태 오차를, $R_k$는 제어 노력의 크기를 penalize한다. $R_k\succ0$이므로 제어입력에 대한 stage cost는 strictly convex이다.
Quadratic value function
종단에서
\[V_N(x)=\frac{1}{2}x^THx\]이므로 $P_N=H$라 두면 $V_N(x)=\frac{1}{2}x^TP_Nx$이다. 이제 어떤 $k+1$에서
\[V_{k+1}(x)=\frac{1}{2}x^TP_{k+1}x\]라고 가정하자. Bellman recursion에 대입하면
\[\begin{aligned} V_k(x) =\min_u\frac{1}{2}\Bigl[ &x^TQ_kx+u^TR_ku \\ &+(A_kx+B_ku)^TP_{k+1}(A_kx+B_ku) \Bigr]. \end{aligned}\]목적함수를 $u$에 대해 미분하면
\[\left(R_k+B_k^TP_{k+1}B_k\right)u +B_k^TP_{k+1}A_kx=0\]을 얻는다. 따라서 최적 입력은 상태에 대한 선형 feedback
\[u_k^\star=-F_kx_k\]이고 feedback gain은
\[F_k =\left(R_k+B_k^TP_{k+1}B_k\right)^{-1} B_k^TP_{k+1}A_k\]이다. $R_k\succ0$이고 $P_{k+1}\succeq0$이면 $R_k+B_k^TP_{k+1}B_k\succ0$이므로 inverse가 존재하고 이 stationary point는 유일한 minimizer이다.
Riccati recursion
$u_k^\star=-F_kx_k$를 Bellman equation에 다시 대입하면 value function은 계속 이차형식을 유지한다.
\[V_k(x)=\frac{1}{2}x^TP_kx,\] \[P_k =Q_k+F_k^TR_kF_k +(A_k-B_kF_k)^TP_{k+1}(A_k-B_kF_k).\]$F_k$를 제거하면 더 익숙한 discrete Riccati recursion을 얻는다.
\[\begin{aligned} P_k =Q_k &+A_k^TP_{k+1}A_k \\ &-A_k^TP_{k+1}B_k \left(R_k+B_k^TP_{k+1}B_k\right)^{-1} B_k^TP_{k+1}A_k. \end{aligned}\]따라서 discrete LQR은 다음의 backward sweep으로 풀린다.
- $P_N=H$로 초기화한다.
- $k=N-1,N-2,\ldots,0$에 대해 $F_k$를 계산한다.
- 같은 단계에서 $P_k$를 계산한다.
- 실제 시스템에서는 $u_k=-F_kx_k$를 적용한다.
$P_k$와 $F_k$는 현재 상태값에 의존하지 않으므로 미리 offline에서 계산할 수 있다. Online 계산은 상태를 측정한 뒤 행렬 $F_k$를 곱하는 것으로 줄어든다. $A_k,B_k,Q_k,R_k$가 시간에 따라 일정해도 유한한 horizon과 terminal cost의 영향 때문에 $F_k$는 일반적으로 시간에 따라 변한다.
Evaluating a Suboptimal Feedback Law
최적 gain $F_k$ 대신 주어진 feedback law
\[u_k=-G_kx_k\]를 사용할 때의 비용도 비슷한 backward recursion으로 계산할 수 있다. Closed-loop dynamics는
\[x_{k+1}=(A_k-B_kG_k)x_k\]이고, $S_N=H$에서 시작하여
\[S_k =Q_k+G_k^TR_kG_k +(A_k-B_kG_k)^TS_{k+1}(A_k-B_kG_k)\]를 뒤로 계산하면 이 제어기의 비용은
\[J_G(x_0)=\frac{1}{2}x_0^TS_0x_0\]이다. 최적 LQR의 비용
\[J^\star(x_0)=\frac{1}{2}x_0^TP_0x_0\]과 비교하면 주어진 gain schedule이 얼마나 suboptimal한지 정량화할 수 있다. 안정화 가능한 임의의 gain과 최적 gain이 상태를 모두 원점으로 보내더라도, transient 동안 필요한 상태 오차와 제어 노력의 누적 비용은 서로 다를 수 있다.
Infinite-Horizon Limit and the Algebraic Riccati Equation
$A,B,Q,R$가 시간에 따라 변하지 않는 LTI 문제를 생각하자. Horizon이 충분히 길고 $(A,B)$가 stabilizable하면 terminal cost의 영향에서 멀리 떨어진 구간에서 $P_k$가 일정한 행렬 $P_{\mathrm{ss}}$로 수렴할 수 있다. Riccati recursion에서 $P_k=P_{k+1}=P_{\mathrm{ss}}$로 두면 discrete algebraic Riccati equation을 얻는다.
\[\begin{aligned} P_{\mathrm{ss}} =Q &+A^TP_{\mathrm{ss}}A \\ &-A^TP_{\mathrm{ss}}B \left(R+B^TP_{\mathrm{ss}}B\right)^{-1} B^TP_{\mathrm{ss}}A. \end{aligned}\]이에 대응하는 정상상태 gain은
\[F_{\mathrm{ss}} =\left(R+B^TP_{\mathrm{ss}}B\right)^{-1} B^TP_{\mathrm{ss}}A\]이다. $Q=C^TC$로 쓸 수 있고 $(A,C)$가 detectable이면 적절한 조건 아래 stabilizing positive-semidefinite solution이 유일하며, closed-loop system
\[x_{k+1}=(A-BF_{\mathrm{ss}})x_k\]은
\[\rho(A-BF_{\mathrm{ss}})<1\]을 만족한다. 여기서 $\rho$는 spectral radius이다. 즉 모든 closed-loop eigenvalue가 unit circle 안에 있어 상태가 점근적으로 $0$으로 수렴한다.
Stabilizability는 제어할 수 없는 mode가 이미 안정해야 한다는 조건이다. Detectability는 비용에서 관측되지 않는 mode가 이미 안정해야 한다는 조건이다. 이 두 조건은 LQR이 불안정한 mode를 제어하고 penalize할 수 있는지를 표현한다.
Interpretation of the LQR Weights
LQR의 feedback gain은 상태 오차와 제어 노력 사이의 절충으로 결정된다.
- $Q$를 크게 하면 중간 상태의 오차를 더 강하게 penalize하므로 일반적으로 더 적극적인 제어를 사용한다.
- $R$을 크게 하면 제어입력이 비싸지므로 더 완만한 입력을 선택한다.
- $H$를 크게 하면 종단 상태 오차가 비싸지므로 horizon 끝에서 목표 상태에 더 가깝게 도달하려 한다.
Scalar system에서 terminal penalty가 매우 크거나 control penalty가 매우 작으면 마지막 단계의 gain은 가능한 한 다음 상태를 즉시 $0$으로 만드는 값에 가까워진다. 그러나 실제 시스템에는 입력 bound와 모델 오차가 있으므로 $R\rightarrow0$인 공격적인 제어가 항상 실용적인 것은 아니다. 또한 standard LQR에 입력 및 상태 제약을 직접 추가하면 단순한 Riccati recursion 구조가 사라진다.
Connection to Continuous Path Planning
Continuous path planning에서 상태 $x$는 위치뿐 아니라 속도, heading, 시간, 에너지 등을 포함할 수 있다. 해류나 바람 같은 환경장 $e(x,t)$는 dynamics와 running cost에 들어가므로 이산화된 전이는
\[x_{k+1}=f_k\bigl(x_k,u_k,e(x_k,t_k)\bigr)\]의 형태가 된다. Bellman recursion은 각 위치와 시간에서 목적지까지의 최적 cost-to-go를 계산하고, 이를 최소화하는 행동을 feedback policy로 저장한다.
따라서 한 초기점에서 한 개의 경로만 구하는 것과 달리, dynamic programming의 결과는 계산 영역의 여러 상태에서 사용할 수 있는 value field와 policy field이다. 새로운 초기 상태가 주어지면 value function을 다시 최적화할 필요 없이 저장된 policy를 따라 경로를 생성할 수 있다. 이후의 핵심 과제는 연속 상태공간에서 이 value function을 얼마나 정확하고 효율적으로 표현할 것인가이다.
Summary
Bellman의 최적성 원리는 최적 궤적의 모든 뒷부분도 해당 중간 상태에서 시작하는 문제의 최적해여야 한다고 말한다. 이 원리에서 현재 stage cost와 다음 상태의 cost-to-go를 합해 최소화하는 Bellman recursion이 나온다. 연속시간 문제는 시간, 상태, 제어입력을 이산화해 같은 구조로 풀 수 있지만, 상태 차원에 대해 격자 수가 지수적으로 증가하는 curse of dimensionality를 갖는다. Linear dynamics와 quadratic cost를 갖는 discrete LQR에서는 value function이 이차형식을 유지하므로 Bellman recursion이 Riccati matrix recursion으로 축약되고, 최적 제어는 미리 계산할 수 있는 선형 state feedback $u_k^\star=-F_kx_k$가 된다.