Focusing in Plan Recognition

Abstract

A plan recognition architecture is presented which exploits application-specific heuristic knowledge to quickly focus the search to a small set of plausible plan interpretations from the very large set of possible interpretations. The heuristic knowledge is formalized for use in a truth maintenance system where interpretation assumptions and their heuristic justifications are recorded. By formalizing this knowledge, the system is able to reason about the assumptions behind the current state of the interpretations. This makes intelligent backtracking and error detection possible. I INTRODUCI’ION An important issue for plan recognition in large search spaces is how to rapidly and accurately recognixe the current plan based on the observation of a small number of plan steps. The need for this type of plan recognition has arisen in the POISE intelligent user interface system [3, 6, 7J. Hierarchies of plans are used to specify typical combinations of user actions and the goals they accomplish. By recognizing a user‘s actions in the context of this model of possible actions, POISE is able to provide intelligent assistance to a user (e-g., agenda management, error detection and correction, and plan completion). Figure 1 describes a simple POISE plan that could be used as part of an intelligent assistant for an office automation system. Plan recognition is a complex task since the recognizer may be forced to keep a very large number of plan interpretations under active consideration because of: 1) concurrency in user activities (i.e., loose constraints on the temporal ordering among plan steps); 2) sharing of plan steps among alternative plans; 3) the possibility that any partial plan might be continued by