Florent Teichteil-Königsbuch, Guillaume Infantes
In order to deal with real-world sequential decision making, stochastic outcomes for actions have to be explicitly taken into account, as in the Markov Decision Processes (MDPs) framework. While MDPs have been studied for a long time, dealing with a large number of states is still an open issue. As the initial state is given, most state-of-the-art algorithms use heuristic information over the MDP domain, in order to deal only with states that are reachable from the initial one. But we think this information still is under-exploited. We give a formal definition of such probabilistic reachability and propose a new algorithm that uses much more explicitly this information in a parametric way. We present results that show that our algorithm outperforms previous algorithms.
Subjects: 1.11 Planning; 15.5 Decision Theory
Submitted: May 5, 2008