Lessons Learned from the CYK Algorithm for Parsing-based Verification of Hierarchical Plans
Open Access
- 8 May 2023
- journal article
- research article
- Published by University of Florida George A Smathers Libraries in The International FLAIRS Conference Proceedings
- Vol. 36
Abstract
Verification of hierarchical plans deals with the problem of whether an action sequence is causally consistent and can be obtained by a decomposition of a goal task. This second sub-problem (finding the decomposition) makes the verification problem NP-hard. The task decomposition structure is very close to a parsing tree of context-free grammar (CFG). Recently, the CFG-parsing algorithm by Cocke–Younger–Kasami (CYK) has been modified to verify hierarchical plans efficiently. Despite being fast, the algorithm can only handle totally-ordered planning domains. In this paper, we ask whether the ideas from the CYK algorithm can be extended to a more general parsing-based approach that covers all planning domains, i.e., including partially ordered ones. More specifically, we study the effect of modifying the domain model by limiting the number of sub-tasks in decomposition methods to two and the effect of changing the parsing strategy.Keywords
This publication has 13 references indexed in Scilit:
- Do It Yourself, but Not Alone: Companion-Technology for Home Improvement—Bringing a Planning-Based Interactive DIY Assistant to LifeKI - Künstliche Intelligenz, 2021
- On Succinct Groundings of HTN Planning ProblemsProceedings of the AAAI Conference on Artificial Intelligence, 2020
- ML-Plan: Automated machine learning via hierarchical planningMachine Learning, 2018
- Attribute grammars with set attributes and global constraints as a unifying framework for planning domain models2017
- This Is a Solution! (... But Is It Though?) - Verifying Solutions of Hierarchical Planning ProblemsProceedings of the International Conference on Automated Planning and Scheduling, 2017
- Assessing the Expressivity of Planning Formalisms through the Comparison to Formal LanguagesProceedings of the International Conference on Automated Planning and Scheduling, 2016
- On the Complexity of HTN Plan Verification and Its Implications for Plan RecognitionProceedings of the International Conference on Automated Planning and Scheduling, 2015
- Hierarchical task and motion planning in the now2011
- Complexity results for HTN planningAnnals of Mathematics and Artificial Intelligence, 1996
- Strips: A new approach to the application of theorem proving to problem solvingArtificial Intelligence, 1971