397.37 점 기반 가치 반복(Point-Based Value Iteration)

부분 관측 마르코프 결정 과정(POMDP)의 정확한 해법은 신뢰 상태 공간(belief space)의 차원이 증가함에 따라 계산 복잡도가 기하급수적으로 증가하는 근본적인 한계를 지닌다. 이러한 “차원의 저주(curse of dimensionality)“를 극복하기 위하여, 전체 신뢰 상태 공간을 탐색하는 대신 선별된 대표 신뢰 점(belief point)들의 집합에 대해서만 가치 함수를 갱신하는 방법론이 제안되었다. 이것이 바로 점 기반 가치 반복(Point-Based Value Iteration, PBVI) 기법이다.

1. 정확한 POMDP 해법의 계산적 한계

POMDP의 가치 함수는 신뢰 상태 $b \in \Delta(S)$ 위에서 정의되는 조각별 선형 볼록(Piecewise Linear and Convex, PWLC) 함수이다. 정확한 가치 반복에서는 각 반복 단계마다 $\alpha$ -벡터의 수가 기하급수적으로 증가한다. 구체적으로, 상태 공간 $|S|$ , 행동 공간 $|A|$ , 관측 공간 $|Z|$ 에 대해 $t$ 번째 반복에서의 $\alpha$ -벡터 수는 최악의 경우 다음과 같이 증가한다.

$|\Gamma_t| = |A| \cdot |\Gamma_{t-1}|^{|Z|}$

여기서 $\Gamma_t$ 는 $t$ 번째 반복에서의 $\alpha$ -벡터 집합을 나타낸다. 이와 같은 이중 지수적(doubly exponential) 증가율은 실제 로봇 임무 계획과 같이 상태 공간이 큰 문제에서는 정확한 해법의 적용을 사실상 불가능하게 만든다.

2. 점 기반 가치 반복의 핵심 아이디어

PBVI의 핵심 착안점은, 로봇이 실제로 도달할 수 있는 신뢰 상태가 전체 신뢰 심플렉스(belief simplex)의 극히 일부에 불과하다는 관측에 기반한다. 따라서 미리 선별한 유한 개의 신뢰 점 집합 $B = \{b_0, b_1, \ldots, b_q\}$ 에 대해서만 가치 함수를 갱신하면, 계산량을 대폭 절감하면서도 충분히 양호한 근사 정책을 도출할 수 있다.

PBVI에서 가치 함수는 여전히 $\alpha$ -벡터들의 집합 $\Gamma$ 로 표현되며, 임의의 신뢰 상태 $b$ 에서의 가치는 다음과 같이 계산된다.

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

그러나 정확한 해법과 달리, PBVI에서는 $\alpha$ -벡터의 수를 $|B|$ 이하로 제한한다. 각 신뢰 점 $b_i \in B$ 에 대해 가장 높은 가치를 제공하는 $\alpha$ -벡터를 하나만 유지하므로, $\alpha$ -벡터의 폭발적 증가를 억제할 수 있다.

3. PBVI 알고리즘의 수학적 형식화

3.1 백업 연산(Backup Operation)

PBVI의 핵심 연산인 백업(backup)은 각 신뢰 점 $b$ 에 대해 최적 $\alpha$ -벡터를 계산하는 과정이다. 주어진 신뢰 점 $b$ 에 대한 백업은 다음 단계로 수행된다.

단계 1: 각 행동 $a \in A$ 와 관측 $z \in Z$ 에 대해 중간 $\alpha$ -벡터 $\alpha_{a,z}$ 를 계산한다.

$\alpha_{a,z}(s) = \gamma \sum_{s' \in S} T(s, a, s') \cdot O(s', a, z) \cdot \alpha'(s')$

여기서 $\gamma$ 는 할인율(discount factor), $T(s, a, s')$ 는 상태 전이 확률, $O(s', a, z)$ 는 관측 확률이며, $\alpha'$ 는 갱신된 신뢰 상태 $b'$ 에서 최대 가치를 제공하는 이전 단계의 $\alpha$ -벡터이다. 구체적으로, $\alpha'$ 는 다음을 만족하는 벡터이다.

$\alpha' = \arg\max_{\alpha \in \Gamma_{t-1}} \sum_{s' \in S} \alpha(s') \cdot b'(s')$

여기서 갱신된 신뢰 상태는 다음과 같다.

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

$\eta$ 는 정규화 상수이다.

단계 2: 각 행동 $a$ 에 대해 관측별 $\alpha$ -벡터를 합산하고 즉각 보상을 포함한다.

$\alpha_a(s) = R(s, a) + \sum_{z \in Z} \alpha_{a,z}(s)$

여기서 $R(s, a)$ 는 상태 $s$ 에서 행동 $a$ 를 수행할 때의 즉각 보상이다.

단계 3: 주어진 신뢰 점 $b$ 에 대해 최적 행동의 $\alpha$ -벡터를 선택한다.

$\alpha_b = \arg\max_{\alpha_a} \sum_{s \in S} \alpha_a(s) \cdot b(s)$

3.2 가치 반복 루프

PBVI의 전체 가치 반복 루프는 다음과 같은 의사코드(pseudocode)로 요약된다.

알고리즘: Point-Based Value Iteration
입력: POMDP 모델 (S, A, Z, T, O, R, γ), 신뢰 점 집합 B
출력: α-벡터 집합 Γ

1. Γ₀ ← 초기 α-벡터 집합 (예: 모두 0)
2. for t = 1, 2, ..., T_max do
3.     Γₜ ← ∅
4.     for each b ∈ B do
5.         αᵦ ← backup(b, Γₜ₋₁)
6.         Γₜ ← Γₜ ∪ {αᵦ}
7.     end for
8.     if |V_{Γₜ}(b) - V_{Γₜ₋₁}(b)| < ε for all b ∈ B then
9.         수렴; 중단
10.    end if
11. end for
12. return Γₜ

4. 신뢰 점 선택 전략

PBVI의 성능은 신뢰 점 집합 $B$ 의 품질에 크게 좌우된다. 따라서, 신뢰 점을 효과적으로 선택하는 전략이 핵심적인 역할을 수행한다.

4.1 확률적 시뮬레이션 기반 확장

가장 기본적인 방법으로, 현재 정책을 따라 POMDP 환경을 시뮬레이션하면서 도달하는 신뢰 상태들을 수집하는 방식이 있다. 초기 신뢰 상태 $b_0$ 에서 출발하여 행동을 선택하고 관측을 수신하면서 신뢰 상태를 갱신해 나간다.

4.2 탐욕적 확장(Greedy Expansion)

Pineau 등(2003)이 제안한 원래의 PBVI 알고리즘에서는 기존 신뢰 점 집합 $B$ 로부터 도달 가능한 후속 신뢰 상태 중에서, 기존 점들과의 $L_1$ 거리가 가장 먼 점을 선택하여 추가하는 탐욕적 확장 전략을 사용하였다.

$b_{\text{new}} = \arg\max_{b' \in \overline{B}} \min_{b \in B} \|b' - b\|_1$

여기서 $\overline{B}$ 는 $B$ 의 각 신뢰 점에서 모든 행동-관측 조합으로 도달 가능한 후속 신뢰 상태의 집합이다. 이 방법은 신뢰 공간을 균일하게 커버하여 정책의 품질을 향상시키는 효과가 있다.

4.3 엡실론 간격 기반 확장

또 다른 전략으로, 가치 함수의 상한(upper bound)과 하한(lower bound) 사이의 간격이 가장 큰 신뢰 점을 우선적으로 추가하는 방법이 있다. 이 방법은 가치 함수의 근사 오차가 큰 영역에 집중적으로 신뢰 점을 배치함으로써 수렴 속도를 가속한다.

5. PBVI의 이론적 성질

5.1 근사 오차 한계

PBVI에서 산출된 가치 함수 $\hat{V}$ 와 최적 가치 함수 $V^*$ 사이의 오차는 신뢰 점 집합의 밀도에 의해 제한된다. 구체적으로, 신뢰 점 집합 $B$ 가 전체 신뢰 심플렉스를 $\epsilon_B$ 의 $L_1$ 거리 이내로 커버한다면, 다음이 성립한다.

$\|V^* - \hat{V}\|_\infty \leq \frac{\gamma \epsilon_B R_{\max}}{(1 - \gamma)^2}$

여기서 $R_{\max} = \max_{s,a} |R(s,a)|$ 이다. 이 부등식은 신뢰 점의 밀도를 높이면 근사 오차가 체계적으로 감소함을 보장한다.

5.2 계산 복잡도

각 백업 연산의 계산 복잡도는 $O(|A| \cdot |Z| \cdot |S|^2 \cdot |\Gamma|)$ 이며, $|\Gamma| \leq |B|$ 이므로 전체 반복당 복잡도는 $O(|B|^2 \cdot |A| \cdot |Z| \cdot |S|^2)$ 이다. 이는 정확한 해법의 이중 지수적 복잡도에 비해 현격히 낮은 다항식 복잡도를 지닌다.

6. PBVI의 확장 알고리즘

PBVI의 기본 프레임워크는 다양한 확장 알고리즘의 토대가 되었다.

6.1 Perseus

Spaan과 Vlassis(2005)가 제안한 Perseus 알고리즘은 PBVI의 효율성을 한층 향상시킨 변형이다. Perseus는 모든 신뢰 점에 대해 백업을 수행하는 대신, 가치가 개선되지 않은 신뢰 점만을 무작위로 선택하여 백업을 수행한다. 이를 통해 반복당 백업 횟수를 대폭 절감하면서도 수렴성을 보장한다. Perseus의 핵심 규칙은 다음과 같다.

$B_{\text{improve}} = \{b \in B \mid V_{\Gamma_t}(b) < V_{\Gamma_{t-1}}(b)\}$

$B_{\text{improve}}$ 가 공집합이 될 때까지 무작위로 신뢰 점을 선택하여 백업을 수행한다.

6.2 HSVI (Heuristic Search Value Iteration)

Smith와 Simmons(2004)가 제안한 HSVI는 가치 함수의 상한과 하한을 동시에 유지하면서, 두 경계의 간격이 큰 방향으로 신뢰 공간을 탐색하는 발견적 방법론이다. HSVI에서의 탐색 방향 선택은 다음 기준에 따른다.

$(a^*, z^*) = \arg\max_{a,z} P(z \mid b, a) \cdot [UB(b_{a,z}) - LB(b_{a,z})]$

여기서 $UB$ 와 $LB$ 는 각각 가치 함수의 상한과 하한을 나타내며, $b_{a,z}$ 는 행동 $a$ 후 관측 $z$ 를 받았을 때의 갱신된 신뢰 상태이다. HSVI는 전방 탐색(forward exploration)과 후방 갱신(backward update)을 교대 수행하여 효율적인 수렴을 달성한다.

6.3 SARSOP (Successive Approximations of the Reachable Space under Optimal Policies)

Kurniawati 등(2008)이 제안한 SARSOP는 최적 정책 하에서 도달 가능한 신뢰 공간의 부분집합에 탐색을 집중시킴으로써 HSVI를 더욱 효율화한 알고리즘이다. SARSOP는 최적 도달 가능 공간(optimally reachable space) $\mathcal{R}^*$ 을 점진적으로 근사하며, 이 공간 밖의 신뢰 점에 대한 불필요한 계산을 제거한다.

7. 로봇 임무 계획에서의 PBVI 적용

7.1 실내 탐색 로봇의 임무 계획

실내 환경에서 탐색 임무를 수행하는 로봇은 센서 불확실성으로 인해 자신의 정확한 위치를 알 수 없는 경우가 빈번하다. 이러한 상황에서 PBVI를 적용하면, 로봇의 위치에 대한 신뢰 상태를 기반으로 탐색 행동과 정보 수집 행동을 균형 있게 결합한 최적 정책을 도출할 수 있다. 예를 들어, 위치 불확실성이 높을 때는 랜드마크를 향해 이동하여 관측 정보를 확보하고, 불확실성이 충분히 낮아지면 목표 지점으로 직행하는 정책이 자동으로 생성된다.

7.2 다중 로봇 감시 임무

다중 로봇 감시 시스템에서는 각 로봇의 관측 범위가 제한되어 있어 침입자의 위치에 대한 부분 관측이 발생한다. PBVI 기반 접근법에서는 침입자 위치에 대한 결합 신뢰 상태를 유지하면서, 각 로봇의 순찰 경로를 최적화할 수 있다. 다만, 다중 로봇 시나리오에서는 신뢰 상태의 차원이 급격히 증가하므로, 분산 PBVI(Decentralized PBVI)나 팩토화된 신뢰 상태(factored belief) 기법과의 결합이 필요하다.

7.3 자율 수중 로봇의 임무 계획

수중 환경에서는 GPS 신호의 부재와 음향 센서의 제한된 정밀도로 인해 높은 수준의 상태 불확실성이 존재한다. PBVI를 적용한 자율 수중 로봇(AUV)의 임무 계획에서는, 수면 부상을 통한 위치 보정 행동과 해저 탐사 행동 사이의 최적 균형을 결정하는 정책을 산출할 수 있다.

8. PBVI의 한계와 개선 방향

PBVI는 POMDP의 실용적 해법으로서 혁신적인 기여를 하였으나, 다음과 같은 한계가 존재한다.

첫째, 신뢰 점 집합의 품질 의존성이 높다. 신뢰 점이 실제 도달 가능한 영역을 충분히 커버하지 못하면 정책의 품질이 저하된다. 이를 완화하기 위해 적응적 신뢰 점 선택 전략이 연구되고 있다.

둘째, 대규모 상태 공간에서의 확장성 문제가 남아 있다. $\alpha$ -벡터가 $|S|$ 차원의 벡터이므로, 상태 공간이 매우 클 경우 각 $\alpha$ -벡터의 저장 및 연산 비용이 증가한다. 이를 해결하기 위해 팩토화된 POMDP(Factored POMDP)와 PBVI의 결합이 연구되고 있다.

셋째, 연속 상태·행동·관측 공간에 대한 직접 적용이 제한적이다. 연속 공간에서는 $\alpha$ -벡터의 조각별 선형 표현이 적합하지 않으므로, 가우시안 혼합 모델(Gaussian Mixture Model) 기반의 연속 PBVI 변형이 필요하다.

9. 요약

점 기반 가치 반복(PBVI)은 POMDP의 정확한 해법이 지닌 계산적 비실용성을 극복하기 위한 핵심 근사 기법이다. 선별된 신뢰 점 집합에 대해서만 가치 함수를 갱신함으로써, $\alpha$ -벡터의 기하급수적 증가를 억제하고 다항식 수준의 계산 복잡도를 달성한다. Perseus, HSVI, SARSOP 등의 후속 알고리즘들은 PBVI의 프레임워크를 확장하여 수렴 속도와 확장성을 한층 개선하였다. 로봇 임무 계획 분야에서 PBVI는 센서 불확실성과 부분 관측 상황 하에서 정보 수집 행동과 목표 달성 행동을 균형 있게 조합하는 최적 정책을 도출하는 데 핵심적인 도구로 활용되고 있다.

10. 참고 문헌

Pineau, J., Gordon, G., & Thrun, S. (2003). “Point-based value iteration: An anytime algorithm for POMDPs.” Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp. 1025–1030.
Spaan, M. T. J., & Vlassis, N. (2005). “Perseus: Randomized point-based value iteration for POMDPs.” Journal of Artificial Intelligence Research, 24, pp. 195–220.
Smith, T., & Simmons, R. (2004). “Heuristic search value iteration for POMDPs.” Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI), pp. 520–527.
Kurniawati, H., Hsu, D., & Lee, W. S. (2008). “SARSOP: Efficient point-based POMDP planning by approximating optimally reachable belief spaces.” Robotics: Science and Systems (RSS).
Shani, G., Pineau, J., & Kaplow, R. (2013). “A survey of point-based POMDP solvers.” Autonomous Agents and Multi-Agent Systems, 27(1), pp. 1–51.

v1.0 | 로봇공학 서적 – Volume 9, Part 53, Chapter 397, Section 37