Planning and plan recognition

Plan recognition is the process of one agent inferring another's intention from the evidence of its actions, so that the inferring agent can act on that intention. Usually it is mutually believed that the inferring agent is observing the acting agent [11]. This is called intended recognition. In this case the acting agent chooses its actions with the expectation that its intention will be inferred and acted upon by the inferring agent. He may thereby choose a plan that is impossible to achieve by himself. Where the inferring agent does not believe that the acting agent believes that it is being observed, it must limit its inferences to those intentions that the acting agent would be able to act upon alone. This is called keyhole recognition.

Plan recognition models start with Kautz's [39] theory. He uses a decomposition chaining model for his plan rules, which he translates into logical rules. These rules can be used to produce explanations in disjunctive normal form. Following the same decomposition chaining planning model, Vilain [73] uses a chart parser to produce answers that match Kautz's theory. Statistical parsing [13] could possibly be applied to plan recognition, whereby each decomposition rule for a symbol has an associated probability of being used by the planner. Statistical parsing is used in parsing sentences to disambiguate those that have many parses, and by the same token may be used by the hearer to pursue only the most likely plan hypotheses. This would be effectively a user modelling approach of the kind that will be taken in this thesis, since the probabilities would reflect the beliefs of the acting agent about their capability to use a plan rule, and about satisfied preconditions of the rule. Charniak and Goldman [14] describe a similar idea, by modelling the planning process with a Bayesian network. Each action is represented by a random variable. The top-level actions of the plans appear as the roots of the network, with different decompositions as their children. Each node in the network is related to its parents by a conditional probability table, which can be trained from data. For a given set of observed actions, the probability of different explanations can be found by following the conditional probability tables. Probabilistic plan recognition is important since in many cases there can be large numbers of unlikely yet possible explanations to a set of actions. For an agent to respond efficiently, it must be able to find out the most likely of those explanations. The same holds in dialogue planning, where with little evidence, the hearer must do the most he can to reduce the set of hypotheses, so that the speaker can be understood. Although the speaker should choose contributions to the dialogue that minimise the hypotheses available to the hearer, probabilistic reasoning allows the hypothesis set to be further reduced. A probabilistic approach to plan recognition is taken in this thesis.

Specifically for dialogue planning, Carberry [10] uses a tree model for plan recognition, called a context model, with parent-child relationships representing decomposition chaining and precondition-effect chaining. Following Grice's description of meaning, her theory encompasses a plan recognition step by the hearer, from which the hearer obtains the speaker's intention, and a continuation of the plan, whereby the hearer adds actions that satisfy the intention. She assumes that dialogues are planned in a focussed way [28]. If an agent is focussed, it will not open a subtree until all of the other subtrees in the context model have been completed. Focussing is important since by limiting the number of continuations of a plan, it reduces the number of hypotheses that the inferring agent must consider, making plan recognition much easier.