Cited By
View all- Mausam Bertoli PWeld D(2007)A hybridized planner for stochastic domainsProceedings of the 20th international joint conference on Artifical intelligence10.5555/1625275.1625594(1972-1978)Online publication date: 6-Jan-2007
Conditional planning in the discrete belief space
Pages 1260 - 1265
Abstract
Probabilistic planning with observability restrictions, as formalized for example as partially observable Markov decision processes (POMDP), has a wide range of applications, but it is computationally extremely difficult. For POMDPs, the most general decision problems about existence of policies satisfying certain properties are undecidable. We consider a computationally easier form of planning that ignores exact probabilities, and give an algorithm for a class of planning problems with partial observability. We show that the basic backup step in the algorithm is NP-complete. Then we proceed to give an algorithm for the backup step, and demonstrate how it can be used as a basis of an efficient algorithm for constructing plans.
References
[1]
{Bertoli et al., 2001} Piergiorgio Bertoli, Alessandro Cimatti, Marco Roveri, and Paolo Traverso. Planning in nondeterministic domains under partial observability via symbolic model checking. In Bernhard Nebel, editor, Proceedings of the 17th International Joint Conference on Artificial Intelligence, pages 473-478. Morgan Kaufmann Publishers, 2001.
[2]
{Bonet and Geffner, 2000} Blai Bonet and Héctor Geffner. Planning with incomplete information as heuristic search in belief space. In Steve Chien, Subbarao Kambhampati, and Craig A. Knoblock, editors, Proceedings of the Fifth International Conference on Artificial Intelligence Planning Systems, pages 52-61. AAAI Press, 2000.
[3]
{Burch et al., 1994} J. R. Burch, E. M. Clarke, D. E. Long, K. L. MacMillan, and D. L. Dill. Symbolic model checking for sequential circuit verification. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 13(4):401-424, 1994.
[4]
{Kaelbling et al., 1998} Leslie Pack Kaelbling, Michael L. Littman, and Anthony R. Cassandra. Planning and acting in partially observable stochastic domains. Artificial Intelligence, 101(1-2):99-134, 1998.
[5]
{Madani et al., 1999} Omid Madani, Steve Hanks, and Anne Condon. On the decidability of probabilistic planning and infinite-horizon partially observable Markov decision problems. In Proceedings of the 16th National Conference on Artificial Intelligence (AAAI-99) and the 11th Conference on Innovative Applications of Artificial Intelligence (IAAI-99), pages 541-548. AAAI Press, 1999.
[6]
{Mundhenk et al., 2000} Martin Mundhenk, Judy Goldsmith, Christopher Lusena, and Eric Allender. Complexity of finite-horizon Markov decision process problems. Journal of the ACM, 47(4):681-720, 2000.
[7]
{Puterman, 1994} M. L. Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 1994.
[8]
{Rintanen, 2002} Jussi Rintanen. Backward plan construction under partial observability. In Malik Ghallab, Joachim Hertzberg, and Paolo Traverso, editors, Proceedings of the Sixth International Conference on Artificial Intelligence Planning Systems, pages 173-182. AAAI Press, 2002.
[9]
{Rintanen, 2004a} Jussi Rintanen. Complexity of planning with partial observability. In Shlomo Zilberstein, Jana Koehler, and Sven Koenig, editors, ICAPS 2004. Proceedings of the Fourteenth International Conference on Automated Planning and Scheduling, pages 345-354. AAAI Press, 2004.
[10]
{Rintanen, 2004b} Jussi Rintanen. Distance estimates for planning in the discrete belief space. In Proceedings of the 18th National Conference on Artificial Intelligence (AAAI- 2004) and the 13th Conference on Innovative Applications of Artificial Intelligence (IAAI-2004), pages 525- 530. AAAI Press, 2004.
[11]
{Smallwood and Sondik, 1973} Richard D. Smallwood and Edward J. Sondik. The optimal control of partially observable Markov processes over a finite horizon. Operations Research, 21:1071-1088, 1973.
[12]
{Weld et al., 1998} Daniel S. Weld, Corin R. Anderson, and David E. Smith. Extending Graphplan to handle uncertainty and sensing actions. In Proceedings of the 15th National Conference on Artificial Intelligence (AAAI-98) and the 10th Conference on Innovative Applications of Artificial Intelligence (IAAI-98), pages 897-904. AAAI Press, 1998.
- Conditional planning in the discrete belief space
Recommendations
Decentralized control of multi-robot partially observable Markov decision processes using belief space macro-actions
This work focuses on solving general multi-robot planning problems in continuous spaces with partial observability given a high-level domain description. Decentralized Partially Observable Markov Decision Processes Dec-POMDPs are general models for ...
Planning with incomplete information as heuristic search in belief space
AIPS'00: Proceedings of the Fifth International Conference on Artificial Intelligence Planning SystemsThe formulation of planning as heuristic search with heuristics derived from problem representations has turned out to be a fruitful approach for classical planning. In this paper, we pursue a similar idea in the context planning with incomplete ...
Analogical replay for efficient conditional planning
AAAI'97/IAAI'97: Proceedings of the fourteenth national conference on artificial intelligence and ninth conference on Innovative applications of artificial intelligenceRecently, several planners have been designed that can create conditionally branching plans to solve problems which involve uncertainty. These planners represent an important step in broadening the applicability of AI planning techniques, but they ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2005
1775 pages
Sponsors
- The International Joint Conferences on Artificial Intelligence, Inc.
Publisher
Morgan Kaufmann Publishers Inc.
San Francisco, CA, United States
Publication History
Published: 30 July 2005
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 19 Nov 2024
Other Metrics
Citations
Cited By
View all- Mausam Bertoli PWeld D(2007)A hybridized planner for stochastic domainsProceedings of the 20th international joint conference on Artifical intelligence10.5555/1625275.1625594(1972-1978)Online publication date: 6-Jan-2007
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in