next up previous contents
Next: Multilogues Up: Design of the planner Previous: Stereotype error   Contents


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:

Figure 3.4: Recombination example (a) Plan library (b) Corresponding game tree with recombination
\includegraphics[width=1\textwidth]{figures/recombination.eps}

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.


next up previous contents
Next: Multilogues Up: Design of the planner Previous: Stereotype error   Contents
bmceleney 2006-12-19