93 citations · 122 across the 9 of their papers we have counts for
3 papers · 1 filter
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…
Nonapproximability Results for Partially Observable Markov Decision Processes
J. Goldsmith, C. Lusena, M. Mundhenk
We show that for several variations of partially observable Markov decision processes, polynomial-time algorithms for finding control policies are unlikely to or simply don't have…
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…