397.34 부분 관측 마르코프 결정 과정(POMDP) 기반 임무 계획

1. 개요

부분 관측 마르코프 결정 과정(Partially Observable Markov Decision Process, POMDP)은 에이전트가 환경의 정확한 상태를 직접 관측할 수 없는 상황에서의 순차적 의사 결정을 모델링하는 수학적 프레임워크이다. 표준 MDP가 완전 관측성(Full Observability)을 가정하는 반면, POMDP는 센서의 한계, 가려진 영역, 통신 지연 등으로 인해 불완전하고 노이즈가 포함된 관측만 가능한 현실적 상황을 다룬다. 이 점에서 POMDP는 실제 로봇 운용 환경의 불확실성을 가장 충실하게 반영하는 의사 결정 모델이라 할 수 있다.

POMDP의 이론적 기초는 Åström이 1965년에 제시한 부분 관측 제어 문제에서 출발하며 (Åström, 1965), Sondik에 의해 유한 수평 POMDP의 최적 해법이 정립되었다 (Sondik, 1971). Kaelbling, Littman, Cassandra 등의 연구를 통해 POMDP의 계산적 기법이 본격적으로 발전하였으며 (Kaelbling et al., 1998), 로봇 공학 분야에서는 수색 및 구조, 자율 탐사, 능동적 인지(Active Perception) 등의 임무 계획에 핵심적으로 활용되고 있다.

2. POMDP의 형식적 정의

POMDP는 7-튜플 $\mathcal{P} = \langle \mathcal{S}, \mathcal{A}, T, R, \Omega, O, \gamma \rangle$ 로 정의된다.

상태 공간(State Space) $\mathcal{S}$ : 환경의 모든 가능한 상태의 유한 집합이다. 에이전트는 현재 상태 $s \in \mathcal{S}$ 를 직접 관측할 수 없다.
행동 공간(Action Space) $\mathcal{A}$ : 에이전트가 선택할 수 있는 행동의 유한 집합이다.
전이 함수(Transition Function) $T: \mathcal{S} \times \mathcal{A} \times \mathcal{S} \rightarrow [0, 1]$ :
$T(s, a, s') = \Pr(s_{t+1} = s' \mid s_t = s, a_t = a)$
보상 함수(Reward Function) $R: \mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R}$ : 상태 $s$ 에서 행동 $a$ 를 실행할 때의 즉각적 보상이다.
관측 공간(Observation Space) $\Omega$ : 에이전트가 수신할 수 있는 모든 관측의 유한 집합이다. 로봇 임무 계획에서 관측은 센서 판독값, 카메라 영상의 특징, 통신 수신 신호 등을 포함한다.
관측 함수(Observation Function) $O: \mathcal{S} \times \mathcal{A} \times \Omega \rightarrow [0, 1]$ :
$O(s', a, o) = \Pr(o_{t+1} = o \mid s_{t+1} = s', a_t = a)$
행동 $a$ 를 실행하여 상태 $s'$ 에 도달했을 때 관측 $o$ 를 수신할 확률이다.
할인 계수(Discount Factor) $\gamma \in [0, 1)$ : 미래 보상의 현재 가치를 결정한다.

MDP의 구성 요소에 관측 공간 $\Omega$ 과 관측 함수 $O$ 가 추가된 것이 POMDP의 본질적 차이이다. 관측 함수가 항등 함수, 즉 $O(s', a, o) = 1$ if $o = s'$ 이면 POMDP는 MDP로 퇴화한다.

3. 신뢰 상태(Belief State)

3.1 신뢰 상태의 정의

POMDP에서 에이전트는 환경의 실제 상태를 알 수 없으므로, 상태에 대한 확률 분포인 신뢰 상태(Belief State) $b$ 를 유지한다. 신뢰 상태는 상태 공간 $\mathcal{S}$ 위의 확률 분포이다:

$b(s) = \Pr(s_t = s \mid h_t), \quad b(s) \geq 0, \quad \sum_{s \in \mathcal{S}} b(s) = 1$

여기서 $h_t = (b_0, a_0, o_1, a_1, o_2, \ldots, a_{t-1}, o_t)$ 는 시각 $t$ 까지의 행동-관측 이력(History)이다. 신뢰 상태는 이 전체 이력을 확률론적으로 요약하는 **충분 통계량(Sufficient Statistic)**이다.

신뢰 상태의 공간은 $(|\mathcal{S}| - 1)$ -차원 단체(Simplex)이다:

$\mathcal{B} = \left\{ b \in \mathbb{R}^{|\mathcal{S}|} \;\middle|\; b(s) \geq 0, \; \sum_{s} b(s) = 1 \right\}$

이 공간은 연속이고 무한하므로, POMDP는 연속 상태 공간을 갖는 MDP, 즉 **신뢰 MDP(Belief MDP)**로 변환된다.

3.2 베이즈 신뢰 갱신

에이전트가 신뢰 상태 $b$ 에서 행동 $a$ 를 실행하고 관측 $o$ 를 수신하면, 신뢰 상태는 베이즈 규칙(Bayes’ Rule)에 의해 다음과 같이 갱신된다:

$b'(s') = \eta \cdot O(s', a, o) \sum_{s \in \mathcal{S}} T(s, a, s') b(s)$

여기서 $\eta$ 는 정규화 상수이다:

$\eta = \frac{1}{\Pr(o \mid b, a)} = \frac{1}{\sum_{s'} O(s', a, o) \sum_{s} T(s, a, s') b(s)}$

이 갱신 과정을 함수적으로 표현하면 $b' = \tau(b, a, o)$ 이다. 신뢰 갱신 연산자 $\tau$ 는 POMDP를 신뢰 MDP로 변환하는 핵심 메커니즘이다.

관측의 사전 확률은 다음과 같다:

$\Pr(o \mid b, a) = \sum_{s' \in \mathcal{S}} O(s', a, o) \sum_{s \in \mathcal{S}} T(s, a, s') b(s)$

4. 신뢰 MDP로의 변환

POMDP는 다음의 신뢰 MDP $\mathcal{M}_b = \langle \mathcal{B}, \mathcal{A}, \tau, \rho, \gamma \rangle$ 로 변환할 수 있다.

상태 공간: 연속 신뢰 상태 공간 $\mathcal{B}$
행동 공간: 원래의 $\mathcal{A}$
전이 역학: $b' = \tau(b, a, o)$ , 관측 $o$ 의 확률 $\Pr(o \mid b, a)$
보상: $\rho(b, a) = \sum_{s \in \mathcal{S}} b(s) R(s, a)$

이 변환에 의해 POMDP의 최적 정책은 신뢰 상태에서 행동으로의 매핑 $\pi^*: \mathcal{B} \rightarrow \mathcal{A}$ 가 된다. 즉, 최적 정책은 현재의 불확실성 수준(신뢰 상태)에 따라 행동을 결정한다.

신뢰 MDP에 대한 벨만 최적 방정식은 다음과 같다:

$V^*(b) = \max_{a \in \mathcal{A}} \left[ \rho(b, a) + \gamma \sum_{o \in \Omega} \Pr(o \mid b, a) V^*(\tau(b, a, o)) \right]$

5. 최적 가치 함수의 구조적 특성

5.1 볼록 구분선형 성질

유한 수평 POMDP에서 최적 가치 함수 $V^*_t(b)$ 는 신뢰 상태 $b$ 에 대해 **볼록(Convex)**이고 **구분선형(Piecewise Linear)**이다. 이는 Sondik에 의해 증명된 핵심 정리이다 (Sondik, 1971).

구체적으로, 시간 단계 $t$ 에서의 최적 가치 함수는 유한 개의 선형 함수(α-벡터)의 상한으로 표현된다:

$V^*_t(b) = \max_{\alpha \in \Gamma_t} \alpha \cdot b = \max_{\alpha \in \Gamma_t} \sum_{s \in \mathcal{S}} \alpha(s) \cdot b(s)$

여기서 $\Gamma_t = \{\alpha_1, \alpha_2, \ldots, \alpha_m\}$ 은 α-벡터의 유한 집합이다. 각 α-벡터 $\alpha \in \mathbb{R}^{|\mathcal{S}|}$ 는 특정 행동 시퀀스에 대응하는 조건부 계획(Conditional Plan)의 기대 보상을 나타낸다.

이 성질은 POMDP의 정확한 해법을 위한 기초가 된다. 가치 함수를 α-벡터 집합으로 표현함으로써, 연속 신뢰 공간에서의 최적화를 유한한 벡터 연산으로 환원할 수 있다.

5.2 α-벡터의 갱신

유한 수평 문제에서 시간 단계 $t+1$ 의 α-벡터 집합 $\Gamma_{t+1}$ 로부터 시간 단계 $t$ 의 α-벡터 집합 $\Gamma_t$ 을 계산하는 벨만 백업(Bellman Backup) 연산은 다음과 같다.

각 행동 $a$ 와 관측 $o$ 에 대해 중간 α-벡터를 계산한다:

$\alpha^{a,o}_{t}(s) = R(s, a) + \gamma \sum_{s'} T(s, a, s') O(s', a, o) \alpha^{*}_{t+1}(s')$

여기서 $\alpha^{*}_{t+1}$ 은 $\Gamma_{t+1}$ 에서 신뢰 상태 $b' = \tau(b, a, o)$ 에 대해 최대값을 달성하는 α-벡터이다.

이 백업 연산의 문제점은 α-벡터의 수가 각 단계에서 $|\Gamma_{t+1}|^{|\Omega|}$ 개까지 기하급수적으로 증가할 수 있다는 것이다. 이로 인해 정확한 POMDP 해법은 중간 규모 이상의 문제에서 계산적으로 비실용적이 된다.

6. 계산 복잡도

POMDP의 최적 정책 계산은 일반적으로 매우 높은 계산 복잡도를 갖는다.

정리 (POMDP의 복잡도). 유한 수평 POMDP의 최적 정책 존재 여부를 판별하는 문제는 PSPACE-완전(PSPACE-Complete)이며, 무한 수평 할인 POMDP의 경우 비결정 가능(Undecidable)할 수 있다 (Papadimitriou & Tsitsiklis, 1987).

이러한 이론적 난이도로 인해, 실용적인 POMDP 해법은 거의 모두 근사적(Approximate) 기법에 의존한다.

7. 로봇 임무 계획에서의 POMDP 모델링

7.1 센서 불확실성의 모델링

로봇 임무 계획에서 POMDP의 주요 적용 동기는 센서의 불완전성이다. 로봇이 환경의 특정 특성(예: 목표 객체의 존재, 지형 상태, 장애물 위치)을 정확히 관측할 수 없을 때, POMDP는 센서 모델을 관측 함수 $O$ 로 명시적으로 표현한다.

예를 들어, 수색 임무에서 로봇이 구역 $i$ 에 목표 객체가 있는지 탐지하는 센서를 사용할 때:

$O(\text{목표 있음}, \text{탐색}(i), \text{탐지}) = p_d \quad (\text{탐지 확률})$
$O(\text{목표 없음}, \text{탐색}(i), \text{탐지}) = p_f \quad (\text{오경보 확률})$

여기서 $p_d$ 는 진양성(True Positive) 확률이고, $p_f$ 는 위양성(False Positive) 확률이다.

7.2 능동적 인지(Active Perception)

POMDP 기반 임무 계획의 핵심적 강점은 **정보 수집 행동(Information-Gathering Action)**을 자연스럽게 통합할 수 있다는 점이다. 로봇은 임무 수행 행동과 정보 수집 행동(센서 재배치, 추가 관측 수행, 탐사 경로 변경 등) 사이의 최적 균형을 POMDP 정책을 통해 자동으로 도출할 수 있다.

이 능력은 MDP에서는 구현하기 어려운 것이다. MDP에서는 상태가 완전히 관측되므로 정보 수집의 가치를 모델링할 수 없다. POMDP에서는 불확실성 감소(신뢰 상태의 엔트로피 감소)가 암묵적으로 더 나은 장기 보상으로 이어지므로, 최적 정책이 탐색과 활용(Exploration-Exploitation)의 균형을 자동으로 달성한다.

7.3 다중 로봇 POMDP

복수의 로봇이 부분 관측 환경에서 협력하는 문제는 분산 POMDP(Decentralized POMDP, Dec-POMDP)로 모델링된다. Dec-POMDP에서는 각 로봇이 자신의 관측만 접근 가능하며, 로봇 간 통신이 제한될 수 있다. Dec-POMDP의 최적 해법은 NEXP-완전(NEXP-Complete)으로서 단일 에이전트 POMDP보다도 계산적으로 더 어렵다 (Bernstein et al., 2002).

8. MDP와 POMDP의 비교

특성	MDP	POMDP
관측 가정	완전 관측	부분 관측
정책 입력	상태 $s$	신뢰 상태 $b$
정보 수집	모델 불가	자연스럽게 통합
해의 공간	유한 ( $m^n$ 개)	연속 (무한)
계산 복잡도	P	PSPACE-완전
실용적 해법	정확 해법 가능	근사 해법 필수

9. 적용 사례

수색 및 구조(SAR) 임무: 재난 현장에서 생존자의 위치가 불확실한 상황에서, 로봇은 POMDP 정책에 따라 탐색 구역을 선택하고, 센서 판독값에 기반하여 신뢰 상태를 갱신하며, 생존자 발견 확률을 최대화하는 최적 탐색 경로를 수행한다.

자율 탐사 임무: 미지의 환경을 탐사하는 로봇은 환경의 지도와 상태에 대한 불완전한 정보를 가지고 있다. POMDP는 탐사와 임무 수행 사이의 최적 균형을 도출하여, 환경 이해도를 높이면서 임무 목표를 달성하는 정책을 생성한다.

감시 및 추적 임무: 이동하는 목표를 추적하는 임무에서, 목표의 위치에 대한 불확실성이 존재한다. POMDP는 센서의 시야각, 탐지 범위, 장애물에 의한 차폐 등을 관측 모델에 반영하여, 목표 추적의 성공 확률을 최대화하는 정책을 도출한다.

10. 참고 문헌

Åström, K. J. (1965). “Optimal Control of Markov Processes with Incomplete State Information.” Journal of Mathematical Analysis and Applications, 10(1), pp. 174-205.
Sondik, E. J. (1971). The Optimal Control of Partially Observable Markov Decision Processes. Ph.D. Thesis, Stanford University.
Kaelbling, L. P., Littman, M. L., & Cassandra, A. R. (1998). “Planning and Acting in Partially Observable Stochastic Domains.” Artificial Intelligence, 101(1-2), pp. 99-134.
Papadimitriou, C. H. & Tsitsiklis, J. N. (1987). “The Complexity of Markov Decision Processes.” Mathematics of Operations Research, 12(3), pp. 441-450.
Bernstein, D. S., Givan, R., Immerman, N., & Zilberstein, S. (2002). “The Complexity of Decentralized Control of Markov Decision Processes.” Mathematics of Operations Research, 27(4), pp. 819-840.
Thrun, S., Burgard, W., & Fox, D. (2005). Probabilistic Robotics. MIT Press.

본 절은 POMDP의 형식적 정의, 신뢰 상태와 베이즈 갱신, 최적 가치 함수의 구조적 특성, 계산 복잡도, 및 로봇 임무 계획에서의 적용을 다루었다. v1.0