Article

Free access

Planning under continuous time and resource uncertainty: a challenge for AI

Authors:

Richard Dearden,

Nicolas Meuleau,

Sailesh Ramakrishnan,

Rich washingtonAuthors Info & Claims

UAI'02: Proceedings of the Eighteenth conference on Uncertainty in artificial intelligence

Pages 77 - 84

Published: 01 August 2002 Publication History

PDF eReader Publisher Site

Abstract

We outline a class of problems, typical of Mars rover operations, that are problematic for current methods of planning under uncertainty. The existing methods fail because they suffer from one or more of the following limitations: 1) they rely on very simple models of actions and time, 2) they assume that uncertainty is manifested in discrete action outcomes, 3) they are only practical for very small problems. For many real world oroblems, these assumptions fail to hold. In particular, when planning the activities for a Mars rover, none of the above assumptions is valid: 1) actions can be concurrent and have differing durations, 2) there is uncertainty concerning action durations and consumption of continuous resources like power, and 3) typical daily plans involve on the order of a hundred actions. This class of problems may be of particular interest to the UAI community because both classical and decision-theoretic planning techniques may be useful in solving it. We describe the rover problem, discuss previous work on planning under uncertainty, and present a detailed, but very small, example illustrating some of the difficulties of finding good plans.

References

[1]

P. Bertoli, A. Cimatti, and M. Roveri. Heuristic search + symbolic model checking = efficient conformant planning. In Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, 2001.

Digital Library

[2]

P. Bertoli, A. Cimatti, M. Roveri, and P. Traverso. Planning in mondeterministic domains under partial observability via symbolic model checking. In Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, 2001.

Digital Library

[3]

D. Bewekas and I. Tsitsiklis. Neuro-dynamic Programming. Athena, Belmont, MA, 1996.

Digital Library

[4]

A. Blum and J. Langford. Probabilistic planning in the Graphplan framework. In Proceedings of the Fifth European Conference on Planning, 1999.

Digital Library

[5]

J. Blythe. Planning under uncertainty in dynamic domains. PhD thesis, CarnegieMellon University, 1998.

[6]

J. Blythe. Decision-theoretic planning. AI Magazine, 20(2):37-54, 1999.

[7]

B. Bonet and H. Geffner. Planning with incomplete information as heuristic search in belief space. In Proceedings of the Fifth International Conference on Artificial Intelligence Planning and Scheduling, pages 52-61, 2000.

Digital Library

[8]

C. Boutillier, T. Dean, and S. Hanks. Decision theoretic planning: structural assumptions and computational leverage. Journal of AI Research, 11: 1-94, 1999.

[9]

J. Boyan and M. Littman. Exact solutions to timedependent MDPs. In Advances in Neural Information Processing Systems 13, pages 1-7. MIT Press, Cambridge, 2000.

[10]

C. Castellini, E. Giunchiglia, and A. Tacchella. Improvements to sat-based conformant planning. In Proceedings of the Sixth European Conference on Planning, 2001.

[11]

A. Cimatti and M. Roveri. Conformant planning via symbolic model checking. Journal of AI Research, 11:305-338,2000.

Digital Library

[12]

D. Draper, S. Hanks, and D. Weld. Probabilistic planning with information gathering and contingent execution. In Proceedings of the Second International Conference on Artificial Intelligence Planning and Scheduling, pages 31-36,1994.

[13]

M. Drummond, I. Bresina, and K. Swanson. Just-In-Case scheduling. In Proceedings of the Twelfth National Conference on Artificial Intelligence, pages 1098-1104,1994.

Digital Library

[14]

O. Etzioni, S. Hanks, D. Weld, D. Draper, N. Lesh, and M. Williamson. An approach to planning with incomplete information. In Proceedings of the Third International Conference on Principles of Knowledge Representation and Reasoning, pages 115-125,1992.

Digital Library

[15]

E. Ferraris and E. Giunchiglia. Planning as satisfiability in nondeterministic domains. In Proceedings of the Seventeenth National Conference on Artificial Intelligence, 2000.

Digital Library

[16]

K. Golden. Leap before you look: information gathering in the PUCCINI planner. In Proceedings of the Fourth International Conference on Artificial Intelligence Planning and Scheduling, pages 70-77,1998.

[17]

R. Goldman and M. Boddy. Conditional linear planning. In Proceedings of the Second International Conference on Artificial Intelligence Planning and Scheduling, pages 80-85,1994.

[18]

J. Kurien, P. Nayak, and D. Smith. Fragment-based conformant planning. In Proceedings of the Sixth International Conference on Artificial Intelligence Planning and Scheduling, 2002.

Digital Library

[19]

N. Kushmerick, S. Hanks, and D. Weld. An algorithm for probabilistic planning. Artificial Intelligence, 76(1-2):239-286,1995.

Digital Library

[20]

M. Littman, I. Goldsmith, and M. Mundhenk. The computational complexity of probabilistic planning. Journal of AI Research, 9: 1-36, 1998.

Digital Library

[21]

S. Majercik and M. Littman. Contingent planning under uncertainty via stochastic satisfiability. In Proceedings of the Sixteenth National Conference on Artificial Intelligence, 1999.

Digital Library

[22]

N. Meuleau, M. Hauskrecht, K. Kim, L. Peshkin, L. Kaelbling, T. Dean, and C. Boutilier. Solving very large weakly coupled Markov decision processes. In Proceedings of the Fifteenth National Conference on Artificial Intelligence, pages 165-172, 1998.

Digital Library

[23]

R. Munos. Variable resolution discretization for highaccuracy solutions of optimal control problems. In Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, 1999.

Digital Library

[24]

R. Munos. A study of reinforcement learning in the continuous case by the means of viscosity solutions. Machine Learning, 40:265-299,2000.

Digital Library

[25]

N. Onder and M. Pollack. Conditional, probabilistic planning: A unifying algorithm and effective search control mechanisms. In Proceedings of the Sixteenth National Conference on Artificial Intelligence, pages 577-584,1999.

Digital Library

[26]

M. Peot. Decision-Theoretic Planning. PhD thesis, Dept. of Engineering-Economic Systems, Stanford University, 1998.

Digital Library

[27]

M. Peot and D. Smith. Conditional nonlinear planning. In Proceedings of the First International Conference on Artificial Intelligence Planning and Scheduling, pages 189-197, 1992.

Digital Library

[28]

L. Pryor and G. Collins. Planning for contingencies: a decision-based approach. Journal of AI Research, 4:287-339, 1996.

Digital Library

[29]

M. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley, New York, NY, 1994.

Digital Library

[30]

J. Rintanen. Constructing conditional plans by a theorem prover. Journal of AI Research, 10:323-352, 1999.

Digital Library

[31]

S. Singh and D. Cohn. How to dynamically merge Markov decision processes. In Advances in Neural Information Processing Systems 11. MIT Press, Cambridge, 1998.

Digital Library

[32]

W. Smart and L. Kaelbling. Practical reinforcement learning in continuous spaces. In Proceedings of the Seventeenth International Conference on Machine Learning, 2000.

Digital Library

[33]

D. Smith, J. Frank, and A. Jónsson. Bridging the gap between planning and scheduling. The Knowledge Engineering Review, 15(1), 2000.

Digital Library

[34]

D. Smith and D. Weld. Conformant graphplan. In Proceedings of the Fifteenth National Conference on Artificial Intelligence, pages 889-896, 1998.

Digital Library

[35]

S. Thrun. Monte Carlo POMDPs. In Advances in Neural Information Processing Systems 12, pages 1064-1070. MIT Press, Cambridge, 1999.

[36]

D. Warren. Generating conditional plans and programs. In Proceedings of the Summer Conference on AI and Simulation of Behavior, 1976.

[37]

D. Weld, C. Anderson, and D. Smith. Extending Graphplan to handle uncertainty and sensing actions. In Proceedings of the Fifteenth National Conference on Artificial Intelligence, pages 897-904, 1998.

Digital Library

Cited By

de Nijs FWalraven EDe Weerdt MSpaan M(2021)Constrained Multiagent Markov Decision ProcessesJournal of Artificial Intelligence Research10.1613/jair.1.1223370(955-1001)Online publication date: 1-May-2021
https://dl.acm.org/doi/10.1613/jair.1.12233
Micheli ADo MSmith D(2015)Compiling away uncertainty in strong temporal planning with uncontrollable durationsProceedings of the 24th International Conference on Artificial Intelligence10.5555/2832415.2832476(1631-1637)Online publication date: 25-Jul-2015
https://dl.acm.org/doi/10.5555/2832415.2832476
Teichteil-Königsbuch F(2012)Fast incremental policy compilation from plans in hybrid probabilistic domainsProceedings of the Twenty-Second International Conference on International Conference on Automated Planning and Scheduling10.5555/3038546.3038576(252-260)Online publication date: 25-Jun-2012
https://dl.acm.org/doi/10.5555/3038546.3038576
Show More Cited By

Index Terms

Planning under continuous time and resource uncertainty: a challenge for AI
1. Computing methodologies
  1. Artificial intelligence
    1. Knowledge representation and reasoning
      1. Probabilistic reasoning
      2. Vagueness and fuzzy logic

Recommendations

Planning under uncertainty: moving forward
Planning to plan under uncertainty: an architecture for reactive meta-planning
Probabilistic planning for continuous dynamic systems under bounded risk

This paper presents a model-based planner called the Probabilistic Sulu Planner or the p-Sulu Planner, which controls stochastic systems in a goal directed manner within user-specified risk bounds. The objective of the p-Sulu Planner is to allow users ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

UAI'02: Proceedings of the Eighteenth conference on Uncertainty in artificial intelligence

August 2002

584 pages

ISBN:1558608974

Editors:
Adnan Darwiche
Univeristy of California, Los Angeles
,
Nir Friedman
Hebrew University, Jerusalem

Sponsors

Information Extraction and Transportation
AAAI: American Association for Artificial Intelligence
Fair, Isaac and Company, Inc.: Fair, Isaac and Company, Inc.
Boeing Research: Boeing Research
University of Alberta: University of Alberta

Publisher

Morgan Kaufmann Publishers Inc.

San Francisco, CA, United States

Publication History

Published: 01 August 2002

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

42
Total Citations
View Citations
238
Total Downloads

Downloads (Last 12 months)43
Downloads (Last 6 weeks)13

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

de Nijs FWalraven EDe Weerdt MSpaan M(2021)Constrained Multiagent Markov Decision ProcessesJournal of Artificial Intelligence Research10.1613/jair.1.1223370(955-1001)Online publication date: 1-May-2021
https://dl.acm.org/doi/10.1613/jair.1.12233
Micheli ADo MSmith D(2015)Compiling away uncertainty in strong temporal planning with uncontrollable durationsProceedings of the 24th International Conference on Artificial Intelligence10.5555/2832415.2832476(1631-1637)Online publication date: 25-Jul-2015
https://dl.acm.org/doi/10.5555/2832415.2832476
Teichteil-Königsbuch F(2012)Fast incremental policy compilation from plans in hybrid probabilistic domainsProceedings of the Twenty-Second International Conference on International Conference on Automated Planning and Scheduling10.5555/3038546.3038576(252-260)Online publication date: 25-Jun-2012
https://dl.acm.org/doi/10.5555/3038546.3038576
Sanner SDelgado Kde Barros L(2011)Symbolic dynamic programming for discrete and continuous state MDPsProceedings of the Twenty-Seventh Conference on Uncertainty in Artificial Intelligence10.5555/3020548.3020623(643-652)Online publication date: 14-Jul-2011
https://dl.acm.org/doi/10.5555/3020548.3020623
Maheswaran RSzekely PSanchez R(2011)Automated adaptation of strategic guidance in multiagent coordinationProceedings of the 14th international conference on Agents in Principle, Agents in Practice10.1007/978-3-642-25044-6_20(247-262)Online publication date: 16-Nov-2011
https://dl.acm.org/doi/10.1007/978-3-642-25044-6_20
Onder NMukherjee ATang P(2010)Construction management applicationsProceedings of the Twentieth International Conference on International Conference on Automated Planning and Scheduling10.5555/3037334.3037376(263-266)Online publication date: 12-May-2010
https://dl.acm.org/doi/10.5555/3037334.3037376
Beaudry EKabanza FMichaud F(2010)Planning for concurrent action executions under action duration uncertainty using dynamically generated Bayesian networksProceedings of the Twentieth International Conference on International Conference on Automated Planning and Scheduling10.5555/3037334.3037337(10-17)Online publication date: 12-May-2010
https://dl.acm.org/doi/10.5555/3037334.3037337
Beaudry ÉKabanza FMichaud F(2010)Planning with Concurrency under Resources and Time UncertaintyProceedings of the 2010 conference on ECAI 2010: 19th European Conference on Artificial Intelligence10.5555/1860967.1861011(217-222)Online publication date: 4-Aug-2010
https://dl.acm.org/doi/10.5555/1860967.1861011
Marecki JVarakantham PLuck MSen S(2010)Risk-sensitive planning in partially observable environmentsProceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: volume 1 - Volume 110.5555/1838206.1838384(1357-1368)Online publication date: 10-May-2010
https://dl.acm.org/doi/10.5555/1838206.1838384
Saigol ZDearden RWyatt JMurton B(2009)Information-lookahead planning for AUV mappingProceedings of the 21st International Joint Conference on Artificial Intelligence10.5555/1661445.1661739(1831-1836)Online publication date: 11-Jul-2009
https://dl.acm.org/doi/10.5555/1661445.1661739
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents