Abstract
Domain-independent planning in general is broadly applicable to a wide range of tasks. Many formalisms exist that allow the description of different aspects of realistic problems. Which one to use is often no obvious choice, since a higher degree of expressiveness usually comes with an increased planning time and/or a decreased policy quality. Under the assumption that hard guarantees are not required, users are faced with a decision between multiple approaches. As a generic model we use a probabilistic description in the form of Markov Decision Processes (MDPs). We define abstracting translations into a classical planning formalism and fully observable nondeterministic planning. Our goal is to give insight into how state-of-the-art systems perform on different MDP planning domains.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Boutilier, C., Dearden, R., Goldszmidt, M.: Stochastic Dynamic Programming with Factored Representations. Artificial Intelligence (AIJ) 121(1-2), 49–107 (2000)
Culberson, J.C., Schaeffer, J.: Searching with pattern databases. In: McCalla, G.I. (ed.) Canadian AI 1996. LNCS, vol. 1081, pp. 402–416. Springer, Heidelberg (1996)
Fu, J., Ng, V., Bastani, F.B., Yen, I.L.: Simple and fast strong cyclic planning for fully-observable nondeterministic planning problems. In: International Joint Conference on Artificial Intelligence (IJCAI), pp. 1949–1954 (2011)
Gaschler, A., Petrick, R.P.A., Kröger, T., Knoll, A., Khatib, O.: Robot task planning with contingencies for run-time sensing. In: ICRA Workshop on Combining Task and Motion Planning (2013)
Hansen, E.A., Zilberstein, S.: LAO*: A heuristic search algorithm that finds solutions with loops. Artificial Intelligence 129(1-2), 35–62 (2001)
Haslum, P., Botea, A., Helmert, M., Bonet, B., Koenig, S.: Domain-independent construction of pattern database heuristics for cost-optimal planning. In: AAAI Conference on Artificial Intelligence (AAAI), pp. 1007–1012 (2007)
Helmert, M.: The fast downward planning system. Journal of Artificial Intelligence Research (JAIR) 26, 191–246 (2006)
Kaelbling, L., Lozano-Perez, T.: Hierarchical task and motion planning in the now. In: IEEE Conference on Robotics and Automation, ICRA (2011)
Kaelbling, L., Lozano-Perez, T.: Integrated task and motion planning in belief space. International Journal of Robotics Research (2013)
Keller, T., Eyerich, P.: A Polynomial All Outcomes Determinization for Probabilistic Planning. In: International Conference on Automated Planning and Scheduling (ICAPS), pp. 331–334. AAAI Press (2011)
Keller, T., Eyerich, P.: PROST: Probabilistic Planning Based on UCT. In: International Conference on Automated Planning and Scheduling (ICAPS). pp. 119–127 (2012)
Keller, T., Eyerich, P., Nebel, B.: Task planning for an autonomous service robot. In: Dillmann, R., Beyerer, J., Hanebeck, U.D., Schultz, T. (eds.) KI 2010. LNCS, vol. 6359, pp. 358–365. Springer, Heidelberg (2010)
Keller, T., Helmert, M.: Trial-based Heuristic Tree Search for Finite Horizon MDPs. In: Proceedings of the 23rd International Conference on Automated Planning and Scheduling (ICAPS 2013), pp. 135–143 (2013)
Kuter, U., Nau, D.S., Reisner, E., Goldman, R.P.: Using classical planners to solve nondeterministic planning problems. In: Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), pp. 190–197 (2008)
Little, I., Thiébaux, S.: Probabilistic planning vs replanning. In: ICAPS Workshop on IPC: Past, Present and Future (2007)
Mattmüller, R., Ortlieb, M., Helmert, M., Bercher, P.: Pattern database heuristics for fully observable nondeterministic planning. In: International Conference on Automated Planning and Scheduling (ICAPS), pp. 105–112 (2010)
Muise, C.J., McIlraith, S.A., Beck, J.C.: Improved non-deterministic planning by exploiting state relevance. In: Proceedings of the 22nd International Conference on Automated Planning and Scheduling, ICAPS (2012)
Nebel, B., Dornhege, C., Hertle, A.: How much does a household robot need to know in order to tidy up your home? In: AAAI Workshop on Intelligent Robotic Systems (2013)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Hertle, A., Dornhege, C., Keller, T., Mattmüller, R., Ortlieb, M., Nebel, B. (2014). An Experimental Comparison of Classical, FOND and Probabilistic Planning. In: Lutz, C., Thielscher, M. (eds) KI 2014: Advances in Artificial Intelligence. KI 2014. Lecture Notes in Computer Science(), vol 8736. Springer, Cham. https://doi.org/10.1007/978-3-319-11206-0_29
Download citation
DOI: https://doi.org/10.1007/978-3-319-11206-0_29
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-11205-3
Online ISBN: 978-3-319-11206-0
eBook Packages: Computer ScienceComputer Science (R0)