제약을 갖는 POMDP를 위한 휴리스틱 검색 가치 반복 알고리즘

Abstract

본 논문에서는 제약을 갖는 부분 관찰 의사결정 과정(constrained partially observable Markov decision process; CPOMDP)을 위한 휴리스틱 검색 가치 반복(heuristic search value iteration; HSVI) 알고리즘인 CHSVI (constrained HSVI)를 제안한다. HSVI는 부분 관찰 의사결정 과정(partially observable Markov decision process; POMDP)의 최적 정책(optimal policy)을 구하는 효율적인 알고리즘 중 하나이다. HSVI는 점-기반 백업(point-based backup)을 통해 최적 정책을 구한다. 점-기반 백업에 사용될 상태확률분포(belief)를 수집하기 위해 가치 함수(value function)의 상계(upper bound)와 하계(lower bound)를 이용하는 휴리스틱 탐색을 수행한다. CHSVI에서도 이와 마찬가지로 가치 함수의 상계와 하계를 이용하여 휴리스틱 탐색을 수행하는데 이 때 제약이 고려된 상계와 하계를 나타낼 필요가 있다. 또한 CPOMDP의 최적 정책이 제약을 갖는 MDP (constrained Markov decision process; CMDP)와 같이 비결정적 정책(randomized policy)일 수 있으므로 이를 고려해야 한다. 본 논문에서는 CPOMDP 가치 함수의 상계와 하계에 대한 표현, 초기화, 측정, 갱신 등을 다루며, 비결정적 정책이 반영된 휴리스틱 탐색을 제안한다. 이를 기반으로 CHSVI 알고리즘을 제시하고 CHSVI로부터 얻어지는 최적 정책의 성능을 실험을 통해 확인한다.