Partially observable Markov decision process (POMDP) is a classic model for representing
sequential decision task with stochastic dynamics on partial observable environments. POMDP can model several real-world domains such as decision-theoretic optimization, robotic aplication, and so on.
However, solving POMDP is known as hard to solve when the number of states grows. It becomes problematic for real-world domains, since they usually has exponential number of states. Therefore,
the approximate solver is needed, especially which can handle large state space eciently by exploiting model structure.
In this work, I present Symbolic GapMin, the approximate solver for factored POMDP with algebraic decision diagram (ADD) representation. Symbolic GapMin eciently uses ADD structure so it can handle exponentially large states and observations without enumerating them. Also, the queue-based search and asynchronous global update of Symbolic GapMin yield fast convergence while using memory eciently.
I also show several experimental results that Symbolic GapMin solves factored POMDP faster than previous approaches, especially that Symbolic GapMin outperforms Symbolic HSVI on several domains.
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이 기존 방법론에 비하여 더 효과적인 계산을 수행함을 보인다.
