We present a new abductive, probabilistic theory of plan recognition. This model dif fers from previous theories in being centered around a model of plan execution: most previous methods have been based on plans as formal objects or on rules describing the recognition process. We show that our new model accounts for phenomena omitted from most previous plan recognition theories: no tably the cumulative effect of a sequence of observations of partially-ordered, interleaved plans and the effect of context on plan adop tion. The model also supports inferences about the evolution of plan execution in situ ations where another agent intervenes in plan execution. This facility provides support for using plan recognition to build systems that will intelligently assist a user. In this paper, we present a new theory of plan recogni tion. Our theory, which is abductive and probabilistic, differs from previous theories in treating plan execu tion as primary. This new perspective clarifies a num ber of difficult issues in plan recognition, permitting solutions to a wider class of plan recognition prob lems and allows plan recognition work to proceed on a firmer theoretical footing. In 1986, Kautz and Allen (K&A) published an article, "Generalized Plan Recognition," (Kautz & Allen 1986) that has framed the discussion of plan recognition ever since. K&A defined the problem of plan recognition as the problem of identifying a minimal set of top level actions sufficient to explain the set of observed actions. Plans were represented in a plan graph, with top-level actions as root nodes and other actions as nodes depending from the top-level actions. To a first approximation, the problem of plan recogmtwn was then a problem of graph covering. K&A formalized this view of plan recognition in terms of McCarthy's circumscription. Unlike K&A's, our abductive, prob�bilistic theory is centered around plan execution, instead of around plan graphs as formal objects. Our new framework clari fies a number of issues that were obscured by previ ous approaches. In particular, our approach handles partially-ordered plans; multiple, interleaved plans; the effect of context on plan choice and is able to cor rectly treat a system that is both recognizing actions of other agents, and acting on its own right. Like K&A, we offer only a formal model of the plan recognition problem. We do not pretend to provide a solution to either the algorithmic or implementa tion problems, only an understanding at the "knowl edge level." We have encoded our plan recognition model in a language that has a computational inter pretation, and we have a proof-of-concept interpreter that has been used to test all examples given in this paper. However, we do not claim that this interpreter provides an efficient solution to the plan recognition problem. There are many ways our model could be implemented; we mention several possibilities in this paper. For that matter, we do not believe that there is a single best algorithm, appropriate for all plan recog nition domains. Our work on plan recognition is motivated by an in terest in procedure-based crisis management, specifi cally in industrial control. We are working on systems that will assist human agents executing crisis manage ment procedures. As a result, our model of plan exe cution is hierarchical and procedural, as distinguished from models in which there are only primitive actions, or models that assume agents are deliberative (e.g., game-theoretic models). This application requires us to account for phenomena omitted from most previous plan recognition theories: notably the cumulative ef fect of a sequence of observations of partially-ordered,
Goldman et al. REF extend this work to a probabilistic model that can handle partially ordered and interleaved plans.
A New Model of Plan Recognition
ArXiv
ArXiv
Computer Science