Interval POMDP Shielding for Imperfect-Perception Agents

1. 문제 정의 (Problem Statement)

• 배경: 자율 시스템은 종종 센서 데이터를 신경망 (DNN) 을 통해 처리하여 상태를 인식합니다. 그러나 센서 오작동이나 환경 변화로 인해 인식된 상태가 실제 상태와 다를 수 있습니다 (불완전 인식).
• 위험: 인식 오류로 인해 에이전트가 잘못된 정보를 바탕으로 위험한 행동을 취할 수 있으며, 이는 안전이 중요한 환경 (예: 자율 비행, 로봇 제어) 에서 치명적입니다.
• 기존 접근법의 한계:
  • 점 추정 (Point Estimation): 유한한 학습 데이터로 인식 확률을 단일 값으로 추정하면, 배포 시 발생하는 분포 이동 (Distributional Shift) 으로 인해 실제 오류율이 추정치보다 훨씬 커질 수 있어 안전 보장이 어렵습니다.
  • 지원을 기반한 차폐 (Support-based Shielding): Carr 등 [8] 의 방법은 확률 값을 버리고 가능한 상태 집합 (Support) 만 고려합니다. 이는 안전성은 보장하지만, 지나치게 보수적 (Conservative) 이어서 실제 사용 가능한 행동을 모두 차단하여 시스템이 멈추게 (Stuck) 만들 수 있습니다.
  • 분포 이동 (Distributional Shift): 제어 정책의 변화 (Control-based shift) 와 배포 환경의 변화 (Deployment shift) 로 인해 학습된 확률 모델이 실제 환경과 달라질 수 있습니다. 특히 배포 시 상태별 방출 확률 (Emission Probability) 이 변하는 경우 기존 방법은 취약합니다.

2. 방법론 (Methodology)

저자들은 유한한 레이블된 데이터에서 학습된 인식 불확실성을 **신뢰 구간 (Confidence Intervals)**으로 모델링하고, 이를 **구간 POMDP (IPOMDP)**로 정의하여 해결책을 제시합니다.

A. 시스템 모델링: 구간 POMDP (IPOMDP)

• 모델 정의: 시스템 동역학은 정확히 알려져 있다고 가정하지만, 상태 $s$에서 관측 $o$로 전환되는 확률 $Z(o|s)$는 고정된 값이 아닌 구간 $[Z^-(o|s), Z^+(o|s)]$로 표현됩니다.
• PAC 보장: Clopper-Pearson 구간을 사용하여 유한 데이터로부터 신뢰 구간을 구성합니다. 이는 학습 데이터의 무작위성에 대해, 실제 인식 모델이 이 구간 집합 안에 있을 확률이 $\lambda$ 이상임을 보장합니다 (Dataset-level correctness guarantee).

B. 런타임 차폐 (Runtime Shielding)

• 개념: 완벽한 인식 (Perfect-perception) 을 가진 상태 기반 차폐 (예: PCIS, Barrier Certificate) 를 불완전 인식 환경으로 확장 (Lift) 합니다.
• 신용도 (Belief) 전파의 어려움: 구간 확률을 사용할 때, 베이즈 필터링을 통해 도달 가능한 신용도 집합 (Belief Set) 을 정확히 계산하면 비볼록 (Non-convex) 해지고 상태 공간이 기하급수적으로 증가하여 계산이 불가능합니다.
• 해결책: 템플릿 다면체 (Template Polytope) 기반 외접 (Over-approximation):
  • 도달 가능한 신용도 집합을 **템플릿 다면체 (Template Polytope)**로 근사화합니다.
  • 선형 프로그래밍 (LP) 활용:
    1. 동역학 업데이트: 선형 변환으로 유지됩니다.
    2. 관측 업데이트: 확률 구간과 신용도의 곱 (이차항) 은 McCormick Envelope을 사용하여 선형 부등식으로 외접합니다.
    3. 정규화: 베이즈 정규화 (나눗셈) 는 Charnes-Cooper 변환을 통해 선형 분수 계획법 (Linear-Fractional Programming) 문제로 변환하여 LP 로 해결합니다.
  • 최악의 경우 (Worst-case) 검증: 모든 가능한 신용도 (Belief Envelope) 에 대해 행위가 안전할 때만 (최악의 경우에도 안전 점수가 임계값 $\beta$ 이상일 때) 행위를 허용합니다.

C. 안전성 보장 (Guarantees)

• 추상화 무결성 (Abstraction Soundness): 실제 인식 모델이 구간 집합 안에 있다면, 차폐가 허용한 모든 행위는 안전 조건을 만족할 확률이 $\beta$ 이상임을 보장합니다.
• 유한 시간 안전성 (Finite-Horizon Safety): 학습 데이터의 무작위성 ($\lambda$) 과 런타임 안전성 ($\beta$) 을 결합하여, $H$ 단계 동안 안전할 확률이 $(\beta \gamma)^H$ 이상임을 보장합니다.

3. 주요 기여 (Key Contributions)

1. IPOMDP 공식화: 유한 데이터의 불확실성을 고려한 구간 POMDP 모델과 이에 대한 차폐 문제를 정의했습니다.
2. 런타임 차폐 구성: 완벽한 인식 차폐를 불완전 인식 환경으로 확장하는 알고리즘을 제안했습니다.
3. 선형 프로그래밍 기반 근사: IPOMDP 에서 도달 가능한 신용도 상태를 외접하는 보수적인 방법론을 개발하고, 이를 LP 를 통해 효율적으로 계산하는 방법을 제시했습니다.
4. 실험적 검증: TaxiNet, Obstacle, CartPole, Refuel 등 4 가지 벤치마크에서 제안된 방법 (Envelope) 과 기존 기법 (Single-Belief, Support-based 등) 을 비교하여 안전성과 사용성 (Stuck rate) 의 균형을 입증했습니다.
5. 확률적 자동자 해석: 구간 신용도 추론에 사용된 볼록 추상화의 수학적 해석을 제공했습니다.

4. 실험 결과 (Experimental Results)

• 벤치마크: TaxiNet (활주로 정렬), Obstacle (장애물 회피), CartPole (균형 유지), Refuel (연료 관리).
• 비교 대상:
  • Observation: 현재 관측만 기반 (메모리 없음).
  • Single-Belief: 점 추정 신용도 기반.
  • Fwd-Sampling: 도달 가능한 신용도 집합을 샘플링하여 하한 (Under-approximation) 을 추정.
  • Envelope (제안): LP 기반의 신용도 외접 (Over-approximation).
  • Carr (Support-based): 상태 지원 집합 기반.
• 결과 요약:
  • CartPole: 관측이 상태를 잘 식별하는 경우, 모든 방법이 유사한 성능을 보임.
  • TaxiNet & Obstacle (불완전 관측):
    • Envelope은 가장 강력한 안전성을 보임 (실패율 Fail rate 최소화).
    • Single-Belief는 점 추정 오차로 인해 위험한 행위를 허용하여 실패율이 높음.
    • **Support-based (Carr)**는 지나치게 보수적이어서 시스템이 멈추는 (Stuck) 경우가 많음.
    • Envelope은 안전성과 멈춤 (Stuck) 사이의 균형을 가장 잘 맞추며, 특히 관측이 불명확한 상황에서 Single-Belief 보다 안전하고 Support-based 보다 덜 보수적입니다.
  • Refuel: 상태 공간이 크고 관측이 제한적일 경우, LP 기반 Envelope 은 계산 비용이 너무 커서 비실용적임. 이 경우 Fwd-Sampling이 확장 가능한 대안이 됨.
• 계산 비용:
  • Observation, Single-Belief: 마이크로초 ($\mu s$) 단위.
  • Fwd-Sampling: 밀리초 ($ms$) 단위.
  • Envelope (LP): 수십~수백 밀리초 ($ms$) 이상 (계산 비용이 높음).

5. 의의 및 결론 (Significance & Conclusion)

• 안전성과 실용성의 균형: 이 논문은 불완전 인식 하에서 안전성을 보장하면서도 시스템이 멈추지 않도록 하는 "중간 지대"를 찾았습니다. 점 추정 (Single-Belief) 은 너무 낙관적이고, 지원 기반 (Support-based) 은 너무 보수적인 문제를 해결합니다.
• 배포 시 이동 (Deployment Shift) 대응: 유한 데이터에서 학습된 구간 모델을 사용하여, 배포 환경에서 발생할 수 있는 인식 오류의 변화를 통계적으로 보장합니다.
• 모듈러 설계: 기존에 개발된 완벽한 인식 차폐 (PCIS 등) 를 그대로 활용할 수 있어, 새로운 차폐를 처음부터 설계할 필요가 없습니다.
• 한계와 전망: LP 기반의 정밀한 차폐는 계산 비용이 높으므로, 대규모 시스템에서는 Fwd-Sampling 과 같은 근사 기법이나 템플릿의 정밀도를 조절하는 것이 필요합니다.

결론적으로, 이 연구는 불완전 인식 에이전트를 위한 강력한 안전 보장 메커니즘을 제공하며, 특히 관측 정보가 제한적이고 불확실성이 큰 환경에서 기존 방법론들의 한계를 극복하는 유효한 대안임을 입증했습니다.