8.96 부분 관측 마르코프 결정 과정(POMDP)의 기초

1. POMDP의 정의

부분 관측 마르코프 결정 과정(Partially Observable Markov Decision Process, POMDP)은 상태가 직접 관측되지 않고 센서 관측을 통해 부분적으로만 추론되는 상황에서의 순차적 의사 결정 프레임워크이다. 완전 관측 가능한 MDP의 확장으로, 로봇 공학의 현실적 불확실성을 반영한다.

2. POMDP의 구성 요소

POMDP는 튜플 $(\mathcal{S}, \mathcal{A}, \mathcal{O}, P, O, R, \gamma)$ 로 기술된다.

상태 집합 $\mathcal{S}$ : 관측되지 않는 시스템 상태
행동 집합 $\mathcal{A}$ : 에이전트가 선택 가능한 행동
관측 집합 $\mathcal{O}$ : 에이전트가 수신하는 관측
전이 확률 $P(s' \vert s, a)$ : 상태 전이 모델
관측 확률 $O(o \vert s', a)$ : 새 상태에서의 관측 모델
보상 함수 $R(s, a)$ 또는 $R(s, a, s')$
할인 인자 $\gamma \in [0, 1)$

3. 믿음 상태(Belief State)

에이전트는 현재 상태를 직접 알 수 없으므로, 상태에 대한 확률 분포 $b(s)$ 를 유지한다. 이를 믿음 상태라 한다.

$b_t(s) = P(s_t = s \vert o_1, a_1, o_2, a_2, \ldots, a_{t-1}, o_t)$

믿음은 POMDP에서 “완전한 과거 이력의 충분 통계량“으로, 최적 의사 결정에 필요한 모든 정보를 담고 있다.

4. 믿음 갱신

행동 $a$ 를 수행하고 관측 $o$ 를 받은 후 믿음이 갱신된다(베이즈 필터).

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

여기서 $\eta$ 는 정규화 상수이다. 이 갱신 규칙을 $b' = \tau(b, a, o)$ 로 표기한다.

5. 가치 함수

5.1 믿음 가치 함수

믿음 상태에서의 기대 누적 보상:

$V^\pi(b) = \mathbb{E}^\pi\left[\sum_{t=0}^{\infty}\gamma^t R(s_t, a_t) \bigg\vert b_0 = b\right]$

5.2 벨만 최적 방정식

$V^*(b) = \max_{a \in \mathcal{A}}\left[R(b, a) + \gamma \sum_{o \in \mathcal{O}}P(o \vert b, a)V^*(\tau(b, a, o))\right]$

여기서 $R(b, a) = \sum_s b(s)R(s, a)$ 는 믿음 상태에서의 기대 보상이다.

6. 가치 함수의 구조

6.1 유한 지평 가치 함수의 볼록성

POMDP의 유한 지평 가치 함수는 믿음 공간에서 구분적 선형 볼록(piecewise-linear convex, PWLC) 함수이다.

$V(b) = \max_\alpha \sum_s \alpha(s)b(s)$

이 성질은 소도닉(Sondik)에 의해 증명되었으며, 효율적 알고리즘의 이론적 기반이다.

6.2 $\alpha$ -벡터

가치 함수는 $\alpha$ -벡터의 집합 $\Gamma = \{\alpha_1, \alpha_2, \ldots\}$ 으로 표현된다. 각 $\alpha$ 벡터는 특정 정책 조각에 해당한다.

$V(b) = \max_{\alpha \in \Gamma}\alpha^T b$

7. POMDP의 복잡도

유한 지평 POMDP의 최적 정책 계산은 PSPACE-완전 문제이다. 무한 지평 POMDP는 일반적으로 계산 불가능하다. 이러한 계산적 난이성 때문에 실용적 해법은 근사에 의존한다.

8. 대표적 알고리즘

8.1 정확 알고리즘

작은 POMDP에 대한 정확 해법으로 증분 가지치기(Incremental Pruning), Witness 알고리즘 등이 있다. 매 반복에서 $\alpha$ -벡터 집합을 생성하고 지배되는 벡터를 제거한다.

8.2 점 기반 가치 반복(Point-Based Value Iteration, PBVI)

대표적인 믿음 집합 $B = \{b_1, b_2, \ldots, b_N\}$ 에서 가치 함수를 유지한다. 각 믿음에서 $\alpha$ -벡터를 갱신하여 근사 가치 함수를 구성한다. PBVI, Perseus, HSVI, SARSOP 등의 변형이 있다.

8.3 온라인 POMDP 해법

실시간으로 현재 믿음에서 행동을 결정하는 방법이다.

POMCP(Partially Observable Monte Carlo Planning): 몬테카를로 트리 탐색을 POMDP에 적용한다.

DESPAT: 확정적 샘플링을 이용한 효율적 온라인 해법이다.

9. 로봇 공학에서의 POMDP 응용

9.1 이동 로봇의 위치 추정 및 계획

위치가 불확실한 로봇이 목표에 도달하기 위한 행동 결정이다. 믿음 상태가 위치 분포이며, 행동이 정보 이득과 목표 접근을 균형 있게 추구한다.

9.2 탐색 및 추적

표적이 이동하고 관측이 잡음을 포함하는 환경에서의 표적 추적. POMDP는 정보 수집(관측)과 표적 접근(추적)을 동시에 최적화한다.

9.3 조작(Manipulation)

물체의 자세가 불확실한 파지 문제에서 POMDP는 촉각 관측에 의한 믿음 갱신과 파지 행동의 최적화를 프레임워크로 제공한다.

9.4 인간-로봇 상호 작용

인간의 의도나 선호를 직접 관측할 수 없는 상황에서, 인간 상태를 숨겨진 변수로 모델링하고 행동(질문, 시연 요청 등)으로 정보를 수집한다.

10. 참고 문헌

Kaelbling, L. P., Littman, M. L., & Cassandra, A. R. (1998). “Planning and Acting in Partially Observable Stochastic Domains.” Artificial Intelligence, 101(1-2), 99–134.
Pineau, J., Gordon, G., & Thrun, S. (2003). “Point-Based Value Iteration: An Anytime Algorithm for POMDPs.” Proceedings of IJCAI, 1025–1032.
Silver, D., & Veness, J. (2010). “Monte-Carlo Planning in Large POMDPs.” Advances in Neural Information Processing Systems (NeurIPS), 23.
Kochenderfer, M. J. (2015). Decision Making Under Uncertainty: Theory and Application. MIT Press.

version: 1.0