Implementing the planner module

The planner module (see figure 3.1) should be implemented as a recursive procedure that constructs the game tree a choice node at a time. For each choice node, the planner should be called. The planner should use a parser, taking plan rules from the given level of the belief model. An algorithm is required to search the given parse tree, in top down, left to right order, for the first node that does not have a full complement of children. If no such node exists, the tree is closed, and the intention rules should be used to attach a parent to the root of the tree. Parents should be repeatedly added until the search algorithm finds that the tree is open. The search algorithm, on finding the first open node, should apply the plan rules, matching with the node and its current children. One more child should be added to right of the current children. This new node should then be repeatedly decomposed at the leftmost child only, until a terminal node is obtained. This terminal node represents an alternative to be used as an edge at the choice node. The parsing and decomposition process should backtrack, so that all of the alternative solutions are obtained. Each solution should then be used as an edge at the choice node. In adding nodes to the parse tree, the planner might encounter intention rules and preconditions. Each of these should be used to generate chance nodes. Along with the set of alternatives, information about these should be returned, and used to insert chance nodes in the game tree, ahead of the choice node. To ensure that chance nodes only occur once in the game tree, propositions and their values that have already been addressed by a chance node should be passed in the recursive call to the procedure that generates the game tree. This is because the evaluation function will always evaluate a second occurrence of a chance node as true in the true branch of the first occurrence, or false in the false branch of the first occurrence.