Abstract
We describe APPSSAT, an approximate probabilistic contingent planner based on ZANDER, a probabilistic contingent planner that operates by converting the planning problem to a stochastic satisfiability (Ssat) problem and solving that problem instead [1]. The values of some of the variables in an Ssat instance are probabilistically determined; APPSSAT considers the most likely instantiations of these variables (the most probable situations facing the agent) and attempts to construct an approximation of the optimal plan that succeeds under those circumstances, improving that plan as time permits. Given more time, less likely instantiations/situations are considered and the plan is revised as necessary. In some cases, a plan constructed to address a relatively low percentage of possible situations will succeed for situations not explicitly considered as well, and may return an optimal or near-optimal plan. This means that APPSSAT can sometimes find optimal plans faster than ZANDER. And the anytime quality of APPSSAT means that suboptimal plans could be efficiently derived in larger time-critical domains in which ZANDER might not have sufficient time to calculate the optimal plan. We describe some preliminary experimental results and suggest further work needed to bring APPSSAT closer to attacking real-world problems.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Majercik, S.M., Littman, M.L.: Contingent planning under uncertainty via stochastic satisfiability. Artificial Intelligence 147, 119–162 (2003)
Littman, M.L., Majercik, S.M., Pitassi, T.: Stochastic Boolean satisfiability. Journal of Automated Reasoning 27, 251–296 (2001)
Drummond, M., Bresina, J.: Anytime synthetic projection: Maximizing the probability of goal satisfaction. In: Proceedings of the Eighth National Conference on Artificial Intelligence, pp. 138–144. Morgan Kaufmann, San Francisco (1990)
Onder, N., Pollack, M.E.: Contingency selection in plan generation. In: Proceedings of the Fourth European Conference on Planning, pp. 364–376 (1997)
Boutilier, C., Dearden, R.: Approximating value trees in structured dynamic programming. In: Proceedings of the Thirteenth International Conference on Machine Learning, pp. 56–62 (1996)
Koller, D., Parr, R.: Computing factored value functions for policies in structured MDPs. In: Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, pp. 1332–1339. The AAAI Press/The MIT Press (1999)
Koller, D., Parr, R.: Policy iteration for factored MDPs. In: Proceedings of the Sixteenth Annual Conference on Uncertainty in Artificial Intelligence (UAI 2000), pp. 326–334 (2000)
Kearns, M.J., Mansour, Y., Ng, A.Y.: A sparse sampling algorithm for near-optimal planning in large markov decision processes. Machine Learning 49, 193–208 (2002)
Zhang, N.L., Lin, W.: A model approximation scheme for planning in partially observable stochastic domains. Journal of Artificial Intelligence Research 7, 199–230 (1997)
Papadimitriou, C.H.: Games against nature. Journal of Computer Systems Science 31, 288–301 (1985)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Majercik, S.M. (2005). APPSSAT: Approximate Probabilistic Planning Using Stochastic Satisfiability. In: Godo, L. (eds) Symbolic and Quantitative Approaches to Reasoning with Uncertainty. ECSQARU 2005. Lecture Notes in Computer Science(), vol 3571. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11518655_19
Download citation
DOI: https://doi.org/10.1007/11518655_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-27326-4
Online ISBN: 978-3-540-31888-0
eBook Packages: Computer ScienceComputer Science (R0)