Dealing with complexity

Through the course of the experiments conducted for this thesis, the complexity of the problems grew, and it became obvious both from a computational complexity analysis of the planning problem and from practical experience that it was easy to construct a reasonable planning problem that would overwhelm the hardware used for the experiment. In particular, it grew difficult to collect plentiful data for some experiments reported in Chapter 5. It is also necessary to control the complexity of the tree so that value of information decisions can be made for long-range plans that are deep rather than wide. In the design chapter (see Section 3.4.9), a number of approaches to the complexity problem were discussed. One of these, "probability mass search" was implemented for controlling the complexity of chance nodes, but was not used. A heuristic beam search was proposed for dealing with choice node complexity. However, it may not be useful when the agents have opposing utility functions, since one agent may unwittingly prune an alternative that the other agent subsequently chooses. On the other hand, there are many applications in which the system and the user share a utility function. In these, a beam search would be most appropriate. The relationship between dialogue efficiency and beam width has yet to be explored. Another promising technique is that of recombination, whose approach was to recombine alternative subdialogues in the game tree, one the subdialogue had closed. This technique is important since it reduces the complexity of the problem to linear from exponential. However, it is not always applicable. While the game tree can take a compact recombined form, the evaluation algorithm complexity is not isomorphic to the game tree shape. This is because where beliefs are revised differently in parallel branches, recombination of belief models in evaluation can only happen if the value of the belief is never needed again in the evaluation. More often than not this will not be the case, and especially in the kind of long-range planning where complexity measures are particularly suitable. The best approach to limiting complexity remains to be seen.