Charles Explorer logo
🇬🇧

Lessons Learned from the CYK Algorithm for Parsing-based Verification of Hierarchical Plans

Publication at Faculty of Mathematics and Physics |
2023

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.