6.137 동적 계획법의 행렬 구조 활용

1. 동적 계획법의 기본 원리

동적 계획법(Dynamic Programming, DP)은 최적성의 원리(principle of optimality)에 기반한 최적화 기법이다. 벨만(Bellman)의 최적성 원리는 다음과 같이 서술된다: 최적 정책(optimal policy)의 부분 정책(sub-policy)도 또한 해당 부분 문제의 최적 정책이다. 이 원리를 이용하면 다단계 결정 문제를 후방(backward)으로 순차적으로 풀 수 있다.

이산 시간 시스템 $\mathbf{x}_{k+1} = \mathbf{f}_k(\mathbf{x}_k, \mathbf{u}_k)$ 에 대하여 비용 함수가

$J = \Phi(\mathbf{x}_N) + \sum_{k=0}^{N-1} L_k(\mathbf{x}_k, \mathbf{u}_k)$

일 때, 비용-진행(cost-to-go) 함수 또는 가치 함수(value function) $V_k(\mathbf{x})$ 는 다음의 벨만 방정식(Bellman equation)을 만족한다.

$V_k(\mathbf{x}) = \min_{\mathbf{u}} \bigl[L_k(\mathbf{x}, \mathbf{u}) + V_{k+1}(\mathbf{f}_k(\mathbf{x}, \mathbf{u}))\bigr]$

종단 조건은 $V_N(\mathbf{x}) = \Phi(\mathbf{x})$ 이다.

2. 선형 이차 조절기(LQR)와 리카티 방정식

2.1 문제 정의

선형 시스템과 이차 비용의 경우, 동적 계획법의 벨만 방정식이 닫힌 형태(closed-form)의 해를 가진다. 이산 시간 LQR 문제는 다음과 같다.

$\begin{aligned} \min_{\mathbf{u}_0, \dots, \mathbf{u}_{N-1}} \quad & \mathbf{x}_N^T \mathbf{Q}_f \mathbf{x}_N + \sum_{k=0}^{N-1} \bigl(\mathbf{x}_k^T \mathbf{Q}_k \mathbf{x}_k + \mathbf{u}_k^T \mathbf{R}_k \mathbf{u}_k\bigr) \\ \text{subject to} \quad & \mathbf{x}_{k+1} = \mathbf{A}_k \mathbf{x}_k + \mathbf{B}_k \mathbf{u}_k \end{aligned}$

여기서 $\mathbf{Q}_k \succeq 0$ 은 상태 가중 행렬, $\mathbf{R}_k \succ 0$ 은 제어 가중 행렬, $\mathbf{Q}_f \succeq 0$ 은 종단 가중 행렬이다.

2.2 가치 함수의 이차 구조

가치 함수가 $V_k(\mathbf{x}) = \mathbf{x}^T \mathbf{P}_k \mathbf{x}$ 의 이차 형태를 가진다고 가정하면, 벨만 방정식에 대입하여 $\mathbf{P}_k$ 에 대한 재귀 관계를 얻는다. 종단 조건으로부터 $\mathbf{P}_N = \mathbf{Q}_f$ 이다.

벨만 방정식의 최소화를 $\mathbf{u}$ 에 대하여 수행하면

$\mathbf{u}_k^* = -(\mathbf{R}_k + \mathbf{B}_k^T \mathbf{P}_{k+1} \mathbf{B}_k)^{-1} \mathbf{B}_k^T \mathbf{P}_{k+1} \mathbf{A}_k \mathbf{x}_k = -\mathbf{K}_k \mathbf{x}_k$

여기서 피드백 이득 행렬 $\mathbf{K}_k$ 는 다음과 같다.

$\mathbf{K}_k = (\mathbf{R}_k + \mathbf{B}_k^T \mathbf{P}_{k+1} \mathbf{B}_k)^{-1} \mathbf{B}_k^T \mathbf{P}_{k+1} \mathbf{A}_k$

2.3 이산 시간 리카티 방정식

$\mathbf{P}_k$ 는 다음의 이산 시간 리카티 차분 방정식(Discrete-time Riccati Difference Equation, DRDE)을 만족한다.

$\mathbf{P}_k = \mathbf{Q}_k + \mathbf{A}_k^T \mathbf{P}_{k+1} \mathbf{A}_k - \mathbf{A}_k^T \mathbf{P}_{k+1} \mathbf{B}_k (\mathbf{R}_k + \mathbf{B}_k^T \mathbf{P}_{k+1} \mathbf{B}_k)^{-1} \mathbf{B}_k^T \mathbf{P}_{k+1} \mathbf{A}_k$

이 방정식은 $k = N-1$ 부터 $k = 0$ 까지 후방으로 재귀적으로 풀어야 한다. 각 시간 단계에서의 주요 행렬 연산은 다음 표와 같다.

연산	행렬 크기	계산 복잡도
$\mathbf{B}_k^T \mathbf{P}_{k+1} \mathbf{B}_k$	$m \times m$	$O(nm^2 + n^2 m)$
$(\mathbf{R}_k + \mathbf{B}_k^T \mathbf{P}_{k+1} \mathbf{B}_k)^{-1}$	$m \times m$	$O(m^3)$
$\mathbf{K}_k$ 계산	$m \times n$	$O(m^2 n)$
$\mathbf{P}_k$ 갱신	$n \times n$	$O(n^2 m + n^3)$

전체 복잡도는 $O(N(n^3 + n^2 m + nm^2 + m^3))$ 이다.

3. 정상 상태 해와 대수 리카티 방정식

시간 불변 시스템 $(\mathbf{A}, \mathbf{B}, \mathbf{Q}, \mathbf{R})$ 에서 시간 구간 $N \to \infty$ 이면, $\mathbf{P}_k$ 는 정상 상태 해 $\mathbf{P}$ 로 수렴한다. 이 $\mathbf{P}$ 는 이산 시간 대수 리카티 방정식(Discrete-time Algebraic Riccati Equation, DARE)을 만족한다.

$\mathbf{P} = \mathbf{Q} + \mathbf{A}^T \mathbf{P} \mathbf{A} - \mathbf{A}^T \mathbf{P} \mathbf{B} (\mathbf{R} + \mathbf{B}^T \mathbf{P} \mathbf{B})^{-1} \mathbf{B}^T \mathbf{P} \mathbf{A}$

DARE의 수치 해법으로는 다음이 사용된다.

반복법: 리카티 차분 방정식을 충분히 많은 단계 반복하여 수렴시킨다. 수렴 속도는 폐루프 시스템의 고유값에 의하여 결정된다.

슈어 분해법: 해밀턴 행렬(Hamiltonian matrix)의 고유 구조를 이용한다. 심플렉틱 행렬(symplectic matrix)

$\mathbf{Z} = \begin{bmatrix} \mathbf{A} + \mathbf{B}\mathbf{R}^{-1}\mathbf{B}^T (\mathbf{A}^{-T}) \mathbf{Q} & -\mathbf{B}\mathbf{R}^{-1}\mathbf{B}^T \mathbf{A}^{-T} \\ -\mathbf{A}^{-T}\mathbf{Q} & \mathbf{A}^{-T} \end{bmatrix}$

의 순서화된 슈어 분해(ordered Schur decomposition)를 이용하여 안정 불변 부분 공간(stable invariant subspace)을 추출하면 $\mathbf{P}$ 를 구할 수 있다.

구조 보존 배증법(Structure-preserving Doubling Algorithm, SDA): 심플렉틱 구조를 보존하면서 이차 수렴하는 알고리즘으로, 대규모 문제에 효율적이다.

4. 해밀턴 행렬의 고유 구조

연속 시간 LQR에서의 해밀턴 행렬은 다음과 같다.

$\mathcal{H} = \begin{bmatrix} \mathbf{A} & -\mathbf{B}\mathbf{R}^{-1}\mathbf{B}^T \\ -\mathbf{Q} & -\mathbf{A}^T \end{bmatrix}$

이 행렬은 고유한 스펙트럼 대칭성을 가진다: $\lambda$ 가 고유값이면 $-\lambda$ 도 고유값이다. 이 성질은 해밀턴 행렬의 구조에서 비롯되며, $\mathbf{J}\mathcal{H}$ 가 대칭인 것과 동치이다. 여기서 $\mathbf{J} = \begin{bmatrix} \mathbf{0} & \mathbf{I} \\ -\mathbf{I} & \mathbf{0} \end{bmatrix}$ 은 심플렉틱 행렬이다.

안정 고유값(음의 실수부)에 대응하는 불변 부분 공간을 $\begin{bmatrix} \mathbf{X}_1 \\ \mathbf{X}_2 \end{bmatrix}$ 라 하면, 연속 시간 대수 리카티 방정식(CARE)의 해는 $\mathbf{P} = \mathbf{X}_2 \mathbf{X}_1^{-1}$ 이다.

5. 동적 계획법의 행렬 구조 활용

5.1 블록 구조와 계산 효율

LQR의 리카티 재귀에서, $\mathbf{P}_k$ 는 $n \times n$ 대칭 행렬이므로 $n(n+1)/2$ 개의 독립 원소만 저장하면 된다. 시스템 행렬 $\mathbf{A}_k, \mathbf{B}_k$ 가 특정 구조(희소, 밴드, 블록 대각 등)를 가지면, 이를 이용하여 리카티 재귀의 계산량을 크게 줄일 수 있다.

예를 들어, 다체(multi-body) 로봇 시스템에서 관성 행렬 $\mathbf{M}(\mathbf{q})$ 이 밴드 구조를 가지면, 선형화된 시스템 행렬도 희소 구조를 상속한다. 이 경우 $\mathbf{P}_k$ 도 근사적으로 밴드 구조를 가질 수 있으며, 이를 활용한 효율적인 알고리즘을 설계할 수 있다.

5.2 분산 시스템에서의 구조적 LQR

다수의 로봇이 연결된 분산 시스템에서, 시스템 행렬이 블록 구조를 가진다.

$\mathbf{A} = \begin{bmatrix} \mathbf{A}_{11} & \mathbf{A}_{12} & \cdots \\ \mathbf{A}_{21} & \mathbf{A}_{22} & \cdots \\ \vdots & \vdots & \ddots \end{bmatrix}$

결합이 약한 경우( $\mathbf{A}_{ij} \approx \mathbf{0}$ , $i \neq j$ ), $\mathbf{P}$ 도 근사적으로 블록 대각이 되며, 각 부분 시스템에 대한 독립적인 리카티 방정식을 병렬로 풀 수 있다.

5.3 크로네커 곱을 이용한 행렬 리카티 방정식의 벡터화

리카티 방정식을 직접 행렬 형태로 다루는 대신, $\text{vec}$ 연산자와 크로네커 곱을 이용하여 벡터 방정식으로 변환할 수 있다. 대칭 행렬 $\mathbf{P}$ 에 대하여 $\text{vech}(\mathbf{P})$ 를 절반 벡터화(half-vectorization)라 하면, 리카티 방정식은 $n(n+1)/2$ 차원의 벡터 재귀로 표현된다. 이는 이론적 분석에 유용하지만, 계산적으로는 직접 행렬 연산이 더 효율적이다.

6. 근사 동적 계획법

상태 공간이 연속이거나 고차원인 경우, 가치 함수를 정확히 표현할 수 없으므로 근사 동적 계획법(Approximate Dynamic Programming, ADP)을 사용한다.

6.1 가치 함수 근사

가치 함수를 기저 함수(basis function)의 선형 결합으로 근사한다.

$\hat{V}(\mathbf{x}; \mathbf{w}) = \sum_{j=1}^{p} w_j \phi_j(\mathbf{x}) = \boldsymbol{\phi}(\mathbf{x})^T \mathbf{w}$

여기서 $\boldsymbol{\phi}(\mathbf{x}) = [\phi_1(\mathbf{x}), \dots, \phi_p(\mathbf{x})]^T$ 는 특징 벡터(feature vector)이고, $\mathbf{w} \in \mathbb{R}^p$ 는 파라미터 벡터이다. 파라미터 $\mathbf{w}$ 를 결정하기 위하여 벨만 오차(Bellman error)를 최소화하는 최소 제곱 문제를 풀면 다음의 선형 시스템이 된다.

$\boldsymbol{\Phi}^T \boldsymbol{\Phi} \mathbf{w} = \boldsymbol{\Phi}^T \mathbf{v}$

여기서 $\boldsymbol{\Phi} \in \mathbb{R}^{s \times p}$ 는 샘플 점들에서의 특징 행렬이고, $\mathbf{v}$ 는 목표 가치 벡터이다.

6.2 이차 가치 함수 근사와 LQR 연결

가치 함수를 이차 형태 $\hat{V}(\mathbf{x}) = \mathbf{x}^T \mathbf{P} \mathbf{x}$ 로 근사하면, LQR의 리카티 해와 동일한 구조를 얻는다. 이는 비선형 시스템에서도 국소적으로 이차 근사가 유효하다는 것을 의미하며, iLQR/DDP 알고리즘의 이론적 기반이 된다.

7. 로봇공학에서의 DP 행렬 구조 활용 사례

문제	DP 적용	핵심 행렬 구조
관절 로봇 제어	유한 시간 LQR	밴드 구조의 리카티 행렬
이동 로봇 경로 계획	격자 기반 DP	희소 전이 행렬
다족 보행	하이브리드 DP	모드별 리카티 해 전환
군집 로봇	분산 DP	블록 대각 리카티 행렬

8. 참고 문헌

Bertsekas, D. P. (2012). Dynamic Programming and Optimal Control (4th ed., Vols. 1 & 2). Athena Scientific.
Anderson, B. D. O., & Moore, J. B. (2007). Optimal Control: Linear Quadratic Methods. Dover Publications.
Lewis, F. L., Vrabie, D., & Syrmos, V. L. (2012). Optimal Control (3rd ed.). Wiley.
Laub, A. J. (1979). A Schur method for solving algebraic Riccati equations. IEEE Transactions on Automatic Control, 24(6), 913–921.
Siciliano, B., Sciavicco, L., Villani, L., & Oriolo, G. (2009). Robotics: Modelling, Planning and Control. Springer.

v 0.1