Structured Reachability Analysis for Markov Decision Processes
  Recent research in decision theoretic planning has focussed on making the
solution of Markov decision processes (MDPs) more feasible. We develop a family
of algorithms for structured reachability analysis of MDPs that are suitable
when an initial state (or set of states) is known. Using compact, structured
representations of MDPs (e.g., Bayesian networks), our methods, which vary in
the tradeoff between complexity and accuracy, produce structured descriptions
of (estimated) reachable states that can be used to eliminate variables or
variable values from the problem description, reducing the size of the MDP and
making it easier to solve. One contribution of our work is the extension of
ideas from GRAPHPLAN to deal with the distributed nature of action
representations typically embodied within Bayes nets and the problem of
correlated action effects. We also demonstrate that our algorithm can be made
more complete by using k-ary constraints instead of binary constraints. Another
contribution is the illustration of how the compact representation of
reachability constraints can be exploited by several existing (exact and
approximate) abstraction algorithms for MDPs.
