기술 요약: 부분 관측 가능 마르코프 결정 과정(POMDP) 및 로보틱스

1. 문제 정의

본 논문은 로보틱스에서 불확inc성 하의 계획 수립(planning under uncertainty)이라는 핵심적인 과제를 다룹니다. 자율 로봇은 액추에이터 오류로 인한 행동의 비결정론적 효과(non-deterministic effects)와 센서 노이즈 및 인지 한계로 인한 상태의 부분 관측 가능성에도 불구하고 전략적인 결정을 내려야 합니다. 이러한 시나리오에서 로봇은 자신의 정확한 상태를 결코 알 수 없으며, 행동과 관측의 이력(history)으로부터 이를 추론해야 합니다.

**부분 관측 가능 마르코프 결정 과정(POMDP)**은 이러한 문제를 모델링하기 위한 수학적으로 원칙적인 프레임워크로 식별됩니다. POMDP는 상태 공간(S), 행동 공간(A), 관측 공간(O), 전이 함수(T), 관측 함수(Z), 보상 함수(R)를 나타내는 튜플 $\langle S, A, O, T, Z, R \rangle$로 정의됩니다. 에이전트는 단일 상태가 아닌 상태에 대한 확률 분포인 신념(belief) $b$를 유지합니다. 목표는 기대 총 할인 보상(expected total discounted reward)을 최대화하는 최적 정책 $\pi^*: B \to A$를 찾는 것입니다.

핵심 과제: 이론적으로는 견고하지만, POMDP에 대한 정확한 최적해를 계산하는 것은 PSPACE-hard입니다. 역사적으로 이러한 계산적 난해함은 POMDP를 로보틱스에 적용하는 데 실용적이지 못하게 만들었습니다. 벤치마크 문제들이 30개 미만의 상태로 제한되었고 해결에 수 시간이 소요되었던 반면, 실제 로보틱스는 실시간 성능과 수천 개의 상태로의 확장성을 요구하기 때문입니다.

2. 방법론: 샘플링 기반 근사 솔버(Sampling-Based Approximate Solvers)

본 논문은 정확한 솔버에서 샘플링 기반 근사 솔버로의 전환을 검토하며, 이러한 방법들이 POMDP를 로보틱스에서 실용적으로 만들었음을 설명합니다. 이러한 방법들은 전역적 최적성(global optimality) 요구 사항을 완화하는 대신, 합리적인 계산 자원 내에서 "좋은" 정책을 계산하는 데 집중합니다.

2.1 일반적 접근 방식

샘플링 기반 솔버는 전체 신념 공간 대신 대표적인 신념(representative beliefs) 집합으로 문제를 제한합니다. 이들은 일반적으로 다음과 같은 프로그램 스켈레톤을 따릅니다:

1. 샘플링(Sampling): 일련의 신념들을 선택합니다 (종종 초기 신념 $b_0$로부터 시작).
2. 추정(Estimation): 휴리스틱과 백업 연산을 사용하여 이러한 샘플링된 신념들의 가치를 추정합니다.
3. 업데이트(Update): 이러한 추정치를 바탕으로 정책 $\pi$를 반복적으로 업데이트합니다.
4. 종료(Termination): 시간 제한에 도달하거나 수렴 임계값에 도달하면 중단합니다.

이러한 솔버들은 오프라인(실행 전 정책 계산) 또는 온라인(정책 계산과 실행을 교차 수행)으로 분류됩니다.

2.2 특정 계산 장벽 해결

본 논문은 특정 샘플링 기법들이 다섯 가지 주요 장애물을 어떻게 완화하는지 상세히 설명합니다.

• 거대 상태 공간 (차원의 저주):

  • 점 기반 가치 반복(Point-Based Value Iteration, PBVI): $b_0$로부터 도달 가능한 신념들을 샘플링하고, 이 지점들에 대해서만 백업을 수행하여 $\alpha$-벡터를 통해 가치 함수를 표현합니다.
  • Perseus: 샘플링된 신념의 부분 집합에 대해 백업을 수행함으로써 효율성을 높입니다.
  • HSVI2 & SARSOP: 상한(upper bound)과 하한(lower bound)을 사용하여 샘플링을 유도합니다. 특히 SARSOP는 최적 정책($R^*$) 하에서 도달 가능한 신념 집합을 샘플링하여, 계산 노력을 관련 있는 영역에 집중하기 위해 부적절한 브랜치를 가지치기(pruning)합니다.
  • 연속 공간: MCVI 및 GCS와 같은 방법은 정책 그래프나 클러스터 샘플링을 사용하여 이러한 개념을 연속 공간으로 확장합니다.

• 긴 계획 지평 (역사의 저주):

  • 매크로 행동(Macro-actions): 계획 트리의 유효 깊이를 줄이기 위해 시간적으로 확장된 행동 시퀀스를 구성합니다 (예: POSMDP를 통해).
  • 자동 생성: 보상 밀도 또는 정보 가치에 기반하여 하위 문제나 마일스톤을 자동으로 생성하는 기법들입니다.

• 거대 관측 공간:

  • 이산화(Discretization): 연속 관측을 이산화하기 위해 가치 함수에서 유도된 특징을 사용합니다.
  • 점진적 확장(Progressive Widening): POMCPOW는 이중 점진적 확장을 사용하여 고려되는 관측 집합을 점진적으로 확장합니다.
  • 지연 신념 추출(Lazy Belief Extraction): LABECOP는 실행 중에 샘플링된 에피소드를 유지하고 가중치를 재조정함으로써 이산화를 완전히 피합니다.

• 거대 행동 공간:

  • 행동 샘플링: 모든 행동에 대한 최대화 과정을 무작위 부분 집합에 대한 최대화로 대체합니다 (예: Perseus, GCS).
  • 최적화: 연속적인 행동을 위해 일반 패턴 탐색(Generalized Pattern Search, GPS-ABT) 또는 베이지안 최적화를 사용하지만, 고차원에서의 확장성은 여전히 제한적입니다.
  • 분위수 통계(Quantile Statistics): 거대 이산 행동 공간을 위한 2단계 샘플링 메커니즘입니다.

• 복잡한 역학(Complex Dynamics):

  • 하이브리드 모델: 비선형 역학을 스위칭 상태 공간 모델(switching state-space models)로 표현합니다.
  • 다단계 몬테카를로(Multi-Level Monte Carlo, MLMLC): 다양한 충실도(fidelity)를 가진 모델을 사용하여 값비싼 동적 시뮬레이션을 근사하며, 고충실도 모델은 가끔씩만 사용합니다.

3. 주요 기여 및 결과

본 논문은 새로운 실험 데이터를 제시하기보다는 최신 기술 수준(state of the art)을 종합하여 로보틱스에서 POMDP의 실현 가능성을 입증합니다.

• 확장성 진보: 본 리뷰는 샘플링 기반 솔버가 <30개의 상태를 처리하던 수준에서 15,000개 이상의 상태와 1,000개 이상의 관측을 처리하는 수준(예: HSVI2, SARSOP)으로 발전했음을 강조합니다. 예를 들어, SARSOP는 RockSample(10,10) 벤치마크(100,000개 이상의 상태)를 수 초 만에 해결했습니다.
• 실제 적용: 본 논문은 SIMPAR 2018 및 ICRA 2018에서의 시연을 인용하며, 물리적 로봇이 POMDP 전략을 사용하여 7일 연속으로 작동했음을 보여줍니다. 결정적으로, 거칠게 학습된 전이 및 관측 모델을 사용했음에도 불구하고, 불확실성을 무시하는 전략이 35%의 성공률을 보인 것에 비해 POMDP 접근 방식은 100%의 성공률을 달로 달성했습니다.
• 소프트웨어 생태계: 본 논문은 이러한 솔버를 구현하고 ROS와 같은 로보틱스 미들웨어와 인터페이스를 제공하여 실질적인 채택을 용이하게 하는 오픈 소스 도구들(예: Symbolic Perseus, ZMDP, APPL, TAPIR, OPPT, pomdp_py)을 목록화합니다.

4. 의의 및 주장

본 논문은 이러한 발전의 의의가 POMDP를 "토이 문제(toy problems)"에만 적용 가능한 이론적 개념에서 현실적인 로보틱스를 위한 실용적인 도구로 변모시킨 데 있다고 주장합니다.

• 강건성(Robustness): 문제를 POMDP로 정식화함으로써 얻는 일차적인 이득은 강건성입니다. 불확실성을 명시적으로 정량화함으로써, POMDP는 정보 수집과 작업 실행 사이의 트레이드오프를 자동으로 균형 있게 조절합니다. 이는 제약이 있는 환경이나 로봇의 능력 한계 근처에서 작동할 때 특히 중요합니다.
• 모델의 실현 가능성: 본 논문은 정확한 모델이 반드시 필요한 것은 아니라고 주장합니다. 솔버가 불확실성을 처리할 수 있을 만큼 충분히 확장 가능하다면, 작은 데이터셋에서 학습된 거친 추정치만으로도 매우 효과적인 정책을 생성할 수 있습니다.
• 모션 플래닝과의 평행 이론: POMDP 솔버의 발전 과정은 샘플링 기반 모션 플래닝(예: 전역 계획에서 지역/쿼리 기반 계획으로의 이동)의 발전 과정과 유사하며, 이는 유사한 이론적 및 알고리즘적 성숙이 이루어졌음을 시사합니다.
• 학습과의 관계: 본 논문은 POMDP와 강화 학습(RL), 특히 모델 기반 베이지안 강화 학습(Model-Based Bayesian RL) 사이의 밀접한 관계를 언급하며, POMDP가 과제를 해결하는 동안 모델 파라미터를 학습하는 데 사용될 수 있음을 밝힙니다.

결론적으로, 본 논문은 고차원 연속 행동 공간과 같은 확장성 과제가 남아있음에도 불구하고, 현재의 샘플링 기반 방법들이 로봇 시스템의 강건성을 크게 향상시키기에 충분히 효율적이며, 따라서 POMDT가 불확실성 하의 계획 수립을 위한 실행 가능한 권장 접근 방식임을 천명합니다.