The Complexity of Plan Existence and Evaluation in Probabilistic Domains

Judy Goldsmith, Michael L. Littman, Martin Mundhenk

We examine the computational complexity of testing and finding small plans in probabilistic planning domains with succinct representations. We find that many problems of interest a…