Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings         Authors   Author's Info   Article details         Search    
The Complexity of Plan Existence and Evaluation in Probabilistic Domains
Judy Goldsmith, Michael 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 are complete for a variety of complexity classes: NP, co-NP, PP, NP^PP, co-NP^PP, and PSPACE. Of these, the probabilistic classes PP and NP^PP are likely to be of special interest in the field of uncertainty in artificial intelligence and are deserving of additional study. These results suggest a fruitful direction of future algorithmic development.
Keywords: Probabilistic planning, complexity, MDPs.
Pages: 182-189
PS Link: http://www.cs.duke.edu/~mlittman/papers/uai97-nppp.ps
PDF Link: /papers/97/p182-goldsmith.pdf
AUTHOR = "Judy Goldsmith and Michael Littman and Martin Mundhenk",
TITLE = "The Complexity of Plan Existence and Evaluation in Probabilistic Domains",
BOOKTITLE = "Proceedings of the Thirteenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-97)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "1997",
PAGES = "182--189"

hosted by DSL   •   site info   •   help