397.36 POMDP 근사 해법 알고리즘

1. 개요

POMDP의 정확한 해법은 최적 가치 함수의 α-벡터 집합이 수평 길이에 대해 이중 기하급수적으로 증가하는 문제로 인해 중간 규모 이상의 문제에서 계산적으로 비실용적이다. 이에 따라 POMDP 분야의 연구는 근사 해법(Approximate Solution) 알고리즘의 개발에 집중되어 왔다. 본 절에서는 POMDP의 주요 근사 해법 알고리즘을 분류하고, 각 기법의 원리, 수학적 기초, 성능 특성, 및 로봇 임무 계획에서의 적용 가능성을 다룬다.

POMDP 근사 해법은 크게 오프라인(Offline) 기법과 온라인(Online) 기법으로 분류된다. 오프라인 기법은 실행 전에 전체 신뢰 공간에 대한 정책을 사전 계산하며, 온라인 기법은 현재 신뢰 상태에서 실시간으로 최적 행동을 탐색한다.

2. 정확 해법의 한계

2.1 Monahan의 열거 알고리즘

Monahan의 열거(Enumeration) 알고리즘은 POMDP의 정확한 해법 중 가장 기본적인 형태이다 (Monahan, 1982). 각 시간 단계에서 가능한 모든 조건부 계획(Conditional Plan)에 대응하는 α-벡터를 열거하고, 지배(Dominated)되는 α-벡터를 가지치기(Pruning)한다.

그러나 잔여 시간 t에서의 α-벡터 수의 상한은:

|\Gamma_t| \leq |\mathcal{A}| \cdot |\Gamma_{t-1}|^{|\Omega|}

이므로, 가지치기 없이는 |\Gamma_t| = O(|\mathcal{A}|^{(|\Omega|^t - 1)/(|\Omega| - 1)})으로 이중 지수적 증가를 보인다. 가지치기를 적용하더라도 α-벡터의 수가 관리 불가능할 정도로 증가하는 경우가 대부분이다.

2.2 Incremental Pruning

Cassandra, Littman, Zhang이 제안한 점증적 가지치기(Incremental Pruning) 알고리즘은 α-벡터의 교차곱을 점진적으로 수행하면서 각 단계에서 지배 벡터를 제거하여 α-벡터 집합의 크기를 최소화한다 (Cassandra et al., 1997). 이 기법은 정확한 해법 중 가장 효율적이지만, 여전히 중규모 이상의 문제에서는 적용이 제한적이다.

3. 오프라인 근사 해법

3.1 격자 기반 근사(Grid-Based Approximation)

신뢰 공간 \Delta^{n-1}에 유한 개의 격자점(Grid Points)을 배치하고, 이 점들에서만 가치 함수를 계산하여 근사하는 기법이다. Lovejoy가 제안한 고정 격자(Fixed Grid) 기법이 초기 연구에 해당한다 (Lovejoy, 1991).

격자점 집합 B = \{b^1, b^2, \ldots, b^K\}에 대해 근사 가치 함수를 계산한 후, 임의의 신뢰 상태 b에서의 가치는 보간(Interpolation)으로 추정한다:

\tilde{V}(b) \approx \sum_{i=1}^{K} w_i(b) \cdot V(b^i)

여기서 w_i(b)는 보간 가중치이다.

격자 기반 근사의 주요 문제는 격자점의 수가 상태 공간 차원에 대해 기하급수적으로 증가하는 **차원의 저주(Curse of Dimensionality)**이다. 이에 따라 불규칙 격자(Irregular Grid)나 적응적 격자(Adaptive Grid) 기법이 연구되었다.

3.2 QMDP 근사

QMDP는 가장 단순한 POMDP 근사 해법 중 하나로, 완전 관측 MDP의 Q-함수(Q_{\text{MDP}}^*)를 사용하여 POMDP의 가치 함수를 근사한다 (Littman et al., 1995):

\tilde{V}(b) = \max_{a \in \mathcal{A}} \sum_{s \in \mathcal{S}} b(s) \cdot Q_{\text{MDP}}^*(s, a)

QMDP는 다음 단계에서 불확실성이 즉시 해소된다는 낙관적(Optimistic) 가정에 기초한다. 따라서 정보 수집 행동의 가치를 과소평가하며, 능동적 인지(Active Perception)가 필요한 문제에서는 성능이 저하된다. 그러나 계산 비용이 MDP 해법과 동일한 수준이므로, 불확실성이 크지 않거나 정보 수집이 중요하지 않은 문제에서 효과적인 기준선(Baseline)으로 활용된다.

3.3 FIB(Fast Informed Bound)

Hauskrecht가 제안한 FIB는 QMDP를 개선한 상한 근사(Upper Bound Approximation) 기법이다 (Hauskrecht, 2000). 관측에 의한 정보 분리를 부분적으로 반영하여 QMDP보다 더 강건한(Tighter) 상한을 제공한다:

\alpha_{\text{FIB}}^a(s) = R(s, a) + \gamma \max_{a'} \sum_{o} \max_{\alpha' \in \Gamma} \sum_{s'} T(s, a, s') O(s', a, o) \alpha'(s')

FIB는 단일 벨만 백업으로 α-벡터 집합을 생성하며, QMDP보다 정확하면서도 계산 비용이 관리 가능한 수준이다.

3.4 정책 그래프(Policy Graph) 기반 기법

정책 그래프 기법은 유한 상태 제어기(Finite-State Controller, FSC)로 POMDP 정책을 표현한다. 제어기는 유한 개의 내부 노드를 가지며, 각 노드는 행동을 지정하고, 관측에 따라 다음 노드로 전이한다.

N-노드 FSC \pi_{\text{FSC}} = \langle \mathcal{N}, \psi, \eta \rangle는 다음으로 구성된다:

• \mathcal{N} = \{n_1, \ldots, n_N\}: 내부 노드 집합
• \psi: \mathcal{N} \rightarrow \mathcal{A}: 노드-행동 매핑
• \eta: \mathcal{N} \times \Omega \rightarrow \mathcal{N}: 노드-관측-전이 매핑

FSC의 노드 수 N을 제한함으로써 정책의 복잡도를 제어할 수 있다. Poupart와 Boutilier의 유계 정책 반복(Bounded Policy Iteration) 기법은 FSC 기반 정책을 반복적으로 개선한다 (Poupart & Boutilier, 2004).

4. 온라인 근사 해법

4.1 전방 탐색(Forward Search) 기법

온라인 기법은 현재 신뢰 상태 b_t로부터 유한 깊이의 탐색 트리를 구성하여 최적 행동을 선택한다. 탐색 트리의 각 노드는 신뢰 상태에 대응하며, 분기는 행동과 관측에 의해 결정된다.

깊이 d의 전방 탐색에서 신뢰 상태 b의 근사 가치는:

\tilde{V}_d(b) = \begin{cases} h_{\text{base}}(b) & \text{if } d = 0 \\ \max_{a} \left[ \rho(b, a) + \gamma \sum_{o} \Pr(o \mid b, a) \tilde{V}_{d-1}(\tau(b, a, o)) \right] & \text{if } d > 0 \end{cases}

여기서 h_{\text{base}}(b)는 기저 휴리스틱(Base Heuristic)으로, QMDP 값이나 하한(Lower Bound) 추정치를 사용한다.

탐색 트리의 크기는 (|\mathcal{A}| \cdot |\Omega|)^d로 깊이에 대해 기하급수적으로 증가하므로, 효율적인 가지치기와 분기 선택 전략이 필요하다.

4.2 POMCP(Partially Observable Monte Carlo Planning)

Silver와 Veness가 제안한 POMCP는 몬테카를로 트리 탐색(Monte Carlo Tree Search, MCTS)을 POMDP에 확장한 온라인 기법이다 (Silver & Veness, 2010). POMCP의 핵심 아이디어는 신뢰 상태를 명시적 확률 분포가 아닌 **파티클 집합(Particle Collection)**으로 표현하는 것이다.

POMCP의 주요 구성 요소:

1. 파티클 신뢰 표현: 신뢰 상태를 K개의 상태 샘플(파티클) \{s^{(1)}, s^{(2)}, \ldots, s^{(K)}\}으로 근사한다.
2. UCB1 기반 행동 선택: 탐색 트리의 각 노드에서 UCB1(Upper Confidence Bounds) 공식을 사용하여 탐색-활용 균형을 달성한다:
   a^* = \arg\max_a \left[ Q(h, a) + c \sqrt{\frac{\log N(h)}{N(h, a)}} \right]
   여기서 Q(h, a)는 이력 h에서 행동 a의 추정 가치, N(h)는 노드 h의 방문 횟수, c는 탐색 상수이다.
3. 롤아웃(Rollout): 리프 노드에서 무작위 정책 또는 휴리스틱 정책으로 시뮬레이션을 수행하여 가치를 추정한다.
4. 파티클 필터링: 관측에 기반하여 파티클을 재가중(Re-weighting)하고 리샘플링(Resampling)한다.

POMCP는 신뢰 상태의 명시적 계산 없이 대규모 POMDP를 처리할 수 있으며, 샘플 수 증가에 따라 최적 행동으로 수렴함이 보장된다.

4.3 DESPOT(Determinized Sparse Partially Observable Tree)

Ye, Somani, Hsu, Lee가 제안한 DESPOT은 확정화된(Determinized) 시나리오를 사용하여 탐색 트리를 효율적으로 구성하는 온라인 기법이다 (Ye et al., 2017). DESPOT은 K개의 무작위 시나리오(전이와 관측의 실현값 시퀀스)를 사전 샘플링하고, 이 시나리오들에 대해서만 탐색 트리를 구성한다.

DESPOT의 핵심 성질:

1. 희소 트리(Sparse Tree): K개의 시나리오로 제한하여 탐색 트리의 크기를 O(K \cdot d)로 제어한다.
2. α-벡터 상한과 하한: 정확한 가치의 상한(Upper Bound)과 하한(Lower Bound)을 유지하여 가지치기를 수행한다.
3. 정칙화(Regularization): 정책의 복잡도에 대한 벌칙항을 추가하여 과적합을 방지한다.

4.4 ABT(Adaptive Belief Tree)

Kurniawati가 개발한 ABT는 온라인 기법의 실시간 적응 능력과 오프라인 기법의 해 품질을 결합한 하이브리드 기법이다. ABT는 신뢰 트리를 점진적으로 구축하면서, 새로운 관측에 따라 트리를 동적으로 갱신한다. 이 기법은 환경이 시간에 따라 변하는 비정상(Non-Stationary) POMDP에 특히 적합하다.

5. 주요 POMDP 근사 해법의 비교

6. 로봇 임무 계획에서의 선택 지침

로봇 임무 계획에서 POMDP 근사 해법의 선택은 문제의 특성에 따라 달라진다:

1. 소규모 상태 공간 + 정확한 해 필요: Incremental Pruning 또는 SARSOP
2. 중규모 상태 공간 + 오프라인 계산 가능: PBVI, PERSEUS, SARSOP
3. 대규모 상태 공간 + 실시간 의사 결정: POMCP, DESPOT
4. 불확실성이 크지 않은 경우: QMDP (기준선)
5. 비정상 환경: ABT 또는 온라인 기법

7. 참고 문헌

• Monahan, G. E. (1982). “A Survey of Partially Observable Markov Decision Processes: Theory, Models, and Algorithms.” Management Science, 28(1), pp. 1-16.
• Cassandra, A. R., Littman, M. L., & Zhang, N. L. (1997). “Incremental Pruning: A Simple, Fast, Exact Method for Partially Observable Markov Decision Processes.” Proceedings of the 13th Conference on Uncertainty in Artificial Intelligence (UAI-97), pp. 54-61.
• Lovejoy, W. S. (1991). “Computationally Feasible Bounds for Partially Observed Markov Decision Processes.” Operations Research, 39(1), pp. 162-175.
• Littman, M. L., Cassandra, A. R., & Kaelbling, L. P. (1995). “Learning Policies for Partially Observable Environments: Scaling Up.” Proceedings of the 12th International Conference on Machine Learning (ICML-95), pp. 362-370.
• Hauskrecht, M. (2000). “Value-Function Approximations for Partially Observable Markov Decision Processes.” Journal of Artificial Intelligence Research, 13, pp. 33-94.
• Poupart, P. & Boutilier, C. (2004). “Bounded Finite State Controllers.” Advances in Neural Information Processing Systems (NeurIPS) 16.
• Silver, D. & Veness, J. (2010). “Monte-Carlo Planning in Large POMDPs.” Advances in Neural Information Processing Systems (NeurIPS) 23, pp. 2164-2172.
• Ye, N., Somani, A., Hsu, D., & Lee, W. S. (2017). “DESPOT: Online POMDP Planning with Regularization.” Journal of Artificial Intelligence Research, 58, pp. 231-266.

본 절은 POMDP의 주요 근사 해법 알고리즘을 오프라인과 온라인 기법으로 분류하고, 각 기법의 원리, 성능 특성, 및 로봇 임무 계획에서의 선택 지침을 다루었다. v1.0