Search
  • All Journals
Advanced Search
Search articles by Title, Author, Keywords, DOI
3.9CiteScore
1.3Impact Factor
Advanced Search
MAP  >  The Knowledge Engineering Review
2019 Volume 34
Article Contents
Next Previous
REVIEW   Open Access    

A review of generalized planning

  • 1.

    Departamento de Sistemas Informáticos y Computación

  • 2.

    Information and Communication Technologies

More Information
  • 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.
  • 加载中
  • 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

  • Cite this article

    Sergio Jiménez, Javier Segovia-Aguas, Anders Jonsson. 2019. A review of generalized planning. The Knowledge Engineering Review. 34:231 doi: 10.1017/S0269888918000231
    Sergio Jiménez, Javier Segovia-Aguas, Anders Jonsson. 2019. A review of generalized planning. The Knowledge Engineering Review. 34:231 doi: 10.1017/S0269888918000231
    shu
Download PDF

Article Metrics

Article views(15) PDF downloads(778)

Other Articles By Authors

REVIEW   Open Access    

A review of generalized planning

  • 1.

    Departamento de Sistemas Informáticos y Computación

  • 2.

    Information and Communication Technologies

The Knowledge Engineering Review  34,  Article number: e5  (2019)  |  Cite this article

Abstract: 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.

    HTML

    Acknowledgments

    • This work is partially supported by grant TIN-2015-67959 and the Maria de Maeztu Units of Excellence Programme MDM-2015-0502, MEC, Spain. S. J. is supported by the Ramon y Cajal program, RYC-2015-18009, funded by the Spanish government.

    Rights and permissions
    • © Cambridge University Press, 2019 2019Cambridge University Press
References (101)
  • About this article
    Cite this article
    Sergio Jiménez, Javier Segovia-Aguas, Anders Jonsson. 2019. A review of generalized planning. The Knowledge Engineering Review. 34:231 doi: 10.1017/S0269888918000231
    Sergio Jiménez, Javier Segovia-Aguas, Anders Jonsson. 2019. A review of generalized planning. The Knowledge Engineering Review. 34:231 doi: 10.1017/S0269888918000231
    shu

    • Catalog

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return
      Return