Planning Under Uncertainty in Large Domains

Principal Investigator

Michael L. Littman

Background

Research in planning, making a sequence of choices to achieve some goal, has been a mainstay of artificial intelligence (AI) for many years. Traditionally, the decision-making models that have been studied admit no uncertainty whatsoever---every aspect of the world that is relevant to the generation and execution of a plan is known in advance. In contrast, work in operations research (OR) has focussed on the uncertainty of actions but uses an impoverished representation for specifying planning problems.

The purpose of this project is to explore some middle ground between these two well-studied extremes with the hope of understanding how we might create systems that can reason efficiently about plans in complex, uncertain worlds.

Papers

Planning As Satisfiability

Michael L. Littman. Initial Experiments in stochastic satisfiability. To appear AAAI, 1999. (abstract, postscript)

Stephen M. Majercik and Michael L. Littman. Using caching to solve larger probabilistic planning problems. In AAAI, pages 954-959, 1998. (postscript, abstract).

Stephen M. Majercik and Michael L. Littman. MAXPLAN: A new approach to probabilistic planning. In AIPS, pages 86--93, 1998. (postscript, abstract).

Michael L. Littman and Stephen M. Majercik. Large-Scale Planning Under Uncertainty: A Survey. In Workshop on Planning and Scheduling for Space, pages 27:1--8, 1997. (postscript)

Planning Complexity

Michael L. Littman, Judy Goldsmith, and Martin Mundhenk. The computational complexity of probabilistic planning. Journal of Artificial Intelligence Research, volume 9, pages 1--36, 1998. (postscript, official JAIR version, abstract)

Judy Goldsmith, Michael L. Littman, and Martin Mundhenk. The complexity of plan existence and evaluation in probabilistic domains. In Dan Geiger and Prakash Pundalik Shenoy, editors, Proceedings of the Thirteenth Annual Conference on Uncertainty in Artificial Intelligence (UAI--97), pages 182--189, San Francisco, CA, 1997. Morgan Kaufmann. (abstract, postscript, Duke CS Technical Report CS-1997-07)

Michael L. Littman. Probabilistic propositional planning: Representations and complexity. In Proceedings of the Fourteenth National Conference on Artificial Intelligence, pages 748--754, 1997. (postscript).

Planning with POMDPs

Leslie Pack Kaelbling, Michael L. Littman and Anthony R. Cassandra. Planning and Acting in Partially Observable Stochastic Domains. Artificial Intelligence, 101: 1-2, pages 99-134, 1998.(official pdf, early version in compressed postscript)

Anthony Cassandra, Michael L. Littman, and Nevin L. Zhang. Incremental pruning: A simple, fast, exact algorithm for partially observable Markov decision processes. In Dan Geiger and Prakash Pundalik Shenoy, editors, Proceedings of the Thirteenth Annual Conference on Uncertainty in Artificial Intelligence (UAI--97), pages 54--61, San Francisco, CA, 1997. Morgan Kaufmann. (postscript, abstract)

Michael Littman, Anthony Cassandra, and Leslie Kaelbling. Learning policies for partially observable environments: Scaling up. In Armand Prieditis and Stuart Russell, editors, Proceedings of the Twelfth International Conference on Machine Learning, pages 362--370, San Francisco, CA, 1995. Morgan Kaufmann. (postscript, Brown extended tech report, abstract)

Reinforcement Learning

Satinder Singh, Tommi Jaakkola, Michael L. Littman and Csaba Szepesvári. Convergence Results for Single-Step On-Policy Reinforcement-Learning Algorithms. Machine Learning, to appear, 1998. (draft in postscript)

Michael L. Littman and Csaba Szepesvári. A generalized reinforcement-learning model: Convergence and applications. In Proceedings of the Thirteenth International Conference on Machine Learning, pages 310-318, 1996. (abstract, postscript)

Leslie Pack Kaelbling, Michael L. Littman, and Andrew W. Moore. Reinforcement learning: A survey. Journal of Artificial Intelligence Research, 4:237-285, 1996. (draft in postscript, official JAIR version)

Leslie Pack Kaelbling, Michael L. Littman, and Andrew W. Moore. An introduction to reinforcement learning. In Luc Steels, editor, Proceedings of the NATO advanced study institute on the biology and technology of intelligent autonomous agents, volume 144, Berlin, 1995. Springer-Verlag.

Michael Littman, Anthony Cassandra, and Leslie Kaelbling. Learning policies for partially observable environments: Scaling up. In Armand Prieditis and Stuart Russell, editors, Proceedings of the Twelfth International Conference on Machine Learning, pages 362--370, San Francisco, CA, 1995. Morgan Kaufmann. (postscript, Brown extended tech report, abstract)

Other Topics

Greg A. Keim, Noam Shazeer, Michael L. Littman, Sushant Agarwal, Catherine M. Cheves, Joseph Fitzgerald, Jason Grosland, Fan Jiang, Shannon Pollard, and Karl Weinmeister. Proverb: The probabilistic cruciverbalist. To appear in AAAI, 1999. (abstract, postscript)

Noam M. Shazeer, Michael L. Littman, and Greg A. Keim. Constraint satisfaction with probabilistic preferences on variable values. Technical Report CS-99-03, Duke University, Department of Computer Science, Durham, NC, February 1999. (abstract, postscript (draft))

Ming-Yang Kao and Michael L. Littman. Algorithms for informed cows. AAAI-97 Workshop on On-Line Search, 1997 (postscript)

Michael S. Fulkerson, Michael L. Littman, and Greg A. Keim. Speeding Safely: Multi-criteria optimization in probabilistic planning. In Proceedings of the Fourteenth National Conference on Artificial Intelligence, page 831, 1997 (postscript).

Michael L. Littman, Thomas L. Dean, and Leslie Pack Kaelbling. On the complexity of solving Markov decision problems. In Proceedings of the Eleventh Annual Conference on Uncertainty in Artificial Intelligence (UAI--95), Montreal, Quebec, Canada, 1995. (postscript, abstract)

This material is based upon work supported by the National Science Foundation under Grant No. 9702576 (CAREER). Any opinions, findings and conclusions or recomendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation (NSF).
Last modified: Fri Jun 11 17:01:46 EDT 1999 by Michael Littman, mlittman@cs.duke.edu