Department of Information Engineering, University of Brescia, via Branze 38, Brescia 25123, Italy e-mail: enricos83@gmail.com"/> School of Computing & Engineering, University of Huddersfield, Huddersfield, HD1 3DH, UK e-mail: m.vallati@hud.ac.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
2021 Volume 36
Article Contents
Next Previous
RESEARCH ARTICLE   Open Access    

Effective grounding for hybrid planning problems represented in PDDL+

  • Department of Information Engineering, University of Brescia, via Branze 38, Brescia 25123, Italy e-mail: enricos83@gmail.com

  • School of Computing & Engineering, University of Huddersfield, Huddersfield, HD1 3DH, UK e-mail: m.vallati@hud.ac.uk

More Information
  • Abstract: Automated planning is the field of Artificial Intelligence (AI) that focuses on identifying sequences of actions allowing to reach a goal state from a given initial state. The need of using such techniques in real-world applications has brought popular languages for expressing automated planning problems to provide direct support for continuous and discrete state variables, along with changes that can be either instantaneous or durative. PDDL+ (Planning Domain Definition Language +) models support the encoding of such representations, but the resulting planning problems are notoriously difficult for AI planners to cope with due to non-linear dependencies arising from the variables and infinite search spaces. This difficulty is exacerbated by the potentially huge fully ground representations used by modern planners in order to effectively explore the search space, which can make some problems impossible to tackle.This paper investigates two grounding techniques for PDDL+ problems, both aimed at reducing the size of the full ground representation by reasoning over the lifted, more abstract problem structure. The first method extends the simple mechanism of invariant analysis to limit the groundings of operators upfront. The second method proposes to tackle the grounding process through a PDDL+ to classical planning abstraction; this allows us to leverage the amount of research done in the classical planning area. Our empirical analysis studies the effect of these novel approaches over both real-world hybrid applications and synthetic PDDL+ problems took from standard benchmarks of the planning community; our results reveal that not only the techniques improve the running time of previous grounding mechanisms but also let the planner extend the reach to problems that were not solvable before.
  • 加载中
  • Antoniou , G., Batsakis , S., Davies , J., Duke , A., McCluskey , T. L., Peytchev , E., Tachmazidis , I. & Vallati , M. 2019. Enabling the use of a planning agent for urban traffic management via enriched and integrated urban data. Transportation Research Part C: Emerging Technologies 98, 284–297.

    Google Scholar

    Areces , C., Bustos , F., Dominguez , M. & Hoffmann , J. 2014. Optimizing planning domains by automatic action schema splitting. In Proceedings of ICAPS, 11–19.

    Google Scholar

    Balduccini , M., Magazzeni , D., Maratea , M. & Leblanc , E. 2017. CASP solutions for planning in hybrid domains. Theory and Practice of Logic Programming 17(4), 591–633.

    Google Scholar

    Barrett , C. W. & Tinelli , C. 2018. Satisfiability modulo theories. In Handbook of Model Checking, 305–343. Springer.

    Google Scholar

    Bertolucci , R., Capitanelli , A., Maratea , M., Mastrogiovanni , F. & Vallati , M. 2019. Automated planning encodings for the manipulation of articulated objects in 3d with gravity. In Proceedings of the XVIIIth International Conference of the Italian Association for Artificial Intelligence (Ai*iA), 135–150.

    Google Scholar

    Bit-Monnot , A. 2018. A constraint-based encoding for domain-independent temporal planning. In Principles and Practice of Constraint Programming - 24th International Conference, CP, Hooker, J. N. (eds), Lecture Notes in Computer Science 11008, 30–46. Springer.

    Google Scholar

    Biundo , S., Aylett , R., Beetz , M., Borrajo , D., Cesta , A., Grant , T., McCluskey , T., Milani , A. & Verfaillie , G. 2003. PLANET roadmap. http://planet.hud.ac.uk/home/.

    Google Scholar

    Bofill , M., Espasa , J. & Villaret , M. (2016) A semantic notion of interference for planning modulo theories. In Proceedings of the Twenty-Sixth International Conference on Automated Planning and Scheduling, ICAPS, 56–64.

    Google Scholar

    Bryce , D., Gao , S., Musliner , D. J. & Goldman , R. P. 2015. Smt-based nonlinear PDDL+ planning. In AAAI, 3247–3253. AAAI Press.

    Google Scholar

    Cashmore , M., Magazzeni , D. & Zehtabi , P. 2020. Planning for hybrid systems via satisfiability modulo theories. Journal of Artificial Intelligence Research 67, 235–283.

    Google Scholar

    Chrpa , L., Scala , E. & Vallati , M. 2015. Towards a reformulation based approach for efficient numeric planning: numeric outer entanglements. In Proceedings of SOCS.

    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 and Theoretical Artificial Intelligence 30(6), 831–856.

    Google Scholar

    Coles , A. J. & Coles , A. 2011. LPRPG-P: relaxed plan heuristics for planning with preferences. In Proceedings of the 21st International Conference on Automated Planning and Scheduling, ICAPS.

    Google Scholar

    Coles , A. J., Coles , A., Fox , M. & Long , D. 2010. Forward-chaining partial-order planning. In Proceedings of the 20th International Conference on Automated Planning and Scheduling, ICAPS, 42–49.

    Google Scholar

    Corrêa , A. B., Pommerening , F., Helmert , M. & Francès , G. 2020. Lifted successor generation using query optimization techniques. In Proceedings of the Thirtieth International Conference on Automated Planning and Scheduling (ICAPS), 80–89.

    Google Scholar

    Della Penna , G., Magazzeni , D., Mercorio , F. & Intrigila , B. 2009. Upmurphi: a tool for universal planning on PDDL+ problems. In ICAPS. AAAI.

    Google Scholar

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

    Google Scholar

    Fox , M., Long , D., Tamboise , G. & Isangulov , R. 2018. Creating and executing a well construction/operation plan. US Patent App. 15/541,381.

    Google Scholar

    Franco , S., Vallati , M., Lindsay , A. & McCluskey , T. L. 2019. Improving planning performance in PDDL+ domains via automated predicate reformulation. In Proceedings of the 19th International Conference Computational Science (ICCS), 491–498.

    Google Scholar

    Garrido , A., Morales , L. & Serina , I. 2012 Using AI planning to enhance e-learning processes. In Proceedings of the Twenty-Second International Conference on Automated Planning and Scheduling, ICAPS. AAAI.

    Google Scholar

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

    Google Scholar

    Gnad , D., Torralba , á., Domínguez , M. A., Areces , C. & Bustos , F. 2019. Learning how to ground a plan - partial grounding in classical planning. In The Thirty-Third AAAI Conference on Artificial Intelligence, 7602–7609. AAAI.

    Google Scholar

    Helmert , M. 2009. Concise finite-domain representations for PDDL planning tasks. Artificial Intelligence 173(5–6), 503–535

    Google Scholar

    Henzinger , T. A. 1996. The theory of hybrid automata. In LICS, 278–292. IEEE Computer Society.

    Google Scholar

    Hoffmann , J. 2003. The metric-ff planning system: Translating “ignoring delete lists” to numeric state variables. Journal of Artificial Intelligence Research 20, 291–341.

    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

    Kaufmann , B., Leone , N., Perri , S. & Schaub , T. 2016. Grounding and solving in answer set programming. AI Magazine 37(3), 25–32.

    Google Scholar

    Kiam , J. J., Scala , E., Javega , M. R. & Schulte , A. 2020. An ai-based planning framework for HAPS in a time-varying environment. In ICAPS, 412–420. AAAI Press.

    Google Scholar

    Koehler , J. & Hoffmann , J. 2000. On the instantiation of ADL operators involving arbitrary first-order formulas. In PuK.

    Google Scholar

    Lifschitz , V. 2008. What is answer set programming? In AAAI, 1594–1597. AAAI Press.

    Google Scholar

    Lipovetzky , N., Burt , C. N., Pearce , A. R. & Stuckey , P. J. 2014. Planning for mining operations with time and resource constraints. In Proceedings of the International Conference on Automated Planning and Scheduling.

    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

    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.

    Google Scholar

    McCluskey , T. L., Vaquero , T. S. & Vallati , M. 2017. Engineering knowledge for automated planning: towards a notion of quality. In Proceedings of the Knowledge Capture Conference, K-CAP, 14:1–14:8.

    Google Scholar

    McDermott , D. V. 2003. Reasoning about autonomous processes in an estimated-regression planner. In ICAPS, 143–152. AAAI.

    Google Scholar

    Newton , M. A. H., Levine , J., Fox , M. & Long , D. 2007. Learning macro-actions for arbitrary planners and domains. In Proceedings of ICAPS.

    Google Scholar

    Parkinson , S., Longstaff , A. & Fletcher , S. 2014. Automated planning to minimise uncertainty of machine tool calibration. Engineering Applications of Artificial Intelligence 30, 63–72.

    Google Scholar

    Petrick , R. P. A. & Foster , M. E. 2013. Planning for social interaction in a robot bartender domain. In Proceedings of the Twenty-Third International Conference on Automated Planning and Scheduling, ICAPS.

    Google Scholar

    Piotrowski , W. M., Fox , M., Long , D., Magazzeni , D. & Mercorio , F. 2016. Heuristic planning for hybrid systems. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, 4254–4255.

    Google Scholar

    Ramírez , 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 the 17th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS, 1318–1326.

    Google Scholar

    Ridder , B. & Fox , M. 2014. Heuristic evaluation based on lifted relaxed planning graphs. In Proceedings of the Twenty-Fourth International Conference on Automated Planning and Scheduling, ICAPS.

    Google Scholar

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

    Google Scholar

    Robinson , N., Gretton , C., Pham , D. N. & Sattar , A. 2008. A compact and efficient SAT encoding for planning. In Proceedings of the Eighteenth International Conference on Automated Planning and Scheduling, ICAPS, 296–303.

    Google Scholar

    Scala , E., Haslum , P. & Thiébaux , S. 2016a. Heuristics for numeric planning via subgoaling. In IJCAI, 3228–3234. IJCAI/AAAI Press.

    Google Scholar

    Scala , E., Haslum , P., Thiébaux , S. & Ramírez , M. 2016b. Interval-based relaxation for general numeric planning. In ECAI, Frontiers in Artificial Intelligence and Applications 285, 655–663. IOS Press.

    Google Scholar

    Scala , E., Haslum , P., Thiébaux , S. & Ramírez , M. 2020a. Subgoaling techniques for satisficing and optimal numeric planning. Journal of Artificial Intelligence Research 68, 691–752.

    Google Scholar

    Scala , E., Saetti , A., Serina , I. & Gerevini , A. E. 2020b. Search-guidance mechanisms for numeric planning through subgoaling relaxation. In ICAPS, 226–234. AAAI Press.

    Google Scholar

    Scala , E. & Vallati , M. 2020. Exploiting classical planning grounding in hybrid pddl+ planning engines. In Proceedings of ICTAI.

    Google Scholar

    Shin , J. & Davis , E. 2005. Processes and continuous change in a sat-based planner. Artificial Intelligence 166(1–2), 194–253.

    Google Scholar

    Thiébaux , S., Coffrin , C., Hijazi , H. & Slaney , J. 2013. Planning with mip for supply restoration in power distribution systems. In Proceedings of the International Joint Conference on Artificial Intelligence.

    Google Scholar

    Vallati , M. & Chrpa , L. 2019. On the robustness of domain-independent planning engines: the impact of poorly-engineered knowledge. In Proceedings of the 10th International Conference on Knowledge Capture, K-CAP, 197–204.

    Google Scholar

    Vallati , M., Chrpa , L. & McCluskey , T. L. 2018. What you always wanted to know about the deterministic part of the international planning competition (IPC) 2014 (but were too afraid to ask). Knowledge Engineering Review. 33, e3.

    Google Scholar

    Vallati , M., Chrpa , L., McCluskey , T. L. & Hutter , F. 2020. On the importance of domain model configuration for automated planning engines. arXiv preprint arXiv:2010.07710.

    Google Scholar

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

    Google Scholar

    Vallati , M., Magazzeni , D., Schutter , B. D., Chrpa , L. & McCluskey , T. L. 2016. Efficient macroscopic urban traffic models for reducing congestion: a PDDL+ planning approach. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, 3188–3194.

    Google Scholar

    Younes , H. L. S. & Simmons , R. G. 2003. VHPOP: versatile heuristic partial order planner. Journal of Artificial Intelligence Research 20, 405–430.

    Google Scholar

  • Cite this article

    Enrico Scala, Mauro Vallati. 2021. Effective grounding for hybrid planning problems represented in PDDL+. The Knowledge Engineering Review 36(1), doi: 10.1017/S0269888921000072
    Enrico Scala, Mauro Vallati. 2021. Effective grounding for hybrid planning problems represented in PDDL+. The Knowledge Engineering Review 36(1), doi: 10.1017/S0269888921000072
    shu
Download PDF

Article Metrics

Article views(98) PDF downloads(53)

Other Articles By Authors

RESEARCH ARTICLE   Open Access    

Effective grounding for hybrid planning problems represented in PDDL+

  • Department of Information Engineering, University of Brescia, via Branze 38, Brescia 25123, Italy e-mail: enricos83@gmail.com

  • School of Computing & Engineering, University of Huddersfield, Huddersfield, HD1 3DH, UK e-mail: m.vallati@hud.ac.uk

  • Received: 02 January 2021
  • Revised: 22 April 2021
  • Accepted: 22 April 2021
  • Published online: 10 June 2021
The Knowledge Engineering Review  36,  2021, 36(1)  |  Cite this article

Abstract: Abstract: Automated planning is the field of Artificial Intelligence (AI) that focuses on identifying sequences of actions allowing to reach a goal state from a given initial state. The need of using such techniques in real-world applications has brought popular languages for expressing automated planning problems to provide direct support for continuous and discrete state variables, along with changes that can be either instantaneous or durative. PDDL+ (Planning Domain Definition Language +) models support the encoding of such representations, but the resulting planning problems are notoriously difficult for AI planners to cope with due to non-linear dependencies arising from the variables and infinite search spaces. This difficulty is exacerbated by the potentially huge fully ground representations used by modern planners in order to effectively explore the search space, which can make some problems impossible to tackle.This paper investigates two grounding techniques for PDDL+ problems, both aimed at reducing the size of the full ground representation by reasoning over the lifted, more abstract problem structure. The first method extends the simple mechanism of invariant analysis to limit the groundings of operators upfront. The second method proposes to tackle the grounding process through a PDDL+ to classical planning abstraction; this allows us to leverage the amount of research done in the classical planning area. Our empirical analysis studies the effect of these novel approaches over both real-world hybrid applications and synthetic PDDL+ problems took from standard benchmarks of the planning community; our results reveal that not only the techniques improve the running time of previous grounding mechanisms but also let the planner extend the reach to problems that were not solvable before.

    HTML

    Acknowledgments

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

    • The present work significantly extends, both theoretically and experimentally, a recent conference paper in which the grounding techniques have been presented (Scala & Vallati, 2020).

    • The logical pillars of the language resemble those used in Satisfiability Modulo Theory languages (Barrett & Tinelli, 2018).

    • The difference between constant and objects is historical, and we leave it here. It serves the purpose of decoupling objects that are constant in any specification of the problem, from objects that depend on a particular instance.

    • Note that a method for taking numeric condition into account has been also hinted at in the Metric-FF planning system (Hoffmann, 2003). However, to the best of our knowledge, no detail has been provided on how actually take into account hidden preconditions in the action numeric effects and undefined values that frequently occur in planning domains. More details in Section 5.

    • A similar relaxation schema has been implemented by the AIBR relaxation heuristic presented by Scala et al. (2016b).

    • This can be obtained by transforming all transition preconditions in Disjunctive Normal Form and then replacing the complex action with a number of copies, one for each disjunct of the formula. All actions will share the same effects, but will differ on the employed disjunct they have been generated from Koehler and Hoffmann (2000).

    • Any logical formula be transformed in polynomial time in an equivalent negation normal form formula. This can be done by pushing negation down to atomic Boolean term and substituting negated numeric constraints with disjunctions.

    • Note that solving the problem exactly is impractical in classical planning too, as it would imply exploring an exponential number of states, and checking for possible substitutions for each encountered state. Techniques based on overestimation of the state space are necessary to avoid this combinatorial explosion.

    • http://www.fast-downward.org/.

    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 in any medium, provided the original work is properly cited.
References (56)
  • About this article
    Cite this article
    Enrico Scala, Mauro Vallati. 2021. Effective grounding for hybrid planning problems represented in PDDL+. The Knowledge Engineering Review 36(1), doi: 10.1017/S0269888921000072
    Enrico Scala, Mauro Vallati. 2021. Effective grounding for hybrid planning problems represented in PDDL+. The Knowledge Engineering Review 36(1), doi: 10.1017/S0269888921000072
    shu

    • Catalog

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return
      Return