Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-27T19:53:13.676Z Has data issue: false hasContentIssue false
  • English
  • Français

A review of generalized planning

Published online by Cambridge University Press:  12 March 2019

Sergio Jiménez ,
Javier Segovia-Aguas  and
Anders Jonsson
Sergio Jiménez
Affiliation:
Departamento de Sistemas Informáticos y Computación, Universitat Politècnica de València, Camino de Vera s/n. 46022 Valencia, Spain e-mail: [email protected]
Javier Segovia-Aguas
Affiliation:
Information and Communication Technologies, Universitat Pompeu Fabra, Roc Boronat 138, 08018 Barcelona, Spain e-mail: [email protected], [email protected]
Anders Jonsson
Affiliation:
Information and Communication Technologies, Universitat Pompeu Fabra, Roc Boronat 138, 08018 Barcelona, Spain e-mail: [email protected], [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Generalized planning studies the representation, computation and evaluation of solutions that are valid for multiple planning instances. These are topics studied since the early days of AI. However, in recent years, we are experiencing the appearance of novel formalisms to compactly represent generalized planning tasks, the solutions to these tasks (called generalized plans) and efficient algorithms to compute generalized plans. The paper reviews recent advances in generalized planning and relates them to existing planning formalisms, such as planning with domain control knowledge and approaches for planning under uncertainty, that also aim at generality.

Type
Review
Information
The Knowledge Engineering Review , Volume 34 , 2019 , e5
Copyright
© Cambridge University Press, 2019 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Albore, A., Palacios, H. & Geffner, H. 2009. A translation-based approach to contingent planning. In IJCAI.Google Scholar
Albore, A., Ramrez, M. & Geffner, H. 2011. Effective heuristics and belief tracking for planning with incomplete information. In ICAPS.Google Scholar
Alford, R., Kuter, U. & Nau, D. S. 2009. Translating htns to PDDL: a small amount of domain knowledge can go a long way. In IJCAI.Google Scholar
Alur, R., Bodik, R., Juniwal, G., Martin, M. M. K., Raghothaman, M., Seshia, S. A., Singh, R., Solar-Lezama, A., Torlak, E. & Udupa, A. 2015. Syntax-guided synthesis. Dependable Software Systems Engineering 40, 1–25.Google Scholar
Bacchus, F. & Kabanza., F. 2000. Using temporal logics to express search control knowledge for planning. Artificial Intelligence 116(1), 123–191.Google Scholar
Bäckström, C., Jonsson, A. & Jonsson, P. 2014. Automaton plans. Journal of Artificial Intelligence Research 51, 255–291.Google Scholar
Baier, J. A., Fritz, C. & McIlraith, S. A. 2007. Exploiting procedural domain control knowledge in state-of-the-art planners. In ICAPS.Google Scholar
Bernhard, N. 2000. On the compilability and expressive power of propositional planning formalisms. Journal of Artificial Intelligence Research 12, 271–315.Google Scholar
Bonet, B. & Geffner, H. 2014. Belief tracking for planning with sensing: width, complexity and approximations. Journal of Artificial Intelligence Research 50, 923–970.Google Scholar
Bonet, B. & Geffner, H. 2015. Policies that generalize: solving many planning problems with the same policy. In IJCAI.Google Scholar
Bonet, B., Palacios, H. & Geffner, H. 2010. Automatic derivation of finite-state machines for behavior control. In AAAI.Google Scholar
Borrajo, D., Roubickova, A. & Serina, I. 2015. Progress in case-based planning. ACM Computing Surveys (CSUR) 47(2), 35.Google Scholar
Botea, A., Enzenberger, M., Müller, M. & Schaeffer, J. 2005. Macro-ff: improving AI planning with automatically learned macro-operators. Journal of Artificial Intelligence Research 24, 581–621.Google Scholar
Cimatti, A., Pistore, M., Roveri, M. & Traverso, P. 2003. Weak, strong, and strong cyclic planning via symbolic model checking. Artificial Intelligence 147(1–2), 35–84.Google Scholar
Cimatti, A., Roveri, M. & Bertoli, P. 2004. Conformant planning via symbolic model checking and heuristic search. Artificial Intelligence 159(1–2), 127–206.Google Scholar
Claßen, J., Engelmann, V., Lakemeyer, G. & Röger, G. 2008. Integrating golog and planning: an empirical evaluation. In Non-Monotonic Reasoning Workshop.Google Scholar
Clarke, E. M., Grumberg, O. & Peled, D. 1999. Model checking. MIT press.Google Scholar
Coles, A. & Smith, A. 2007. Marvin: a heuristic search planner with online macro-action learning. Journal of Artificial Intelligence Research 28, 119–156.Google Scholar
Craven, M. & Slattery, S. 2001. Relational learning with statistical predicate invention: better models for hypertext. Machine Learning 43(1), 97–119.Google Scholar
Cresswell, S. & Alexandra, M. 2004. Coddington. Compilation of LTL goal formulas into PDDL. In ECAI.Google Scholar
Domshlak, C. 2013. Fault tolerant planning: complexity and compilation. In ICAPS.Google Scholar
Fern, A., Khardon, R. & Tadepalli, P. 2011. The first learning track of the international planning competition. Machine Learning 84(1–2), 81–107.Google Scholar
Fern, A., Yoon, S. & Givan, R. 2006. Approximate policy iteration with a policy language bias: solving relational markov decision processes. Journal of Artificial Intelligence Research 25, 75–118.Google Scholar
Fikes, R. E., Hart, P. E. & Nilsson, N. J. 1972. Learning and executing generalized robot plans. Artificial intelligence 3, 251–288.Google Scholar
Fox, M., Gerevini, A., Long, D. & Serina, I. 2006. Plan stability: replanning versus plan repair. In ICAPS.Google Scholar
Fox, M. & Long, D. 2003. Pddl2. 1: an extension to pddl for expressing temporal planning domains. Journal of Artificial Intelligence Research 20, 61–124.Google Scholar
Francès, G. & Geffner, H. 2015. Modeling and computation in planning: better heuristics from more expressive languages. In ICAPS.Google Scholar
Francès, G. & Geffner, H. 2016. E-strips: existential quantification in planning and constraint satisfaction. In IJCAI.Google Scholar
Frances, G., Ramrez, M., Lipovetzky, N. & Geffner, H. 2017. Purely declarative action representations are overrated: classical planning with simulators. In IJCAI.Google Scholar
Fritz, C., Baier, J. A. & McIlraith, S. A. 2008. Congolog, sin trans: compiling congolog into basic action theories for planning and beyond. In KR.Google Scholar
Geffner, H. & Bonet, B. 2013. A concise introduction to models and methods for automated planning. Synthesis Lectures on Artificial Intelligence and Machine Learning 8(1), 1–141.Google Scholar
Gerevini, A. & Long, D. 2005. Plan constraints and preferences in pddl3. The language of the fifth international planning competition. Technical Report, Department of Electronics for Automation, University of Brescia, 75.Google Scholar
Ghallab, M., Nau, D. & Traverso, P. 2004. Automated Planning: Theory and Practice. Elsevier.Google Scholar
Gulwani, S. 2011. Automating string processing in spreadsheets using input-output examples. In ACM SIGPLAN Notices 46, 317–330. ACM.Google Scholar
Gulwani, S., Hernandez-Orallo, J., Kitzelmann, E., Muggleton, S. H., Schmid, U. & Zorn, B. 2015. Inductive programming meets the real world. Communications of the ACM 58, 90–99.Google Scholar
Hector, J. 2005. Levesque. Planning with loops. In IJCAI.Google Scholar
Helmert, M. 2006. The fast downward planning system. Journal of Artificial Intelligence Research 26, 191–246.Google Scholar
Hoffmann, J. 2015. Simulated penetration testing: From dijkstra to turing test++. In ICAPS.Google Scholar
Hoffmann, J. & Brafman, R. I. 2006. Conformant planning via heuristic forward search: a new approach. Artificial Intelligence 170(6–7), 507–541.Google Scholar
Hoffmann, J., Porteous, J. & Sebastia, L. 2004. Ordered landmarks in planning. Journal of Artificial Intelligence Research 22, 215–278.Google Scholar
Howey, R., Long, D. & Fox, M. 2004. Val: automatic plan validation, continuous effects and mixed initiative planning using pddl. In ICTAI.Google Scholar
Hu, Y. & Giacomo, G. D. 2011. Generalized planning: synthesizing plans that work for multiple environments. In IJCAI.Google Scholar
Hu, Y. & Giacomo, G. D. 2013. A generic technique for synthesizing bounded finite-state controllers. In ICAPS.Google Scholar
Hu, Y. & Levesque, H. J. 2011. A correctness result for reasoning about one-dimensional planning problems. In IJCAI.Google Scholar
Ivankovic, F. & Haslum, P. 2015. Optimal planning with axioms. In IJCAI.Google Scholar
Jiménez, S. & Jonsson, A. 2015. Computing plans with control flow and procedures using a classical planner. In SOCS.Google Scholar
Jonsson, A. 2009. The role of macros in tractable planning. Journal of Artificial Intelligence Research 36, 471–511.Google Scholar
Khardon, R. 1999. Learning action strategies for planning domains. Artificial Intelligence 113(1), 125–148.Google Scholar
Kolobov, A. 2012. Planning with markov decision processes: an AI perspective. Synthesis Lectures on Artificial Intelligence and Machine Learning 6(1), 1–210.Google Scholar
Lake, B. M., Salakhutdinov, R. & Tenenbaum, J. B. 2015. Human-level concept learning through probabilistic program induction. Science 350(6266), 1332–1338.Google Scholar
Leung, A., Sarracino, J. & Lerner, S. 2015. Interactive parser synthesis by example. In ACM SIGPLAN Notices, 50, 565–574. ACM.Google Scholar
Levesque, H. J., Reiter, R., Lespérance, Y., Lin, F. & Scherl, R. B. 1997. Golog: a logic programming language for dynamic domains. The Journal of Logic Programming 31(1–3), 59–83.Google Scholar
Long, D. & Fox, M. 2003. The 3rd international planning competition: results and analysis. Journal of Artificial Intelligence Research 20, 1–59.Google Scholar
Lotinac, D., Segovia-Aguas, J., Jiménez, S. & Jonsson, A. 2016. Automatic generation of high-level state features for generalized planning. In IJCAI.Google Scholar
Lukás, C. 2010. Generation of macro-operators via investigation of action dependencies in plans. The Knowledge Engineering Review 25(3), 281–297.Google Scholar
Marthi, B., Russell, S. J. & Wolfe, J. A. 2007. Angelic semantics for high-level actions. In ICAPS.Google Scholar
Martn, M. & Geffner, H. 2004. Learning generalized policies from planning examples using concept languages. Applied Intelligence 20(1), 9–19.Google Scholar
Mausam, & Kolobov, A. 2012. Planning with markov decision processes: an AI perspective. Morgan & Claypool Publishers.Google Scholar
McDermott, D., Ghallab, M., Howe, A., Knoblock, C., Ram, A., Veloso, M., Weld, D. & Wilkins, D. 1998. Pddl-the planning domain definition language.Google Scholar
Mitchell, T. M. 1982. Generalization as search. Artificial Intelligence 18, 203–226.Google Scholar
Mitchell, T. M. 1997. Machine Learning, 1st edition. McGraw-Hill Inc.Google Scholar
Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G. & Petersen, S. 2015. Human-level control through deep reinforcement learning. Nature 518(7540), 529–533.Google Scholar
Muggleton, S. 1999. Inductive logic programming: issues, results and the challenge of learning language in logic. Artificial Intelligence 114(1), 283–296.Google Scholar
Muise, C. J., Belle, V. & McIlraith, S. A. 2014. Computing contingent plans via fully observable non-deterministic planning. In AAAI.Google Scholar
Muise, C., McIlraith, S. A. & Belle, V. 2014. Non-deterministic planning with conditional effects. In ICAPS.Google Scholar
Nau, D. S., Au, T.-C., Ilghami, O., Kuter, U., Murdock, J. W., Wu, D. & Yaman, F. 2003. Shop2: An HTN planning system. Journal of Artificial Intelligence Research 20, 379–404.Google Scholar
Newell, A., Shaw, J. C. & Simon, H. A. 1959. A general problem-solving program for a computer. Computers and Automation 8(7), 10–16.Google Scholar
Palacios, H. & Geffner, H. 2009. Compiling uncertainty away in conformant planning problems with bounded width. Journal of Artificial Intelligence Research 35, 623–675.Google Scholar
Pan, S. J. & Yang, Q. 2010. A survey on transfer learning. IEEE Transactions on Knowledge and Data Engineering 22(10), 1345–1359.Google Scholar
Pednault, E. P. D. 1989. Adl: Exploring the middle ground between strips and the situation calculus. In KR.Google Scholar
Petrick, R. P. A. & Bacchus, F. 2004. Extending the knowledge-based approach to planning with incomplete information and sensing. In ICAPS.Google Scholar
Porco, A., Machado, A. & Bonet, B. 2011. Automatic polytime reductions of np problems into a fragment of strips. In ICAPS.Google Scholar
Pralet, C., Verfaillie, G., Lematre, M. & Infantes, G. 2010. Constraint-based controller synthesis in non-deterministic and partially observable domains. In ECAI.Google Scholar
Ross Quinlan, J. 1990. Learning logical definitions from relations. Machine Learning 5, 239–266.Google Scholar
Ramírez, M. & Geffner, H. 2010. Probabilistic plan recognition using off-the-shelf classical planners. In AAAI.Google Scholar
Ramirez, M. & Geffner, H. 2016. Heuristics for planning, plan recognition and parsing. arXiv preprint arXiv:1605.05807.Google Scholar
Rintanen, J. 2012. Planning as satisfiability: heuristics. Artificial Intelligence Journal 193, 45–86.Google Scholar
Rintanen, J. 2015. Impact of modeling languages on the theory and practice in planning research. In AAAI, 4052–4056.Google Scholar
Röger, G., Helmert, M. & Nebel, B. 2008. On the relative expressiveness of adl and golog: the last piece in the puzzle. In KR.Google Scholar
Rosa, T. D. L., Jiménez, S., Fuentetaja, R. & Borrajo, D. 2011. Scaling up heuristic planning with relational decision trees. Journal of Artificial Intelligence Research 40, 767–813.Google Scholar
Sardina, S., Giacomo, G. D., Lespérance, Y. & Levesque, H. J. 2004. On the semantics of deliberation in indigolog from theory to implementation. Annals of Mathematics and Artificial Intelligence 41(2–4), 259–299.Google Scholar
Scala, E., Ramirez, M., Haslum, P. & Thiebaux, S. 2016. Numeric planning with disjunctive global constraints via smt. In ICAPS.Google Scholar
Schwinghammer, J., Birkedal, L., Reus, B. & Yang, H. 2009. Nested hoare triples and frame rules for higher-order store. In International Workshop on Computer Science Logic.Google Scholar
Segovia-Aguas, J., Jiménez, S. & Jonsson, A. 2016a. Generalized planning with procedural domain control knowledge. In ICAPS.Google Scholar
Segovia-Aguas, J., Jiménez, S. & Jonsson, A. 2016b. Hierarchical finite state controllers for generalized planning. In IJCAI.Google Scholar
Segovia-Aguas, J., Jiménez, S. & Jonsson, A. 2017a. Generating context-free grammars using classical planning. In IJCAI.Google Scholar
Segovia-Aguas, J., Jiménez, S. & Jonsson, A. 2017b. Unsupervised classification of planning instances. In ICAPS.Google Scholar
Shivashankar, V., Kuter, U., Nau, D. & Alford, R. 2012. A hierarchical goal-based formalism and algorithm for single-agent planning. In AAMAS.Google Scholar
Slaney, J. & Thiébaux, S. 2001. Blocks world revisited. Artificial Intelligence 125(1), 119–153.Google Scholar
Solar-Lezama, A., Tancau, L., Bodik, R., Seshia, S. & Saraswat, V. 2006. Combinatorial sketching for finite programs. ACM SIGOPS Operating Systems Review 40, 404–415.Google Scholar
Srivastava, S., Immerman, N. & Zilberstein, S. 2011a. A new representation and associated algorithms for generalized planning. Artificial Intelligence 175(2), 615–647.Google Scholar
Srivastava, S., Immerman, N., Zilberstein, S. & Zhang, T. 2011b. Directed search for generalized plans using classical planners. In ICAPS.Google Scholar
Thiébaux, S., Hoffmann, J. & Nebel, B. 2005. In defense of pddl axioms. Artificial Intelligence 168(1), 38–69.Google Scholar
Torlak, E. & Bodik, R. 2013. Growing solver-aided languages with rosette. In ACM international symposium on New ideas, new paradigms, and reflections on programming & software, 135–152. ACM.Google Scholar
Utgoff, P. E. 1989. Incremental induction of decision trees. Machine Learning 4(2), 161–186.Google Scholar
Vallati, M., Chrpa, L., Grzes, M., McCluskey, T. L., Roberts, M. & Sanner, S. 2015. The 2014 international planning competition: progress and trends. AI Magazine 36(3), 90–98.Google Scholar
Veloso, M., Carbonell, J., Perez, A., Borrajo, D., Fink, E. & Blythe, J. 1995. Integrating planning and learning: the prodigy architecture. Journal of Experimental & Theoretical Artificial Intelligence 7(1), 81–120.Google Scholar
Winner, E. & Veloso, M. 2003. Distill: learning domain-specific planners by example. In ICML.Google Scholar
Winner, E. & Veloso, M. 2007. Loopdistill: Learning looping domain-specific planners from example plans. In ICAPS, Workshop on Artificial Intelligence Planning and Learning.Google Scholar
Yoon, S., Fern, A. & Givan, R. 2008. Learning control knowledge for forward search planning. The Journal of Machine Learning Research 9, 683–718.Google Scholar
Younes, H. L. S. & Littman, M. L. 2004. PPDDL1. 0: an extension to pddl for expressing planning domains with probabilistic effects. Technical Report, CMU-CS-04-162.Google Scholar