An Algorithm for Plan Recognition in Collaborative Discourse

AN ALGORITHM FOR PLAN RECOGNITION IN COLLABORATIVE DISCOURSE* Karen E. Lochbaum Aiken Computation Lab Harvard University 33 Oxford Street Cambridge, MA 02138 kel~harvard.harvard.edu ABSTRACT A model of plan recognition in discourse must be based on intended recognition, distinguish each agent's be- liefs and intentions from the other's, and avoid as- sumptions about the correctness or completeness of the agents' beliefs. In this paper, we present an algo- rithm for plan recognition that is based on the Shared- Plan model of collaboration (Grosz and Sidner, 1990; Lochbaum et al., 1990) and that satisfies these con- straints. INTRODUCTION To make sense of each other's utterances, conversa- tional participants must recognize the intentions be- hind those utterances. Thus, a model of intended plan recognition is an important component of a theory of discourse understanding. The model must distinguish each agent's beliefs and intentions from the other's and avoid assumptions about the correctness or complete- ness of the agents' beliefs. Early work on plan recognition in discourse, e.g. Allen & Perrault (1980); Sidner & Israel (1981), was based on work in AI planning systems, in particu- lar the STRIPS formalism (Fikes and Nilsson, 1971). However, as Pollack (1986) has argued, because these systems do not differentiate between the beliefs and intentions of the different conversational participants, they are insufficient for modelling discourse. Although Pollack proposes a model that does make this distinc- tion, her model has other shortcomings. In particular, it assumes a master/slave relationship between agents (Grosz and Sidner, 1990) and that the inferring agent has complete and accurate knowledge of domain ac- tions. In addition, like many earlier systems, it relies upon a set of heuristics to control the application of plan inference rules. In contrast, Kautz (1987; 1990) presented a theo- retical formalization of the plan recognition problem, *This research has been supported by U S WEST Ad- vanced Technologies and by a Bellcore Graduate Fellow- ship. and a corresponding algorithm, in which the only con- clusions that are drawn are those that are "absolutely justified." Although Kautz's work is quite elegant, it too has several deficiencies as a model of plan recogni- tion for discourse. In particular, it is a model of keyhole recognition m the inferring agent observes the actions of another agent without that second agent's knowl- edge -- rather than a model of intended recognition. Furthermore, both the inferring and performing agents are assumed to have complete and correct knowledge of the domain. In this paper, we present an algorithm for intended recognition that is based on the SharedPlan model of collaboration (Grosz and Sidner, 1990; Lochbaum et al., 1990) and that, as a result, overcomes the limita- tions of these previous models. We begin by briefly presenting the action representation used by the algo- rithm and then discussing the type of plan recogni- tion necessary for the construction of a SharedPlan. Next, we present the algorithm itself, and discuss an initial implementation. Finally, because Kautz's plan recognition Mgorithms are not necessarily tied to the assumptions made …

Content truncated to 500 words