Abstract
In this paper we tackle the sailing strategies problem, a stochastic shortest-path Markov
decision process. The problem of solving large Markov decision processes accurately and quickly
is challenging. Because the computational effort incurred is considerable, current research focuses
on finding superior acceleration techniques. For instance, the convergence properties of current solution
methods depend, to a great extent, on the order of backup operations. On one hand, algorithms
such as topological sorting are able to find good orderings, but their overhead is usually
high. On the other hand, shortest path methods, such as Dijkstras algorithm, which is based on
priority queues, have been applied successfully to the solution of deterministic shortest-path Markov
decision processes. Here, we propose improved value iteration algorithms based on Dijkstras algorithm
for solving shortest path Markov decision processes. The experimental results on a stochastic
shortest-path problem show the feasibility of our approach.
