Using regressive graph as a novel paradigm in plan recognition

We introduce a novel algorithm to plan recognition using a compact structure called regressive graph. The regressive graph is first constructed to represent the actions that are observed or may happen, the propositions denoting the world state and the goals at each time step, and then it searches a valid plan for each goal achieved. Our approach to plan recognition does not need a plan library, which may cause the problems in searching the plan space of exponential size. Using a regressive method, the algorithm allows more than one action to be observed in one time step, and all the actions that may happen can be maintained so that all the possible goals can be recognized. Last we prove our algorithm is polynomial-space and polynomial-time. And the experiments also show that our algorithm has excellent performance in terms of accuracy, efficiency, and scalability.