Representation and construction of the game tree

To decide a strategy on the systems turn, a game tree is constructed, and then evaluated so that the maximum utility alternative at the root node is used as the act for the current turn. It was stated earlier in the chapter that the game tree should be constructed incrementally, taking the perspective of the acting agent at each node. Preconditions determine the applicability of acts, and so different belief states result in different game trees. The objective of the planner is to determine the best strategy over all of the possible belief states. For example, a plan with two preconditions might have four combinations of belief states ( two times two ), each with a different probability. The planner must find the value of the each strategy in each of the belief states and take a weighted sum according to the probability of each state. This follows from the use of the maximum expected utility rule. Instead of using many such game trees, a representation has been chosen in which just one tree is used. Whenever a precondition occurs for an act, a "chance node" should be inserted just before the choice node in the game tree. Chance nodes always have two branches, one for each outcome of the precondition value. In the "true" outcome, the act appears at the following choice node. In the "false" outcome the act does not appear at the following choice node. This representation allows all of the different trees to be conflated into one, sharing the construction and evaluation effort where the different trees have common roots. The game tree can be equally well evaluated using a logical belief model, or the probabilistic model. The logical approach would be in keeping with Pollack's notion [53] of differing belief sets, while retaining the traditional logical model of belief. Instead of taking weighted sums over chance nodes, possible outcomes would be obtained, by checking whether the proposition at the chance node is believed (in which case only the "true" branch is possible) , disbelieved (in which case only the "false" branch is possible), or neither (in which case both branches are possible). This style of reasoning is particularly useful for the risk averse agent who would like to know the worst possible outcomes for the alternative available to him, given a set of nested beliefs. For example, if lives were at stake, a dialogue could be planned whose effect in revising the belief model would be to prune away the chance nodes at which both branches were previously possibilities, hopefully leaving a tree with no outcomes of plan failure. The probabilistic, rather than the possibilistic approach to game tree evaluation is taken for the design presented in this thesis.

To construct a choice node in the game tree, the plan rules should be invoked as follows. The planner process should take as input the dialogue history and the belief model of the agent, and grow a game tree incrementally by planning forwards by one step at each game tree node, providing a strategy set which forms the node's branches. To do this, the planner should consult the plan rules of the level in the belief model of the acting agent. This is because each agent may have different capabilities. For example the system may believe that it is possible to make a pavlova with strawberries, but not expect the user to hold this plan rule as a capability. The dialogue history, concatenated with the sequence of acts that forms the path from the root of the game tree should parsed (using a standard parser for phrase structure grammars) according to the hierarchical plan rules. Then, a set of alternative strategies should be generated to continue the recognised plan by one step. This is done by planning forward in a focussed manner until a leaf act is obtained. To plan in a focussed manner the parse tree should be searched in left to right order for a node that does not have a full complement of children. Forward planning proceeds from the first such node. This process is the same as that of Carberry [10] (see section 2.5). If the parse tree is full (closed), a parent should be added to its root and forward planning should proceed along the path to this parent's second child. To do this the intention rules should be used (section 3.4.2). There may be many different ways both of parsing and planning forward. The alternative strategies should be gathered from each of these. To construct the subsequent choice node in the game tree, the next level of the belief model should be consulted, and using its plan rules, the act sequence reparsed from the perspective of the acting agent, and the next act produced. Since there may be different sets of plan rules, a different parse must be done at each level [53]. A game tree constructed from the perspective of the agent at level 1 would therefore alternate between consulting level 1 and level 2 of the belief model in progressing through the game tree.

Chance nodes occur in two ways. First, if planning forward produces a branch at a choice node whose act has a precondition, a chance node ensures that the branch can only be added in the true branch of the chance node. Second, if a full plan tree is found, a parent must be added to the root. There may be many candidate parents, whose occurrence follows a probability distribution. Using the intention beliefs (section 3.4.2), a chance node should be generated to differentiate the different intention states that the acting agent may be in.