Hierarchical planning, in particular, Hierarchical Task Networks, was proposed as a method to describe plans by decomposition of tasks to sub-tasks until primitive tasks, actions, are obtained. Plan verification assumes a complete plan as input, and the objective is finding a task that decomposes to this plan. In plan recognition, a prefix of the plan is given and the objective is finding a task that decomposes to the (shortest) plan with the given prefix. This paper describes how to verify and recognize plans using a common method known from formal grammars, by parsing. Hierarchical planning is a practically important approach to automated planning based on encoding abstract plans as hierarchical task networks (HTNs) BID3 . The network describes how compound tasks are decomposed, via decomposition methods, to sub-tasks and eventually to actions forming a plan. The decomposition methods may specify additional constraints among the subtasks such as partial ordering and causal links.There exist only two systems for verifying if a given plan complies with the HTN model (a given sequence of actions can be obtained by decomposing some task). One system is based on transforming the verification problem to SAT BID2 and the other system is using parsing of attribute grammars BID1 . Only the parsing-based system supports HTN fully (the SAT-based system does not support the decomposition constraints).Parsing became popular in solving the plan recognition problem BID5 as researchers realized soon the similarity between hierarchical plans and formal grammars, specifically context-free grammars with parsing trees close to decomposition trees of HTNs. The plan recognition problem can be formulated as the problem of adding a sequence of actions after some observed partial plan such that the joint sequence of actions forms a complete plan generated from some task (more general formulations also exist). Hence plan recognition can be seen as a generalization of plan verification. There exist numerous approaches to plan recognition using parsing or string rewriting (Avrahami-Zilberbrand and Kaminka 2005; BID5 BID4 BID5 ), but they use hierarchical models that are weaker than HTNs. The languages defined by HTN planning problems (with partial-order, preconditions and effects) lie somewhere between context-free (CF) and context-sensitive (CS) languages BID5 so to model HTNs one needs to go beyond the CF grammars. Currently, the only grammar-based model covering HTNs fully uses attribute grammars BID0 . Moreover, the expressivity of HTNs makes the plan recognition problem undecidable BID2 . Currently, there exists only one approach for HTN plan recognition. This approach relies on translating the plan recognition problem to a planning problem BID5 , which is a method invented in BID5 .In this paper we focus on verification and recognition of HTN plans using parsing. The uniqueness of the proposed methods is that they cover full HTNs including task interleaving, partial order of sub-tasks, and other decomposition constraints (prevailing constraints, specifically). The methods are derived from the plan verification technique proposed in BID1 .There are two novel contributions of this paper. First, we will simplify the above mentioned verification technique by exploiting information about actions and states to improve practical efficiency of plan verification. Second, we will extend that technique to solve the plan (task) recognition problem. For plan verification, only the method in BID1 supports HTN fully. We will show that the verification algorithm can be much simpler and, hence, it is expected to be more efficient. For plan recognition, the method proposed in BID5 can in principle support HTN fully, if a full HTN planner is used (which is not the case yet as prevailing conditions are not supported). However, like other plan recognition techniques it requires the top task (the goal) and the initial state to be specified as input. A practical difference of out methods is that they do not require information about possible top (root) tasks and an initial state as their input. This is particularly interesting for plan/task recognition , where existing methods require a set of candidate tasks (goals) to select from (in principle, they may use all tasks as candidates, but this makes them inefficient). In the paper, we proposed two versions of the parsing technique for verification of HTN plans and for recognition of HTN plans. As far as we know, these are the only approaches that currently cover HTN fully including all decomposition constraints. Both versions can be applied to solve both verification and recognition problems, but as we demonstrated using an example, each of them has some deficiencies when applied to the other problem.The next obvious step is implementation and empirical evaluation of both techniques. There is no doubt that the novel verification algorithm is faster than the previous approaches BID2 and BID1 . The open question is how much faster it will be, in particular for large plans. The efficiency of the novel plan recognition technique in comparison to existing compilation technique BID5 ) is less clear as both techniques use different approaches, bottom-up vs. top-down. The disadvantage of the compilation technique is that it needs to re-generate the known plan prefix, but it can exploit heuristics to remove some overhead there. Contrary, the parsing techniques looks more like generate-and-test, but controlled by the hierarchical structure. It also guarantees finding the shortest extension of plan prefix.
The paper describes methods to verify and recognize HTN plans by parsing of attribute grammars.
{"src": "scitldr-AIC_train", "paper_id": "HJgRIrHWt4"}