Complexity

Computational complexity is a subject that must be addressed, since game trees grow exponentially with the number of steps in the dialogue, so that their construction and evaluation is not effectively computable. Here are some candidate mechanisms to deal with this problem:

• Focussing In keeping with Carberry [10], the planner only admits plan hypotheses that are focussed (see Section 2.5 for an explanation of focussing). This greatly reduces the branching of the game tree, yet the unfocused plans are usually so unlikely that there is little error in pruning them.

• Alpha-beta pruning Where the agents have opposing utility functions, alpha-beta pruning [59] can be used to prune away branches of the game tree by considering that the utility of branches so far evaluated in the game tree bounds the utility that the agent will accept for the unexplored branches. The agent at the previous level can use the bound to immediately discount an entire branch. However, agents with opposing utility functions rarely use spoken dialogue, so this sort of pruning would rarely be useful.

• Abstraction Since planning is performed by hierarchical decomposition, planning can be done at any level of abstraction. By choosing a higher level of abstraction, the planner can look further ahead, but use fewer steps in doing so.

• Heuristic search The agent can take estimates of utility from a higher level of abstraction, or from a breadth-first partially developed game tree at the current level of abstraction. With these estimates, the agent should advance the leading branches of the game tree, since the trailing branches are unlikely to be chosen. The branch-and-bound algorithm can also be used to prune paths without sacrificing optimality, by pruning those paths that can never lead to a plan that is better than the best one found so far. Heuristic search may be problematic however. This is because the agents have different beliefs and utility values, and so one agent cannot prune alternatives that are only poor from its perspective. One way to deal with this might be to prune only those branches that are poor from the perspective of both agents. This ought to be effective in the cooperative setting where despite differences of belief, there is often agreement about the poorer alternatives.

• Probability mass search The utility function is computed using weighted sums. Therefore, error that is propagated through the game tree in computing the utility is also weighted. Therefore, the subtrees with greater weight deserve deeper exploration. This heuristic has been implemented by using a mass value that is propagated through the tree from the root. The mass is divided according to the weights at the chance nodes. Once the mass falls below a threshold, pruning begins. The effect of this pruning is to limit the chance nodes in the tree to a beam, with weighted random selection of branches at chance nodes once the threshold value has been reached.

• Recombination Plans can decompose in many different ways, since each action can have a number of decomposition rules. This leads to many paths in the game tree for alternative subdialogues that serve some root goal. However, once the subdialogue is finished with, the goal's parent is expanded in the same way, no matter which of the paths was taken in the subdialogue. Paths can therefore recombine at the end of subdialogues. This could be useful in generating the game tree, but would not reduce the complexity in evaluating it since beliefs are revised differently for each of the paths. Often though, such beliefs might only be used within one subdialogue. For example, in booking a flight, a subdialogue about whether the flier wants a window seat would refer to beliefs that are only relevant to dialogues about sitting in an aeroplane. In such cases, dialogue planning obtains the important property of computational tractability, with the number of edges in the game tree being linear with the number of decomposition rules in the plan library. The proof of this property is by induction on the plan library. Assume first that plan libraries do not allow decompositions to be recursive in that they refer to their own parents. This is acceptable for most problems. Addition of a new decomposition rule to a plan library then results in the addition of at most one extra edge at the corresponding node in the game tree. It then requires one more edge to recombine this node with its sibling nodes to close the subdialogue. Therefore the size of the game tree is linear with the size of the plan library. Figure 3.4 illustrates a plan library, and its corresponding recombined game tree. Implementation of the recombination planner is left to future work.

• Alternating mutual belief In many dialogues, it is mutually believed that the dialogue is observed by both agents, and that appropriate belief revision inferences are made. Therefore whenever a belief is revised, it can be assumed to be revised at every second level of the belief model, producing an alternating mutual belief. For example, if agent 1 declares that the sky is blue, it should expect that agent 2 has observed this declaration and so a revision is appropriate at level 3. This argument can be extended to level 5, 7 and so on. It is often the case that the agents begin a dialogue with mutually believed stereotypes. For instance one may be a 'customer' and the other may be a 'travel agent'. As a result, at the beginning and throughout the dialogue, every second level is identical. This fact makes construction and evaluation of the game tree more efficient, since only one tree is required and it can be evaluated in one pass. Previously, it had to be evaluated many times from the different perspectives of the different levels of the belief model.

Figure 3.4: Recombination example (a) Plan library (b) Corresponding game tree with recombination

Only one of the complexity strategies has been implemented, the probability mass search, but there are no results describing its effectiveness. It is promising in that the implementation is straightforward, and that it allows enough samples of the possible dialogue outcomes to be taken to make an effective decision while keeping the complexity of the chance nodes linear with respect to the dialogue length. Unfortunately there is no general way to prune the choice nodes. Although it seems more difficult to implement, and requires certain properties of the plan rules, recombination might be the next most promising candidate since it changes the complexity of the game tree, both choice nodes and chance nodes, without threatening to degrade the performance of the system.

It might be argued that a system that performs computations with game trees would be slow to respond in real time, and therefore irritating to the user. However, for unwieldy game trees used in routine dialogues, strategies can be precomputed by the planner, and updated at regular intervals as the stereotype model develops, perhaps once a day. The strategies would be represented by a stored game tree pruned to the system's best play at each system choice node. Such a tree could be consulted almost instantaneously.