A Novel Parsing-based Approach for Verification of Hierarchical Plans

Abstract

Hierarchical Task Networks were proposed as amethod to describe plans by decomposition of tasks to subtasksuntil primitive tasks, actions, are obtained. Valid plans –sequences of actions – must adhere both to causal dependenciesbetween the actions and to the structure given by the decompositionof the goal task. Plan verification aims at finding if a givenplan is valid, that is, if it is causally consistent and it can beobtained by decomposition of some task. The paper describes anovel parsing-based approach for hierarchical plan verificationthat is orders of magnitude faster than existing methods.