×

zbMATH — the first resource for mathematics

Concise finite-domain representations for PDDL planning tasks. (English) Zbl 1191.68635
Summary: We introduce an efficient method for translating planning tasks specified in the standard PDDL formalism into a concise grounded representation that uses finite-domain state variables instead of the straight-forward propositional encoding. Translation is performed in four stages. Firstly, we transform the input task into an equivalent normal form expressed in a restricted fragment of PDDL. Secondly, we synthesize invariants of the planning task that identify groups of mutually exclusive propositions which can be represented by a single finite-domain variable. Thirdly, we perform an efficient relaxed reachability analysis using logic programming techniques to obtain a grounded representation of the input. Finally, we combine the results of the third and fourth stage to generate the final grounded finite-domain representation.The presented approach has originally been implemented as part of the Fast Downward planning system for the 4th International Planning Competition (IPC4). Since then, it has been used in a number of other contexts with considerable success, and the use of concise finite-domain representations has become a common feature of state-of-the-art planners.

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Software:
PDDL; CPlan
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ausiello, G.; Crescenzi, P.; Gambosi, G.; Kann, V.; Marchetti-Spaccamela, A.; Protasi, M., Complexity and approximation, (1999), Springer-Verlag · Zbl 0937.68002
[2] Bäckström, C.; Nebel, B., Complexity results for SAS^{+} planning, Computational intelligence, 11, 4, 625-655, (1995)
[3] J. Benton, M. van den Briel, S. Kambhampati, A hybrid linear programming and relaxed plan heuristic for partial satisfaction planning problems, in: Boddy et al. [4], pp. 34-41
[4] ()
[5] Bonet, B.; Geffner, H., Planning as heuristic search, Artificial intelligence, 129, 1, 5-33, (2001) · Zbl 0971.68146
[6] Bylander, T., The computational complexity of propositional STRIPS planning, Artificial intelligence, 69, 1-2, 165-204, (1994) · Zbl 0821.68065
[7] Y. Chen, X. Zhao, W. Zhang, Long-distance mutual exclusion for propositional planning, in: M.M. Veloso (Ed.), Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI 2007), 2007
[8] Creignou, N.; Khanna, S.; Sudan, M., Complexity classifications of Boolean constraint satisfaction problems, SIAM monographs on discrete mathematics and applications, vol. 7, (2001), SIAM · Zbl 0981.68058
[9] S. Cresswell, M. Fox, D. Long, Extending TIM domain analysis to handle ADL constructs, in: AIPS ’02 Workshop on Knowledge Engineering Tools and Techniques for A.I. Planning, 2002
[10] Dechter, R., Constraint processing, (2003), Morgan Kaufmann
[11] Do, M.B.; Kambhampati, S., Planning as constraint satisfaction: solving the planning graph by compiling it into CSP, Artificial intelligence, 132, 2, 151-182, (2001) · Zbl 0983.68181
[12] Dowling, W.F.; Gallier, J.H., Linear-time algorithms for testing the satisfiability of propositional Horn formulae, Journal of logic programming, 1, 3, 367-383, (1984)
[13] Ebbinghaus, H.-D.; Flum, J.; Thomas, W., Mathematical logic, (1994), Springer-Verlag · Zbl 0795.03001
[14] S. Edelkamp, Planning with pattern databases, in: A. Cesta, D. Borrajo (Eds.), Pre-proceedings of the Sixth European Conference on Planning (ECP’01), Toledo, Spain, 2001
[15] Edelkamp, S.; Helmert, M., Exhibiting knowledge in planning problems to minimize state encoding length, ()
[16] S. Edelkamp, M. Helmert, On the implementation of MIPS, in: P. Traverso, M. Veloso, F. Giunchiglia (Eds.), Proceedings of the AIPS-2000 Workshop on Model-Theoretic Approaches to Planning, 2000
[17] Edelkamp, S.; Helmert, M., The model checking integrated planning system (MIPS), AI magazine, 22, 3, 67-71, (2001)
[18] S. Edelkamp, J. Hoffmann, PDDL2.2: The language for the classical part of the 4th International Planning Competition, Tech. Rep. 195, Albert-Ludwigs-Universität Freiburg, Institut für Informatik, 2004
[19] Erol, K.; Nau, D.S.; Subrahmanian, V.S., Complexity, decidability and undecidability results for domain-independent planning, Artificial intelligence, 76, 1-2, 65-88, (1995) · Zbl 1013.68548
[20] Fox, M.; Long, D., The automatic inference of state invariants in TIM, Journal of artificial intelligence research, 9, 367-421, (1998) · Zbl 0910.68199
[21] Fox, M.; Long, D., PDDL2.1: an extension to PDDL for expressing temporal planning domains, Journal of artificial intelligence research, 20, 61-124, (2003) · Zbl 1036.68093
[22] Garey, M.R.; Johnson, D.S., Computers and intractability — A guide to the theory of NP-completeness, (1979), Freeman · Zbl 0411.68039
[23] Gazen, B.C.; Knoblock, C.A., Combining the expressivity of UCPOP with the efficiency of graphplan, ()
[24] A. Gerevini, D. Long, Plan constraints and preferences in PDDL3, Tech. Rep. R. T. 2005-08-47, Dipartimento di Elettronica per l’Automazione, Università degli Studi di Brescia, 2005
[25] Gerevini, A.; Schubert, L., Inferring state constraints for domain-independent planning, ()
[26] A. Gerevini, L. Schubert, Discovering state constraints for planning: DISCOPLAN, Tech. Rep. 2005-09-48, Department of Electronics for Automation, University of Brescia, 2005
[27] Haslum, P.; Botea, A.; Helmert, M.; Bonet, B.; Koenig, S., Domain-independent construction of pattern database heuristics for cost-optimal planning, ()
[28] Helmert, M., A planning heuristic based on causal graph analysis, ()
[29] Helmert, M., The fast downward planning system, Journal of artificial intelligence research, 26, 191-246, (2006) · Zbl 1182.68245
[30] M. Helmert, H. Geffner, Unifying the causal graph and additive heuristics, in: Proceedings of the Eighteenth International Conference on Automated Planning and Scheduling (ICAPS 2008), 2008
[31] M. Helmert, P. Haslum, J. Hoffmann, Flexible abstraction heuristics for optimal sequential planning, in: Boddy et al. [4], pp. 176-183
[32] Hoffmann, J., Where ‘ignoring delete lists’ works: local search topology in planning benchmarks, Journal of artificial intelligence research, 24, 685-758, (2005) · Zbl 1080.68668
[33] Hoffmann, J.; Nebel, B., The FF planning system: fast plan generation through heuristic search, Journal of artificial intelligence research, 14, 253-302, (2001) · Zbl 0970.68044
[34] Jonsson, P.; Bäckström, C., State-variable planning under structural restrictions: algorithms and complexity, Artificial intelligence, 100, 1-2, 125-176, (1998) · Zbl 0906.68140
[35] Kautz, H.; Selman, B., Planning as satisfiability, ()
[36] Kautz, H.; Selman, B., Pushing the envelope: planning, propositional logic, and stochastic search, ()
[37] J. Koehler, J. Hoffmann, Handling of inertia in a planning system, Tech. Rep. 122, Albert-Ludwigs-Universität Freiburg, Institut für Informatik, 1999
[38] McDermott, D., The 1998 AI planning systems competition, AI magazine, 21, 2, 35-55, (2000)
[39] Pednault, E.P.D., ADL: exploring the middle ground between STRIPS and the situation calculus, ()
[40] Richter, S.; Helmert, M.; Westphal, M., Landmarks revisited, ()
[41] Rintanen, J., A planning algorithm not based on directional search, () · Zbl 0916.68139
[42] Rintanen, J., An iterative algorithm for synthesizing invariants, ()
[43] J. Rintanen, Compact representation of sets of binary constraints, in: Proceedings of the 17th European Conference on Artificial Intelligence (ECAI 2006), 2006
[44] U. Scholz, Extracting state constraints from PDDL-like planning domains, in: AIPS-2000 Workshop on Analyzing and Exploiting Domain Knowledge for Efficient Planning, 2000
[45] Ullman, J.D., Principles of database and knowledge-base systems, vol. I: classical database systems, (1988), Computer Science Press
[46] Ullman, J.D., Principles of database and knowledge-base systems, vol. II: the new technologies, (1989), Computer Science Press
[47] van Beek, P.; Chen, X., Cplan: A constraint programming approach to planning, ()
[48] van den Briel, M.; Benton, J.; Kambhampati, S.; Vossen, T., An LP-based heuristic for optimal planning, () · Zbl 1145.68537
[49] van den Briel, M.; Vossen, T.; Kambhampati, S., Reviving integer programming approaches for AI planning: A branch-and-cut framework, () · Zbl 1175.90058
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.