7.76 벨만의 동적 계획법과 HJB 방정식

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

동적 계획법(Dynamic Programming, DP)은 리처드 벨만(Richard Bellman)이 1950년대에 제안한 최적화 방법론으로, 다단계 의사결정 문제를 재귀적으로 분해하여 해결하는 접근법이다. 그 핵심은 최적성의 원리(principle of optimality)에 있으며, 벨만은 이를 다음과 같이 진술하였다.

“최적 정책은 초기 상태와 초기 결정이 무엇이든 간에, 나머지 결정들이 초기 결정의 결과로 생성된 상태에 대해 최적 정책을 구성해야 한다는 성질을 갖는다.”

즉, 최적 궤적의 임의의 부분 궤적 또한 해당 부분 문제에 대해 최적이다. 이 원리는 전역 최적화 문제를 국소적인 하위 문제들의 연쇄로 분해할 수 있는 이론적 기반을 제공한다.

2. 최적 비용 함수의 정의

연속 시간 최적 제어 문제에서 시각 $t$ , 상태 $\mathbf{x}$ 를 출발점으로 하여 잔여 구간 $[t, t_f]$ 에서 달성 가능한 최적 비용(cost-to-go)을 최적 비용 함수(optimal cost function) 또는 가치 함수(value function)로 정의한다.

$V(\mathbf{x}, t) = \min_{\mathbf{u}(\cdot) \in \mathcal{U}} \left\{ \phi(\mathbf{x}(t_f), t_f) + \int_{t}^{t_f} L(\mathbf{x}(s), \mathbf{u}(s), s) \, ds \right\}$

여기서 최소화는 시각 $t$ 에서 상태 $\mathbf{x}(t) = \mathbf{x}$ 를 초기 조건으로 하고 동역학 $\dot{\mathbf{x}} = \mathbf{f}(\mathbf{x}, \mathbf{u}, s)$ 를 만족하는 모든 허용 제어에 대해 수행된다. 종단 시각에서의 경계 조건은 다음과 같다.

$V(\mathbf{x}, t_f) = \phi(\mathbf{x}, t_f)$

3. 벨만 방정식의 유도

최적성의 원리를 적용하여 구간 $[t, t_f]$ 를 $[t, t + \Delta t]$ 와 $[t + \Delta t, t_f]$ 로 분할한다. 첫 번째 구간에서의 비용과 두 번째 구간에서의 최적 비용을 결합하면 다음의 재귀 관계를 얻는다.

$V(\mathbf{x}, t) = \min_{\mathbf{u} \in \mathcal{U}} \left\{ \int_{t}^{t + \Delta t} L(\mathbf{x}(s), \mathbf{u}(s), s) \, ds + V(\mathbf{x}(t + \Delta t), t + \Delta t) \right\}$

$\Delta t \to 0$ 의 극한에서 적분을 $L(\mathbf{x}, \mathbf{u}, t) \Delta t + O(\Delta t^2)$ 로 근사하고, $V(\mathbf{x}(t + \Delta t), t + \Delta t)$ 를 1차 테일러 전개하면 다음을 얻는다.

$V(\mathbf{x}, t) = \min_{\mathbf{u} \in \mathcal{U}} \left\{ L(\mathbf{x}, \mathbf{u}, t) \Delta t + V(\mathbf{x}, t) + \frac{\partial V}{\partial t} \Delta t + \left( \frac{\partial V}{\partial \mathbf{x}} \right)^T \mathbf{f}(\mathbf{x}, \mathbf{u}, t) \Delta t + O(\Delta t^2) \right\}$

양변에서 $V(\mathbf{x}, t)$ 를 소거하고 $\Delta t$ 로 나눈 후 $\Delta t \to 0$ 의 극한을 취하면 다음을 얻는다.

$0 = \min_{\mathbf{u} \in \mathcal{U}} \left\{ L(\mathbf{x}, \mathbf{u}, t) + \frac{\partial V}{\partial t} + \left( \frac{\partial V}{\partial \mathbf{x}} \right)^T \mathbf{f}(\mathbf{x}, \mathbf{u}, t) \right\}$

4. 해밀턴-야코비-벨만(HJB) 방정식

위의 결과를 재정리하면 해밀턴-야코비-벨만(Hamilton-Jacobi-Bellman, HJB) 방정식을 얻는다.

$-\frac{\partial V}{\partial t} = \min_{\mathbf{u} \in \mathcal{U}} \left\{ L(\mathbf{x}, \mathbf{u}, t) + \left( \frac{\partial V}{\partial \mathbf{x}} \right)^T \mathbf{f}(\mathbf{x}, \mathbf{u}, t) \right\}$

경계 조건: $V(\mathbf{x}, t_f) = \phi(\mathbf{x}, t_f)$

해밀토니안을 이용하면 HJB 방정식은 다음과 같이 간결하게 표현된다.

$-\frac{\partial V}{\partial t} = \min_{\mathbf{u} \in \mathcal{U}} H\left(\mathbf{x}, \frac{\partial V}{\partial \mathbf{x}}, \mathbf{u}, t\right)$

여기서 $H(\mathbf{x}, \mathbf{p}, \mathbf{u}, t) = L(\mathbf{x}, \mathbf{u}, t) + \mathbf{p}^T \mathbf{f}(\mathbf{x}, \mathbf{u}, t)$ 이고, $\mathbf{p} = \frac{\partial V}{\partial \mathbf{x}}$ 이다.

HJB 방정식은 상태 공간과 시간에 대한 1차 편미분 방정식(partial differential equation)으로, 종단 시각 $t_f$ 로부터 시간 역방향으로 풀어야 한다.

5. HJB 방정식과 폰트랴긴 최대 원리의 관계

HJB 방정식의 해 $V(\mathbf{x}, t)$ 가 충분히 매끄러운 경우, 가치 함수의 그래디언트와 공상태 변수는 최적 궤적 위에서 일치한다.

$\boldsymbol{\lambda}^*(t) = \frac{\partial V}{\partial \mathbf{x}} \bigg\vert_{\mathbf{x}^*(t), t}$

이 관계는 두 접근법 사이의 깊은 연결을 보여 준다. 폰트랴긴의 최대 원리가 최적 궤적을 따르는 필요 조건(경로 관점)을 제공하는 반면, HJB 방정식은 전체 상태 공간에서의 최적 비용 함수(장 관점)를 기술한다. 폰트랴긴의 최대 원리는 필요 조건이지만, HJB 방정식은 가치 함수가 존재하고 매끄러운 경우 충분 조건까지 제공한다.

6. 충분 조건으로서의 HJB 방정식

다음의 검증 정리(verification theorem)가 성립한다. $V(\mathbf{x}, t)$ 가 HJB 방정식을 만족하는 $C^1$ 함수이고, $\mathbf{u}^*(\mathbf{x}, t)$ 가 HJB 방정식 우변의 최소화를 달성하는 제어 법칙이라 하자. 그러면 $\mathbf{u}^*$ 는 전역 최적 제어이며, $V$ 는 최적 비용 함수이다.

이 정리의 핵심은 HJB 방정식이 충분 조건을 제공한다는 점이다. 임의의 허용 제어 $\mathbf{u}(\cdot)$ 에 대해 다음이 성립한다.

$V(\mathbf{x}_0, t_0) \leq \phi(\mathbf{x}(t_f)) + \int_{t_0}^{t_f} L(\mathbf{x}, \mathbf{u}, t) \, dt$

등호는 $\mathbf{u} = \mathbf{u}^*$ 일 때에만 성립한다.

7. 최적 피드백 제어

HJB 방정식의 중요한 특성은 최적 제어를 폐루프 피드백 형태로 제공한다는 점이다. 가치 함수 $V(\mathbf{x}, t)$ 를 알고 있으면, 최적 제어는 현재 상태의 함수로 즉시 결정된다.

$\mathbf{u}^*(\mathbf{x}, t) = \arg\min_{\mathbf{u} \in \mathcal{U}} \left\{ L(\mathbf{x}, \mathbf{u}, t) + \left( \frac{\partial V}{\partial \mathbf{x}} \right)^T \mathbf{f}(\mathbf{x}, \mathbf{u}, t) \right\}$

이는 폰트랴긴의 최대 원리가 제공하는 개루프(open-loop) 최적 제어와 대비된다. 피드백 형태의 최적 제어는 초기 조건의 변화나 외란에 대해 본질적인 강건성(robustness)을 갖는다.

8. 선형 이차 문제에서의 HJB 방정식

선형 시스템 $\dot{\mathbf{x}} = \mathbf{A}\mathbf{x} + \mathbf{B}\mathbf{u}$ 와 이차 비용 함수

$J = \frac{1}{2}\mathbf{x}^T(t_f)\mathbf{S}_f\mathbf{x}(t_f) + \frac{1}{2}\int_{t_0}^{t_f} [\mathbf{x}^T\mathbf{Q}\mathbf{x} + \mathbf{u}^T\mathbf{R}\mathbf{u}] \, dt$

에 대해, 가치 함수를 $V(\mathbf{x}, t) = \frac{1}{2}\mathbf{x}^T\mathbf{P}(t)\mathbf{x}$ 로 가정한다. $\frac{\partial V}{\partial \mathbf{x}} = \mathbf{P}(t)\mathbf{x}$ 를 HJB 방정식에 대입하고 $\mathbf{u}$ 에 대해 최소화하면 다음을 얻는다.

$\mathbf{u}^* = -\mathbf{R}^{-1}\mathbf{B}^T\mathbf{P}(t)\mathbf{x}$

이를 HJB 방정식에 다시 대입하면 $\mathbf{P}(t)$ 에 대한 행렬 리카티 미분 방정식을 얻는다.

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

경계 조건: $\mathbf{P}(t_f) = \mathbf{S}_f$

이 결과는 선형 이차 문제에서 HJB 방정식이 유한 차원 행렬 방정식으로 축소됨을 보여 주며, 해석적으로 다룰 수 있는 드문 경우에 해당한다.

9. 차원의 저주

HJB 방정식의 주요 한계는 차원의 저주(curse of dimensionality)이다. 이 용어는 벨만 자신이 명명한 것으로, 상태 공간의 차원 $n$ 이 증가함에 따라 HJB 방정식을 수치적으로 풀기 위해 필요한 계산 자원이 기하급수적으로 증가하는 현상을 지칭한다.

상태 공간을 격자(grid)로 이산화하여 HJB 방정식을 수치적으로 풀 때, 각 차원을 $N$ 개의 격자점으로 분할하면 전체 격자점의 수는 $N^n$ 이 된다. 로봇 매니퓰레이터의 경우 상태 벡터가 관절 위치와 속도로 구성되어 $n = 2k$ ( $k$ 는 관절 수)이므로, 6자유도 매니퓰레이터는 12차원의 상태 공간을 갖는다. 이러한 고차원 문제에서 격자 기반 수치 해법은 실질적으로 불가능하다.

10. 점성 해와 약해

HJB 방정식의 해가 고전적 의미에서 매끄럽지 않은 경우가 발생한다. 특히 제어 입력에 구간 제약이 있는 경우, 최적 제어의 전환(switching) 지점에서 가치 함수의 미분 가능성이 깨질 수 있다. 이러한 상황에서는 점성 해(viscosity solution)의 개념이 도입된다.

점성 해는 크랜달(Crandall)과 리옹(Lions)에 의해 1983년에 정립된 약해(weak solution)의 개념으로, 고전적 미분 가능성을 요구하지 않으면서도 해의 존재성과 유일성을 보장한다. HJB 방정식의 점성 해 $V$ 는 다음의 두 부등식을 동시에 만족한다.

아래 점성 조건(viscosity subsolution): 임의의 매끄러운 시험 함수 $\varphi$ 가 $V - \varphi$ 의 극대점 $(\mathbf{x}_0, t_0)$ 에서 다음을 만족한다.

$-\frac{\partial \varphi}{\partial t} \leq \min_{\mathbf{u} \in \mathcal{U}} H\left(\mathbf{x}_0, \frac{\partial \varphi}{\partial \mathbf{x}}, \mathbf{u}, t_0\right)$

위 점성 조건(viscosity supersolution): 임의의 매끄러운 시험 함수 $\varphi$ 가 $V - \varphi$ 의 극소점 $(\mathbf{x}_0, t_0)$ 에서 다음을 만족한다.

$-\frac{\partial \varphi}{\partial t} \geq \min_{\mathbf{u} \in \mathcal{U}} H\left(\mathbf{x}_0, \frac{\partial \varphi}{\partial \mathbf{x}}, \mathbf{u}, t_0\right)$

11. 수치 해법

11.1 격자 기반 방법

저차원 문제( $n \leq 4$ 정도)에서는 상태 공간을 격자로 이산화하고, HJB 방정식을 유한 차분법(finite difference method) 또는 수준 집합 방법(level set method)으로 풀 수 있다. 시간 역방향 적분은 종단 조건 $V(\mathbf{x}, t_f) = \phi(\mathbf{x})$ 에서 출발하여 $t_0$ 까지 진행한다.

11.2 근사 동적 계획법

차원의 저주를 완화하기 위한 방법으로 근사 동적 계획법(Approximate Dynamic Programming, ADP)이 연구되어 왔다. 가치 함수를 기저 함수(basis function)의 선형 결합으로 근사한다.

$\hat{V}(\mathbf{x}, t) = \sum_{k=1}^{K} w_k(t) \phi_k(\mathbf{x})$

여기서 $\phi_k(\mathbf{x})$ 는 사전에 선택된 기저 함수이고, $w_k(t)$ 는 학습을 통해 결정되는 가중치이다. 이 접근법은 강화 학습(reinforcement learning)과 밀접한 관련이 있으며, 고차원 로봇 시스템에 대한 근사적 최적 제어를 제공한다.

12. 이산 시간 동적 계획법

연속 시간 HJB 방정식의 이산 시간 대응물은 벨만 방정식(Bellman equation)이다. 시간 축을 $t_0, t_1, \ldots, t_N = t_f$ 로 이산화하면, 최적 비용 함수는 다음의 재귀식을 만족한다.

$V_k(\mathbf{x}_k) = \min_{\mathbf{u}_k \in \mathcal{U}} \left\{ L_k(\mathbf{x}_k, \mathbf{u}_k) + V_{k+1}(\mathbf{f}_k(\mathbf{x}_k, \mathbf{u}_k)) \right\}$

경계 조건: $V_N(\mathbf{x}_N) = \phi(\mathbf{x}_N)$

이 재귀식을 $k = N-1$ 에서 $k = 0$ 까지 역방향으로 풀면 각 시각과 상태에서의 최적 제어를 결정할 수 있다. 이산 시간 동적 계획법은 연속 시간 HJB 방정식의 수치적 구현에 직접적으로 대응하며, 로봇 궤적 최적화의 수치 해법에서 핵심적인 역할을 한다.

13. 로봇 공학에서의 응용

동적 계획법과 HJB 방정식은 로봇 공학에서 다음과 같은 문제에 적용된다.

저차원 경로 계획: 이동 로봇의 2차원 또는 3차원 경로 계획에서 격자 기반 동적 계획법이 전역 최적 경로를 보장하는 방법으로 활용된다. 상태 공간의 차원이 낮아 계산 부담이 관리 가능한 수준이다.

도달 가능 집합 분석: 비행 로봇이나 자율 주행 차량의 안전 분석에서, HJB 방정식의 영수준 집합(zero level set)을 통해 시스템이 안전 영역 내에 머물 수 있는 상태의 집합(도달 가능 집합)을 계산한다.

강화 학습과의 연계: 벨만 방정식은 강화 학습의 이론적 기초를 형성한다. 마르코프 결정 과정(Markov Decision Process, MDP)에서의 가치 함수 학습은 벨만 방정식의 반복적 근사에 해당하며, 이는 고차원 로봇 제어 문제에 학습 기반 최적 제어를 적용하는 경로를 제공한다.

14. 참고 문헌

Bellman, R. (1957). Dynamic Programming. Princeton University Press.
Bertsekas, D. P. (2012). Dynamic Programming and Optimal Control (4th ed., Vols. 1–2). Athena Scientific.
Kirk, D. E. (2004). Optimal Control Theory: An Introduction. Dover Publications.
Bardi, M., & Capuzzo-Dolcetta, I. (1997). Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations. Birkhäuser.
Lewis, F. L., Vrabie, D., & Syrmos, V. L. (2012). Optimal Control (3rd ed.). Wiley.

version: 1.0