Homepage
Research
Students
Courses
Robots
Papers
Videos
Press
Talks
Faq
CV
Lab
Travel
Contact
Personal
Links


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