×

zbMATH — the first resource for mathematics

Computing programs for generalized planning using a classical planner. (English) Zbl 07099202
Summary: Generalized planning is the task of generating a single solution (a generalized plan) that is valid for multiple planning instances. In this paper we introduce a novel formalism for representing generalized plans that borrows two mechanisms from structured programming: control flow and procedure calls. On one hand, control flow structures allow to compactly represent generalized plans. On the other hand, procedure calls allow to represent hierarchical and recursive solutions as well as to reuse existing generalized plans. The paper also presents a compilation from generalized planning into classical planning which allows us to compute generalized plans with off-the-shelf planners. The compilation can incorporate prior knowledge in the form of auxiliary procedures which expands the applicability of the approach to more challenging tasks. Experiments show that a classical planner using our compilation can compute generalized plans that solve a wide range of generalized planning tasks, including sorting lists of variable size or DFS traversing variable-size binary trees. Additionally the paper presents an extension of the compilation for computing generalized plans when generalization requires a high-level state representation that is not provided a priori. This extension brings a new landscape of benchmarks to classical planning since classification tasks can naturally be modeled as generalized planning tasks, and hence, as classical planning tasks. Finally the paper shows that the compilation can be extended to compute control knowledge for off-the-shelf planners and solve planning instances that are difficult to solve without such additional knowledge.
MSC:
68T Artificial intelligence
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Winner, E.; Veloso, M., Distill: learning domain-specific planners by example, (International Conference on Machine Learning, (2003)), 800-807
[2] Bonet, B.; Palacios, H.; Geffner, H., Automatic derivation of finite-state machines for behavior control, (AAAI Conference on Artificial Intelligence, (2010))
[3] Hu, Y.; Levesque, H. J., A correctness result for reasoning about one-dimensional planning problems, (International Joint Conference on Artificial Intelligence, (2011)), 2638-2643
[4] Srivastava, S.; Immerman, N.; Zilberstein, S.; Zhang, T., Directed search for generalized plans using classical planners, (International Conference on Automated Planning and Scheduling, (2011)), 226-233
[5] Hu, Y.; De Giacomo, G., A generic technique for synthesizing bounded finite-state controllers, (International Conference on Automated Planning and Scheduling, (2013))
[6] Khardon, R., Learning action strategies for planning domains, Artif. Intell., 113, 1, 125-148, (1999) · Zbl 0943.68130
[7] Martín, M.; Geffner, H., Learning generalized policies from planning examples using concept languages, Appl. Intell., 20, 9-19, (2004) · Zbl 1078.68713
[8] Baier, J. A.; Fritz, C.; McIlraith, S. A., Exploiting procedural domain control knowledge in state-of-the-art planners, (ICAPS, (2007)), 26-33
[9] Jiménez, S.; Jonsson, A., Computing plans with control flow and procedures using a classical planner, (Proceedings of the Eighth Annual Symposium on Combinatorial Search. Proceedings of the Eighth Annual Symposium on Combinatorial Search, SOCS-15, (2015)), 62-69
[10] Segovia-Aguas, J.; Jiménez, S.; Jonsson, A., Generalized planning with procedural domain control knowledge, (Proceedings of the International Conference on Automated Planning and Scheduling, (2016))
[11] Lotinac, D.; Segovia, J.; Jiménez, S.; Jonsson, A., Automatic generation of high-level state features for generalized planning, (International Joint Conference on Artificial Intelligence, (2016))
[12] Botea, A.; Enzenberger, M.; Müller, M.; Schaeffer, J., Macro-ff: improving AI planning with automatically learned macro-operators, J. Artif. Intell. Res., 24, 581-621, (2005) · Zbl 1080.68657
[13] Coles, A.; Smith Marvin, A., A heuristic search planner with online macro-action learning, J. Artif. Intell. Res., 28, 119-156, (2007) · Zbl 1182.68231
[14] Jonsson, A., The role of macros in tractable planning, J. Artif. Intell. Res., 471-511, (2009) · Zbl 1185.68642
[15] Yoon, S.; Fern, A.; Givan, R., Learning control knowledge for forward search planning, J. Mach. Learn. Res., 9, 683-718, (2008) · Zbl 1225.68246
[16] De la Rosa, T.; Jiménez, S.; Fuentetaja, R.; Borrajo, D., Scaling up heuristic planning with relational decision trees, J. Artif. Intell. Res., 767-813, (2011) · Zbl 1216.68242
[17] Rintanen, J., Planning as satisfiability: heuristics, Artif. Intell. J., 193, 45-86, (2012) · Zbl 1270.68276
[18] Pralet, C.; Verfaillie, G.; Lemaître, M.; Infantes, G., Constraint-based controller synthesis in non-deterministic and partially observable domains, (European Conference on Artificial Intelligence, (2010)), 681-686 · Zbl 1211.93047
[19] Fox, M.; Gerevini, A.; Long, D.; Serina, I., Plan stability: replanning versus plan repair, (ICAPS, vol. 6, (2006)), 212-221
[20] Borrajo, D.; Roubíčková, A.; Serina, I., Progress in case-based planning, ACM Comput. Surv., 47, 2, 35, (2015)
[21] Levesque, H. J.; Reiter, R.; Lespérance, Y.; Lin, F.; Scherl, R. B., Golog: a logic programming language for dynamic domains, J. Funct. Logic Program., 31, 1-3, 59-83, (1997) · Zbl 0880.68008
[22] Sardina, S.; De Giacomo, G.; Lespérance, Y.; Levesque, H. J., On the semantics of deliberation in indigolog—from theory to implementation, Ann. Math. Artif. Intell., 41, 2-4, 259-299, (2004) · Zbl 1048.68100
[23] Röger, G.; Helmert, M.; Nebel, B., On the relative expressiveness of adl and golog: the last piece in the puzzle, (KR, (2008))
[24] Claßen, J.; Engelmann, V.; Lakemeyer, G.; Röger, G., Integrating golog and planning: an empirical evaluation, (Non-Monotonic Reasoning Workshop, (2008))
[25] Srivastava, S.; Immerman, N.; Zilberstein, S., A new representation and associated algorithms for generalized planning, Artif. Intell., 175, 2, 615-647, (2011) · Zbl 1216.68253
[26] Albore, A.; Palacios, H.; Geffner, H., A translation-based approach to contingent planning, (International Joint Conference on Artificial Intelligence, (2009))
[27] Boutilier, C.; Reiter, R.; Price, B., Symbolic dynamic programming for first-order mdps, (IJCAI, vol. 1, (2001)), 690-700
[28] Gretton, C.; Thiébaux, S., Exploiting first-order regression in inductive policy selection, (Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence, (2004), AUAI Press), 217-225
[29] Gulwani, S., Automating String Processing in Spreadsheets Using Input-Output Examples, ACM SIGPLAN Not., vol. 46, 317-330, (2011), ACM · Zbl 1284.68700
[30] Solar-Lezama, A.; Tancau, L.; Bodik, R.; Seshia, S.; Saraswat, V., Combinatorial sketching for finite programs, Oper. Syst. Rev., 40, 404-415, (2006)
[31] Lake, B. M.; Salakhutdinov, R.; Tenenbaum, J. B., Human-level concept learning through probabilistic program induction, Science, 350, 6266, 1332-1338, (2015) · Zbl 1355.68230
[32] Finkbeiner, B.; Schewe, S., Bounded synthesis, Int. J. Softw. Tools Technol. Transf., 15, 5-6, 519-539, (2013)
[33] Bacchus, F.; Kabanza, F., Using temporal logics to express search control knowledge for planning, Artif. Intell., 116, 1, 123-191, (2000) · Zbl 0939.68827
[34] Veloso, M.; Carbonell, J.; Perez, A.; Borrajo, D.; Fink, E.; Blythe, J., Integrating planning and learning: the prodigy architecture, J. Exp. Theor. Artif. Intell., 7, 1, 81-120, (1995) · Zbl 0939.68830
[35] Shivashankar, V.; Kuter, U.; Nau, D.; Alford, R., A hierarchical goal-based formalism and algorithm for single-agent planning, (Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems, vol. 2, (2012), International Foundation for Autonomous Agents and Multiagent Systems), 981-988
[36] Nau, D. S.; Au, T.-C.; Ilghami, O.; Kuter, U.; Murdock, J. W.; Wu, D.; Yaman, F., Shop2: an HTN planning system, J. Artif. Intell. Res., 20, 379-404, (2003) · Zbl 1058.68106
[37] Mitchell, T. M., Generalization as search, Artif. Intell., 18, 2, 203-226, (1982)
[38] Muggleton, S., Inductive logic programming: issues, results and the challenge of learning language in logic, Artif. Intell., 114, 1, 283-296, (1999) · Zbl 0939.68574
[39] Palacios, H.; Geffner, H., Compiling uncertainty away in conformant planning problems with bounded width, J. Artif. Intell. Res., 35, 623-675, (2009) · Zbl 1183.68584
[40] Fox, M.; Long, D., Pddl2. 1: an extension to PDDL for expressing temporal planning domains, J. Artif. Intell. Res., 20, 61-124, (2003) · Zbl 1036.68093
[41] Hu, Y.; De Giacomo, G., Generalized planning: synthesizing plans that work for multiple environments, (International Joint Conference on Artificial Intelligence, (2011)), 918-923
[42] Fern, A.; Khardon, R.; Tadepalli, P., The first learning track of the international planning competition, Mach. Learn., 84, 1-2, 81-107, (2011)
[43] Jiménez, S.; De La Rosa, T.; Fernández, S.; Fernández, F.; Borrajo, D., A review of machine learning for automated planning, Knowl. Eng. Rev., 27, 04, 433-467, (2012)
[44] Bylander, T., The computational complexity of propositional STRIPS planning, Artif. Intell., 69, 165-204, (1994) · Zbl 0821.68065
[45] Helmert, M., The fast downward planning system, J. Artif. Intell. Res., 26, 191-246, (2006) · Zbl 1182.68245
[46] Richter, S.; Westphal, M., The LAMA planner: guiding cost-based anytime planning with landmarks, J. Artif. Intell. Res., 39, 127-177, (2010) · Zbl 1205.68383
[47] Ramirez, M.; Lipovetzky, N.; Muise, C., Lightweight automated planning ToolKiT, (2015)
[48] Domshlak, C., Fault tolerant planning: complexity and compilation, (Proceedings of the Twenty-Third International Conference on Automated Planning and Scheduling. Proceedings of the Twenty-Third International Conference on Automated Planning and Scheduling, ICAPS, (2013))
[49] Shivashankar, V.; Kuter, U.; Nau, D.; Alford, R., A hierarchical goal-based formalism and algorithm for single-agent planning, (Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems, vol. 2, (2012), International Foundation for Autonomous Agents and Multiagent Systems), 981-988
[50] Hogg, C.; Munoz-Avila, H.; Kuter, U., HTN-maker: learning HTNs with minimal additional knowledge engineering required, (AAAI, (2008)), 950-956
[51] Lotinac, D.; Jonsson, A., Constructing hierarchical task models using invariance analysis, (European Conference on Artificial Intelligence, (2016))
[52] Marthi, B.; Russell, S.; Wolfe, J., Angelic semantics for high-level actions, (Proceedings of the Seventeenth International Conference on Automated Planning and Scheduling. Proceedings of the Seventeenth International Conference on Automated Planning and Scheduling, ICAPS, (2007)), 232-239
[53] Alford, R.; Kuter, U.; Nau, D. S., Translating HTNs to PDDL: a small amount of domain knowledge can go a long way, (International Joint Conference on Artificial Intelligence, (2009)), 1629-1634
[54] Zimmerman, T.; Kambhampati, S., Learning-assisted automated planning: looking back, taking stock, going forward, AI Mag., 24, 2, 73, (2003)
[55] Bishop, C. M., Pattern Recognition and Machine Learning, (2006), Springer · Zbl 1107.68072
[56] Cresswell, S.; Coddington, A. M., Compilation of ltl goal formulas into PDDL, (ECAI, (2004)), 985-986
[57] Hoffmann, J.; Edelkamp, S., The deterministic part of ipc-4: an overview, J. Artif. Intell. Res., 519-579, (2005) · Zbl 1080.68669
[58] Thiébaux, S.; Hoffmann, J.; Nebel, B., In defense of PDDL axioms, Artif. Intell., 168, 1, 38-69, (2005) · Zbl 1132.68714
[59] Ivankovic, F.; Haslum, P., Optimal planning with axioms, (International Joint Conference on Artificial Intelligence, (2015), AAAI Press), 1580-1586
[60] Chandra, A.; Merlin, P., Optimal implementation of conjunctive queries in relational data bases, (Proceedings of the Ninth Annual ACM Symposium on Theory of Computing, (1977))
[61] Michalski, R. S.; Carbonell, J. G.; Mitchell, T. M., Machine Learning: An Artificial Intelligence Approach, (2013), Springer Science & Business Media
[62] Levesque, H. J., Planning with loops, (IJCAI, (2005)), 509-515
[63] Patrizi, F.; Lipoveztky, N.; De Giacomo, G.; Geffner, H., Computing infinite plans for ltl goals using a classical planner, (Twenty-Second International Joint Conference on Artificial Intelligence, (2011))
[64] Frances, G.; Geffner, H., ∃-strips: existential quantification in planning and constraint satisfaction, (IJCAI, (2016)), 3082-3088
[65] Fern, A.; Yoon, S. W.; Givan, R., Learning domain-specific control knowledge from random walks, (ICAPS, (2004)), 191-199
[66] Fuentetaja, R.; Borrajo, D., Improving control-knowledge acquisition for planning by active learning, (Machine Learning: ECML 2006: Proceedings of the 17th European Conference on Machine Learning. Machine Learning: ECML 2006: Proceedings of the 17th European Conference on Machine Learning, Berlin, Germany, September 18-22, 2006, (2006)), 138-149
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.