397.30 마르코프 결정 과정(MDP) 기반 임무 계획

1. 개요

마르코프 결정 과정(Markov Decision Process, MDP)은 불확실성이 존재하는 환경에서 순차적 의사 결정을 수학적으로 모델링하는 프레임워크이다. 로봇 임무 계획에서 MDP는 행동의 결과가 확률적으로 결정되는 상황을 체계적으로 다루며, 기대 보상(Expected Reward)을 최대화하는 최적 정책(Optimal Policy)을 도출하는 데 활용된다. 결정론적 계획 기법이 행동의 결과를 완전히 예측 가능하다고 가정하는 반면, MDP 기반 임무 계획은 센서 노이즈, 액추에이터 오차, 환경 변동 등 실제 로봇 운용 환경에서 불가피하게 발생하는 불확실성을 명시적으로 반영한다.

MDP의 이론적 기초는 Bellman의 동적 프로그래밍(Dynamic Programming) 원리에 근거하며 (Bellman, 1957), 이후 Puterman에 의해 체계적인 수학적 이론이 정립되었다 (Puterman, 1994). 로봇 공학 분야에서는 Thrun, Burgard, Fox가 확률론적 로봇 공학(Probabilistic Robotics)의 맥락에서 MDP를 활용한 의사 결정 체계를 제시한 바 있다 (Thrun et al., 2005).

2. MDP의 형식적 정의

MDP는 튜플 $\mathcal{M} = \langle \mathcal{S}, \mathcal{A}, T, R, \gamma \rangle$ 로 정의된다.

상태 공간(State Space) $\mathcal{S}$ : 시스템이 취할 수 있는 모든 가능한 상태의 유한 집합이다. 로봇 임무 계획에서 상태는 로봇의 위치, 배터리 잔량, 임무 진행 상황, 환경 조건 등을 포함하는 복합적 표현이다.
행동 공간(Action Space) $\mathcal{A}$ : 에이전트가 각 상태에서 선택할 수 있는 행동의 유한 집합이다. 상태 의존적 행동 집합 $\mathcal{A}(s) \subseteq \mathcal{A}$ 을 정의하여 특정 상태에서 실행 가능한 행동만 허용할 수 있다.
전이 함수(Transition Function) $T: \mathcal{S} \times \mathcal{A} \times \mathcal{S} \rightarrow [0, 1]$ :

$T(s, a, s') = P(s_{t+1} = s' \mid s_t = s, a_t = a)$

상태 $s$ 에서 행동 $a$ 를 실행했을 때 상태 $s'$ 로 전이할 확률을 정의한다. 모든 상태-행동 쌍에 대해 다음의 정규화 조건을 만족하여야 한다:

$\sum_{s' \in \mathcal{S}} T(s, a, s') = 1, \quad \forall s \in \mathcal{S}, \; a \in \mathcal{A}(s)$

보상 함수(Reward Function) $R: \mathcal{S} \times \mathcal{A} \times \mathcal{S} \rightarrow \mathbb{R}$ : 상태 $s$ 에서 행동 $a$ 를 실행하여 상태 $s'$ 로 전이할 때 얻는 즉각적 보상이다. 단순화하여 $R(s, a)$ 또는 $R(s)$ 로 표기하기도 한다.
할인 계수(Discount Factor) $\gamma \in [0, 1)$ : 미래 보상의 현재 가치를 조절하는 매개변수이다. $\gamma$ 가 0에 가까울수록 근시안적(Myopic) 정책을, 1에 가까울수록 장기적 보상을 중시하는 정책을 유도한다.

3. 마르코프 성질과 기본 가정

MDP의 핵심 가정은 **마르코프 성질(Markov Property)**이다. 이 성질은 미래의 상태가 현재의 상태와 행동에만 의존하며, 과거의 상태 이력에는 독립적임을 의미한다:

$P(s_{t+1} \mid s_t, a_t, s_{t-1}, a_{t-1}, \ldots, s_0, a_0) = P(s_{t+1} \mid s_t, a_t)$

이 가정은 상태 표현이 의사 결정에 필요한 모든 정보를 충분히 포함하고 있음을 요구한다. 로봇 임무 계획에서 이 조건을 충족시키기 위해서는 상태 공간의 설계가 매우 중요하다. 예를 들어, 로봇의 현재 위치만으로 상태를 정의하면 마르코프 성질이 위반될 수 있으므로, 방문한 지점, 적재 물품, 잔여 에너지 등을 상태에 포함시켜야 한다.

또한, MDP는 다음의 추가적 가정을 전제로 한다:

완전 관측성(Full Observability): 에이전트는 매 시간 단계에서 환경의 정확한 상태를 관측할 수 있다.
정상성(Stationarity): 전이 확률과 보상 함수가 시간에 따라 변하지 않는다.
이산 시간(Discrete Time): 의사 결정이 이산적인 시간 단계에서 이루어진다.

4. 정책과 가치 함수

4.1 정책의 정의

정책(Policy) $\pi$ 는 각 상태에서 어떤 행동을 선택할지를 결정하는 규칙이다. 결정론적 정책(Deterministic Policy)은 함수 $\pi: \mathcal{S} \rightarrow \mathcal{A}$ 로 표현되며, 확률론적 정책(Stochastic Policy)은 조건부 확률 분포 $\pi(a \mid s)$ 로 표현된다. 유한 MDP에서는 최적 정책이 반드시 결정론적 정책으로 존재함이 증명되어 있다 (Puterman, 1994).

4.2 상태 가치 함수

정책 $\pi$ 를 따를 때 상태 $s$ 의 기대 누적 할인 보상을 정의하는 상태 가치 함수(State Value Function)는 다음과 같다:

$V^\pi(s) = \mathbb{E}_\pi \left[ \sum_{t=0}^{\infty} \gamma^t R(s_t, \pi(s_t)) \;\middle|\; s_0 = s \right]$

이 함수는 현재 상태에서 정책 $\pi$ 를 무한히 따를 때 얻을 수 있는 기대 총 보상의 현재 가치를 나타낸다.

4.3 행동 가치 함수

행동 가치 함수(Action Value Function) 또는 Q-함수는 상태 $s$ 에서 행동 $a$ 를 선택한 후 정책 $\pi$ 를 따를 때의 기대 누적 보상이다:

$Q^\pi(s, a) = \mathbb{E}_\pi \left[ \sum_{t=0}^{\infty} \gamma^t R(s_t, a_t) \;\middle|\; s_0 = s, a_0 = a \right]$

두 가치 함수 사이에는 다음의 관계가 성립한다:

$V^\pi(s) = Q^\pi(s, \pi(s))$

$Q^\pi(s, a) = R(s, a) + \gamma \sum_{s' \in \mathcal{S}} T(s, a, s') V^\pi(s')$

5. 벨만 방정식

5.1 벨만 기대 방정식

정책 $\pi$ 에 대한 상태 가치 함수는 벨만 기대 방정식(Bellman Expectation Equation)을 만족한다:

$V^\pi(s) = \sum_{a \in \mathcal{A}} \pi(a \mid s) \left[ R(s, a) + \gamma \sum_{s' \in \mathcal{S}} T(s, a, s') V^\pi(s') \right]$

결정론적 정책의 경우 이는 다음과 같이 단순화된다:

$V^\pi(s) = R(s, \pi(s)) + \gamma \sum_{s' \in \mathcal{S}} T(s, \pi(s), s') V^\pi(s')$

이 방정식은 $|\mathcal{S}|$ 개의 미지수를 갖는 $|\mathcal{S}|$ 개의 선형 연립 방정식 체계를 형성하므로, 가우스 소거법 등의 직접 해법으로 풀 수 있다. 그러나 상태 공간이 큰 경우 이 직접 해법은 $O(|\mathcal{S}|^3)$ 의 계산 복잡도를 가지므로 비효율적이다.

5.2 벨만 최적 방정식

최적 정책 $\pi^*$ 에 대응하는 최적 가치 함수 $V^*(s) = \max_\pi V^\pi(s)$ 는 벨만 최적 방정식(Bellman Optimality Equation)을 만족한다:

$V^*(s) = \max_{a \in \mathcal{A}(s)} \left[ R(s, a) + \gamma \sum_{s' \in \mathcal{S}} T(s, a, s') V^*(s') \right]$

행동 가치 함수에 대한 벨만 최적 방정식은 다음과 같다:

$Q^*(s, a) = R(s, a) + \gamma \sum_{s' \in \mathcal{S}} T(s, a, s') \max_{a' \in \mathcal{A}(s')} Q^*(s', a')$

최적 정책은 최적 가치 함수로부터 탐욕적(Greedy)으로 도출할 수 있다:

$\pi^*(s) = \arg\max_{a \in \mathcal{A}(s)} \left[ R(s, a) + \gamma \sum_{s' \in \mathcal{S}} T(s, a, s') V^*(s') \right]$

6. 로봇 임무 계획에서의 MDP 모델링

6.1 상태 공간 설계

로봇 임무 계획에서 MDP의 상태 공간은 임무 수행에 필요한 모든 정보를 포함하도록 설계되어야 한다. 대표적인 상태 변수는 다음과 같다:

로봇 위치: 이산적 위치 노드 또는 그리드 셀로 표현한다.
임무 진행 상태: 각 하위 작업(Sub-Task)의 완료 여부를 이진 벡터로 표현한다.
자원 상태: 배터리 잔량, 적재 용량 등을 이산화하여 표현한다.
환경 상태: 장애물 존재 여부, 기상 조건 등 외부 환경 변수를 포함한다.

상태 공간의 크기는 각 변수의 도메인 크기의 곱으로 결정되므로, 변수의 수가 증가하면 상태 공간이 지수적으로 증가하는 차원의 저주(Curse of Dimensionality) 문제가 발생한다.

6.2 전이 확률의 구성

로봇 임무 계획에서 전이 확률은 로봇의 동역학 모델과 환경의 불확실성을 반영한다. 예를 들어, 로봇이 위치 $l_i$ 에서 위치 $l_j$ 로 이동하는 행동을 실행할 때:

$T((l_i, \mathbf{m}), \text{move}(l_j), (l_j, \mathbf{m})) = p_{\text{success}}$

$T((l_i, \mathbf{m}), \text{move}(l_j), (l_i, \mathbf{m})) = 1 - p_{\text{success}}$

여기서 $\mathbf{m}$ 은 임무 진행 상태 벡터이고, $p_{\text{success}}$ 는 이동 성공 확률이다. 이 확률은 경로의 특성, 장애물 밀도, 기상 조건 등에 따라 달라질 수 있다.

6.3 보상 함수의 설계

보상 함수는 임무 목표와 운용 제약을 반영하도록 설계한다. 일반적으로 다음의 구성 요소를 포함한다:

$R(s, a) = R_{\text{goal}}(s) + R_{\text{step}}(a) + R_{\text{constraint}}(s, a)$

$R_{\text{goal}}(s)$ : 목표 상태 도달 시 부여하는 양의 보상
$R_{\text{step}}(a)$ : 각 행동 실행에 대한 음의 보상(시간, 에너지 비용 반영)
$R_{\text{constraint}}(s, a)$ : 제약 조건 위반에 대한 큰 음의 보상(벌칙)

보상 함수의 적절한 설계는 MDP 기반 임무 계획의 성공에 결정적인 역할을 한다. 보상의 규모와 구조가 최적 정책의 행동 패턴을 결정하므로, 보상 공학(Reward Engineering)에 대한 세심한 고려가 필요하다.

7. 유한 수평 MDP와 무한 수평 MDP

7.1 유한 수평 MDP

유한 수평(Finite-Horizon) MDP는 의사 결정의 시간 단계 수 $H$ 가 유한하게 고정된 경우이다. 목적 함수는 다음과 같다:

$V^\pi_t(s) = \mathbb{E}_\pi \left[ \sum_{k=t}^{H-1} R(s_k, a_k) + R_H(s_H) \;\middle|\; s_t = s \right]$

여기서 $R_H(s_H)$ 는 종료 상태의 보상이다. 유한 수평 MDP에서는 할인 계수가 필요하지 않으며, 최적 정책이 시간 의존적(Non-Stationary)일 수 있다. 즉, 동일한 상태에서도 남은 시간 단계에 따라 최적 행동이 달라질 수 있다.

후진 귀납법(Backward Induction)을 통해 최적 가치 함수를 계산한다:

$V^*_H(s) = R_H(s)$

$V^*_t(s) = \max_{a \in \mathcal{A}(s)} \left[ R(s, a) + \sum_{s' \in \mathcal{S}} T(s, a, s') V^*_{t+1}(s') \right], \quad t = H-1, \ldots, 0$

7.2 무한 수평 MDP

무한 수평(Infinite-Horizon) MDP에서는 할인 계수 $\gamma < 1$ 을 도입하여 총 보상의 수렴을 보장한다. 이 경우 최적 정책은 정상적(Stationary)이며, 시간에 독립적이다. 무한 수평 MDP의 장점은 정책의 단순성에 있으며, 실제 로봇 임무 계획에서 임무의 종료 시점이 불확실한 경우에 적합하다.

가치 함수의 유계성(Boundedness)은 다음과 같이 보장된다. 보상이 $|R(s, a)| \leq R_{\max}$ 로 유계인 경우:

$|V^*(s)| \leq \frac{R_{\max}}{1 - \gamma}, \quad \forall s \in \mathcal{S}$

8. MDP와 다른 계획 패러다임의 비교

MDP 기반 임무 계획은 결정론적 계획과 비교하여 다음의 특성을 갖는다:

특성	결정론적 계획	MDP 기반 계획
행동 결과	확정적	확률적
해의 형태	행동 시퀀스	정책 (상태→행동 매핑)
불확실성 처리	불가	명시적 모델링
관측 가정	완전 관측	완전 관측
최적성 기준	최소 비용/길이	최대 기대 보상
계산 복잡도	PSPACE-완전	P (다항 시간)

MDP의 주목할 만한 장점 중 하나는, 유한 상태-행동 공간에서 최적 정책을 다항 시간에 계산할 수 있다는 것이다. 이는 결정론적 계획의 PSPACE-완전 복잡도와 대비되는 이론적 우수성이다. 그러나 실제로는 상태 공간의 크기가 지수적으로 증가할 수 있어, 대규모 문제에서는 근사 기법이 필요하다.

9. 확장 MDP 모델

9.1 제약 MDP(Constrained MDP)

제약 MDP(CMDP)는 기대 보상 최대화와 함께 부가적인 제약 조건을 만족시키는 정책을 탐색한다. 로봇 임무 계획에서 에너지 소모량, 위험 지역 통과 횟수 등에 대한 제약을 부과할 때 활용된다:

$\max_\pi \mathbb{E}_\pi \left[ \sum_{t=0}^{\infty} \gamma^t R(s_t, a_t) \right] \quad \text{subject to} \quad \mathbb{E}_\pi \left[ \sum_{t=0}^{\infty} \gamma^t C_i(s_t, a_t) \right] \leq d_i, \; i = 1, \ldots, k$

여기서 $C_i$ 는 $i$ 번째 비용 함수이고, $d_i$ 는 해당 제약의 상한이다. CMDP는 선형 프로그래밍(Linear Programming)을 통해 해를 구할 수 있으며, 최적 정책이 확률론적(Randomized)일 수 있다는 특성이 있다 (Altman, 1999).

9.2 분해 가능 MDP(Factored MDP)

차원의 저주를 완화하기 위해 상태 공간을 인수분해(Factoring)하는 기법이다. 상태를 독립적인 상태 변수의 집합 $\mathcal{S} = \mathcal{X}_1 \times \mathcal{X}_2 \times \cdots \times \mathcal{X}_n$ 으로 표현하고, 전이 함수와 보상 함수의 구조적 독립성을 활용하여 계산을 효율화한다. 동적 베이즈 네트워크(Dynamic Bayesian Network, DBN)를 사용하여 전이 함수의 조건부 독립성 구조를 표현할 수 있다 (Boutilier et al., 2000).

9.3 반마르코프 결정 과정(Semi-MDP)

행동의 지속 시간이 가변적인 경우를 다루는 확장 모델이다. 로봇 임무 계획에서 이동, 조작, 대기 등 행동의 소요 시간이 다를 때 적절하다. 반마르코프 결정 과정(SMDP)에서는 행동 $a$ 를 실행할 때 소요 시간 $\tau$ 도 확률적으로 결정되며, 할인 계수가 시간에 따라 적용된다:

$V^*(s) = \max_{a \in \mathcal{A}(s)} \left[ R(s, a) + \sum_{s' \in \mathcal{S}} T(s, a, s') \mathbb{E}[\gamma^\tau] V^*(s') \right]$

10. 참고 문헌

Bellman, R. (1957). Dynamic Programming. Princeton University Press.
Puterman, M. L. (1994). Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley-Interscience.
Thrun, S., Burgard, W., & Fox, D. (2005). Probabilistic Robotics. MIT Press.
Boutilier, C., Dean, T., & Hanks, S. (1999). “Decision-Theoretic Planning: Structural Assumptions and Computational Leverage.” Journal of Artificial Intelligence Research, 11, pp. 1-94.
Boutilier, C., Dearden, R., & Goldszmidt, M. (2000). “Stochastic Dynamic Programming with Factored Representations.” Artificial Intelligence, 121(1-2), pp. 49-107.
Altman, E. (1999). Constrained Markov Decision Processes. Chapman and Hall/CRC.

본 절은 마르코프 결정 과정(MDP)의 수학적 정의, 벨만 방정식, 로봇 임무 계획에서의 모델링 기법, 및 확장 MDP 모델을 다루었다. v1.0