Research And Implementation Of The Probabilistic Plan Recognition Based On EG-Pruning

Plan recognition means that the recognizer observes the impoverished and fragmented description of actions performed by one or more agents and then infers a rich and highly interrelated description. The new description fills out details of the setting and predicts the goals and future actions of the agent. But it is usually very difficult to confirm plan hypotheses uniquely, because there is some domains in which there exists some actions that contribute to more than one goal, or in the observed domain, the agent pursues multiple plans simultaneously, and further more, some of these domains are only partially observable. The existence of these problems prevents the application of some existent plan recognition methods to real world problem. For example, the large number of complex domain features, without probabilistic state transition models makes using an Abstract Markov Model (AMM) difficult; methods based on probabilistic grammars do not handle concurrent and interleaved goals; although it searches fast, methods based on grammar parsing can not treat ordering constraints, etc. Goldman & Geib have put forward a new model of plan recognition based on plan execution in 1999, and then improved it in 2005. Their method cannot only recognize the partially ordered or interleaved, multiple plans, but also treat the partial observability of the domains. But, with the ratio of the unobserved action in the whole plan hypotheses increasing, the efficiency of the algorithm will decrease sharply.In this paper, we have put forward a novel plan recognition method, the core of which is EG-Pruning. This new algorithm, is based on the effective graph searching, and infers the unobserved actions using the two kinds of ordering constraints defined in this paper through extending EG, prunes the current EG by soft ordering constraints checking to make the set of goal hypotheses restricted, and then computes the probabilities of the goal hypotheses 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. Profit from these steps, our new algorithm clarifies a number of issues that were obscured by previous approaches. In particular, it 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 and intrusion detection.Based on the algorithm proposed above, we have implemented a new plan recognition system-EGPPR, which cannot only recognize the plan and the goal the agent being performed efficiently, but also indicate the actions the agent will take, and also exclude the misleading actions too. More over, as there is no ready plan recognition system inland, so our EGPPR system will be significant both in research and practice due to its novelty.