Symbolic Stochastic Focused Dynamic Programming with Decision Diagrams.pdf

Symbolic Stochastic Focused Dynamic Programming with Decision Diagrams ¨ Florent Teichteil-Konigsbuch and Patrick Fabiani ONERA-DCSD ´ 2 Avenue Edouard-Belin 31055 Toulouse, France (florent.teichteil,patrick.fabiani)@cert.fr Abstract based on dynamic programming and includes two classes of algorithms : value iteration and policy iteration. The first is We present a stochastic planner based on Markov De- an iteration on the value function associated with each state, cision Processes (MDPs) that participates to the prob- abilistic planning track of the 2006 International Plan- that is to say the expected accumulated reward if we start ning Competition. The planner transforms the PPDDL from this state. When the iterated value function stabilizes, problems into factored MDPs that are then solved with the optimal value function is reached and the optimal policy a structured modified value iteration algorithm based on follows. In the policy iteration scheme, the current policy is the safest stochastic path computation from the initial assessed on the infinite horizon and improved locally at each states to the goal states. First, a state subspace is com- iteration. The value of a policy π is solution