A Heuristic Search Algorithm for Acting Optimally in Markov Decision Processes with Deterministic Hidden State
By
Jamieson Schulte and Sebastian Thrun
Abstract: 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.
Available for download in