Tr-FSP: Forward Stochastic Planning using Probabilistic Reachability

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

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.