A Heuristic Search Algorithm for Acting Optimally in Markov Decision Processes with Deterministic Hidden State

Abstract

Submitted to NIPS 2001 We propose a heuristic search algorithm for finding optimal policies in a new class of sequential decision making problems. This class extends Markov decision processes by a limited type of hidden state, paying tribute to the fact that many robotic problems indeed possess hidden state. The proposed search algorithm exploits the problem formulation to devise a fast bound-searching algorithm, which in turn cuts down the complexity of finding optimal solutions to the decision making problem by orders of magnitude. Extensive comparisons with state-of-the-art MDP and POMDP algorithms illustrate the effectiveness of our approach. 1