title: Probabilistic Propositional Planning: Representations and Complexity
author: Michael L. Littman 
number: CS-1996-18
date: December 1996

abstract:

Many representations for probabilistic propositional planning problems
have been studied.  This paper reviews several such representations
and shows that, in spite of superficial differences between the
representations, they are ``expressively equivalent,'' meaning that
planning problems specified in one representation can be converted to
equivalent planning problems in any of the other representations with
at most a polynomial increase in the resulting representation and the
number of steps needed to reach the goal with sufficient probability.
The paper proves that the computational complexity of determining
whether a successful plan exists for planning problems expressed in
any of these representations is EXPTIME-complete and PSPACE-complete
when plans are restricted to take a polynomial number of steps.