The dialogue interpretation algorithm

The hypotheses on the user's plans that the system builds during a dialogue are represented, as in [Carberry1988], by Context Models (CMs): they are trees whose nodes are partially instantiated actions (the structure of CMs reflects the DH and the GH in the plan library). For each sentence of a user, the system identifies the actions that s/he might be focused on, it examines their relationship with the previous part of the dialogue, and it expands the active CMs in order to collect all the information needed for an helpful answer. After a possible clarification dialogue, the information to be provided is selected from the CMs on the basis of the input utterance. In the following we will describe the steps through which the extended CMs are built, and then exploited during response production.

The plan-recognition and response production algorithm

1.   Action identification: on the basis of the input sentence, a set of actions is selected from the plan library; each of them possibly represents the aspect of the task on which the user's attention is currently focused. The action identification is accomplished by means of rules which are partially ordered according to the constraints that they impose on the structure of the surface form of the utterance.

2. Focusing: the set of CMs produced by the analysis of the previous sentences of the dialogue is updated to take into account the actions identified in step . CMs that cannot be related to them are rejected (this phase of the algorithm takes care of the coherence problem cited in the introduction of this paper). The focusing heuristics are ordered to prefer interpretations suggesting a continuation of the current topic of the dialogue. In particular, heuristics that make it possible to relate the last utterance to the most recent actions considered during the dialogue are stronger than those that make it possible to refer to less recent ones, or to some parts of the higher-level task that have not been considered before (see [Carberry1988]).

3.   Upward expansion: CMs that are part of only one higher level plan in the DH are expanded upward in the plan library, for establishing which higher-level action the user is committed to.

4.   Addition of more specific actions in the GH to the actions in the CMs:

   the purpose of this step is to generate more precise hypotheses on the user's plans starting from the current CMs. For each action in the frontier of a CM, its more specific actions in the GH are inspected. If the UM enables the system to determine which of the more specific actions of an action act the user wants to perform, then the more specific action is appended in the CM under the occurrence of act.

5.   Downward expansion: the actions in each CM are repeatedly decomposed into more elementary ones until they are no further decomposable or the UM suggests that the user knows how to perform every action in the frontier of the CM. Actions that have more specific actions in the GH are not expanded unless it is possible to infer (from the contents of the UM) which of the alternative more specific actions is feasible for the user; in that case, the feasible action is attached to the CM.

6.   Backward expansion through enablement links: each CM is expanded in order to include the steps necessary for satisfying the preconditions of the actions which the user (according to the UM) is not able to plan by himself.

7.   Evaluation of the relevance of the ambiguity among CMs: if more than one CM is active, the ambiguity is evaluated, to establish whether a single reply can be given to the user's utterance. If this is not the case, a clarification dialogue [van Beek et al. 1993] is started to identify the user's intentions and solve the ambiguity.

8. Selection of the contents of the answer: the contents of the answer to the user's utterance are chosen on the basis of the structure of the sentence itself and of the information contained in the selected unambiguous CMs (this aspect has been partially investigated in [Ardissono et al. 1993a]). The downward and backward expansion phases provide the CMs with the information for answering at the proper detail level, according to the user's knowledge on the domain.

  
Figure: Schema of the dialogue interpretation algorithm

Step of the algorithm deals with the problem of evaluating the relevance of an ambiguity among different active hypotheses on the user's plans. In particular, the notion of relevance addressed in our work represents a refinement of that defined in [van Beek and Cohen1991], [van Beek et al. 1993]. In those works the relevance of an ambiguity is mainly based on the constraints associated with the selected plans. Van Beek and Cohen avoid clarification dialogues when they are useless, because they should distinguish among candidate plans all of which fail for the same unsatisfied set of constraints. In [Ardissono et al. 1993a] we refined their critiquing procedure for the identification of failing constraints, by considering the fact that complete knowledge of the truth value of constraints is not always possible for an automated system, as well as for a human consultant. In particular, constraints can be divided in at least three categories: a) those whose value is certainly known by the system, because they are in its domain of competence (e.g. whether the library is open); b) those concerned with private information of the user (e.g. if s/he is a student), whose value is unknown to the system, unless the user specifies it during the dialogue; c) those concerned with information that, in principle, can neither be known to the system, nor to the user (e.g. whether a certain book is present in the library when the user produces the utterance). While the resolution of ambiguities is possible for constraints of the first class, as far as the other ones are concerned it is possible that the system is unaware of their truth value; in this case, it can manage the situation by ignoring such constraints in the ambiguity resolution phase and by specifying, for each of the alternative hypotheses, which values of the parameters of the constraints make them true (case b), or by recommending to the user to check the constraints (case c).

The UM is built starting from the user's utterances by means of acquisition and expansion rules that will be described in the next sections. Figure represents the main phases of the plan recognition process (the plain rectangles) and it shows the steps of the algorithm where the plan recognizer and the user model component interact. The dashed rectangles in the figure represent the phases of extension of the UM.

In order to view the steps outlined above from the right perspective, it is important to stress again the twofold function of the plan recognizer: the upward expansion of CMs is motivated by the fact that the system must get the widest possible understanding of the users' plans and goals. However, the system also must discover which pieces of information they possibly need in order to carry out their plans. So, there is a second main phase in which it moves downward and backward to suggest how the substeps of their plan can be executed, and how the required preconditions can be obtained (see steps and of the plan-recognition algorithm). While in the expansion of the higher-level part of CMs the UM only helps in disregarding higher-level goals that are considered implausible for the user, i.e. in the resolution of ambiguities, in the second phase it is also useful to stop the movement downwards. In fact, in the absence of the UM, there are just two alternatives: either simply considering the required substeps (no help), or going down to the elementary actions (probably too much help).

The task of disambiguating among the candidate hypotheses on the user's plans is initially dealt with during the focusing phase, where the system tries to relate the user's sentences with the context established by the previous part of the dialogue. However, the further application of disambiguation rules (that will be presented in section ) helps the system to reduce the set of hypotheses on the user's plans so that, when evaluating the relevance of the ambiguity, the set of candidates is smaller and the clarification dialogues are shorter.

  
Figure: Application of the dialogue interpretation algorithm to an example

In order to clarify the interpretation process described above, we consider a simplified version of the dialogue reported in section :

A1:

I would like to prepare the laboratory work of the DS examination.

A2:

How may I be authorized to access the computer labs?

B1:

To be authorized to access the computer labs you should apply for the access: you should go to the secretariat, provide your registration number and ask for the pass of the laboratories.

In Figure we show the significant changes in the data structures while applying the dialogue interpretation algorithm shown in Figure . We omit for simplicity the details about the contents of the UM and the CMs. In the figure, circles represent the input sentences, while rectangles represent the current status of the active CMs in each phase of the analysis. Only the phases that modify the CMs are represented.