Graph Construction and Analysis as a Paradigm for Plan Recognition

Abstract

We present a novel approach to plan recognition in which graph construction and analysis is used as a paradigm. We use a graph structure called a Goal Graph for the plan recognition problem. The Goal Graph is first constructed to represent the observed actions, the state of the world, and the achieved goals at consecut-ive time steps. It also represents various connections between nodes in the Goal Graph. The Goal Graph can then be analysed at each time step to recognise those achieved goals that are consistent with the actions ob-served so far. The Goal Graph analysis can also re-veal valid plans for the recognised goals or part of the recognised goals. We describe two algorithms, Goal-GraphConstructor and GoalGraphAnalyser, based on this paradigm. These algorithms are sound, polynomial-time and polynomial-space. The algorithms have been tested in two domains with up to 245 goal schemata and 100000 possible goals. They perform well in these do-mains in terms of efficiency, accuracy and scalability.