School of Computing and Engineering, University of Huddersfield, Huddersfield HD1 3DH, UK"/>
Search
  • All Journals
Advanced Search
Search articles by Title, Author, Keywords, DOI
Submit Manuscript
7.7CiteScore
2.0Impact Factor
Advanced Search
MAP  >  The Knowledge Engineering Review
2023 Volume 38
Article Contents
Next Previous
REVIEW   Open Access    

Reformulation techniques for automated planning: a systematic review

  • School of Computing and Engineering, University of Huddersfield, Huddersfield HD1 3DH, UK

More Information
  • Abstract: Automated planning is a prominent area of Artificial Intelligence and an important component for intelligent autonomous agents. A cornerstone of domain-independent planning is the separation between planning logic, that is the automated reasoning side, and the knowledge model, that encodes a formal representation of domain knowledge needed to reason upon a given problem to synthesize a solution plan. Such a separation enables the use of reformulation techniques, which transform how a model is represented in order to improve the efficiency of plan generation. Over the past decades, significant research effort has been devoted to the design of reformulation techniques. In this paper, we present a systematic review of the large body of work on reformulation techniques for classical planning, aiming to provide a holistic view of the field and to foster future research in the area. As a tangible outcome, we provide a qualitative comparison of the existing classes of techniques, that can help researchers gain an overview of their strengths and weaknesses.
  • 加载中
  • Ai-Chang , M., Bresina , J., Charest , L., Chase , A., Hsu , J.-J., Jonsson , A., Kanefsky , B., Morris , P., Rajan , K., Yglesias , J., et al. 2004. Mapgen: mixed-initiative planning and scheduling for the mars exploration rover mission. IEEE Intelligent Systems 19(1), 8–12.

    Google Scholar

    Alhossaini , M. & Beck , J. C. 2013. Instance-specific remodelling of planning domains by adding macros and removing operators. In Tenth Symposium of Abstraction, Reformulation, and Approximation.

    Google Scholar

    Amarel , S. 1968. On representations of problems of reasoning about actions. Machine Intelligence.

    Google Scholar

    Areces , C. E., Bustos , F., Dominguez , M. & Hoffmann , J. 2014. Optimizing planning domains by automatic action schema splitting. In Twenty-Fourth International Conference on Automated Planning and Scheduling.

    Google Scholar

    Armano , G., Cherchi , G. & Vargiu , E. 2004. Automatic generation of macro-operators from static domain analysis. In Proceedings of the 16th European Conference on Artificial Intelligence, 955–956.

    Google Scholar

    Asai , M. & Fukunaga , A. 2015. Solving large-scale planning problems by decomposition and macro generation. In Proceedings of the International Conference on Automated Planning and Scheduling, 25, 16–24.

    Google Scholar

    Baryannis , G., Kritikos , K. & Plexousakis , D. 2017. A specification-based QoS-aware design framework for service-based applications. Service Oriented Computing and Applications 11(3), 301–314. ISSN 1863-2394. doi: 10.1007/s11761-017-0210-4.

    CrossRef   Google Scholar

    Baryannis , G. & Plexousakis , D. 2013. WSSL: a fluent calculus-based language for web service specifications. In 25th International Conference on Advanced Information Systems Engineering (CAiSE 2013), Salinesi , C., Norrie , M. C. & Pastor , Ó. (eds), Lecture Notes in Computer Science 7908, 256–271. Springer Berlin Heidelberg. ISBN 978-3-642-38708-1. doi: 10.1007/978-3-642-38709-8_17.

    Google Scholar

    Baryannis , G. & Plexousakis , D. 2014. Fluent calculus-based semantic web service composition and verification using WSSL. In 9th International Workshop on Semantic Web Enabled Software Engineering (SWESE2013), co-located with ICSOC 2013, Lomuscio, A., et al. (eds), Lecture Notes in Computer Science 8377, 256–270. Springer International Publishing Switzerland. doi: 10.1007/978-3-319-06859-6_23.

    Google Scholar

    Baryannis , G., Validi , S., Dani , S. & Antoniou , G. 2019. Supply chain risk management and artificial intelligence: state of the art and future research directions. International Journal of Production Research 57(7), 2179–2202. doi: 10.1080/00207543.2018.1530476.

    CrossRef   Google Scholar

    Bocchese , A. F., Fawcett , C., Vallati , M., Gerevini , A. E. & Hoos , H. H. 2018. Performance robustness of AI planners in the 2014 international planning competition. AI Community 31(6), 445–463.

    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

    Cardellini , M., Maratea , M., Vallati , M., Boleto , G. & Oneto , L. 2021. In-station train dispatching: a PDDL+ planning approach. In Proceedings of the International Conference on Automated Planning and Scheduling, 450–458.

    Google Scholar

    Castellanos-Paez , S., Rombourg , R. & Lalanda , P. 2021a. ERA: Extracting planning macro-operators from adjacent and non-adjacent sequences. In Pacific Rim Knowledge Acquisition Workshop, 30–45. Springer.

    Google Scholar

    Castellanos-Paez , S., Rombourg , R. & Lalanda , P. 2021b. On the relevance of extracting macro-operators with non-adjacent actions: does it matter? In 13th International Conference on Agents and Artificial Intelligence.

    Google Scholar

    Chrpa , L. 2010a. Combining learning techniques for classical planning: Macro-operators and entanglements. In 2010 22nd IEEE International Conference on Tools with Artificial Intelligence, 2, 79–86. IEEE.

    Google Scholar

    Chrpa , L. 2010b. Generation of macro-operators via investigation of action dependencies in plans. The Knowledge Engineering Review 25(3), 281–297.

    Google Scholar

    Chrpa , L. and Barták , R. 2009. Reformulating planning problems by eliminating unpromising actions. In Eighth Symposium on Abstraction, Reformulation, and Approximation.

    Google Scholar

    Chrpa , L. and McCluskey , T. L. 2012. On exploiting structures of classical planning problems: Generalizing entanglements. In ECAI, 240–245.

    Google Scholar

    Chrpa , L., McCluskey , T. L. & Osborne , H. 2012. Reformulating planning problems: a theoretical point of view. In 25th International Florida Artificial Intelligence Research Society Conference, 14–19.

    Google Scholar

    Chrpa , L., Scala , E. & Vallati , M. 2015a. Towards a reformulation based approach for efficient numeric planning: numeric outer entanglements. In Eighth Annual Symposium on Combinatorial Search.

    Google Scholar

    Chrpa , L. and Siddiqui , F. H. 2015. Exploiting block deordering for improving planners efficiency. In Twenty-Fourth International Joint Conference on Artificial Intelligence.

    Google Scholar

    Chrpa , L. and Vallati , M. 2019. Improving domain-independent planning via critical section macro-operators. In Proceedings of the AAAI Conference on Artificial Intelligence, 7546–7553.

    Google Scholar

    Chrpa , L. and Vallati , M. 2022. Planning with critical section macros: theory and practice. Journal of Artificial Intelligence Research.

    Google Scholar

    Chrpa , L., Vallati , M., McCluskey , T. L. and Kitchin , D. 2013. Generating macro-operators by exploiting inner entanglements. In Tenth Symposium of Abstraction, Reformulation, and Approximation.

    Google Scholar

    Chrpa , L., Vallati , M. & McCluskey , T. L. 2014. Mum: a technique for maximising the utility of macro-operators by constrained generation and use. In Twenty-Fourth International Conference on Automated Planning and Scheduling.

    Google Scholar

    Chrpa , L., Vallati , M. & McCluskey , T. L. 2015b. On the online generation of effective macro-operators. In Twenty-Fourth International Joint Conference on Artificial Intelligence.

    Google Scholar

    Chrpa , L., Vallati , M. & McCluskey , T. L. 2018. Outer entanglements: a general heuristic technique for improving the efficiency of planning algorithms. Journal of Experimental & Theoretical Artificial Intelligence 30(6), 831–856.

    Google Scholar

    Chrpa , L., Vallati , M. & McCluskey , T. L. 2019. Inner entanglements: narrowing the search in classical planning by problem reformulation. Computational Intelligence 35(2), 395–429.

    Google Scholar

    Cooper , M. C., Maris , F. & Régnier , P. 2010. Compilation of a high-level temporal planning language into PDDL 2.1. In 2010 22nd IEEE International Conference on Tools with Artificial Intelligence, 181–188.

    Google Scholar

    Corrêa , A. B., Pommerening , F., Helmert , M. & Frances , G. 2020. Lifted successor generation using query optimization techniques. In Proceedings of the International Conference on Automated Planning and Scheduling, 30, 80–89.

    Google Scholar

    Dawson , C. & Siklossy , L. 1977. The role of preprocessing in problem solving systems: “an ounce of reflection is worth a pound of backtracking”. In Proceedings of the 5th International Joint Conference on Artificial Intelligence-Volume 1, 465–471.

    Google Scholar

    Dodaro , C., Maratea , M. & Vallati , M. 2022. On the configuration of more and less expressive logic programs. In Theory and Practice of Logic Programming, 1–29. doi: 10.1017/S1471068422000096.

    CrossRef   Google Scholar

    Dulac , A., Pellier , D., Fiorino , H. & Janiszek , D. 2013. Learning useful macro-actions for planning with n-grams. In 2013 IEEE 25th International Conference on Tools with Artificial Intelligence, 803–810.

    Google Scholar

    Fikes , R. E. & Nilsson , N. J. 1971. Strips: a new approach to the application of theorem proving to problem solving. Artificial Intelligence 2(3–4), 189–208.

    Google Scholar

    Fox , M. & Long , D. 1998. The automatic inference of state invariants in TIM. Journal of Artificial Intelligence Research 9, 367–421.

    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

    Fox , M. & Long , D. 2006. Modelling mixed discrete-continuous domains for planning. Journal of Artificial Intelligence Research 27, 235–297.

    Google Scholar

    Franco , S., Vallati , M., Lindsay , A. & McCluskey , T. L. 2019. Improving planning performance in PDDL+ domains via automated predicate reformulation. In Computational Science - ICCS 491–498.

    Google Scholar

    Gerevini , A. E., Haslum , P., Long , D., Saetti , A. & Dimopoulos , Y. 2009. Deterministic planning in the fifth international planning competition: PDDL3 and experimental evaluation of the planners. Artificial Intelligence 173(5–6), 619–668.

    Google Scholar

    Gerevini , A., Saetti , A. & Vallati , M. 2014. Planning through automatic portfolio configuration: the pbp approach. Journal of Artificial Intelligence Research 50, 639–696.

    Google Scholar

    Gerevini , A. & Schubert , L. 1998. Inferring state constraints for domain-independent planning. In Proceedings of the American Artificial Intelligence Conference, AAAI/IAAI, 905–912.

    Google Scholar

    Ghallab , M., Nau , D. & Traverso , P. 2004. Automated Planning: Theory and Practice. Elsevier.

    Google Scholar

    Grastien , A. & Scala , E. 2020. CPCES: a planning framework to solve conformant planning problems through a counterexample guided refinement. Artificial Intelligence 284, 103271.

    Google Scholar

    Haslum , P. & Jonsson , P. 2000. Planning with reduced operator sets. In AIPS, 150–158.

    Google Scholar

    Hoffmann , J. & Nebel , B. 2001. The ff planning system: fast plan generation through heuristic search. Journal of Artificial Intelligence Research 14, 253–302.

    Google Scholar

    Hofmann , T., Niemueller , T. & Lakemeyer , G. 2017. Initial results on generating macro actions from a plan database for planning on autonomous mobile robots. In Twenty-Seventh International Conference on Automated Planning and Scheduling.

    Google Scholar

    Hofmann , T., Niemueller , T. & Lakemeyer , G. 2020. Macro operator synthesis for adl domains. In ECAI 2020, 761–768. IOS Press.

    Google Scholar

    Horcčk, R. and Fišer, D. 2021. Endomorphisms of lifted planning problems. In Proceedings of the International Conference on Automated Planning and Scheduling, 31, 174–183.

    Google Scholar

    Howe , A. E. and Dahlman , E. 2002. A critical assessment of benchmark comparison in planning. Journal of Artificial Intelligence Research 17, 1–33.

    Google Scholar

    Iba , G. A. 1985. Learning by discovering macros in puzzle solving. In Proceedings of the 9th International Joint Conference on Artificial Intelligence - Volume 1, 640–642.

    Google Scholar

    Iba , G. A. 1989. A heuristic approach to the discovery of macro-operators. Machine Learning 3(4), 285–317.

    Google Scholar

    Jiménez , S., De La Rosa , T., Fernández , S., Fernández , F. & Borrajo , D. 2012. A review of machine learning for automated planning. The Knowledge Engineering Review 27(4), 433–467.

    Google Scholar

    Kitchenham , B. & Charters , S. 2017. Guidelines for performing systematic literature reviews in software engineering. Technical Report EBSE-2007-01, EBSE Technical Report.

    Google Scholar

    Korf , R. E. 1985. Macro-operators: a weak method for learning. Artificial Intelligence 26(1), 35–77.

    Google Scholar

    Kovács , D. L. 2012. A multi-agent extension of PDDL3.1. In Proceedings of the 3rd Workshop on the International Planning Competition (IPC), ICAPS-2012, Atibaia, Sao Paulo, Brazil, 19–27.

    Google Scholar

    Long , D., Fox , M. & Hamdi , M. 2002. Reformulation in planning. In International Symposium on Abstraction, Reformulation, and Approximation, 18–32.

    Google Scholar

    McCluskey , T. L. 1987. Combining weak learning heuristics in general problem solvers. In Proceedings of the 10th International Joint Conference on Artificial Intelligence - Volume 1, IJCAI’87, San Francisco, CA, USA, 331–333. Morgan Kaufmann Publishers Inc.

    Google Scholar

    McCluskey , T. L. & Vallati , M. 2017. Embedding automated planning within urban traffic management operations. In Proceedings of the Twenty-Seventh International Conference on Automated Planning and Scheduling, ICAPS, 391–399. AAAI Press.

    Google Scholar

    McDermott , D. M. 2000. The 1998 AI planning systems competition. AI Magazine 21(2), 35–35.

    Google Scholar

    Minton , S. 1985. Selectively generalizing plans for problem-solving. In IJCAI, 596–599. Citeseer.

    Google Scholar

    Newton , M. H. & Levine , J. 2007. Wizard: suggesting macro-actions comprehensively. In Proceedings of the Doctoral Consortium held at ICAPS, 7.

    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

    Pednault , E. P. 1987. Formulating multiagent, dynamic-world problems in the classical planning framework. In Reasoning About Actions & Plans, 47–82. Elsevier.

    Google Scholar

    Percassi , F. & Gerevini , A. E. 2019. On compiling away PDDL3 soft trajectory constraints without using automata. In Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling, ICAPS, 320–328.

    Google Scholar

    Percassi , F., Scala , E. & Vallati , M. 2021. Translations from discretised PDDL+ to numeric planning. In Proceedings of the International Conference on Automated Planning and Scheduling, 31, 252–261.

    Google Scholar

    Piacentini , C., Alimisis , V., Fox , M. & Long , D. 2013. Combining a temporal planner with an external solver for the power balancing problem in an electricity network. In Proceedings of the Twenty-Third International Conference on Automated Planning and Scheduling, ICAPS. AAAI.

    Google Scholar

    Ramrez , M., Papasimeon , M., Lipovetzky , N., Benke , L., Miller , T., Pearce , A. R., Scala , E. & Zamani , M. 2018. Integrated hybrid planning and programmed control for real time UAV maneuvering. In Proceedings of AAMAS, 1318–1326.

    Google Scholar

    Riddle , P., Barley , M. & Franco , S. 2013. Problem reformulation as meta-level search. In Proceedings of the Conference on Advances in Cognitive Systems.

    Google Scholar

    Riddle , P., Barley , M., Franco , S. & Douglas , J. 2015a. Automated transformation of PDDL representations. In International Symposium on Combinatorial Search.

    Google Scholar

    Riddle , P., Barley , M., Franco , S. & Douglas , J. 2015b. Bagged representations in PDDL. In 4th Workshop on the International Planning Competition, 17–23.

    Google Scholar

    Riddle , P., Barley , M., Franco , S. & Douglas , J. 2015c. Analysis of bagged representations in PDDL. In Workshop on Heuristics and Search for Domain-independent Planning, 17–23.

    Google Scholar

    Riddle , P., Douglas , J., Barley , M. & Franco , S. 2016. Improving performance by reformulating PDDL into a bagged representation. In Proceedings of the 8th Workshop on Heuristic Search for Domain-independent Planning (HSDIP@ ICAPS), 28–36.

    Google Scholar

    Riddle , P. J., Holte , R. C. & Barley , M. W. 2011. Does representation matter in the planning competition? In Ninth Symposium of Abstraction, Reformulation, and Approximation.

    Google Scholar

    Sanner , S. 2010. Relational dynamic influence diagram language (rddl): language description. Unpublished ms. Australian National University 32, 27.

    Google Scholar

    Scala , E. 2014. Plan repair for resource constrained tasks via numeric macro actions. In Proceedings of the Twenty-Fourth International Conferenc on International Conference on Automated Planning and Scheduling, ICAPS’14, 280–288. AAAI Press. ISBN 9781577356608.

    Google Scholar

    Serina , I. 2010. Kernel functions for case-based planning. Artificial Intelligence 174(16–17), 1369–1406.

    Google Scholar

    Siddiqui , F. H. & Haslum , P. 2012. Block-structured plan deordering. In Australasian Joint Conference on Artificial Intelligence, 803–814.

    Google Scholar

    Taig , R. & Brafman , R. I. 2013. Compiling conformant probabilistic planning problems into classical planning. In Twenty-Third International Conference on Automated Planning and Scheduling.

    Google Scholar

    Vallati , M., Chrpa , L. & Kitchin , D. 2013. An automatic algorithm selection approach for planning. In 2013 IEEE 25th International Conference on Tools with Artificial Intelligence, 1–8. IEEE.

    Google Scholar

    Vallati , M., Chrpa , L. & McCluskey , T. 2017. Improving a planner’s performance through online heuristic configuration of domain models. In Proceedings of the 10th International Symposium on Combinatorial Search (SoCS 2017), 171–172.

    Google Scholar

    Vallati , M., Chrpa , L., McCluskey , T. L. & Hutter , F. 2021. On the importance of domain model configuration for automated planning engines. Journal of Automated Reasoning 65(6), 727–773.

    Google Scholar

    Vallati , M., Chrpa , L. & Serina , I. 2020. Mevo: a framework for effective macro sets evolution. Journal of Experimental & Theoretical Artificial Intelligence 32(4), 685–703.

    Google Scholar

    Vallati , M., Hutter , F., Chrpa , L. & McCluskey , T. L. 2015. On the effective configuration of planning domain models. In Twenty-Fourth International Joint Conference on Artificial Intelligence.

    Google Scholar

    Vallati , M. & Kitchin , D. 2020. Knowledge Engineering Tools and Techniques for AI Planning. Springer.

    Google Scholar

    Vallati , M. & Serina , I. 2018. A general approach for configuring PDDL problem models. In Twenty-Eighth International Conference on Automated Planning and Scheduling.

    Google Scholar

    Younes , H. L. & Littman , M. L. 2004. PPDDL1.0: an extension to PDDL for expressing planning domains with probabilistic effects. Technical Report CMU-CS-04-162, 2, 99.

    Google Scholar

  • Cite this article

    Diaeddin Alarnaouti, George Baryannis, Mauro Vallati. 2023. Reformulation techniques for automated planning: a systematic review. The Knowledge Engineering Review 38(1), doi: 10.1017/S0269888923000097
    Diaeddin Alarnaouti, George Baryannis, Mauro Vallati. 2023. Reformulation techniques for automated planning: a systematic review. The Knowledge Engineering Review 38(1), doi: 10.1017/S0269888923000097
    shu
Download PDF

Article Metrics

Article views(95) PDF downloads(52)

Other Articles By Authors

REVIEW   Open Access    

Reformulation techniques for automated planning: a systematic review

  • School of Computing and Engineering, University of Huddersfield, Huddersfield HD1 3DH, UK

  • Received: 14 June 2022
  • Revised: 22 November 2022
  • Accepted: 11 October 2023
  • Published online: 08 November 2023
The Knowledge Engineering Review  38,  2023, 38(1)  |  Cite this article

Abstract: Abstract: Automated planning is a prominent area of Artificial Intelligence and an important component for intelligent autonomous agents. A cornerstone of domain-independent planning is the separation between planning logic, that is the automated reasoning side, and the knowledge model, that encodes a formal representation of domain knowledge needed to reason upon a given problem to synthesize a solution plan. Such a separation enables the use of reformulation techniques, which transform how a model is represented in order to improve the efficiency of plan generation. Over the past decades, significant research effort has been devoted to the design of reformulation techniques. In this paper, we present a systematic review of the large body of work on reformulation techniques for classical planning, aiming to provide a holistic view of the field and to foster future research in the area. As a tangible outcome, we provide a qualitative comparison of the existing classes of techniques, that can help researchers gain an overview of their strengths and weaknesses.

    HTML

    Acknowledgments

    • Mauro Vallati is supported by the UKRI Future Leaders Fellowship [grant number MR/T041196/1].

    • The interested reader is referred to the ICAPS website: https://www.icaps-conference.org/

    • https://www.icaps-conference.org/competitions/.

    Rights and permissions
    • This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution and reproduction, provided the original article is properly cited.
References (87)
  • About this article
    Cite this article
    Diaeddin Alarnaouti, George Baryannis, Mauro Vallati. 2023. Reformulation techniques for automated planning: a systematic review. The Knowledge Engineering Review 38(1), doi: 10.1017/S0269888923000097
    Diaeddin Alarnaouti, George Baryannis, Mauro Vallati. 2023. Reformulation techniques for automated planning: a systematic review. The Knowledge Engineering Review 38(1), doi: 10.1017/S0269888923000097
    shu

    • Catalog

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return
      Return