Probabilistic Plan Recognition Based on Algorithm of EG-Pruning

Some new concepts are introduced, including soft ordering constraint, hard ordering constraint and goal hypotheses sub-tree. All of these concepts together with the concept of supporting degree are incorporated into simple hierarchical (task decomposition) plan, thus results in extended hierarchy (task decomposition) plan. Using this extended hierarchical (task decomposition) plan as plan representation, we present a novel probabilistic algorithm of plan recognition. The core of our algorithm is EG-Pruning. The new algorithm infers the unobserved actions using the two kinds of ordering constraints defined above to extend EG and prunes the current EG by soft ordering constraints checking to make the set of goal hypotheses restricted. Then the probabilities of the goal hypotheses are computed to grade them. Finally, it extends the goal hypotheses sub-trees selected according to their probabilities to attain the whole plan hypotheses. Meanwhile, we have introduced the concept of supporting degree to make the recognition change reasonable with more evidence collected. Benefiting from these steps, our new algorithm clarifies a number of issues that were obscured by previous approaches. In particular, our approach can handle partial observation of domains, partially ordered plans and multiple, interleaved plans. Further, it is able to eliminate the Agent´s misleading actions. The implementation of this algorithm will have a very considerable prospect in computer network security