396.91 POMDP(부분 관측 마르코프 결정 과정) 기반 임무 접근

1. 개요

실제 로봇 임무 환경에서 로봇은 환경의 완전한 상태를 직접 관측할 수 없다. 센서의 잡음, 제한된 시야, 가림 현상(occlusion) 등으로 인해 환경 상태에 대한 불완전하고 불확실한 정보만이 가용하다. 부분 관측 마르코프 결정 과정(Partially Observable Markov Decision Process, POMDP)은 이러한 부분 관측성(partial observability)을 수학적으로 엄밀하게 다루는 순차적 의사 결정 프레임워크이다. 본 절에서는 POMDP의 수학적 정의, 해법 알고리즘, 그리고 로봇 임무 관리에의 적용을 체계적으로 다룬다.

2. POMDP의 수학적 정의

2.1 형식적 정의

POMDP는 다음의 7-튜플로 정의된다(Kaelbling, Littman, & Cassandra, 1998).

$\text{POMDP} = \langle \mathcal{S}, \mathcal{A}, \mathcal{O}, T, O, R, \gamma \rangle$

각 구성 요소의 정의는 다음과 같다.

$\mathcal{S}$ : 상태 공간(state space). 환경의 가능한 모든 상태의 집합이다. 임무 관리에서는 로봇 상태, 환경 상태, 임무 진행 상태를 통합한 복합 상태를 포함한다.
$\mathcal{A}$ : 행동 공간(action space). 로봇이 취할 수 있는 모든 행동의 집합이다. 임무 수준에서는 과업 전환, 경로 변경, 임무 중단 등이 포함된다.
$\mathcal{O}$ : 관측 공간(observation space). 로봇이 수신할 수 있는 모든 관측의 집합이다.
$T: \mathcal{S} \times \mathcal{A} \times \mathcal{S} \rightarrow [0, 1]$ : 상태 전이 함수. $T(s' \mid s, a) = P(s_{t+1} = s' \mid s_t = s, a_t = a)$ 로, 상태 $s$ 에서 행동 $a$ 를 취했을 때 상태 $s'$ 로 전이할 확률이다.
$O: \mathcal{S} \times \mathcal{A} \times \mathcal{O} \rightarrow [0, 1]$ : 관측 함수. $O(o \mid s', a) = P(o_{t+1} = o \mid s_{t+1} = s', a_t = a)$ 로, 행동 $a$ 를 취하고 상태 $s'$ 에 도달했을 때 관측 $o$ 를 수신할 확률이다.
$R: \mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R}$ : 보상 함수. 상태 $s$ 에서 행동 $a$ 를 취했을 때 받는 즉시 보상이다.
$\gamma \in [0, 1)$ : 할인 계수(discount factor). 미래 보상의 현재 가치를 결정한다.

2.2 신념 상태(Belief State)

POMDP에서는 실제 상태를 직접 관측할 수 없으므로, 에이전트는 상태에 대한 확률 분포인 신념 상태(belief state) $b \in \Delta(\mathcal{S})$ 를 유지한다. 신념 상태 $b(s)$ 는 현재 상태가 $s$ 일 확률을 나타낸다.

초기 신념 $b_0$ 로부터 출발하여, 행동 $a$ 를 취하고 관측 $o$ 를 수신한 후의 신념 갱신은 베이즈 규칙에 의해 다음과 같이 수행된다.

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

여기서 $\eta$ 는 정규화 상수로, $b'$ 이 확률 분포를 형성하도록 보장한다.

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

이 갱신 과정을 바우만-베이즈 필터(Bayesian belief update)라 하며, 이를 함수로 표기하면 $b' = \tau(b, a, o)$ 이다.

2.3 신념 MDP로의 환원

Åström(1965)은 POMDP가 신념 공간(belief space) 위의 (완전 관측) MDP로 환원될 수 있음을 증명하였다. 이 신념 MDP는 다음과 같이 정의된다.

$\text{Belief MDP} = \langle \Delta(\mathcal{S}), \mathcal{A}, T_b, R_b, \gamma \rangle$

여기서 $T_b$ 는 신념 상태의 전이 함수이고, $R_b(b, a) = \sum_{s \in \mathcal{S}} R(s, a) \cdot b(s)$ 는 신념 상태에서의 기대 보상이다. 최적 정책 $\pi^*: \Delta(\mathcal{S}) \rightarrow \mathcal{A}$ 는 이 신념 MDP의 최적 정책에 해당한다.

3. 최적 가치 함수와 정책

3.1 벨만 방정식

POMDP의 최적 가치 함수 $V^*(b)$ 는 다음의 벨만 방정식(Bellman equation)을 만족한다.

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

여기서 $P(o \mid b, a) = \sum_{s' \in \mathcal{S}} O(o \mid s', a) \sum_{s \in \mathcal{S}} T(s' \mid s, a) \cdot b(s)$ 는 신념 $b$ 에서 행동 $a$ 를 취했을 때 관측 $o$ 를 수신할 확률이다.

3.2 가치 함수의 조각적 선형 볼록 구조

유한 지평(finite horizon) POMDP에서 최적 가치 함수는 조각적 선형 볼록(piecewise linear and convex, PWLC) 함수임이 알려져 있다(Smallwood & Sondik, 1973). 즉, 가치 함수는 유한 개의 $\alpha$ -벡터(alpha vector)의 집합 $\Gamma = \{\alpha_1, \alpha_2, \ldots, \alpha_m\}$ 으로 표현되며, 각 신념 $b$ 에서의 가치는 다음과 같다.

$V(b) = \max_{\alpha \in \Gamma} \sum_{s \in \mathcal{S}} \alpha(s) \cdot b(s) = \max_{\alpha \in \Gamma} \alpha \cdot b$

각 $\alpha$ -벡터는 특정 행동과 대응되며, 이를 통해 신념 공간의 각 영역에서 최적 행동이 결정된다.

4. POMDP 해법 알고리즘

4.1 정확 해법(Exact Algorithms)

가치 반복(Value Iteration): Sondik(1971)이 제안한 기본 알고리즘으로, $\alpha$ -벡터 집합을 반복적으로 갱신하여 최적 가치 함수에 수렴시킨다. 그러나 $\alpha$ -벡터의 수가 반복마다 기하급수적으로 증가하여, 실용적 규모의 문제에는 적용이 어렵다.
Incremental Pruning: Cassandra, Littman, Zhang(1997)이 제안한 알고리즘으로, 가치 반복 과정에서 불필요한 $\alpha$ -벡터를 즉시 제거하여 계산 효율을 개선한다.
Witness Algorithm: 기하학적 성질을 활용하여 $\alpha$ -벡터의 생성과 제거를 효율적으로 수행한다.

4.2 근사 해법(Approximate Algorithms)

POMDP의 정확한 최적 해를 구하는 것은 PSPACE-complete 문제로 알려져 있다(Papadimitriou & Tsitsiklis, 1987). 따라서 실용적 규모의 임무 관리 문제에는 근사 해법이 필수적이다.

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

Pineau, Gordon, Thrun(2003)이 제안한 PBVI는 전체 신념 공간 대신 유한 개의 대표 신념 점(representative belief point)에서만 가치 갱신을 수행한다. $B = \{b_1, b_2, \ldots, b_q\}$ 를 대표 신념 집합이라 하면, 갱신 규칙은 다음과 같다.

$\alpha_a^{b_i}(s) = R(s, a) + \gamma \sum_{o \in \mathcal{O}} \max_{\alpha' \in \Gamma} \sum_{s' \in \mathcal{S}} O(o \mid s', a) \cdot T(s' \mid s, a) \cdot \alpha'(s')$

PBVI는 정확 해법 대비 시간 복잡도를 $O(|\mathcal{S}|^2 |\mathcal{A}| |\mathcal{O}| |B|)$ 로 감소시키며, 중간 규모의 POMDP에 효과적이다.

4.2.2 SARSOP

Kurniawati, Hsu, Lee(2008)가 제안한 SARSOP(Successive Approximations of the Reachable Space under Optimal Policies)은 최적 정책 하에서 도달 가능한 신념 공간 영역에 집중하여 탐색 효율을 극대화한다. 상한(upper bound)과 하한(lower bound)의 교차 갱신을 통해 근사 해의 품질을 점진적으로 개선한다.

4.2.3 DESPOT

Ye, Somani, Hsu, Lee(2017)가 제안한 DESPOT(Determinized Sparse Partially Observable Tree)은 온라인 계획 알고리즘으로, 임의로 샘플링된 시나리오(scenario)에 기반한 희소 트리(sparse tree)를 구성하여 현재 신념에서의 최적 행동을 근사한다. 실시간성이 요구되는 로봇 임무 관리에 적합하다.

4.2.4 Monte Carlo Tree Search 기반 접근

POMCP(Partially Observable Monte Carlo Planning)는 Silver와 Veness(2010)가 제안한 알고리즘으로, UCT(Upper Confidence Bounds applied to Trees) 방법을 POMDP에 확장한다. 파티클 필터를 활용하여 신념 상태를 근사하고, 몬테카를로 시뮬레이션을 통해 행동의 가치를 추정한다.

5. 로봇 임무 관리에의 POMDP 적용

5.1 임무 계획에의 적용

POMDP를 임무 계획에 적용할 때, 상태 공간은 환경의 불확실한 요소(표적 위치, 장애물 분포, 통신 상태 등)와 임무 진행 상태의 곱 공간으로 구성된다. 행동 공간에는 이동, 탐색, 관측, 통신, 대기, 복귀 등의 임무 수준 행동이 포함된다.

탐색-구조 임무 예시: 재난 환경에서 생존자의 위치가 불확실한 상황을 고려하자. 상태 공간은 로봇의 위치와 각 영역의 생존자 존재 여부의 곱으로 정의되고, 관측 모델은 센서의 탐지 확률과 오경보 확률로 정의된다. POMDP 정책은 탐지 확률이 높은 영역을 우선 탐색하면서, 관측 결과에 따라 신념을 갱신하고 탐색 전략을 적응적으로 변경한다.

5.2 임무 모니터링에의 적용

임무 수행 중 환경 변화나 로봇의 상태 저하를 감지하는 과정에 POMDP를 적용할 수 있다. 이 경우 상태는 “정상 운용”, “경미한 이상”, “중대한 장애” 등의 임무 건강 상태를 포함하며, 관측은 센서 판독값과 진단 데이터로 구성된다. POMDP 정책은 관측 결과에 따라 추가 진단, 임무 계속, 임무 중단 등의 결정을 내린다.

5.3 정보 수집과 능동 인식

POMDP의 핵심적 강점 중 하나는 정보 수집 행동의 가치를 자동으로 추론한다는 점이다. 불확실성이 높은 상태에서 관측 행동(센서 조향, 접근 관찰 등)을 취하면 신념의 불확실성이 감소하고, 이후 더 나은 의사 결정이 가능해진다. 이러한 장기적 정보 가치(value of information)는 POMDP의 가치 함수에 내재적으로 반영된다.

6. POMDP의 확장과 변형

6.1 연속 공간 POMDP

실제 로봇 임무에서는 상태, 행동, 관측이 연속 공간인 경우가 대부분이다. 연속 공간 POMDP의 해법으로 가우시안 과정(Gaussian Process) 기반 근사, 점 기반 방법의 연속 확장, 그리고 심층 강화 학습(Deep Reinforcement Learning) 기반 접근이 연구되고 있다.

6.2 분산형 POMDP(Dec-POMDP)

다중 로봇 시스템에서 각 로봇이 부분적이고 상이한 관측을 수행하는 경우, 분산형 POMDP(Decentralized POMDP, Dec-POMDP)가 적용된다(Bernstein, Givan, Immerman, & Zilberstein, 2002). Dec-POMDP는 $\langle \mathcal{I}, \mathcal{S}, \{\mathcal{A}_i\}, \{\mathcal{O}_i\}, T, O, R, \gamma \rangle$ 로 정의되며, $\mathcal{I}$ 는 에이전트 집합이다. Dec-POMDP의 최적 해를 구하는 것은 NEXP-complete 문제로, 단일 에이전트 POMDP보다 훨씬 높은 계산 복잡도를 갖는다.

6.3 제약 조건 기반 POMDP(Constrained POMDP)

임무 관리에서는 누적 보상의 최대화 외에, 안전 제약(예: 충돌 확률 상한), 자원 제약(예: 에너지 소비 상한) 등의 부가적 제약 조건이 존재한다. 제약 조건 기반 POMDP(Constrained POMDP, C-POMDP)는 이러한 제약을 형식적으로 다룬다(Undurti & How, 2010).

$\max_\pi \quad V^\pi(b_0) \quad \text{subject to} \quad C_k^\pi(b_0) \leq c_k, \quad k = 1, \ldots, K$

여기서 $C_k^\pi(b_0)$ 는 정책 $\pi$ 하에서 $k$ 번째 제약 지표의 누적 기대값이다.

7. 실용적 구현 고려사항

7.1 상태 공간 축소

POMDP의 계산 복잡도는 상태 공간의 크기에 민감하다. 임무 관리 수준에서의 적용을 위해서는 저수준 연속 상태를 추상화하여 유한하고 관리 가능한 크기의 상태 공간을 설계하는 것이 중요하다. 상태 압축(state aggregation), 특징 기반 상태 표현(feature-based state representation), 계층적 추상화(hierarchical abstraction) 등이 활용된다.

7.2 온라인 계획과 실시간 실행

로봇 임무 관리에서는 사전에 완전한 정책을 계산하기 어려운 경우가 많다. 온라인 계획(online planning) 접근법은 현재 신념에서 제한된 미래 지평에 대해서만 계획을 수립하고, 새로운 관측이 들어올 때마다 계획을 갱신한다. DESPOT, POMCP 등의 온라인 알고리즘이 이 맥락에서 활용된다.

7.3 모델 학습

POMDP의 전이 함수 $T$ , 관측 함수 $O$ , 보상 함수 $R$ 은 사전에 정확히 알려져 있지 않은 경우가 많다. 베이즈 강화 학습(Bayesian Reinforcement Learning)이나 모델 기반 강화 학습(Model-Based RL)을 통해 실제 운용 데이터로부터 POMDP 모델을 학습하는 연구가 진행되고 있다.

8. 참고 문헌

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.
Åström, K. J. (1965). “Optimal Control of Markov Processes with Incomplete State Information.” Journal of Mathematical Analysis and Applications, 10(1), 174–205.
Smallwood, R. D., & Sondik, E. J. (1973). “The Optimal Control of Partially Observable Markov Processes over a Finite Horizon.” Operations Research, 21(5), 1071–1088.
Pineau, J., Gordon, G., & Thrun, S. (2003). “Point-Based Value Iteration: An Anytime Algorithm for POMDPs.” Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI), 1025–1030.
Kurniawati, H., Hsu, D., & Lee, W. S. (2008). “SARSOP: Efficient Point-Based POMDP Planning by Approximating Optimally Reachable Belief Spaces.” Proceedings of Robotics: Science and Systems (RSS).
Silver, D., & Veness, J. (2010). “Monte-Carlo Planning in Large POMDPs.” Advances in Neural Information Processing Systems (NeurIPS), 23, 2164–2172.
Ye, N., Somani, A., Hsu, D., & Lee, W. S. (2017). “DESPOT: Online POMDP Planning with Regularization.” Journal of Artificial Intelligence Research, 58, 231–266.
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), 819–840.
Papadimitriou, C. H., & Tsitsiklis, J. N. (1987). “The Complexity of Markov Decision Processes.” Mathematics of Operations Research, 12(3), 441–450.

본 절의 내용은 2025년 기준 POMDP 이론과 로봇 임무 관리 적용의 연구 동향을 반영하였다.