Factored POMDP를 위한 Symbolic GapMin 알고리즘

Abstract

Partially observable Markov decision process(POMDP)는 순차적 의사결정을 위한 모델로, 확률적인 환경 변화와 부분적인 관찰을 표현하는 기본적인 방법이다. POMDP는 선택 이론 기반 최적화나 로봇 조종 등의 많은 응용 범위를 가진다. 하지만, POMDP의 최적해를 구하는 것은 POMDP의 문제 크기가 커질수록 급격하게 어려운 문제이고, 실제 응용 상황에서는 문제 크기가 지수적으로 증가하기 때문에 이에 어려움이 따른다. 따라서 근사해를 구하는 기법들이 주로 연구되고 있으며, 또한 주어진 문제의 특수한 구조를 이용하는 방법이 필요하게 된다. 본 연구에서는 Symbolic GapMin이라는 알고리즘을 제안한다. 이 알고리즘은 factored POMDP라는 방식으로 표현된 POMDP를 Algebraic Decision Diagram(ADD)를 이용하여 계산하는 근사 알고리즘이다. Symbolic GapMin은 ADD를 효율적으로 사용하여 지수적인 계산을 피하며, 또한 큐 기반의 탐색과 전체에 적용되는 갱신 작업은 효율적인 계산을 이끈다. 본 연구에서는 기존에 제안되었던 Symbolic HSVI와의 실험적 비교를 수행하며, 많은 경우 Symbolic GapMin이 기존 방법론에 비하여 더 효과적인 계산을 수행함을 보인다.