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.