The Computational Complexity of Probabilistic Planning

M. L. Littman, J. Goldsmith, M. Mundhenk

We examine the computational complexity of testing and finding small plans in probabilistic planning domains with both flat and propositional representations. The complexity of pla…